Two-Dimensional Cutting Stock Problems with a Modified Column Generation Method

Main Article Content

Sirirat Juttijudata*
Phissanu Sudjarittham

Abstract

The two-dimensional cutting stock problems pose mathematical challenges due to the nature of mixed integer linear programming resulting in NP-hard problems.  At the same time, the problems are industrially important in manufacturing, logistic and supply chain industries. The ability to solve large-scale two-dimensional cutting stock problems could have a great impact on research community as well as industries. The objective of this work is to develop a framework of solution method for two-dimensional cutting stock problems using a modified column generation method. Two-stage Guillotine cutting patterns are considered. The relationship between the cutting patterns in the first and second stages gives rise to additional constraints that are not previously found in one-dimensional cutting stock problems. As a result, the column generation method was modified to handle these additional constraints. In order to further simplify the problem, LP relaxation is used in conjunction with the column generation. Integer solution can be obtained by rounding of LP solution. The lower bound of the problems may be estimated from the minimization of LP problem; allowing the optimality of solution obtained to be assessed in terms of, for example, the worst performance ratio. With the instance problem studied in this work, the modified column generation method performs well and produces the optimal result that is only 1% less than optimal solution obtained from the exact algorithm, which is the effect of rounding. In terms of speed, the proposed method requires only 1/200 floating point operations compared to the full problem with all feasible solutions (from the instance problem studied here). The proposed method may be further fine-tuned both in terms of rounding techniques with some tweaks in the column generation method in the future. The special structures of the problems should be further exploited for the advantage of the solution methods for large-scale problems.


 


Keywords: two-dimensional cutting stock problems; Guillotine constraints; column generation

*Corresponding author: Tel.: +66 16 46 5636


                                           E-mail: srcsrr@ku.ac.th

Downloads

Download data is not yet available.

Article Details

Section
Research Articles

References

[1] Delorme, M., Iori, M. and Martello, S., 2016. Bin packing and cutting stock problems: mathematical models and exact algorithms, European Journal of Operational Research, 225 (1), 1-20.
[2] Gilmore , P.C. and Gomory, R.E., 1965. Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94-120.
[3] Gilmore , P.C. and Gomory, R.E., 1965. The theory and computation of knapsack functions, Operations Research, 14, 1045-1074.
[4] Benati, S., 1997. An algorithm for a cutting stock problem on a strip. Journal of the Operational Research Society, 39, 288-294.
[5] Johnson, R.E., 1986. Rounding algorithms for cutting stock problems. Asia-Pacific Journal of Operational Research, 3, 166-171.
[6] Suliman, S.M.A., 2005. A sequential heuristic procedure for the two-dimensional cutting stock problem. International Journal of Production Economics, 99 (1-2), 177-185.
[7] Hopper, E. and Turton, B., 1999. A genetic algorithm for a 2D industrial packing problem. Computers and Industrial Engineering, 37 (1-2), 375-378.
[8] Levine, J. and Ducatelle, F., 2004. Ant colony optimization and local search for bin packing and cutting stock problems. Journal of Operational Research Society, 55(7), 705-716.
[9] Lasdon, L.S., 1979. Optimization Theory for Large Systems. London: MacMillan Publishing.