Search

The Cutting Stock Problem consists in supplying customers' orders while minimizing waste. The solution of this problem is a set of cutting patterns that show how the raw material has to be cut into required sizes and quantities. Although this solution fulfils orders and minimizes waste, a further problem arises in practical applications. This problem, usually know as the Pattern Sequencing Problem (PSP) or pattern allocation problem, calls for sequencing the previously generated patterns in order to minimize the number of customers contemporary waiting for their orders. In particular, consider a production line where there are batches consisting of sets of items that are all released at the same time. All items of the same type, say q, are collected into a single stack (buffer) b(q) that is "active" in the time window defined by the release times of the first and the last batches containing an item of type q. It is often the case that too many active stacks lead to inefficiency: for instance, in wood panel sizing centers in the furniture enterprises, the maximum number of stacks is fixed by the plant layout. Thus, when all of the stack places are used, the pieces not matching with the stacks must be carried to the later operations. Different release orders of the batches define time intervals of different lengths in which the individual stacks are "active". The Open Stack Problem (OSP) consists in finding a release sequence of the batches that minimizes the number of buffers that are simultaneously active. This problem has been shown to be NP-hard by Linhares et al. (2002). The sequencing aspects of cutting stock problems have been examined by different researches and the interest about this subject has considerably grown in the last years. In particular, among the most relevant contributions on the argument, we mention here Becceneri et al. (2004), M.G. de la Banda et al. (2006), Faggioli et al. (1998), Linhares et al. (2002), Oliveira et al. (2003). An important contribution has been also given by theConstraint Modeling Challenge 2005, that consisted in an international challenge for solving several benchmark instances of OSP. Here we present three new formulations in terms of Linear Integer Programming for the OSP problem. In the first one (LOP), a Linear Ordering approach is used to model the sequence of the cutting schemes. In the second formulation (C1P), we reduced the OSP problem to the one of minimizing the maximum number of ones in each column of a 0/1 matrix which is required to have the "consecutive ones property" for the rows. Such matrices have been first characterized by Tucker (1972) in terms of forbidden minors; more recently, Oswald and Reinelt (2003) defined a linear relaxation of the convex hull of the characteristic vectors of the matrices with the consecutive ones property, based on four families of inequalities derived from the Tucker minors. In the third formulation we propose (LOP-C1P), the two previous approaches are merged together in order to define a single integer linear program by adding an appropriate set of coupling constraints. The three formulations defined above have been implemented and the lower bounds obtained by the associated linear relaxations have been compared with the ones defined by the formulation proposed by Baptiste (2005) that is, at our best knowledge, the only MIP formulation for the OSP problem in the literature. The computational results gave evidence that, both in terms of computing times and quality of the bounds, our formulations are more effective than the one by Baptiste. Finally, a Branch-and-Cut code has been implemented for each of the three formulations (LOP, C1P, LOP-C1P). The effectiveness of these algorithms have been tested on several sets of benchmark instances proposed in the literature or coming from real world pattern sequencing problems in furniture enterprises. The computational results obtained give evidence of the effectivenes of the proposed procedures in terms of computing times and quality of the solutions. In particular, significant improvements are obtained in all the cases, by using, in the Branch-and-Cut procedure, the upper bounds defined by the genetic algorithm proposed by De Giovanni, Massi, and Pezzella (2007). References: - J.C. Becceneri, H.H. Yanasse, N.Y. Soma, A method for solving the minimization of the maximum number of open stacks problem within a cutting process,Computers and Operations Research, vol. 31, pagg. 2315-2332, 2004. - P. Baptiste, Simple MIP Formulations to Minimize the Maximum Number of Open Stacks, Proceedings of the Constraint Modelling Challenge 2005, in conjunction with The Fifth Workshop on Modelling and Solving Problems with Constraints Held at IJCAI 2005, Edinburgh, Scotland, 31 July, 2005. - Constraints Modeling Challenge 2005, Edinburgh, 2005 (www.dcs.stand.ac.uk/~jpg/challenge/). - M.G. de la Banda, P.J. Stuckey , Using Dynamic Programming to Minimize the Maximum Number of Open Stacks, INFORMS Journal of Computing, to appear. - E. Faggioli, C.A. Bentivoglio, Heuristic and exact methods for the cutting sequencing problem, European Journal of Operational Research, vol. 110, pagg. 564-575, 1998. - A.C.M. de Oliveira, L.A.N. Lorena, Sequencing Cutting Patterns and VLSI Gates by Population Training Algorithms, EURO/INFORMS Conference, Istanbul, 6-10 luglio 2003. - A. Linhares, H.H. Yanasse, Connections between cutting-pattern sequencing, VLSI Design, and flexible machines, Computers and Operations Research, vol. 29, pagg. 1759-1772, 2002. - M. Oswald and G. Reinelt, Constructing New Facets of the Consecutive Ones Polytope, Combinatorial Optimization -- Eureka, You Shrink! Papers Dedicated to Jack Edmonds, 5th International Workshop, Aussois, 2001, M. Juenger, G. Reinelt, and G. Rinaldi eds, vol. 2570 of LNCS, Springer-Verlag, pp. 147-157, 2003. - F. Pezzella, L. De Giovanni, G. Massi, "An adaptive genetic algorithm for the cutting-pattern sequencing problem", Annual conference AIRO, Genova, 2007 - A. Tucker, A structure theorem for the consecutive 1's property, J. Combinatorial Theory Ser. B, vol. 2, pp. 153-162, 1972.