Abstract
This paper presents a recursive algorithm for constrained two-dimensional guillotine cutting problems of rectangular items. The algorithm divides a stock plate into a sequence of small rectangular blocks. For the current block considered, it selects an item, puts it at the left-bottom corner of the block, and determines the direction of the dividing cut that divides the unoccupied region of the block into two smaller blocks for further consideration. The dividing cut is either along the upper edge or along the right edge of the selected item. The upper bound obtained from the unconstrained solution is used to shorten the searching space. The computational results on benchmark problems indicate that the algorithm can improve the solutions, and is faster than other algorithms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Wascher, G., Haussner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Christofides, N., Whitlock, C.: An algorithm for two-dimensional cutting problems. Oper. Res. 25, 30–34 (1977)
Christofides, N., Hadjiconstantinou, E.: An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. Eur. J. Oper. Res. 83, 21–38 (1995)
Hifi, M., Zissimopoulos, V.: Constrained two-dimensional cutting: an improvement of Christofides and Whitlock’s exact algorithm. J. Oper. Res. Soc. 5, 8–18 (1997)
Wang, P.Y.: Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 32(3), 573–586 (1983)
Vasko, F.J.: A computational improvement to Wang’s two-dimensional cutting stock algorithm. Comput. Ind. Eng. 16, 109–115 (1989)
Hifi, M.: An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. Comput. Oper. Res. 24, 727–736 (1997)
Viswanathan, K.V., Bagchi, A.: Best-first search methods for constrained two-dimensional cutting stock problems. Oper. Res. 41, 768–776 (1993)
Daza, V.P., Alvarenga, A.G., Diego, J.: Exact solutions for constrained two-dimensional cutting problems. Eur. J. Oper. Res. 84, 633–644 (1995)
Cung, V.D., Hifi, M., Le Cun, B.: Constrained two-dimensional cutting stock problems. A best-first branch-and-bound algorithm. Int. Trans. Oper. Res. 7, 185–210 (2000)
Amaral, A.R.S., Wright, M.: Efficient algorithm for the constrained two-dimensional cutting stock problem. Int. Trans. Oper. Res. 8, 3–13 (2001)
Morabito, R.N., Arenales, M.N.: Staged and constrained two-dimensional guillotine cutting problems: an AND/OR graph approach. Eur. J. Oper. Res. 94, 548–560 (1996)
Zissimopoulos, V.: Heuristic methods for solving (un)constrained two-dimensional cutting stock problems. Method. Oper. Res. 49, 345–357 (1984)
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)
Alvarez-Valdes, R., Parajon, A., Tamarit, J.M.: A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput. Oper. Res. 29, 925–947 (2002)
Hifi, M.: Dynamic programming and hill-climbing techniques for the constrained two-dimensional cutting stock problem. J. Comb. Optim. 8, 65–84 (2004)
Cui, Y.: An exact algorithm for generating homogenous T-shape cutting patterns. Comput. Oper. Res. 34(4), 1107–1120 (2007)
Cui, Y.: Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns. Comput. Oper. Res. 35, 212–225 (2008)
Beasley, J.E.: Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36, 297–306 (1985)
Young-Gun, G., Seong, Y.J., Kang, M.K.: A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. Oper. Res. Lett. 31, 301–307 (2003)
Cui, Y., Wang, Z., Li, J.: Exact and heuristic algorithms for staged cutting problems. Proc. Inst. Mech. Eng. Part B: 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.: Generating optimal T-shape cutting patterns for rectangular blanks. Proc. Inst. Mech. Eng. Part B: J. Eng. Manuf. 218(B8), 857–866 (2004)
Cui, Y.: Simple block patterns for the two-dimensional cutting problem. Math. Comput. Model. 45(7–8), 943–953 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, Y. A recursive algorithm for constrained two-dimensional cutting problems. Comput Optim Appl 41, 337–348 (2008). https://doi.org/10.1007/s10589-007-9103-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9103-3