Approximation Method for Solving Rectangular Guillotine Cutting-Stock Problems - Abdul Rahman; Ihda Hasbiyati; Wamiliana; Moh Danil Hendry Gamal (Integra: Journal of Integrated Mathematics and Computer Science, 2026)
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.