Top > IJAT > A Solution for 2D Rectangular Cutting Stock Problems with 3-St ...

single-au.php

IJAT Vol.4 No.5 pp. 461-468
doi: 10.20965/ijat.2010.p0461
(2010)

Paper:

Views over last 60 days: 964

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

Received:
May 11, 2010
Accepted:
July 27, 2010
Published:
September 5, 2010
Creative Commons License
Keywords:
cutting stock problem(CSP), cutting process, practical constraint, 3-stage guillotine cutting, simulated annealing
Abstract
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.
Cite this article as:
M. Sugi, Y. Shiomi, T. Okubo, K. Inoue, and J. Ota, “A Solution for 2D Rectangular Cutting Stock Problems with 3-Stage Guillotine-Cutting Constraint,” Int. J. Automation Technol., Vol.4 No.5, pp. 461-468, 2010.
Data files:
References
  1. [1] 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.
  2. [2] 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.
  3. [3] 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.
  4. [4] 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.
  5. [5] 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.
  6. [6] 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.
  7. [7] 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.
  8. [8] J. E. Beasley, “Algorithms for Unconstrained Two-Dimensional Guillotine Cutting,” Journal of Operational Research Society, Vol.36. No.4. pp. 297-306, 1985.
  9. [9] 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.
  10. [10] 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.
  11. [11] 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.
  12. [12] 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.
  13. [13] S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, New Series, Vol.220, No.4598, 1983.
  14. [14] 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.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 22, 2024