×

A new dynamic programming procedure for three-staged cutting patterns. (English) Zbl 1268.90061

Summary: Three-staged patterns are often used to solve the 2D cutting stock problem of rectangular items. They can be divided into items in three stages: Vertical cuts divide the plate into segments; then horizontal cuts divide the segments into strips, and finally vertical cuts divide the strips into items. An algorithm for unconstrained three-staged patterns is presented, where a set of rectangular item types are packed into the plate so as to maximize the pattern value, and there is no constraint on the frequencies of each item type. It can be used jointly with the linear programming approach to solve the cutting stock problem. The algorithm solves three large knapsack problems to obtain the optimal pattern: one for the item layout on the widest strip, one for the strip layout on the longest segment, and the third for the segment layout on the plate. The computational results indicate that the algorithm is efficient.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wascher G., Haussner H., Schumann H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007) · Zbl 1278.90347 · doi:10.1016/j.ejor.2005.12.047
[2] Cui Y.: Generating optimal T-shape cutting patterns for rectangular blanks. J. Eng. Manuf. 218, 857–866 (2004) · doi:10.1243/0954405041486037
[3] Gilmore P.C., Geomory R.E.: Multistage cutting stock problems of two and more dimensions. Oper. Res. 13, 94–120 (1966) · Zbl 0128.39601 · doi:10.1287/opre.13.1.94
[4] Beasley J.E.: Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36, 297–306 (1985) · Zbl 0589.90040
[5] Morabito R., Arenales M.N.: Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach. Eur. J. Oper. Res. 94, 548–560 (1996) · Zbl 0947.90537 · doi:10.1016/0377-2217(95)00128-X
[6] Cui Y., Wang Z., Li J.: Exact and heuristic algorithms for staged cutting problems. J. Eng. Manuf. 219(B2), 201–208 (2005) · doi:10.1243/95440505X8136
[7] Hifi M.: Exact algorithms for large-scale unconstrained two and three staged cutting problems. Comput. Optim. Appl. 18, 63–88 (2001) · Zbl 0963.90051 · doi:10.1023/A:1008743711658
[8] Cui Y., Huang L., He D.: Generating optimal multiple-segment cutting patterns for rectangular blanks. J. Eng. Manuf. 218(B11), 1483–1490 (2004) · doi:10.1243/0954405042418446
[9] Fayard D., Hifi M., Zissimopoulos V.: An efficient approach for large-scale two-dimensional guillotine cutting stock problems. J. Oper. Res. Soc. 49, 1270–1277 (1998) · Zbl 1140.90374
[10] Vanderbeck F.: A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Manag. Sci. 47, 864–879 (2001) · Zbl 1232.90326 · doi:10.1287/mnsc.47.6.864.9809
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.