الگوریتم برنامه ریزی پویا برای برش بهینه مستطیل های مساوی

This paper presents dynamic programming algorithms for generating optimal guillotine-cutting patterns of equal rectangles. The algorithms are applicable for solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. The algorithms are able to generate the simplest optimal patterns to simplify the cutting process. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths no longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. The computational results indicate that the algorithms presented are more efficient than the branch-and-bound algorithms, which are the best algorithms so far that can guarantee the simplest patterns.

The rectangular cutting stock problem occurs when rectangular sheets in stock are to be cut into smaller rectangles or blanks, to meet a customer’s demand [1], [2], [3] and [4]. Where the blank area must be no larger than the sheet area, some trim loss is expected. Some customers may need blanks of different sizes. Those involved in mass production may want a large number of blanks of the same size. In the former case, nested layouts are often used and blanks of different sizes may appear in the same layout. In the latter case, only blanks of the same size can appear in a layout. This paper refers to the cutting stock problem of equal rectangles as the CSPER, where guillotine shear is used to cut the sheet into blanks. This type of cutting stock problem is also identified as the guillotine-cutting problem [5] and [6], or the guillotine pallet loading problem, and is denoted 2/B/O/C of guillotine type [7]. The CSPER in this paper includes four types of problems: the unconstrained problem where the blank demand is unconstrained, the constrained problem where the blank demand must be met exactly, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. Several algorithms have been published for the CSPER [8], [9], [10], [11] and [12]. Agrawal presented a branch-and-bound algorithm (BBA) for the unconstrained problem [8]. In reference [9], the BBA was extended to solve the constrained problem, and the unconstrained problem with blade length constraint. If the memory of the computer used to perform the algorithm is not large enough, the BBA will not guarantee the optimality of the solution. This will be further discussed in presenting the computational results. A polynomial time algorithm was introduced in [10] for the unconstrained problem. The time efficiency of the algorithm is high. The patterns generated are slightly difficult to cut since they are often not the simplest ones. Arslanov constructed a linear time algorithm for the unconstrained problem in [11]. The algorithm has the highest time efficiency. Similarly it does not guarantee that the patterns generated are the simplest ones for cutting. The dynamic programming algorithm was applied to solve the unconstrained problem in [12]. It does not consider the blade length constraint, and neither guarantees the simplicity of the cutting process. This paper presents dynamic programming algorithms to solve the four types of problems mentioned above. First the dynamic programming algorithm for the unconstrained problem is constructed, which can generate the simplest optimal pattern. Then the algorithm is extended to solve the constrained problem. Another two algorithms are introduced to deal with the blade length constraint, one for the unconstrained problem, and the other for the constrained problem. Computations are performed to compare the algorithms with the branch-and-bound algorithms, which are the best so far that can guarantee the simplest optimal patterns. The results indicate that the algorithms of this paper are more efficient.

Four algorithms based on dynamic programming are presented, which are capable of dealing with four types of problems often encountered in practice: the unconstrained problem, the constrained problem, the unconstrained problem with blade length constraint, the constrained problem with blade length constraint. Algorithm A is the basis of the others. It may generate the simplest optimal patterns, with the cutting process being simplified. This is important to practical applications. Another advantage of the DPA is the easiness to design and understand. Even the engineers may realize the algorithms to solve the CSPER of their factories. Although linear time algorithm exists for the CSPER, it does not guarantee that the pattern generated is the simplest optimal pattern. If the simplest optimal patterns are wanted, the BBA is the best so far. The computational results indicate that for problems of larger scale (such as the test problems of this paper), the DPA is much more time efficient than the BBA.