Name
Title | ||
|---|---|---|
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 G. The paper extends the case G=K"n introduced in 1999 by McDiarmid. We show that some properties holding for G=K"n are no longer valid for the general case; however, for special cases of practical relevance, properly including G=K"n, 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.disopt.2010.10.002 | Discrete Optimization |
Keywords | Field | DocType |
special case,pattern minimization problem,case g,set packing,distinct cutting pattern,general case,open stack minimization,cutting stock,good lower bound,pattern minimization,stock problem,stock item,work-in-process minimization problem,feasible cutting pattern,lower bound,cutting stock problem,polynomial time,work in process,exact solution | Minimization problem,Graph,Discrete mathematics,Mathematical optimization,Work in process,Scheduling (computing),Minification,Set packing,Cutting stock problem,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
8 | 2 | Discrete Optimization |
Citations | PageRank | References |
2 | 0.39 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandro Aloisio | 1 | 13 | 6.01 |
| Claudio Arbib | 2 | 119 | 22.41 |
| Fabrizio Marinelli | 3 | 258 | 20.55 |