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 2 parts can be cut from any stock item, hence the feasible cutting patterns form the arc set of an undirected graph G. The paper extends the case G = Kn introduced in 1999 by McDiarmid. We show that some properties holding for G = Kn are no longer valid for the general case; however, for special cases of practical relevance, properly including G = 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.