A skyline heuristic for the 2D rectangular packing and strip packing problems

Lijun Wei; Wee-Chong Oon; Wenbin Zhu; Andrew Lim

doi:10.1016/j.ejor.2011.06.022

Author(s)

Lijun Wei
Wee-Chong Oon
Wenbin Zhu
Andrew Lim

Related Research Unit(s)

Department of Management Sciences

Detail(s)

Original language	English
Pages (from-to)	337-346
Journal / Publication	European Journal of Operational Research
Volume	215
Issue number	2
Publication status	Published - 1 Dec 2011

Link(s)

DOI	DOI https://doi.org/10.1016/j.ejor.2011.06.022 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-80051785319&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(26087149-8dfc-4164-9944-c1106ad2ddb0).html

Abstract

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an "iterative doubling" binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP. © 2011 Elsevier B.V. All rights reserved.

Research Area(s)

Cutting and packing, Heuristics, Tabu search

Citation Format(s)

[ RIS ] [ BibTeX ]

A skyline heuristic for the 2D rectangular packing and strip packing problems. / Wei, Lijun; Oon, Wee-Chong; Zhu, Wenbin et al.
In: European Journal of Operational Research, Vol. 215, No. 2, 01.12.2011, p. 337-346.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Wei, L, Oon, W-C, Zhu, W & Lim, A 2011, 'A skyline heuristic for the 2D rectangular packing and strip packing problems', European Journal of Operational Research, vol. 215, no. 2, pp. 337-346. https://doi.org/10.1016/j.ejor.2011.06.022

Wei, L., Oon, W.-C., Zhu, W., & Lim, A. (2011). A skyline heuristic for the 2D rectangular packing and strip packing problems. European Journal of Operational Research, 215(2), 337-346. https://doi.org/10.1016/j.ejor.2011.06.022

Wei L, Oon WC, Zhu W, Lim A. A skyline heuristic for the 2D rectangular packing and strip packing problems. European Journal of Operational Research. 2011 Dec 1;215(2):337-346. doi: 10.1016/j.ejor.2011.06.022

Wei, Lijun ; Oon, Wee-Chong ; Zhu, Wenbin et al. / A skyline heuristic for the 2D rectangular packing and strip packing problems. In: European Journal of Operational Research. 2011 ; Vol. 215, No. 2. pp. 337-346.