Approximation Method for Solving Rectangular Guillotine Cutting-Stock Problems
Article Sidebar
Main Article Content
Abstract
Rectangular cutting-stock problems are fundamental optimization challenges in manufacturing industries, where the objective is to cut rectangular items from larger sheets while minimizing material waste. This paper introduces an approximation approach to solve rectangular cutting-stock problems with guillotine cuts, where cutting patterns are produced through a column generation framework. In the proposed approach, the master problem determines an optimal combination of cutting patterns, while new patterns are generated through pricing subproblems formulated as knapsack problems. Dynamic programming is employed to efficiently solve these knapsack subproblems, enabling the identification of high-quality cutting patterns. By iteratively enriching the pattern set, the method approximates the optimal solution without requiring exhaustive enumeration of all feasible patterns. The method offers a practical and scalable solution for rectangular cutting-stock problems encountered in real-world practice.
Article Details
References
[1] John E. Beasley. An exact two-dimensional guillotine cutting algorithm. Operations Research, 33(4):847–859, 1985.
[2] Hao Zhang, Shaowen Yao, Qiang Liu, Lijun Wei, Libin Lin, and Jiewu Leng. An exact approach for the constrained two-dimensional guillotine cutting problem with defects. International Journal of Production Research, 61(9):2986–3003, 2023.
[3] Dianjian Wu and Chunping Yan. Balanced approach for the two-dimensional rectangular guillotine cutting stock problem with setup cost. In IOP Conference Series: Materials Science and Engineering, volume 452, page 022087. IOP Publishing, 2018.
[4] François Clautiaux, Antoine Jouglet, Jacques Carlier, and Aziz Moukrim. A new constraint programming approach for the orthogonal packing problem. Computers & Operations Research, 35(3):944–959, 2008.
[5] Didier Fayard, Mhand Hifi, and Vassilis Zissimopoulos. An efficient approach for large-scale two-dimensional guillotine cutting stock problems. Journal of the Operational Research Society, 49(12):1270–1277, 1998.
[6] André Soares Velasco and Eduardo Uchoa. Improved state space relaxation for constrained two-dimensional guillotine cutting problems. European Journal of Operational Research, 272(1):106–120, 2019.
[7] Mir-Bahador Aryanezhad, Nima Fakhim Hashemi, Ahmad Makui, and Hasan Javanshir. A simple approach to the two-dimensional guillotine cutting stock problem. Journal of Industrial Engineering International, 8(1):21, 2012.
[8] Dianjian Wu and Guangyou Yang. A heuristic approach for two-dimensional rectangular cutting stock problem considering balance for material utilization and cutting complexity. Advances in Materials Science and Engineering, 2021(1):3732720, 2021.
[9] Sergey Polyakovskiy and Peter J. Stuckey. A constraint programming solution to the guillotine rectangular cutting problem. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 33, pages 352–360, 2023.
[10] Paul C. Gilmore and Ralph E. Gomory. A linear programming approach to the cutting-stock problem. Operations Research, 9(6):849–859, 1961.
[11] Paul C. Gilmore and Ralph E. Gomory. A linear programming approach to the cutting stock problem—part II. Operations Research, 11(6):863–888, 1963.
[12] Weiping Pan. An exact algorithm for two-dimensional cutting problems based on multi-level pattern. Graphical Models, 133:101220, 2024.
[13] Glauber Ferreira Cintra, Flávio Keidi Miyazawa, Yoshiko Wakabayashi, and Eduardo C. Xavier. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1):61–85, 2008.
[14] Fabio Furini, Enrico Malaguti, Rosa Medina Durán, Alfredo Persiani, and Paolo Toth. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size. European Journal of Operational Research, 218(1):251–260, 2012.
[15] K. Novianingsih, R. Hadianti, and S. Uttunggadewa. Column generation technique for solving two-dimensional cutting stock problems: method of stripe approach. Journal of the Indonesian Mathematical Society, pages 161–172, 2007.
[16] Sirirat Juttijudata and Phissanu Sudjarittham. Two-dimensional cutting stock problems with a modified column generation method. Current Applied Science and Technology, pages 217–225, 2020.
[17] Jianyu Long, Zhong Zheng, Xiaoqiang Gao, Panos M. Pardalos, and Wanzhe Hu. An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem. Annals of Operations Research, 289(2):291–311, 2020.
[18] Massimo Bertolini, D. Mezzogori, F. Zammori, et al. Hybrid heuristic for the one-dimensional cutting stock problem with usable leftovers and additional operating constraints. International Journal of Industrial Engineering Computations, 15(1):149–170, 2024.
[19] Qiulian Chen and Yan Chen. Heuristics for the two-dimensional cutting stock problem with usable leftover. Intelligent Data Analysis, 28(2):591–611, 2024.
[20] Wayne L. Winston. Operations Research: Applications and Algorithm. Thomson Learning, Inc., 2004.
[21] Hamdy A. Taha. Operations Research: An Introduction. Pearson Education India, 2013.