A parallel algorithm for constrained two-staged two-dimensional cutting problems |
| |
Authors: | Mhand Hifi Stephane NegreRachid Ouafi Toufik Saadi |
| |
Affiliation: | a Université de Picardie Jules Verne, Unité de Recherche EPROAD, 5 rue du Moulin Neuf, 80000 Amiens, France b Université de Technologie Houari-Boumediene, LAID3, El Alia, BP 32, Bab Ezzouar, 16111 Alger, Algeria |
| |
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. |
| |
Keywords: | Beam-search Dynamic programming Heuristics Knapsack Master-slave paradigm Optimization |
本文献已被 ScienceDirect 等数据库收录! |
|