|
|||||
|
|
A block-based layer building approach for the 2D guillotine strip packing problem |
|
| Authors: | Lijun Wei Tian Tian Wenbin Zhu Andrew Lim |
| Institution: | 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, Jiangxi 330013, People’s Republic of China;2. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong;3. School of Business Administration, South China University of Technology, Guangzhou, Guangdong 510641, People’s Republic of China;4. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, People’s Republic of China |
| Abstract: | We examine the 2D strip packing problems with guillotine-cut constraint, where the objective is to pack all rectangles into a strip with fixed width and minimize the total height of the strip. We combine three most successful ideas for the orthogonal rectangular packing problems into a single coherent algorithm: (1) packing a block of rectangles instead of a single rectangle in each step; (2) dividing the strip into layers and pack layer by layer; and (3) unrolling and repacking the top portion of the solutions where usually wasted space occurs. Computational experiments on benchmark test sets suggest that our approach rivals existing approaches. |
| Keywords: | Cutting Packing Guillotine-cut Best-fit heuristic Layer-building |
| 本文献已被 ScienceDirect 等数据库收录！ | |