The Research And Development Of Two-dimensional Irregular Polygons Packing System

Two-dimensional packing problem arises from a variety of situations including apparel industry, parts nesting problems and Super Large-Scale Integration (SLSI). Packing belongs to NP-complete (nondeterministic polynomial time complete) problem, which is too difficult to be expressed accurately in simple information model. In addition, the part that can be expressed in mathematical model belongs to NP-complete problem. The algorithms of solving two-dimensional irregular polygons packing problem including simulated annealing (SA), genetic algorithm (GA) and composing of polygons are analyzed deeply in this paper.SA is a stochastic optimization technique that has been used to solve continuous, order discrete and muti-modal optimization problems. This paper improved the way of neighborhood search of SA algorithm. The extended pattern search is adopted, in which three ways are chosen, that can change the packing states of objects (translation, rotation, swap) and two kinds of pattern search matrices (translation and rotation pattern search matrices) are introduced. A general model of SA algorithm is presented and is used to layout the irregular polygons. The judgment of intersection and other constrains of irregular polygons are analyzed, such as two irregular polygons cannot intersect. After packing, all polygons should locate in the down-left corner of a given rectangle and the width of packed polygons should be less than the given width. It has been proved that SA algorithm shortens the computation time and improves the solution.GA is a searching algorithm that is based on the evolution theory and principles of genetics of bioscience. Three operators (crossover, replication, mutation) are used in two-dimensional packing. Many parent generations make many filial generations, and then the individual will be abandoned according to the value of the objective function. Its encoding way is also analyzed in this paper. We adopt SA to produce the initial packing, which ensure the parent generations are choiceness. The crossover (Pc)can prevent the fitness individual to be abandoned, the probability of mutation (Pm) can prevent the algorithm is convergent before premature. In addition, the producing of break point of crossover and mutation is stochastic, which ensure GA can search every region. So GA has the ability to escape from local minima. It has been proved that GA algorithm shortens the computation time and improves the solution.The composing of polygons is researched in this paper. Though simulating the state of packing, adopting the experience of manual packing and heuristics knowledge to control the searching way and limit the search space, it changes the packing problem into the problem of searching best path in the state space.At last, a simple prospect for the possible applications is given.