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 Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant 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.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
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.
