Cutting stock with no three parts per pattern: Work-in-process and pattern minimization

The Pattern Minimization Problem (PMP) consists in finding, among the optimal solutions of a cutting stock problem, one that minimizes the number of distinct cutting patterns activated. The Work-in-process Minimization Problem (WMP) calls for scheduling the patterns so as to maintain as few open stacks as possible. This paper addresses a particular class of problems, where no more than two parts can be cut from any stock item, hence the feasible cutting patterns form the arc set of an undirected graph GG. The paper extends the case G=KnG=Kn introduced in 1999 by McDiarmid. We show that some properties holding for G=KnG=Kn are no longer valid for the general case; however, for special cases of practical relevance, properly including G=KnG=Kn, quasi-exact solutions for the PMP and the WMP can be found: the latter in polynomial time, the former via a set-packing formulation providing very good lower bounds.