Two-Dimensional Cutting Stock Problems with a Modified Column Generation Method
Article Sidebar
Main Article Content
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
Article Details
Copyright Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
Here is the link for download: Copyright transfer form.pdf
References
[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.