Connections between cutting-pattern sequencing, VLSI design, and flexible machines

Abstract

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 VLS1 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.