TY - JOUR
T1 - A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem
AU - Zhang, Defu
AU - Wei, Lijun
AU - Leung, Stephen C.H.
AU - Chen, Qingshan
PY - 2013/3
Y1 - 2013/3
N2 - This paper presents a binary search heuristic algorithm for the rectangular strip-packing problem. The problem is to pack a number of rectangles into a sheet of given width and infinite height so as to minimize the required height. We first transform this optimization problem into a decision problem. A least-waste-first strategy and a minimal-inflexion-first strategy are proposed to solve the related decision problem. Lastly, we develop a binary search heuristic algorithm based on randomized local search to solve the original optimization problem. The computational results on six classes of benchmark problems have shown that the presented algorithm can find better solutions within a reasonable time than the published best heuristic algorithms for most zero-waste instances. In particular, the presented algorithm is proved to be the dominant algorithm for large zero-waste instances. © 2013 INFORMS.
AB - This paper presents a binary search heuristic algorithm for the rectangular strip-packing problem. The problem is to pack a number of rectangles into a sheet of given width and infinite height so as to minimize the required height. We first transform this optimization problem into a decision problem. A least-waste-first strategy and a minimal-inflexion-first strategy are proposed to solve the related decision problem. Lastly, we develop a binary search heuristic algorithm based on randomized local search to solve the original optimization problem. The computational results on six classes of benchmark problems have shown that the presented algorithm can find better solutions within a reasonable time than the published best heuristic algorithms for most zero-waste instances. In particular, the presented algorithm is proved to be the dominant algorithm for large zero-waste instances. © 2013 INFORMS.
KW - Binary search
KW - Heuristic
KW - Local search
KW - Rectangular strip packing
UR - http://www.scopus.com/inward/record.url?scp=84877965293&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84877965293&origin=recordpage
U2 - 10.1287/ijoc.1120.0505
DO - 10.1287/ijoc.1120.0505
M3 - 21_Publication in refereed journal
VL - 25
SP - 332
EP - 345
JO - ORSA journal on computing
JF - ORSA journal on computing
SN - 0899-1499
IS - 2
ER -