A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem
Sławomir Bąk, Jacek Błażewicz, Grzegorz Pawlak, Maciej Płaza, Edmund K. Burke, Graham Kendall
INFORMS Journal on Computing · 2011 · Volume 23 · Issue 1
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
Enable JavaScript for citation tools and additional paper interactions.