ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY

NURIYEV, U.; TANIR, D.; GULER, A.; UGURLU, O.

ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY

D. TANIR, (Yönetim ve Bilgi Sistemleri Bölümü, İktisadi ve İdari Bilimler Fakültesi Bilimler, Kafkas Üniversitesi, Kars, Türkiye.)

O. UGURLU, (Matematik Bölümü, Fen Fakültesi, Ege Üniversitesi, İzmir, Türkiye)

A. GULER, (Bilgisayar Teknolojileri Bölümü, Meslek Yüksekokulu, Yaşar Üniversitesi, İzmir, Türkiye)

U. NURIYEV (Matematik Bölümü, Fen Fakültesi, Ege Üniversitesi, İzmir, Türkiye)

TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics

6 0

Yıl: 2019 Cilt: 9 Sayı: 3 Sayfa Aralığı: 473 - 484 Metin Dili: İngilizce İndeks Tarihi: 26-10-2021

ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY

Öz:

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.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

[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 method,Pesquisa 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)

APA	TANIR D, UGURLU O, GULER A, NURIYEV U (2019). ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. , 473 - 484.
Chicago	TANIR D.,UGURLU O.,GULER A.,NURIYEV U. ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. (2019): 473 - 484.
MLA	TANIR D.,UGURLU O.,GULER A.,NURIYEV U. ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. , 2019, ss.473 - 484.
AMA	TANIR D,UGURLU O,GULER A,NURIYEV U ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. . 2019; 473 - 484.
Vancouver	TANIR D,UGURLU O,GULER A,NURIYEV U ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. . 2019; 473 - 484.
IEEE	TANIR D,UGURLU O,GULER A,NURIYEV U "ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY." , ss.473 - 484, 2019.
ISNAD	TANIR, D. vd. "ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY". (2019), 473-484.

APA	TANIR D, UGURLU O, GULER A, NURIYEV U (2019). ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics, 9(3), 473 - 484.
Chicago	TANIR D.,UGURLU O.,GULER A.,NURIYEV U. ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics 9, no.3 (2019): 473 - 484.
MLA	TANIR D.,UGURLU O.,GULER A.,NURIYEV U. ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics, vol.9, no.3, 2019, ss.473 - 484.
AMA	TANIR D,UGURLU O,GULER A,NURIYEV U ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics. 2019; 9(3): 473 - 484.
Vancouver	TANIR D,UGURLU O,GULER A,NURIYEV U ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY. TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics. 2019; 9(3): 473 - 484.
IEEE	TANIR D,UGURLU O,GULER A,NURIYEV U "ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY." TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics, 9, ss.473 - 484, 2019.
ISNAD	TANIR, D. vd. "ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH DIVISIBLE ITEMS: A CASE STUDY IN STEEL INDUSTRY". TWMS (Turkic World Mathematical Society) Journal of Applied and Engineering Mathematics 9/3 (2019), 473-484.