Paper Info
Title
An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem.
Abstract
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.
Year
DOI
Venue
2016
10.1287/ijoc.2016.0708
INFORMS Journal on Computing
Keywords
Field
DocType
exact algorithm, two-dimensional cutting/packing, guillotine cuts, rotation, strip cutting
Horizontal and vertical,Decision problem,Mathematical optimization,Heuristic,Exact algorithm,Rectangle,Mathematics,Speedup
Journal
Volume
Issue
ISSN
28
4
1091-9856
Citations 
PageRank 
References 
3
0.41
24
Authors
1
Name
Order
Citations
PageRank
Krzysztof Fleszar136825.38