A Solution for 2D Rectangular Cutting Stock Problems with 3-Stage Guillotine-Cutting Constraint
Masao Sugi*, Yusuke Shiomi**, Tsuyoshi Okubo**,
Kazuyoshi Inoue**, and Jun Ota***
*Tokyo University of Agriculture and Technology, 2-24-16 Naka-cho, Koganei-shi, Tokyo 184-8588, Japan
**NS Solutions Corporation, 27-1 Shinkawa 2-chome, Chuo-ku, Tokyo 104-0033, Japan
***The University of Tokyo, Kashiwanoha 5-1-5, Kashiwa, Chiba 277-8568, Japan
The cutting stock problem (CSP) adversely affecting processing industry profits has been studied aggressively in mathematical planning but the results are not often used at real production sites and solutions are often still found manually by experienced personnel because real processing constraints have not been focused on. This paper deals with the 2-dimensional rectangular cutting stock problem (2DRCSP) in which the shape of a cut piece is rectangular, assuming a roll-shaped stock often used in actual processing and proposing a solution taking processing called 3-stage guillotine cutting into account.
-  P. C. Gilmore and R. E. Gomory, “A Linear Programming Approach to The Cutting-Stock Problem,” Operations Research, Vol.9, No.6, pp. 849-859, 1961.
-  P. E. Sweeney and E. R. Paternoster, “Cutting and Packing Problems: A Categorized, Application-Oriented Research Bibliography,” Journal of the Operational Research Society, Vol.43, No.7, pp. 691-706, 1992.
-  G. Wäscher, H. Haubner, and H. Schumann, “An Improved Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol.183, No.3, pp. 1109-1130, 2007.
-  E. Hopper and B. H. C. Turton, “A Review of The Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems,” Artificial Intelligence Review, Vol.16, No.4, pp. 257-300, 2001.
-  S. Martello, M. Monaci, and D. Vigo, “An Exact Approach to The Strip-Packing Problem,” INFORMS journal on Computing, Vol.15, pp. 310-319, 2003.
-  B. S. Baker, E. G. Coffman Jr., and R. L. Rivest, “Orthogonal Packings in Two Dimensions,” SIAM Journal on Computing, Vol.9, No.4, pp. 846-855, 1980.
-  E. K. Burke, G. Kendall, and G. Whitwell, “A New Placement Heuristic for The Orthogonal Stock-Cutting Problem,” Operations Research, Vol.52, No.4, pp. 655-671, 2004.
-  J. E. Beasley, “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting,” Journal of Operational Research Society, Vol.36. No.4. pp. 297-306, 1985.
-  D. Fayard, M. Hifi, and V. Zissimopoulos, “An Efficient Approach for Large-Scale Two-Dimensional Guillotine Cutting Stock Problems,” Journal of the Operational Research Society, Vol.49, pp. 1270-1277, 1998.
-  A. T. Rahmani and N. Ono, “An Evolutionary Approach to Two-Dimensional Guillotine Cutting Problem,” Proceedings of 1995 IEEE International Conference on Evolutionary Computing, Vol.1, 1995.
-  F. Vanderbeck, “A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem,” Management Science, Vol.47 No.6, pp. 864-879, 2001.
-  J. Puchinger and G. R. Raidl, “Models and Algorithms for Three-Stage Two-Dimensional Bin Packing,” European Journal of Operational Research, Vol.183, No.3, pp. 1304-1327, 2007.
-  S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol.220, No.4598, 1983.
-  E. G. Coffman Jr., M. R. Garey, D. S. Johnson, and R. E. Tarjan, “Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms,” SIAM Journal on Computing, Vol.9 No.4, pp. 801-826, 1980.