DocumentCode :
2252645
Title :
An improved algorithm for the strip packing problem
Author :
Akeb, Hakim ; Hifi, Mhand ; Lazure, Dominique
Author_Institution :
ISC Paris Sch. of Manage., Paris, France
fYear :
2012
fDate :
9-12 Sept. 2012
Firstpage :
357
Lastpage :
364
Abstract :
This paper solves the strip packing problem (SPP) that consists in packing a set of circular objects into a rectangle of fixed width and unlimited length. The objective is to minimize the length of the rectangle that will contain all the objects such that no object overlaps another one. The proposed algorithm uses a look-ahead method combined with beam search and a restarting strategy. The particularity of this algorithm is that it can achieve good results quickly (faster than other known methods and algorithms) even when the number of objects is large. The results obtained on well-known benchmark instances from the literature show that the algorithm improves a lot of best known solutions.
Keywords :
bin packing; search problems; SPP; beam search; fixed width; look-ahead method; restarting strategy; strip packing problem; unlimited length; Containers; Equations; Mathematical model; Search problems; Standards; Strips; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2012 Federated Conference on
Conference_Location :
Wroclaw
Print_ISBN :
978-1-4673-0708-6
Electronic_ISBN :
978-83-60810-51-4
Type :
conf
Filename :
6354496
Link To Document :
بازگشت