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.

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

ALOISIO, ALESSANDRO;ARBIB, CLAUDIO;
2011-01-01

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/89458
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 10
social impact