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

Abstract: 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 . The paper extends the case introduced in 1999 by McDiarmid. We show that some properties holding for are no longer valid for the general case; however, for special cases of practical relevance, properly including , 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. [Copyright &y& Elsevier]