A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

22 Scopus Citations
View graph of relations

Author(s)

  • Defu Zhang
  • Lijun Wei
  • Stephen C.H. Leung
  • Qingshan Chen

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)332-345
Journal / PublicationINFORMS Journal on Computing
Volume25
Issue number2
Publication statusPublished - Mar 2013

Abstract

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.

Research Area(s)

  • Binary search, Heuristic, Local search, Rectangular strip packing

Citation Format(s)

A binary search heuristic algorithm based on randomized local search for the rectangular strip-packing problem. / Zhang, Defu; Wei, Lijun; Leung, Stephen C.H.; Chen, Qingshan.

In: INFORMS Journal on Computing, Vol. 25, No. 2, 03.2013, p. 332-345.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal