Contributing to solving a one-dimensional cutting stock problema with two objectives based on the generation of cutting patterns

Boualem Slimi; Moncef Abbas

doi:10.24310/recta.23.1.2022.19865

Authors

Boualem Slimi Bilda University Algeria
Moncef Abbas Université des Sciences et Technologies Houari Boumadian Algeria

DOI:

https://doi.org/10.24310/recta.23.1.2022.19865

Keywords:

Trim loss, setups, feasible cutting pattern, feasible cutting plan, cutting stock problem with two-objectives.

Abstract

En las versiones clásicas del problema del material de corte, el objetivo es encontrar una solución para cortar un objeto principal en varias partes comúnmente llamadas piezas, para minimizar la pérdida total de recorte de la materia prima. Numerosos estudios han abordado este tipo de problema. Sin embargo, en las aplicaciones del mundo real, generalmente existen restricciones que hacen que la forma del problema sea diferente de la versión clásica y que sea más difícil de resolver. En este artículo se propone una técnica para resolver el problema del stock de corte unidimensional con dos objetivos, donde se busca minimizar al mismo tiempo la pérdida total de recorte de la materia prima y el número de setups a realizar. Esta técnica está constituida por dos etapas cuya primera consiste en generar todos los patrones de corte factibles y la segunda permite construir planos de corte, satisfaciendo las demandas, gracias a un subconjunto de estos patrones. Estos diferentes planes de corte representan todas las soluciones factibles, cada una de las cuales se caracteriza por un número de configuraciones y cantidad total de caídas.

Downloads

Download data is not yet available.

Publication Facts

This article

Author statements

Data availability

N/A

16%

External funding

N/A

32%

Competing interests

N/A

11%

This journal

Other journals

Articles accepted

4%

33%

Days to publication

691

145

Indexed in

—

Editor & editorial board: profiles
Academic society: N/A
Publisher: UMA Editorial. Universidad de Málaga

References

Aliano Filho, A., Moretti, A. C., Pato, M. V. & Oliveira, W. A. (2017). A comparative study of exact methods for the biobjective integer one-dimensional cutting stock problem, Journal of the Operational Research, 69(1), 91-107.

https://doi.org/10.1057/s41274-017-0214-7

Arbel, A. (1993). Large-scale optimization methods applied to the cutting stock problem of irregular shapes. The International Journal of Production Research, 31(2), 483-500.

https://doi.org/10.1080/00207549308956738

Araujo, S., Poldi, K. C. & Smith. J. (2014). A genetic algorithm for the one-dimensional cutting stock problem with Setups. Pesquisa Operacional, 34(2): 165-187.

https://doi.org/10.1590/0101-7438.2014.034.02.0165

Campello, S. C., Ghidini, C. T., Ayres, A. O. C. & Oliveira. W. A. (2020). A multi- objective integrated model for lot sizing and cutting stock problems, Journal of the Operational Research Society, 71: 9, 1466-1478.

https://doi.org/10.1080/01605682.2019.1619892

Cui, Y. & Yang, Y. (2010). A heuristic for the one-dimensional cutting stock problem with usable leftover. European Journal of Operational Research, 204(2), 245-250.

https://doi.org/10.1016/j.ejor.2009.10.028

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

https://doi.org/10.1016/j.ejor.2014.12.015

Diegel, A., Montocchio, E., Walters, E., Schalkwyk, S. & Naidoo. S. (1996). Setup minimizing condition in the trim loss problem. European Journal of Operational Research, 95, 631-640.23, 483-493.

https://doi.org/10.1016/0377-2217(95)00303-7

Delorme, M., Iori, M. & Martello, S., (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255 (1), 1-20.

https://doi.org/10.1016/j.ejor.2016.04.030

Ehrgott, M. & Gandibleux, X. (2000). A survey and annotated bibliography of multi-objective combinatorial optimization. Operational Research Spektrum, 22, 425-460.

https://doi.org/10.1007/s002910000046

Farley, A. A. (1988). Mathematical programming models for cutting-stock problems in the clothing industry. Journal of the Operational Research Society, 39(1), 41-53.

https://doi.org/10.1057/jors.1988.6

Filho, A. A., Moretti, A. C. & Pato, M. V. (2018). A comparative study of exact methods for the biobjective integer one-dimensional cutting stock problem. Journal of the Operational Research Society, 69(1), 91-107.

https://doi.org/10.1057/s41274-017-0214-7

Gilmore, P. C. & Gomory, R. E. (1961). A Linear programming approach to the cutting stock problem. Operations Research, 9, 849-859.

https://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.

https://doi.org/10.1287/opre.11.6.863

Gilmore, P. C. & Gomory, R .E. (1965). Multistage cutting stock problems of two and more dimensions. Operations Research., 13 (1), 94-120.

https://doi.org/10.1287/opre.13.1.94

Golfeto, R., Moretti, A. C. & Salles-Neto. L. L. (2009b). A genetic symbiotic algorithm applied to the cutting- stock problem with multiple objectives. Advanced, Modeling and Optimization, 11, 473-501.

Haessler, R. W. (1975). Controlling cutting pattern changes in one-dimensional trim Problems, Operations Research. 23, 483-493.

https://doi.org/10.1287/opre.23.3.483

Haessler, R. W. (1980). A Note on computational modifications to the Gilmore -Gomory cutting stock problem. Operations Research, 28, 1001-1005.

https://doi.org/10.1287/opre.28.4.1001

Kolen, A. W. J. & Spieksma, F. C. R. (2000). Solving a bi-criterion cutting stock problem with openended demand: a case study. Journal of The Operational Research Society, 51, 1238-1247.

https://doi.org/10.1057/palgrave.jors.2601023

Lee, J. (2007). In situ column generation for a cutting-stock problem. Computers & Operations Research, 34, Issue 8, 2345-2358.

https://doi.org/10.1016/j.cor.2005.09.007

Martinovic, J., Scheithauer, G. & Valério de Carvalho, J. M. (2018). A comparative study of the arc flow model and the one-cut model for one-dimensional cutting stock problems, European Journal of Operational Research, 266 (2), 458-471.

https://doi.org/10.1016/j.ejor.2017.10.008

Pazand, K. & Mohammadi. A. (2009). Extended haessler heuristic algorithm for cutting stock problem: a case study in film Industry. Australian Journal of Basic and Applied Sciences, 3(4): 3944-3953, ISSN 1991-8178.

Salles-Neto, L. L., Rufiàn-Lizana, A. M., Arana-Jimenez & Ruiz-Garzon. G. (2010). Weak efficiency in Cutting-stock problem, Congresso nacional de matemática aplicada e computational, 33. v. 3, p. 652-658. ISSN 1984-820X.

Suliman, S. M. (2001). Pattern generating procedure for the cutting stock problem. International Journal of Production Economics, 74(1-3), 293-301.

https://doi.org/10.1016/S0925-5273(01)00134-7

Tanir, D., Ugurlu, O., Guler, A. & Nuriyev, U. (2019). One-dimensional cutting stock problem with divisible items: a case study in steel industry, TWMS Journal of Applied and Engineering Mathematics, V.9, N.3, 2019. 473- 484.

Umetani, S., Yagiura, M. & Ibaraki, T. (2003). An LP-based local search to the one-dimensional cutting stock problem using a given number of cutting patterns. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86- A, 1093-1102.

Wäscher, G. & Henn, S. (2013). Extensions of cutting problems, setups. Pesquisa Operational, Vol 33 (2). 133-162.

https://doi.org/10.1590/S0101-74382013000200001