An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem

摘要

We propose a new exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem, which asks if a set of rectangular items can be cut from a single stock rectangle using guillotine cuts only, with fixed item orientation or with 90-degree item rotation. Our algorithm constructs patterns of items by means of horizontal and vertical builds. To speed up the algorithm and reduce its memory requirement, patterns are constructed in the order of nondecreasing waste, the patterns that use the same subset of items are grouped together, and dominated patterns in each group are discarded. Moreover, a heuristic capable of completing a partial pattern is repeatedly used during the algorithm to quickly determine a feasible solution. Furthermore, the algorithm tries to prove infeasibility with a subset of items before considering all items. We test our algorithm on benchmark instances for the two-dimensional guillotine strip-cutting problem, which we solve by varying the strip height and testing with our algorithm whether a feasible solution exists. We show that our approach outperforms all previously proposed algorithms for the problem with fixed item orientation. Computational experiments for the problem with item rotation are also reported.