کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
480080 1644955 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A reduction approach for solving the rectangle packing area minimization problem
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A reduction approach for solving the rectangle packing area minimization problem
چکیده انگلیسی

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.


► The paper deals with the rectangle packing area minimization problem (RPAMP).
► A heuristic is proposed that is based on 2D knapsack/strip packing algorithms.
► New best solutions were found for Ami33, Ami49 and other MCNC and GSRC instances.
► Results are also reported for 24 new RPAMP benchmark instances.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 224, Issue 3, 1 February 2013, Pages 486–496
نویسندگان
,