Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Wascher G., Haussner H., Schumann H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Cui Y.: Generating optimal T-shape cutting patterns for rectangular blanks. J. Eng. Manuf. 218, 857–866 (2004)
Gilmore P.C., Geomory R.E.: Multistage cutting stock problems of two and more dimensions. Oper. Res. 13, 94–120 (1966)
Beasley J.E.: Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36, 297–306 (1985)
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)
Cui Y., Wang Z., Li J.: Exact and heuristic algorithms for staged cutting problems. J. Eng. Manuf. 219(B2), 201–208 (2005)
Hifi M.: Exact algorithms for large-scale unconstrained two and three staged cutting problems. Comput. Optim. Appl. 18, 63–88 (2001)
Cui Y., Huang L., He D.: Generating optimal multiple-segment cutting patterns for rectangular blanks. J. Eng. Manuf. 218(B11), 1483–1490 (2004)
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)
Vanderbeck F.: A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Manag. Sci. 47, 864–879 (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cui, Y. A new dynamic programming procedure for three-staged cutting patterns. J Glob Optim 55, 349–357 (2013). https://doi.org/10.1007/s10898-012-9930-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9930-3