A skyline-based heuristic for the 2D rectangular strip packing problem

Lijun Wei; Andrew Lim; Wenbin Zhu

doi:10.1007/978-3-642-21827-9_29

A skyline-based heuristic for the 2D rectangular strip packing problem

Lijun Wei
, Andrew Lim
, Wenbin Zhu^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

10 Citations (Scopus)

Abstract

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem that represents packings using a skyline. To solve the 2D rectangular strip packing problem, we make use of this heuristic as a subroutine in an iterative deepening binary search on the maximum height of the packing that incorporates a tabu search mechanic. Our approach outperforms all existing approaches on several sets of standard benchmark test cases for the 2D strip packing problem. © 2011 Springer-Verlag.

Original language	English
Title of host publication	Modern Approaches in Applied Intelligence
Subtitle of host publication	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings
Publisher	Springer Verlag
Pages	286-295
Volume	6704 LNAI
Edition	PART 2
ISBN (Print)	9783642218262
DOIs	https://doi.org/10.1007/978-3-642-21827-9_29
Publication status	Published - 2011
Event	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011 - Syracuse, NY, United States Duration: 28 Jun 2011 → 1 Jul 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6704 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011
Place	United States
City	Syracuse, NY
Period	28/06/11 → 1/07/11

Research Keywords

Heuristics
Packing
Tabu Search

Access Output

10.1007/978-3-642-21827-9_29

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Wei, L., Lim, A., & Zhu, W. (2011). A skyline-based heuristic for the 2D rectangular strip packing problem. In Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings (PART 2 ed., Vol. 6704 LNAI, pp. 286-295). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6704 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-642-21827-9_29

Wei, Lijun ; Lim, Andrew ; Zhu, Wenbin. / A skyline-based heuristic for the 2D rectangular strip packing problem. Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings. Vol. 6704 LNAI PART 2. ed. Springer Verlag, 2011. pp. 286-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9ce7e2809a414beda395f800673e81ef,

title = "A skyline-based heuristic for the 2D rectangular strip packing problem",

abstract = "In this paper, we propose a greedy heuristic for the 2D rectangular packing problem that represents packings using a skyline. To solve the 2D rectangular strip packing problem, we make use of this heuristic as a subroutine in an iterative deepening binary search on the maximum height of the packing that incorporates a tabu search mechanic. Our approach outperforms all existing approaches on several sets of standard benchmark test cases for the 2D strip packing problem. {\textcopyright} 2011 Springer-Verlag.",

keywords = "Heuristics, Packing, Tabu Search",

author = "Lijun Wei and Andrew Lim and Wenbin Zhu",

year = "2011",

doi = "10.1007/978-3-642-21827-9\_29",

language = "English",

isbn = "9783642218262",

volume = "6704 LNAI",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "286--295",

booktitle = "Modern Approaches in Applied Intelligence",

address = "Germany",

edition = "PART 2",

note = "24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011 ; Conference date: 28-06-2011 Through 01-07-2011",

}

Wei, L, Lim, A & Zhu, W 2011, A skyline-based heuristic for the 2D rectangular strip packing problem. in Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings. PART 2 edn, vol. 6704 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6704 LNAI, Springer Verlag, pp. 286-295, 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Syracuse, NY, United States, 28/06/11. https://doi.org/10.1007/978-3-642-21827-9_29

A skyline-based heuristic for the 2D rectangular strip packing problem. / Wei, Lijun; Lim, Andrew; Zhu, Wenbin.
Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings. Vol. 6704 LNAI PART 2. ed. Springer Verlag, 2011. p. 286-295 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6704 LNAI).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A skyline-based heuristic for the 2D rectangular strip packing problem

AU - Wei, Lijun

AU - Lim, Andrew

AU - Zhu, Wenbin

PY - 2011

Y1 - 2011

N2 - In this paper, we propose a greedy heuristic for the 2D rectangular packing problem that represents packings using a skyline. To solve the 2D rectangular strip packing problem, we make use of this heuristic as a subroutine in an iterative deepening binary search on the maximum height of the packing that incorporates a tabu search mechanic. Our approach outperforms all existing approaches on several sets of standard benchmark test cases for the 2D strip packing problem. © 2011 Springer-Verlag.

AB - In this paper, we propose a greedy heuristic for the 2D rectangular packing problem that represents packings using a skyline. To solve the 2D rectangular strip packing problem, we make use of this heuristic as a subroutine in an iterative deepening binary search on the maximum height of the packing that incorporates a tabu search mechanic. Our approach outperforms all existing approaches on several sets of standard benchmark test cases for the 2D strip packing problem. © 2011 Springer-Verlag.

KW - Heuristics

KW - Packing

KW - Tabu Search

UR - https://www.scopus.com/pages/publications/79960475970

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-79960475970&origin=recordpage

U2 - 10.1007/978-3-642-21827-9_29

DO - 10.1007/978-3-642-21827-9_29

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783642218262

VL - 6704 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 286

EP - 295

BT - Modern Approaches in Applied Intelligence

PB - Springer Verlag

T2 - 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011

Y2 - 28 June 2011 through 1 July 2011

ER -

Wei L, Lim A, Zhu W. A skyline-based heuristic for the 2D rectangular strip packing problem. In Modern Approaches in Applied Intelligence: 24th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2011, Proceedings. PART 2 ed. Vol. 6704 LNAI. Springer Verlag. 2011. p. 286-295. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-21827-9_29

A skyline-based heuristic for the 2D rectangular strip packing problem

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this