ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY
Loading...
Date
2019
Authors
D. TANIR
O. UGURLU
A. GULER
U. NURIYEV
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
Abstract
Abstract. This paper considers the one-dimensional cutting stock problem (1D-CSP)with divisible items which arises in the steel industries. While planning the steel cuttingoperations each item can be divided into smaller pieces then they can be recombinedby welding. The objective is to minimize both the trim loss and the number of thewelds. The problem can be seen as a natural generalization of the cutting stock problem(CSP) with skiving option [1] where recombining operation has a cost. In this paper amathematical model for the problem is given and a dynamic programming based heuristicalgorithm is proposed in accordance with the company needs. Furthermore a software which is based on the proposed heuristic algorithm is developed to use in MKA Company and its performance is analyzed by solving real-life problems in the steel industry. Thecomputational experiments show the efficiency of the proposed algorithm.
Description
Keywords
Matematik
Fields of Science
Citation
[1] Johnson M. P. Rennick C. and Zak E. (1997) A new model for complete solutions to onedimensional stock problems Siam Review 39(3) pp. 472-483.[2] Kellerer H. Pferschy U. and Pisinger D. (2004) Knapsack Problems Springer-Verlag Berlin Heidelberg.3] Garey M. R. and Johnson D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness Freemann New York.[4] Zak E. J. (2003) The Skiving Stock Problem as a Counterpart of the Cutting Stock Problem Int. Trans. in Op. Rs. 10: 637-650.[5] Jahromi M. H. Tavakkoli-Moghaddam R. Makui A. and Shamsi A. (2012) Solving a onedimensional cutting stock problem by simulated annealing and tabu search Journal of Industrial Engineering International 8(1): 1-8.[6] Kantorovich L. V. (1960) Mathematical methods of organizing and planning production Management Sci. 6(4): 366-422.[7] Gilmore P. C. and Gomory R.E. (1961) A linear programming approach to the cutting-stock problem European Journal of Operational Research 9(6) pp. 849-859.[8] Dyckhoff H. (1990) A typology of cutting and packing problems European Journal of Operational Research 44(2) pp. 145-159.[9] Waescher G. and Gau T. (1996) Heuristics for the Integer one-dimensional Cutting Stock Problem - A Computational Study OR Spektrum 18(3) pp. 131-144.[10] Gradisar M. Kljaji M. Resinovi G. and Jesenko J. (1999a) A sequential heuristic procedure for one-dimensional cutting European Journal of Operational Research 114(3) pp. 557-568.[11] Gradisar M. Resinovic G. and Kljajic M. (1999b) A hybrid approach for optimization of onedimensional cutting European Journal of Operational Research 119(3) pp. 719-728.[12] Vance P. Barnhart C. Johnson E.L. and Nemhauser G.L. (1994) Solving binary cutting stock problems by column generation and branch-and-bound Computational Optimization and Applications 3(2) pp. 111-130.[13] Vance P. (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem Computational Optimization and Applications 9(3) pp. 211-228.[14] Valerio de Carvalho J.M. (1999) Exact solution of bin-packing problems using column generation and branch-and-bound Annals of Operation Research 86 pp. 629-659.[15] Vanderbeck F. (1999) Computational study of a column generation algorithm for bin-packing and cutting stock problems Mathematical Programming 86(3) pp. 565-594.[16] Vanderbeck F. (2000) On DantzigWolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm Operations Research 48(1) pp. 111-128.[17] Scheithauer G. Terno J. Muller A. and Belov G. (2001) Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm Journal of the Operational Research Society 52(12) pp. 1390-1401.[18] Mukhacheva E. A. Belov G. Kartak V. and Mukhacheva A. S. (2001) One-dimensional cutting stock problem: Numerical experiments with the sequential value correction method and a modified branch-and-bound methodPesquisa Operacional 2000(2) pp. 153-168.[19] Belov G. and Scheithauer G. (2002) A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths European Journal of Operational Research 141(2) pp. 274-294.[20] Umetani S. Yagiura M. and Ibaraki T. (2003) One-dimensional cutting stock problem to minimize the number of different patterns European Journal of Operational Research 146(2) 388-402.[21] Johnston R.E. and Sadinlija E. (2004) A new model for complete solutions to one-dimensional stock problems European Journal of Operational Research 153(1) pp. 176-183.[22] Belov G. and Scheithauer G. (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting European Journal of Operational Research 171(1) pp. 85-106.[23] Dikili A. C. Sarz E. and Pek N. A. (2007) A successive elimination method for one-dimensional stock cutting problems in ship production Ocean engineering 34(13) pp. 1841-1849.[24] Reinertsen H. and Vossen T. W. (2010) The one-dimensional cutting stock problem with due dates European Journal of Operational Research 201(3) pp. 701-711.[25] Cherri A. C. M. N. Arenales and Yanasse H.H. (2009) The one-dimensional cutting stock problems with usable leftover: a heuristic approach European Journal of Operational Research 196 (3) pp. 85-106.[26] Cherri A. C. Arenales M. N. and Yanasse H. H. (2013) The usable leftover one-dimensional cutting stock problem-a priority-in-use heuristic Intl. Trans. in Op. Res. 20(2) pp. 198-199.[27] Berberler M. E. and Nuriyev U. (2010) A New Heuristic Algorithm for the One-Dimensional Cutting Stock Problem Appl. Comp. Math 9 (1) pp. 19-30[28] Mobasher A. and Ekici A. (2013) Solution approaches for the cutting stock problem with setup cost Computers and Operations Research 40(1) 225-235.[29] Johnson M. P. Rennick C. and Zak E. (1997) A new model for complete solutions to one-dimensional stock problems Siam Review 39(3) pp. 472-483.[30] Arbib C. Marinelli F. Rossi F. and Di Iorio F. (2002) Cutting And Reuse: An Application from Automobile Component Manufacturing Operations Research 50 (6) 923-934.[31] Arbib C. and Marinelli F. (2005) Integrating Process Optimization and Inventory Planning in Cutting-Stock with Skiving Option: An Optimization Model and its Application European Journal of Operational Research 163 (3) pp. 617-630.[32] MKA Company Accessed January 6 2017. https://www.mkasteel.com[33] Liang K. H. Yao X. Newton Y. and Hoffman D. (2002) A new evolutionary approach to cutting stock problems with and without contiguity Comput. Oper. Res. 29(12) pp. 164159.[34] Yang C. T. Sung T. C. and Weng W. C. (2006) An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems Advances in Engineering Software 37(8) pp. 502-513.[35] http://www.optimalprograms.com/realcut1d.htm (Real Cut optimization 1D software)[36] http://www.nirvanatec.com/bar nesting software.html (Plus 1D optimization software)
WoS Q
Scopus Q
Source
Volume
Issue
Start Page
End Page
Collections
