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

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 cutting operations, each item can be divided into smaller pieces, then they can be recombined by welding. The objective is to minimize both the trim loss and the number of the welds. 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, a mathematical model for the problem is given and a dynamic programming based heuristic algorithm 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. The computational experiments show the eciency of the proposed algorithm.

Keywords

• Production,Cutting Stock Problems,Skiving option,Heuristics,Steel Industry.

References

1. 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.
2. Kellerer, H., Pferschy, U. and Pisinger, D., (2004), Knapsack Problems, Springer-Verlag, Berlin Hei- delberg.
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 one- dimensional 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, Manage- ment Sci., 6(4): 366-422.
7. Gilmore, P. C., and Gomory R.E., (1961), A linear programming approach to the cutting-stock prob- lem, 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 one- dimensional 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 prob- lems 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, Com- putational 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)