A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem

作者：Bak Slawomir^*; Blazewicz Jacek; Pawlak Grzegorz; Plaza Maciej; Burke Edmund K; Kendall Graham

来源：INFORMS Journal on Computing, 2011, 23(1): 15-25.

DOI：10.1287/ijoc.1100.0394

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

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.

• 出版日期2011