Article ID: | iaor2003242 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 12 |
Start Page Number: | 1759 |
End Page Number: | 1772 |
Publication Date: | Oct 2002 |
Journal: | Computers and Operations Research |
Authors: | Yanasse Horacio Hideki, Linhares Alexandre |
Keywords: | production: FMS, combinatorial analysis |
The minimization of open stacks problem (MOSP) arises on the sequencing of a set of cutting patterns in order to minimize the maximum number of open stacks around the cutting saw. A previous study formulated the problem mathematically and raised a number of theoretical conjectures. In this work we deal with those conjectures. It is shown that the MOSP is NP-hard. A connection to the field of VLSI design, joining practitioners from both computer science and operations research, is established. Additional conjectures concerning the existence of simultaneous optimal solutions to related pattern-sequencing problems are also clarified.