Solving The Rectangle Packing Problem Of The Discrete Particle Swarm Algorithm

Rectangle packing problem is a kind of cutting problem, usually consists of packing given rectangle pieces into a large rectangle stock plate, with a requirement of maximum usage of the stock plate. It is a typical combination optimization and has been proved to be a NP-complete problem.In this thesis, rectangle packing problem will be converted into combinatorial optimization problem through the nesting layout rules (rectangle fill algorithm). Because of the solution space of the rectangle packing problem is discrete not continuous, a discrete particle swarm optimization algorithm was been presented. First of all, according to the characteristics of discrete combinatorial optimization problem, the particle's position, velocity and computing rules were redefined and modified. Then using the rectangle fill algorithm to decode and calculate the utilization of materials as the fitness function of DPSO. In the end, the optimal solution of the problem will be found by iterative search. Through the comparing with the other typical algorithms, the results of this DPSO algorithm show a better performance in the search.