Research Of Rectangular Packing Methods Based On Estimation Of Distribution Algorithms

This paper mainly studies the optimization of rectangular strip packing. The problem of the Rectangular strip packing can be described as putting the needed the Rectangular of same or various sizes on the Rectangular sheet based on the given packing algorithm, which aim at minimizing sheet's unused area after cutting. The problems of the Rectangular packing optimization are widely existed in many manufacturing fields, such as machinery manufacturing, furniture production, papermaking, clothing, leather cutting and so on. The study of the Rectangular strip packing provide great practical significance for increasing material utilization ratio, reducing production cost, and enhancing the enterpeise's economic benefit.The optimization of Rectangular strip packing is a combination optimization problem, which belongs to NP complete problem in Mathematics. It is difficult to find the exact global optimum in a certain period of time because of the high complexity of computation. People usually take the intelligent algorithm and heuristic algorithm to solve the problem of the Rectangular strip packing. Such as Genetic Algorithm, Ant Colony Algorithm, Particle Swarm Optimization Algorithm, Simulated Annealing Algorithm, Bottom-Left Algorithm, Difference Process Algorithm and so on.While, it is hard to get better results and improve the algorithm performance with single intelligent algorithm or heuristic algorithm. This paper proposed a hybrid algorithm which combined Estimation of distribution algorithm and a kind of improved Lowest Horizontal Search Algorithm, after studying the algorithm of many scholars both at home and abroad. Estimation of distribution algorithm is a new intelligent algorithm with a new evolutionary model, which based on probability model to realize the population evolution. It is the latest effort to apply EDAs to solve the the Rectangular strip packing for the successful application of EDAs in many other fields. In this paper,The main idea and characteristics of EDA are introduced in detail. Besides, a kind of improved Lowest Horizontal Search Algorithm is proposed after a comparative analysis of Bottom-Left algorithm, Lowest Horizontal algorithm and Lowest Horizontal search algorithm, which can record free area and combine the small free area that produced during the process of the Rectangular packing to the large based on the position relationship of the free the Rectangular area. The improved algorithm can obtain better sequence and better location of each the Rectangular by comparing the size of each the Rectangular with the free area and putting the appropriate the Rectangular strips into the free area. So,the improved algorithm reuse the free area and improve the using ratio of sheet, which overcome the drawbacks of Lowest Horizontal search algorithm.In the process of solving the Rectangular strip packing by using the hybrid algorithm, Estimation of distribution algorithm is taken to acquire a better arrangement sequence, and the improved Lowest Horizontal search algorithm is taken to put the Rectangular strips and produce the Rectangular layout. The test results of algorithm shows that the hybrid algorithm possesses high efficiency and provide important significance for increasing material utilization ratio, reducing production cost, and enhancing the enterpeise's economic benefit.