A two-stage intelligent search algorithm for the two-dimensional strip packing problem

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

92 Scopus Citations
View graph of relations

Author(s)

  • Stephen C.H. Leung
  • Defu Zhang
  • Kwang Mong Sim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)57-69
Journal / PublicationEuropean Journal of Operational Research
Volume215
Issue number1
Publication statusPublished - 16 Nov 2011

Abstract

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances. © 2011 Elsevier B.V. All rights reserved.

Research Area(s)

  • Heuristic search, Packing problem, Simulated annealing

Citation Format(s)

A two-stage intelligent search algorithm for the two-dimensional strip packing problem. / Leung, Stephen C.H.; Zhang, Defu; Sim, Kwang Mong.
In: European Journal of Operational Research, Vol. 215, No. 1, 16.11.2011, p. 57-69.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review