A parallel branch-and-bound approach to the rectangular guillotine strip cutting problem

Citation

Bak S, Blazewicz J, Pawlak G, Plaza M, Burke E & Kendall G (2011) A parallel branch-and-bound approach to the rectangular guillotine strip cutting problem. INFORMS Journal on Computing, 23 (1), pp. 15-25. https://doi.org/10.1287/ijoc.1100.0394

Abstract
This paper presents a parallel branch-and-bound method to address the two-dimensional rectangular guillotine strip cutting problem. Our paper focuses on a parallel branching schema. We present a series of computational experiments to evaluate the strength of the approach. Optimal solutions have been found for some benchmark instances that had unknown solutions until now. For many other instances, we demonstrate that the proposed approach is time effective. The efficiency of the parallel version of the algorithm is compared and the speedup, when increasing the number of processors, is clearly demonstrated with an upper bound calculated by a specialised heuristic procedure.

Keywords
production scheduling; cutting stock; material handling; parallel branch-and-bound method; analysis of algorithms

Journal
INFORMS Journal on Computing: Volume 23, Issue 1