Implementation of On-Line Cutting Stock Problem on NC Machines

Authors: Jui P. Hung, Hsia C. Chang, Yuan L. Lai

Abstract:

Introduction applicability of high-speed cutting stock problem (CSP) is presented in this paper. Due to the orders continued coming in from various on-line ways for a professional cutting company, to stay competitive, such a business has to focus on sustained production at high levels. In others words, operators have to keep the machine running to stay ahead of the pack. Therefore, the continuous stock cutting problem with setup is proposed to minimize the cutting time and pattern changing time to meet the on-line given demand. In this paper, a novel method is proposed to solve the problem directly by using cutting patterns directly. A major advantage of the proposed method in series on-line production is that the system can adjust the cutting plan according to the floating orders. Examples with multiple items are demonstrated. The results show considerable efficiency and reliability in high-speed cutting of CSP.

Keywords: Cutting stock, Optimization, Heuristics

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058717

References:

[1] E. Sweeney, E.R. Paternoster, Cutting and packing problems: A categorized, application-oriented research bibliography, Journal of the Operational Research Society 43 (1992), pp. 691-706.
[2] R. Morabito, M. Arenales, Optimizing the cutting of stock plates in a furniture company, International Journal of Production Research 38 (12) 2000, pp. 2725-2742.
[3] R. Ghodsi, F. Sassani, Real-time optimum sequencing of wood cutting process, International Journal of Production Research 43 (6) 2005, pp. 1127-1141.
[2] C.T. Yang, T.C. Sung, W.C. Weng, An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems, Advances in Engineering Software 37 (2006), pp. 502-513.
[3] H.H. Yanasse, M.S. Limeira, A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Computers & Operations Research 33 (2006), pp. 2744-2756.
[4] A.C. Dikili, A.C. Takinac─▒, N.A. Pek, A new heuristic approach to one-dimensional stock-cutting problems with multiple stock lengths in ship production, Ocean Engineering 156 (2008), pp. 1929-1935.
[5] C. Alves, J.M. Valério de Carvalho, A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem, Computers & Operations Research 35 (2008), pp. 1315-1328.
[6] J. Rietz, S. Dempe, Large gaps in one-dimensional cutting stock problems, Discrete Applied Mathematics 156 (2008), pp. 1929-1935.
[7] H. Dyckhoff, A typlology of cutting and packing problems, European Journal of Operational Research 44 (1990), pp. 145-159.
[8] G. Wäscher, H. Haussner, H. Schumann. An improved typology of cutting and packing problems, European Journal of Operational Research 183(3) (2007), pp. 1109-1130.
[9] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Operations Research 9 (1961), pp. 849-859.
[10] L. Davis, Handbook of genetic algorithms, New York: Van Nostrand Reinhold, 1991.
[11] E. Falkenauer, A hybrid grouping genetic algorithm for bin-packing, Journal of Heuristics 2(1) 1996, pp. 5-30.
[12] K.H. Liang, X. Yao, C. Newton, D. Hoffman, A new evolutionary approach to cutting stock problems with and without contiguity, Computers and Operations Research 29 2002, pp. 1641-1659.
[13] O. Holthaus, Decomposition Approaches for Solving the Integer One-Dimensional Cutting Stock Problem with Different Types of Standard Lengths, European Journal of Operational Research 141 2002, pp. 295-312.
[14] G. Belov, G. Scheithauer, A branch-and-cut-and-price algorithm for onedimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research 171(1) 2006, pp. 85-106.
[15] A.C. Dikili, E. Sarioz, N. AkmanPek, A successive elimination method for one-dimensional stock cutting problems in ship production, Ocean Engineering 34(13) 2007, pp. 1841-1849.
[16] J.M. Valério de Carvalho, LP models for bin packing and cutting stock problems, European Journal of Operational Research 141(2) 2002, pp. 253-273.
[17] Z. Degraeve, M. Peeters, Optimal integer solutions to industrial cutting-stock problems: Part 2. Benchmark results, INFORMS Journal on Computing 15(1) 2003, pp. 58-81.
[18] I. Hajizadeh, C.G. Lee. Alternative configurations for cutting machines in a tube cutting mill, European Journal of Operational Research 183(3) 2007, pp. 1385-1396.
[19] K.C. Poldi, M.N. Arenales, Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths, Computers and Operations Research 36(6) 2009, pp. 2074-2081.
[20] R.E. Johnston, E. Sadinlija, A new model for complete solutions to one-dimensional cutting stock problems, European Journal of Operational Research 153 2004, pp. 176-183.
[21] C.T. Ragsdale, C.W. Zobel, The ordered cutting stock problem, Decision Sciences 35(1) 2004, pp. 83-100.
[22] P. Trkman, M. Gradisar, One-dimensional cutting stock optimization in consecutive time periods, European Journal of Operational Research 179(2) 2007, pp. 291-301.
[23] H.H. Yanasse, M.J. Pinto Lamosa, An integrated cutting stock and sequencing problem, European Journal of Operational Research 183(3) 2007, pp. 1353-1370.
[26] J. Erjavee, M. Gradisar, P. Trkman, Renovation of the cutting stock process, International Journal of Production Research 47 2009, pp. 3979-3996.