Research On Solving Algorithm And Parallel Method Of Circle Packing Problem

Packing optimization problems can be found in many areas such asmachine manufacturing, garment processing, publication printing and traffictransportation, and it belongs to the NP-complete problem with the mostcomplicated computation. Therefore, research on solving algorithm of packingproblem has an important significance in production practice and calculationtheory science.Circle packing problem appears widely in daily production and life, andcompared to other types of packing problems, the research of this problem isunder a relatively small situation. In this paper, by the analysis of the currentresearch status, a series of new methods is presented for circle packingproblem. The main contents are listed as follows：(1) To solve the problem of packing circles into a rectangular container,an order-oriented filling algorithm driven by a binary search and apartheno-genetic algorithm (PGA-BOFA) is proposed, which is a nestediteration. In its kernel, OFA is an enhanced packing procedure with an edgepattern and a circle order, and produces a packing arrangement for a rectanglewith fixed width and length. The inner loop (BOFA) of PGA-BOFA calls for OFA iteratively through a binary search to find the packing arrangement withminimum rectangle length, while the outer iterating loop changes the circleorder and the edge pattern applied in BOFA by a partheno-genetic algorithm.(2) A quasi-rectangle packing idea is presented by the definition ofpseudo-side and pseudo-vertex. Under the new designed layout strategies,PGA-BOFA can also be used to solve the problem of packing circles into acircular container.(3) Combine both the inherent parallel characteristic of PGA and highlyparallel technology of HPC system, a parallel PGA-BOFA algorithm(PPGA-BOFA) is proposed based on the idea of divide and rule. Model ofmaster/slave-coarse grain is presented to be employed to the evolution of multipopulations with different strategies during computing, optimal solutioncollected and overall migration strategies are applied to improve the searchingspeed and strengthen diversity of the population。Finally, PPGA-BOFA isimplemented based on the MPI technology in the designed HPC system。The reasonableness and effectiveness of the above mentioned methodshave been verified by testing lagre number of benchmark instances.