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.
Titolo: | Cutting stock with no three parts per pattern: Work-in-process and pattern minimization | |
Autori: | ||
Data di pubblicazione: | 2011 | |
Rivista: | ||
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 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. | |
Handle: | http://hdl.handle.net/11697/89458 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |