Research On Rectangular Optimal Layout Algorithm And System Implementation

The problem of rectangular layout is to put various different sizes rectangular objects into stock sheets, how to make the ratio of material highly under the condition of no interference and not beyond the boundary [1]. It is extensively applied into the glass, steel plate, timber, leather etc. From mathematics calculation complexity theory, the problem whose computation is the most complex in theory belongs to the NP complete problem. The solution of the valid polynomial time calculate way can't find out by now. A good packing scheme can not only save raw material and reduce production cost, but also bring economic benefit for and enhance the competitiveness of enterprises. Therefore, research on the problem of optimal layout for rectangular part is very important in theory and applications.In this paper, the features of problem are studied and its mathematics model is established. Some kind of optimal algorithms and common layout algorithms for the optimal layout of rectangular part are introduced. Under certain constraints, genetic algorithm is applied into the optimal layout of rectangular part. The results of instances are compared each other and analyzed in detail.Firstly, introduce the mathematics model of the optimal layout of rectangular part and some kind of common layout algorithms, such as the surplus rectangular to match algorithm, bottom-left algorithm,'downstairs'algorithm, on the basis of the lowest horizontal line-search algorithm. We compare these algorithms.Secondly, introduced the rectangular parts'cutting draft of the large-scale production, such as guillotine; lay the same rectangular object together in order to improve efficiency; there is the guarantee of the safe distance while process.Then introduce the basic theory of genetic algorithm. The genetic algorithm is used to solve the problem of rectangular part optimal layout. In the meantime, the coding method, fitness function definition, GA operator and some key parameters are given. The result is analyzed and compared with each other through examples.Finally, according to above theory, we develop system of rectangular object optimal layout with VB.NET, including user login, the management of parts and stock sheets and optimal layout.The paper applied genetic algorithm and on the basis of the lowest horizontal line-search algorithm into rectangular object optimal layout. The experimental results satisfy craft requirement of guillotine and laying the same rectangular object together, and the ratio of using of stock sheets is about 94 percents. It can be used in practice.