|
|||||
|
|
A skyline heuristic for the 2D rectangular packing and strip packing problems |
|
| Authors: | Lijun WeiWee-Chong Oon Wenbin Zhu Andrew Lim |
| Affiliation: | a Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong b Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong c Department of Logistics and Maritime Studies, Faculty of Business, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong |
| 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. |
| Keywords: | Cutting and packing Heuristics Tabu search |
| 本文献已被 ScienceDirect 等数据库收录！ | |