Two-dimensional Rectangular Optimal Nesting

The problem of two-dimensional optimal layout for rectangular parts widely exists in many manufacturing industries, such as glasswork, steel plate machining, lumbering, rag trade, shipbuilding and so on. A good packing scheme can not only save raw material and reduce the production cost, but also bring economic benefits for enterprises and enhance the competitiveness of enterprises. The problem whose computation is the the most complex in theory belongs to the NP complete problems. The optimal solution is very difficult to obtain by the exact algorithms when the scale of the problem expands largely. Therefore, research on the problem of two-dimensional optimal layout for rectangular parts is very important in theory and applications.In this paper, the features of the problem are studied and its mathematical model is established. Then three methods are applied to solving the problem. The results of four numerical examples under different constraints are compared with each other and analyzed in detail.Firstly, the genetic algorithm(GA) is used to solve the problem of rectangular parts optimal layout. In the meantime, the coding method, fitness function definition, GA operators and some key parameters are given. The results of numerical examples show that GA can generally obtain good solutions.Then we attempt to put forward one kind of immune algorithm(IA) to solve the problem, because GA will fall into premature convergence easily when the initial solutions aren't distributed equably. Due to the strategy of the group renewal based on the density of antibodies, IA can effectively maintain the multiplicity among antibodies and overcome premature convergence. It is proved that IA can obtain better optimized solutions than GA. However, IA has a defect that it runs more slowly than GA.Finally, we redefine the similarity between two antibodies, improve the way of calculating the density and add vaccination operator to the basic immune algorithm.