Implementation of On-Line Cutting Stock Problem on NC Machines

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.

• Jui P. Hung
• Hsia C. Chang
• Yuan L. Lai

• Cutting stock
• Optimization
• Heuristics

[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.