A fast layer-based heuristic for non-guillotine strip packing

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

36 Scopus Citations
View graph of relations

Author(s)

  • Stephen C.H. Leung
  • Defu Zhang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)13032-13042
Journal / PublicationExpert Systems with Applications
Volume38
Issue number10
Publication statusPublished - 15 Sep 2011

Abstract

In this paper, an orthogonal strip packing problem with rotation of items and without the guillotine packing constraint is considered. A fast heuristic algorithm for the large-scale problems is presented. This heuristic algorithm is mainly based on heuristic strategies inspired by the wall-building rule of bricklayers in daily life. The heuristics is simple and the setting of parameter is not required. Each layer is initialized with either a single item or a bunch of equal-width items. The remaining part of the layer is filled by a bottom-left strategy preferring items which eliminate corners of the current layout. Items can also be placed across several layers. Then, the evaluation rule, which is based on the fitness value for different rectangles to a given position, is able to select an appropriate rectangle to pack. The computational results on a broad range of benchmark problems show that the fast layer-based heuristic algorithm can compete with other latest heuristics and meta-heuristics from the literature in terms of both solution quality and computational time. The fast layer-based heuristic algorithm can compete with the latest published algorithms. In particular, it performs better for large-scale problem instances. © 2010 Elsevier Ltd. All rights reserved.

Research Area(s)

  • Heuristic, Local search, Optimization, Packing problem

Citation Format(s)

A fast layer-based heuristic for non-guillotine strip packing. / Leung, Stephen C.H.; Zhang, Defu.

In: Expert Systems with Applications, Vol. 38, No. 10, 15.09.2011, p. 13032-13042.

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