In this paper, we address the Minimization of Open Stacks Problem (MOSP). This problem often appears during production planning of manufacturing industries, such as in the cutting of objects to comply with space constraints around the cutting machine in the glass, furniture, and metallurgical industries. The MOSP is also pertinent to the field of VLSI design and Graph theory. The MOSP consists of finding an optimal sequence of a given set of patterns, while minimizing the maximum number of simultaneously open stacks. To effectively model and solve the problem, we present a novel Integer Linear Programming (ILP) formulation based on a graph representation of the problem. We derive an ILP formulation from the modeling approach of Faggioli & Bentivoglio (1998) for the MOSP. Then we develop a simple Constraint Programming (CP) model based on interval variables and renewable resources. We performed computational experiments to evaluate the proposed approaches in comparison with other ILP formulations from the literature. The proposed approaches are competitive in solution quality and computational time for small and moderate sized problem instances.
Citation
Instituto de Ciência e Tecnologia, Universidade Federal de São Paulo, Brazil, Avenida Cesare Mansueto Giulio Lattes, 1201, 12247-014, Eugênio de Melo, São José dos Campos, SP, Brazil.