Chinese Journal of Computers   Full Text
Title	A Bricklaying Heuristic Algorithm for the Orthogonal Rectangular Packing Problem
Authors	ZHANG De-Fu1) HAN Shui-Hua2) YE Wei-Guo2)
Address	1)(Department of Computer Science and Technology, Xiamen University, Xiamen, Fujian 361005) 2)(Department of Management Science, Xiamen University, Xiamen, Fujian 361005)
Year	2008
Issue	No.3(509—515)
Abstract &   Background	Abstract A novel and effective bricklaying heuristic algorithm for two-dimensional rectangular Packing problem is presented. This algorithm is mainly based on bricklaying heuristic strategies inspired by a large number of experiences accumulated by bricklayers during the process of building the wall, especially, the building wall strategy based on the reference brick is presented. The computational results on large number of Benchmark problems have shown that this algorithm not only runs in shorter time than known meta-heuristic but also finds shorter height. keywords the orthogonal rectangular Packing problem; heuristic; bricklaying rule; local search; reference brick background The strip Packing problem with rotation constraint belongs to NP hard problem. At present, some excellent algorithms have been presented to solve the problem. The bricklaying heuristic algorithm based on the reference line is novel and efficient. The computational results have shown that this algorithm not only runs in shorter time than known meta-heuristic but also finds shorter height. The work is supported by the National Natural Science Foundation of China (grant No.60773126) and the Province Nature Science Foundation of Fujian (grant No.A0710023) and academician start-up fund (grant No.X01109) and 985 information technology fund (grant No.0000-X07204) in Xiamen University. The projects aim at designing highly efficient algorithms for NP hard problems, such as the Packing problem and timetabling problem, which are the most important part of automated Packing and timetabling software. The project team has designed some efficient algorithm for SAT problem, the circle Packing problem, the rectangle Packing problem and three dimensional Packing problem, some results has been published. The fundamental aim of this paper is to investigate two-dimensional Packing problems and to develop state-of-the-art algorithms that could be used in an industrial setting. The paper belongs to one of the key parts of the project.