Using Layer Patterns in Solving the Two-Dimensional Cutting Stock Problem

10.6186/IJIMS.2011.22.2.6

Xiao-Qing Wang；Ling Huang；Yao-Dong Cui

Two-dimensional cutting ； cutting stock ； layer patterns

International Journal of Information and Management Sciences

22：2（2011 / 06 / 01）

189 - 200

英文

The two-phase cutting process is often used to divide stock plates into rectangular items. At the first phase, an automatic machine with multiple parallel cutters divides the plate into several sections in one pass. The sections are divided into blanks by simple equipments at the second phase. This paper focuses on the two-dimensional cutting stock problem of rectangular items, where the two-phase process is applied. Layer patterns are used because they are useful for the improvement of the efficiency of the cutting process. The algorithm is based on linear programming approach (LPA). In each cycle of the simplex iteration, it calls a dynamic programming procedure to generate an optimal layer pattern, and introduces it into the base matrix to obtain a new solution. Each LPA solution (often fractional) is rounded to obtain the integer solution. The best integer solution is taken as the final solution. The computational results indicate that layer patterns are useful for two-dimensional stock cutting.

1. Chang, S. H.,Pao, S. H.(2010).A manufacturer's optimal quantity discount and return policy through game-theoretic approach again.International Journal of Information and Management Sciences,21,73-90.
   連結：
2. Gunawan, A.,Ng, K. M.(2011).Solving the teacher assignment problem by two metaheuristics.International Journal of Information and Management Sciences,22,73-86.
   連結：
3. Yang, S. J.,Hsu, C. J.(2010).Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration.International Journal of Information and Management Sciences,21,177-195.
   連結：
4. Beasley, J. E.(1985).Algorithms for unconstrained two-dimensional guillotine cutting.Journal of the Operational Research Society,36,297-306.
5. Cui, Y.(2007).Simple block patterns for the two-dimensional cutting problem.Mathematical and Computer Modelling,45,943-953.
6. Cui, Y.(2004).Generating optimal T-shape cutting patterns for rectangle blanks.Engineering Manufacture,218,857-866.
7. Cui, Y.,He, D.,Song, X.(2006).Generating optimal two-section cutting patterns for rectangular blanks.Computers and Operations Research,33,1505-1520.
8. Cui, Y.,Wang, Z.(2005).Exact and heuristic algorithms for staged cutting problems.Journal of Engineering Manufacture,219,201-208.
9. Fayard, D.,Hifi, M.,Zissimopoulos, V.(1998).An efficient approach for large-scale two-dimensional guillotine cutting stock problems.Journal of the Operational Research Society,49,1270-1277.
10. Gilmore, P. C.,Gomory, R. E.(1965).Multistage cutting stock problems of two and more dimensions.Operations Research,13,94-120.
11. Hifi, M.(2011).Exact algorithms for large-scale unconstrained two and three staged cutting problems.Computational Optimization and Applications,18,63-88.
12. Wang, X.、Li, S.、Cui, Y.(2010)。Dynamic programming algorithm for generating optimal layer patterns of rectangular blanks。Application Research of Computers，27，2040-2042。