Production
https://prod.org.br/doi/10.1590/0103-6513.20170105
Production
Research Article

Modification of Haessler’s sequential heuristic procedure for the one-dimensional cutting stock problem with setup cost

Mateus Martin; Antonio Moretti; Marcia Gomes-Ruggiero; Luiz Salles Neto

Downloads: 0
Views: 807

Abstract

Abstract: Paper aims: We propose a modified Sequential Heuristic Procedure (MSHP) to reduce the cutting waste and number of setups for the One-Dimensional Cutting Stock Problem with Setup Cost.

Originality: This heuristic modifies Haessler’s sequential heuristic procedure (1975) by adapting the Integer Bounded Knapsack Problem to generate cutting patterns, instead of the original lexicographic search employed. The solution strategy is to generate different cutting plans using MSHP, and then to use an integer programming model to seek even better results.

Research method: It is a axiomatic research, ordinary in studies of Operational Research.

Main findings: In the computational experiments, we demonstrate the effectiveness of the algorithm with two sets of benchmark instances by comparing it with other approaches, and obtaining better solutions for some scenarios.

Implications for theory and practice: The approach is suitable for practitioners from different industrial settings due to its easily coding and possible adaptation for problem extensions.

Keywords

Cutting stock, Problem, Setup costs, Heuristics

References

Araujo, S., Poldi, K., & Smith, J. (2014). A genetic algorithm for the one-dimensional cutting stock problem with setups. Pesquisa Operacional, 34(2), 165-187. http://dx.doi.org/10.1590/0101-7438.2014.034.02.0165.

Aliano Filho, A., Moretti, A. & Pato, M. (2017). A comparative study of exact methods for the bi-objective integer one-dimensional cutting stock problem. The Journal of the Operational Research Society, 69, 1-18. http://dx.doi.org/10.1057/s41274-017-0214-7.

Belov, G., & Scheithauer, G. (2007). Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting. INFORMS Journal on Computing, 19(1), 27-35. http://dx.doi.org/10.1287/ijoc.1050.0132.

Cherri, A. C., Arenales, M. N., Yanasse, H. H., Poldi, K. C., & Gonçalves Vianna, A. C. (2014). The one-dimensional cutting stock problem with usable leftovers - A survey. European Journal of Operational Research, 236(2), 395-402. http://dx.doi.org/10.1016/j.ejor.2013.11.026.

Cui, Y., Zhao, X., Yang, Y., & Yu, P. (2008). A heuristic for the one-dimensional cutting stock problem with pattern reduction. Proceedings of the Institution of Mechanical Engineers. Part B, Journal of Engineering Manufacture, 222(6), 677-685. http://dx.doi.org/10.1243/09544054JEM966.

Cui, Y., Zhong, C., & Yao, Y. (2015). Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost. European Journal of Operational Research , 243(2), 540-546. http://dx.doi.org/10.1016/j.ejor.2014.12.015.

Diegel, A., Miller, G., Montocchio, E., van Schalkwyk, S., & Diegel, O. (2006). Enforcing minimum run length in the cutting stock problem. European Journal of Operational Research, 171(2), 708-721. http://dx.doi.org/10.1016/j.ejor.2004.09.039.

Cemil Dikili, A., Sarıöz, E., & Akman Pek, N. (2007). A successive elimination method for one-dimensional stock cutting problems in ship production. Ocean Engineering , 34(13), 1841-1849. http://dx.doi.org/10.1016/j.oceaneng.2006.11.008.

Eilon, S. (1960). Optimizing the shearing of steel bars. Journal of Mechanical Engineering Science, 2(2), 129-142. http://dx.doi.org/10.1243/JMES_JOUR_1960_002_022_02.

Foerster, H., & Wäscher, G. (2000). Pattern reduction in one-dimensional cutting stock problems. International Journal of Production Research, 38(7), 1657-1676. http://dx.doi.org/10.1080/002075400188780.

Gau, T., & Wäscher, G. (1995). CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European Journal of Operational Research, 84(3), 572-579. http://dx.doi.org/10.1016/0377-2217(95)00023-J.

Gilmore, P. C., & Gomory, R. E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 9(6), 849-859. http://dx.doi.org/10.1287/opre.9.6.849.

Gilmore, P. C., & Gomory, R. E. (1963). A Linear Programming Approach to the Cutting Stock Problem - Part II. Operations Research, 11(6), 863-888. http://dx.doi.org/10.1287/opre.11.6.863.

Haessler, R. W. (1975). Controlling Cutting Pattern Changes in One-Dimensional Trim Problems. Operations Research, 23(3), 483-493. http://dx.doi.org/10.1287/opre.23.3.483.

Henn, S., & Wäscher, G. (2013). Extensions of cutting problems: setups. Pesquisa Operacional, 33(2), 133-162. http://dx.doi.org/10.1590/S0101-74382013000200001.

Kantorovich, L. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4), 366-422. http://dx.doi.org/10.1287/mnsc.6.4.366.

Kolen, A., & Spieksma, F. (2000). Solving a bi-criterion cutting stock problem with open-ended demand: a case study. The Journal of the Operational Research Society , 51(11), 1238-1247. http://dx.doi.org/10.1057/palgrave.jors.2601023.

Metzger, R. W. (1958). Stock slitting. In R. W. Metzger. Elementary mathematical programming. New York: Wiley.

Mobasher, A., & Ekici, A. (2013). Solution approaches for the cutting stock problem with setup cost. Computers & Operations Research, 40(1), 225-235. http://dx.doi.org/10.1016/j.cor.2012.06.007.

Umetani, S., Yagiura, M., & Ibaraki, T. (2003). One-dimensional cutting stock problem to minimize the number of different patterns. European Journal of Operational Research , 146(2), 388-402. http://dx.doi.org/10.1016/S0377-2217(02)00239-4.

Umetani, S. (2018). Benchmark instances for the one-dimensional cutting stock problem. Osaka: Osaka University. Retrieved in 05 November 2017, from https://sites.google.com/site/shunjiumetani/benchmark.

Vahrenkamp, R. (1996). Random search in the one-dimensional cutting stock problem. European Journal of Operational Research, 95(1), 191-200. http://dx.doi.org/10.1016/0377-2217(95)00198-0.

Yanasse, H. (1997). On a pattern sequencing problem to minimize the maximum number of open stacks. European Journal of Operational Research, 100(3), 454-463. http://dx.doi.org/10.1016/S0377-2217(97)84107-0.

Yanasse, H. H., & Limeira, M. S. (2006). A hybrid heuristic to reduce the number of different patterns in cutting stock problems. Computers & Operations Research , 33(9), 2744-2756. http://dx.doi.org/10.1016/j.cor.2005.02.026.
 

5bc4e64c0e8825e4048efc3c production Articles
Links & Downloads

Production

Share this page
Page Sections