Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1134600 | Computers & Industrial Engineering | 2012 | 13 Pages |
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.
Related Topics
Physical Sciences and Engineering
Engineering
Industrial and Manufacturing Engineering
Authors
Mhand Hifi, Stephane Negre, Rachid Ouafi, Toufik Saadi,