Study On Intelligent Search Algorithms Based On Knowledge For Constrained Circle And Rectangle Orthogonal Packing Problem

Packing problems (layout design problem) derive from many engineering designareas, such as: printed circuit board (PCB) design, the satellite module layout design,slab design and matching surplus slab for iron and steel companies, plate cutting inprocessing industry, and so on. For the problems in this paper, it is required to use assmall space as possible to pack all objects, or to pack as more objects as possible inthe container while satisfying given performance constraints. Because of the NP hardnature, they have been widely researched by scholars. The existing algorithms tosolve the above problems mainly include the following three types: heuristicalgorithms, evolutionary algorithms and hybrid algorithms. The heuristic algorithmshave higher computational effciency, but they are without global search ablity. Forevolutionary algorithms, their situation is just the reverse. So, scholars have beenstudying the hybrid algorithm which consists of the heuristic algorithm with theevolutionary algorithm for a long time. But cruuently, it is a lack of power solutionapproaches for the problems in this paper. Therefore, with the support of the NationalScience and Technology Support Project (No.2012-BAF10B04), and the NationalNatural Science Foundation of China (No.61272294), our subject group studies onthe layout design problem of the satellite module, two problems of the slab design andsurplus slab-matching for iron and steel companies. Transforming them into rectanglepacking problem, circle and rectangle packing problem with constraints for solving,we obtain many achievements, whose computational efficiency, solution precisionand stability are higher than those of existing algorithms. The main works of thispaper include three aspects:(1) For orthogonal rectangle packing problem with constraints, a fast heuristic antcolony algorithm is proposed. Its heuristic construction of the feasible solution is thatthe roulette wheel selection is used in ordering, and the overlap-allowed fieldsgenerated by given rules are used in quickly positioning retangles. The numericalexperimental results show that the performance of the proposed algorithm is superiorto those of existing algorithms.(2) For the circle and orthogonal rectangle packing problem with constraints, thispaper puts forwards a heuristic ant colony algorithm. Replacing the circle by itscircumscribed rectangle, this problem is transformed into the orthogonal rectangle packing problem with constraint. In the process of positioning, the proposed adaptivemove strategy makes the layout scheme more compact. The numerical experimentalresults show that both the computational efficiency and accuracy of the proposedalgorithm are higher than of those of existing algorithms.(3) For the slab design and surplus slab-macthcing problem, this paper proposes adivide-and-conquer heuristic algorithm. For the slab design, the orders are diviedseveral subset in the grade of steel, producted line and the thickness, and then for eachsubset, all plate schemes are constructed suing the strategy of backtracking and thelimited neighborhood order, and the candidate slab schemes are obtained bycalculating parameters of slabs corresponding to each plate scheme passed by rules,and then the optimal slab scheme is searched out from the candidate schemes by usingthe proposed k-step backtracking. For the surplus slab-matching, an order subset isfound for each surplus slab, then according to the above slab design method, itscandidate slab scheme set is calculated and their optimal scheme is found bybacktracking. In addition, due to the introduction of the parallel mechanism, both theefficiency of the slab design and surplus slab-matching are futher improved. Thestatistical data of one Iron and Steel Company show that the yields of the slab designand surplus slab-matching of two algorithms are higher than those of the artificialdesign and matching based on MES, respectively.Under the background of the satellite layout problem, slab design and matchingproblem for iron and steel enterprises, this paper is mainly focused on the research ofthe rectangle packing problem, circle and rectangle packing problem with constraint,slab design problem and surplus slab matching problem and the proposed algorithmshave good performance.