Title: Solving the one-dimensional cutting stock problem under discrete, uncertain, time-varying demands using a hybrid of special-purpose Benders' decomposition and column generation

Authors: Aphisak Witthayapraphakorn; Sasarose Jaijit; Peerayuth Charnsethikul

Addresses: Department of Industrial Engineering, Faculty of Engineering, University of Phayao, 19 Moo 2, Tambon Maeka, Amphur Muang Phayao, Phayao 56000, Thailand ' Department of Industrial Engineering, Faculty of Engineering at Kamphaeng Saen, Kasetsart University, Nakhon Pathom 73140, Thailand ' Industrial Engineering Department, Faculty of Engineering, Kasetsart University, 50 Ngam Wong Wan Road, Ladyao, Chatuchak, Bangkok 10900, Thailand

Abstract: This study shows the integration of Benders' decomposition, column generation, and a special-purpose algorithm for solving the one-dimensional cutting stock problem under discrete, uncertain, time-varying demands. The results show that there is a linear relationship between the processing time and the number of scenarios involved in the raw material cutting patterns. Moreover, the algorithm results are not different from using column generation. During the search for production patterns, the quality of the solutions relies on the convergence tolerance. As the tolerance approaches zero, the solutions become near-optimal, but the computational time increases substantially. In addition, the experimental results indicate that the proposed method is suitable for large-scale problems.

Keywords: stochastic linear programming; one-dimensional cutting stock problem; uncertain demands; large-scale linear programming; Benders' decomposition.

DOI: 10.1504/IJMOR.2021.113578

International Journal of Mathematics in Operational Research, 2021 Vol.18 No.3, pp.360 - 383

Received: 08 Nov 2019
Accepted: 31 Dec 2019
Published online: 12 Mar 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article