A Sequential Heuristics Procedure For Rectangle Packing Problems

Computer aided Nesting (CAN) is one of the widely used computer aided technique, which is used to instruct industries to deal with the cutting stock problem in order to achieve the objectives of saving raw material and reducing the cost of product.The cutting stock problem exists in many industries of the national economy, in which the two-dimension cutting stock problem is applied widely. The rectangle packing problem is the base of the two-dimension cutting stock problem, so doing the research on it is a significant issue to find out the optimal layout of rectangular blanks. Rectangle packing problem refers to determine a cutting solution which is to satisfy the demand of all blanks by using plates as few as possible, on condition that there are enough plates. Scholars in and abroad have done extensive research on this problem, and proposed a variety of algorithms such as: linear programming algorithm,simulated annealing algorithm, genetic algorithm. This paper adopts a heuristic algorithm to solve the rectangle packing problem. The answer to the packing problem is a cutting solution which consists of one or more cutting patterns, and demonstrates the number of raw material used by every pattern. The cutting pattern must be feasible, it means that the blanks packed in the plate can't overlap with each other and anyone of them can't exceed the border of the plate. It is crucial to acquire a good cutting solution that adopts suitable rectangle packing algorithm to generate cutting patterns. The main function of the algorithm which generates the cutting pattern is to confirm a set of blanks and determine the arrangement of the set's blanks on the plate. The cutting algorithm can be sorted into unconstrained algorithm and constrained algorithm according to whether there is a limit of the times that the blank appears in the plate. The unconstrained one doesn't restrict the amount of blanks, but the constrained one restricts that the number of every blank can't exceed its permitted upper bound. In addition, according to whether to allow packing variety sizes of blanks in a plate, the corresponding cutting pattern is called unit-cutting patterns and multi-cutting pattern, comparatively, though the cutting process of multi-cutting pattern is more complex, it can improve material utilization significantly. This paper mainly does research on using constrained algorithm to generate the multi-cutting pattern.In this paper, an improved sequential heuristics procedure is adopted to confirm an optimal cutting solution, the main work is to combine the quasi-human algorithm which generates the cutting pattern with the sequential heuristics procedure based on value correction, and the details of this paper are as follows:Firstly, a quasi-human algorithm is introduced to generate cutting pattern which has the maximum value per unit area on basis of the optimal packing model. While using quasi-human algorithm to pack a rectangle blank, the blank always occupies a corner, and a hole as possible as it can. The quasi-human algorithm consists of greedy-algorithm and backtrack-algorithm. Greedy-algorithm always does the corner-occupying action with maximal caving degree. The backtrack-algorithm is used on the basis of greedy algorithm, once a blank is packed into the plate, the backtrack-algorithm is applied to confirm a corner-occupying action which has the maximal grade and then to do this action. On the basis of quasi-human algorithm, we improve the algorithm by reducing the number of corners and increasing the amount of strategy for selecting a corner-occupying action.Secondly, a value correction formula from the one-dimension packing problem is extended to solve the rectangle packing problem. The cutting patterns in the cutting solution are generated sequentially, when a pattern is generated by the quasi-human algorithm, every blanks in the plate of this pattern must be evaluating by the status of layout. The blank's value is corrected by using the evaluation's result combine with the prior information, and to get more reasonable by doing value correction repeatedly. Using traditional sequential heuristics procedure to generate cutting solution easily lead to local optimum situation, but combining with value correction can effectively avoid this situation and reach the global optimum. Several solutions are generated iteratively by implementing the sequential heuristics procedure based on value correction, and the solution with highest material utilization will be chosen. In addition, making the remaining material as long as possible and the patterns as few as possible are also the optimization goal of this paper.Finally, designing and developing the rectangle packing system. The presented algorithm in this paper is tested by using a large number of experiments, and the results are compared with interrelated literatures as well as commercial software, the results show that the algorithm presented in this paper can lead to high material utilization. In a word, the rectangle packing algorithm presented in this paper is efficient.