An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem
提出一种新的精确算法，解决二维阶段无限制断头切割/装箱决策问题，即判断一组矩形物品能否从单个矩形板材上通过断头切割得到，支持固定方向或90度旋转。算法通过水平和垂直构建模式、按废料非递减顺序构造、分组丢弃被支配模式、启发式补全部分模式及子集不可行性检验来提升效率。
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.