Research On Knowledge Heuristic Algorithms For Two2D Packing Problems

Complex layout design problem derives from the satellite space layout design, thefacility layout design, printing circuit board design, plate cutting-stock problem of iron andsteel enterprise, and on so. The layout design problem may be classified into the layoutdesign problem with performance constraints and the layout design problem withoutperformance constraints according to whether it has performance constraints or not. Theformer includes the packing problem with equilibrium constraints, weighted packingproblem, and the reverse layout problem of plate cutting and so on. The latter mainlycontains the circle packing problem, rectangular packing problem and so on. All the twolayout design problems in this paper belong to combinational optimization problem andhave NP-hard attribute, which respectively are the2D equal circle packing problem withoutperformance constraints and the cutting-stock problem of rectangular plate for iron and steelenterprise with performance constraints. Some scholars have been researching them for along time and proposed many efficient algorithmes, but the solution accuracy andcomputational efficiency need to be further improved. The work is supported by NationalNatural Science Fundation, Sub-project of National Science&Technology Pillar Program,Hunan Provincial Natural Science Foundation, and Research Foundation of EducationBureau of Hunan Province. The two layout design problems are studied respectively in thispaper. The paper respectively presents a heuristic algorithm for equal circle packingproblem and a divide-conquer heuristic search algorithm for cutting-stock problem ofrectangular plate for iron and steel enterprise. The main work and innovation are as follows:1. For the equal circle packing problem, this paper proposes a heuristic algorithm.Firstly, a heuristic location rule generating ring directly is proposed. Then, the heuristiclocation rule is combined with QuasiPQuasiH algorithm to solve this problem. Thenumerical experiments show its effectiveness for solving the equal circle packing problem.2. For the cutting-stock problem of the rectangular plate for iron and steel enterprisethis paper presentes a divide-conquer heuristic search algorithm. The mathematical modelof the problem is built and transformed. Firstly, the corresponding cutting rules andknowledge are extracted from the problem itself and the experiences of MES-basedhuman-machine interactive design, then the plates and contracts are divided into severalgroups according to cutting rules, then all candidate schemes of each group are constructedthrough adopting the proposed divide-conquer heuristic search algorithm and they aresorted by the rolling yield in descending order. The optimal combination scheme of eachsurplus plate is found by quality-monitoring its candidate schemes. Both combination efficiency and utilization ratio of the surplus plates of the proposed algorithm are higherthan those of human machine interactive method based on MES.For2D equal circle packing problem, the initial solution which has little interference isgenerated by using the heuristic location rule generating ring directly. Then the optimalsolution is obtained through the QuasiPQuasiH algorithm. For the cutting-stock problem ofrectangular plate for iron and steel enterprise, both combination efficiency and utilizationratio of the proposed algorithm are superior to those of MES-based human-machineinteractive method. Finally, we hope that the algorithms in this paper can be helpful to solveother layout problemes.