An efficient heuristic algorithm for arbitrary shaped rectilinear block packing problem |
| |
Authors: | Duanbing Chen Jingfa Liu Yan Fu Mingsheng Shang |
| |
Affiliation: | 1. School of Computer Science, University of Electronic Science and Technology of China, Chengdu 610054, PR China;2. School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, PR China |
| |
Abstract: | Arbitrary shaped rectilinear block packing problem is a problem of packing a series of rectilinear blocks into a larger rectangular container, where arbitrary shaped rectilinear block is a polygonal block whose interior angle is either 90° or 270°. This problem involves many industrial applications, such as VLSI design, timber cutting, textile industry and layout of newspaper. Many algorithms based on different strategies have been presented to solve it. In this paper, we proposed an efficient heuristic algorithm which is based on principles of corner-occupying action and caving degree describing the quality of packing action. The proposed algorithm is tested on six instances from literatures and the results are rather satisfying. The computational results demonstrate that the proposed algorithm is rather efficient for solving the arbitrary shaped rectilinear block packing problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|