A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem
2010; Institute for Operations Research and the Management Sciences; Volume: 23; Issue: 1 Linguagem: Inglês
10.1287/ijoc.1100.0394
ISSN1526-5528
AutoresSławomir Bąk, Jacek Błażewicz, Grzegorz Pawlak, Maciej Płaza, Edmund Burke, Graham Kendall,
Tópico(s)Manufacturing Process and Optimization
ResumoThis 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.
Referência(s)