A parallel algorithm for constrained two‐staged two‐dimensional cutting problems

A parallel algorithm for constrained two‐staged two‐dimensional cutting problems

0.00 Avg rating0 Votes
Article ID: iaor20121192
Volume: 62
Issue: 1
Start Page Number: 177
End Page Number: 189
Publication Date: Feb 2012
Journal: Computers & Industrial Engineering
Authors: , , ,
Keywords: combinatorial optimization
Abstract:

In this paper, we solve the two‐staged two‐dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree‐search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master–slave paradigm. The master processor serves to guide the search‐resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large‐scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.

Reviews

Required fields are marked *. Your email address will not be published.