El Problema de patrones de corte, clasificación y enfoques/Cutting stock problem, classification and approaches
DOI:
https://doi.org/10.15665/rp.v15i1.718Palabras clave:
Planeación del inventario, proceso de cortado, minimización de desperdiciosResumen
Cutting stock problem abarca el tema de cortar grandes rollos de algún material (papel, textil, acero, madera, etc) en pequeñas tiras de diferentes anchos, que se utilizan como materia prima para la fabricación de un producto final. En este trabajo se presenta inicialmente una introducción de lo que significa en complejidad la solución de un problema de este tipo en una empresa. Luego se enuncian sus antecedentes mediante los trabajos más importantes encontrados en la literatura, destacando algunos trabajos Colombianos. Posteriormente, recordamos la clasificación propuesta por Dyckhoff en 1990 y se aportan sugerencias de otros aspectos a tener en cuenta cuando se aborda el Cutting stock problema. Finalmente se enmarcan los cuatro enfoques de solución más comunes dando ideas para investigaciones futuras.
Citas
H. Dyckhoff, “A typology of cutting and packing problems,” European Journal of Operational Research, 44, 145-159, 1990.
F. Clautiaux, C. Alves, J.V. de Carvalho, and J. Rietz, “New stabilization procedures for the cutting stock problem,” INFORMS Journal on Computing, 23, 530-545, 2010.
C. P. Gracia, “Métodos y Algoritmos para resolver problemas de Corte unidimensional en entornos realistas,” Aplicación a una empresa del Sector Siderúrgico. Departamento de Organización de Empresas. Universitat Politécnica Valéncia, Valencia, España, 2010.
J.A. Abbasi, and M.H. Sahir, “Development of Optimal Cutting Plan using Linear Programming Tools and MATLAB Algorithm,” International Journal of Innovation, Management and Technology, 1(5), 483-492, 2010.
R. Haessler, and P. Sweeney, “Cutting stock problems and solution procedures,” European Journal of Operational Research, 54, 141-150, 1991.
P. Gilmore, and R. Gomory, “A linear programming approach to the Cutting Stock Problem-Part II,” Operations Research, 11(6), 863-888, 1963.
A.C. Dikili, E. Sarıoz, and N. Akman , “A successive elimination method for one-dimensional stock cutting problems in ship production,” Ocean Engineering, 34, 1841–1849, 2007.
R. Varela, C. Vela, J. Puente, M. Sierra, and G-R. Inés, “An effective solution for a real cutting stock problem in manufacturing plastic rolls,” Ann Oper Res, 166, 125–146, 2009.
K. Poldi, and M. Nereu, “Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths,” Computers & Operations Research, 36, 2074-2081, 2009.
S. Suliman, “A sequential heuristic procedure for the two-dimensional cutting-stock problem,” Int. J. Production Economics, 99, 177–185, 2006.
A. Farley, “The cutting stock problem in the canvas industry,” European Journal of Operational Research, 44, 247-255, 1990.
J. Beasley, “Algorithms for unconstrained two-dimensional guillotine cutting,” Journal of the Operational Research Society, 36, 297-306, 1985.
S. Hahn, “ On the optimal cutting of defective sheets,” Operations Research, 16, 1100-1114, 1968.
P. Wang, “Two algorithms for constrained two dimensional cutting stock problems,” Operations Research, 31, 573-586, 1983.
C.-T. Yang, T.-C. Sung, and W.-C. Weng, “An improved tabu search approach with mixed objective function for one-dimensional cutting stock problems”. Advances in Engineering Software, 37, 502–
, 2006.
R. Baldacci, and M. A. Boschetti, “A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem,” European Journal of Operational Research, 183, 1136–1149, 2007.
A. Mobasher, and A. Ekici, “Solution approaches for the cutting stock problem with setup cost,” Computers & Operations Research, 2012.
J. Jaramillo, F. Correa, and R. Jaramillo, “Desarrollo de un Método Basado en Algoritmos Genéticos y Programación Lineal Para la Solución de un Problema de Corte Unidimensional,” Cuarto Congreso Colombiano de Computación 4CCC. Sociedad Colombiana de Computación, 2009.
E. Toro, A. Rueda, and M. Granada, “Algoritmo de búsqueda tabú aplicado a la solución del problema de corte bidimensional guillotinado,” Universidad Tecnológica de Pereira, 37, 43-48, 2007.
E. Toro, A. Rueda, and H. Ruiz, “Efecto de la configuración inicial en la solución del problema de corte bidimensional usando el algoritmo de búsqueda tabú,” Revista Colombiana de Tecnologías de Avanzada, 1(11), 107-113, 2008.
D. Alvarez, “Solución del problema de empaquetamiento óptimo bidimensional en un sola placa, en placas y rollos infinitos con y sin rotación de piezas usando técnicas metaheurísticas de optimización”. Universidad Tecnológica de Pereira, Pereira, Colombia, 2010.
G. Wäscher, H. Haußner, and H. Schumann, “An improved typology of cutting and packing problems,” European Journal of Operational Research, 183, 1109–1130, 2007.
H. Hideki, and M.J. Pinto, “An integrated cutting stock and sequencing problem,” European Journal of Operational Research (183), 1353–1370, 2007.
J. Karelahti, “Solving the cutting stock problem in the steel industry”. Department of Engineering Physics and Mathematics. Helsinki University of Technology, 2-5, 2002.
R. Haessler, “A note on computational modifications to the Gilmore-Gomory”. Operations Research, 28, 1001-1005, 1980.
N. Christofides, and E. Hadjiconstantinou, “An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts”. European Journal of Operational Research, 83, 21-38, 1995.
J. Valério de Carvalho, and A. Guimaraes Rodrigues, “An LP-based approach to a two-stage cutting stock problem,” European Journal of Operational Research, 84, 580-589, 1995.
S. Benati, “An Algorithm for a Cutting Stock Problem on a Strip,” The Journal of the Operational Research Society, 48(3), 288-294, 1997.
S. Suliman, “Pattern generating procedure for the cutting stock problem,” Int. J. Production Economics, 74, 293-301, 2001.
O. Holthaus, “Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths,” European Journal of Operational Research, 141, 295-312, 2002.
E. Zak, “Modeling multistage cutting stock problems”. European Journal of Operational Research, 141, 313–327, 2002.
H. Mhand, “Exact algorithms for unconstrained three-dimensional cutting problems: a comparative study,” Computers & Operations Research, 31, 657-674, 2004.
J.-F. Tsai, P.-L. Hsieh, and Y.-H. Huang, “An optimization algorithm for cutting stock problems in the TFT-LCD industry,” Computers & Industrial Engineering, 57, 913-919, 2009.
A. Cherri, and N.M. Arenales, and H.H Yanasse, “The one-dimensional cutting stock problem with usable leftover– A heuristic approach”. European Journal of Operational Research, 196, 897-908, 2009.
N. Kasimbeyli, T. Sarac, and R. Kasimbeyli, “A two-objective mathematical model without cutting patterns for one-dimensional assortment problems”. Journal of Computational and Applied Mathematics. 235, 4663–4674, 2010.
R. Macedo, C. Alves, and J. Valério de Carvalho, “Arc-flow model for the two-dimensional guillotine cutting stock problem,” Computers & Operations Research, 37, 991-1001, 2010.
S. Wongprakornkul, and P. Charnsethikul, “Solving One-Dimensional Cutting Stock Problem with Discrete Demands and Capacitated Planning Objective,” Journal of Mathematics and Statistics, 6, 79-83, 2010.
M.E. Berberler, U. Nuriyev, and A. Yıldırım, “A software for the one-dimensional cutting stock problem,” Journal of King Saud University (Science), 23,69–76, 2011.
F. Furini, E. Malaguti, R. M. Durán, A. Persiani, and P. Toth P, “A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size,” European Journal of Operational Research. 218 251–260, 2012.
Y. Cui, and Z. Zhao, “Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns,” European Journal of Operational Research, 231, 288–298, 2013.
H.-C. Lu, Y.-H. Huang, K.-A. Tseng, “An integrated algorithm for cutting stock problems in the thin-film transistor liquid crystal display industry,” Computers & Industrial Engineering, 64 1084–1092, 2013.
Y. Cui, and Y.-P. Cui. “Heuristic for the two-dimensional arbitrary stock-size cutting stock problem,” Computers & Industrial Engineering, 78 195–204, 2014.
R. Maged, O. Ashraf , M. Sayed M. “3D overlapped grouping Ga for optimum 2D guillotine cutting stock problem,” Alexandria Engineering Journal. 53, 491–503, 2014.
Cui, Y.-P., Tang, T.-B. Parallelized sequential value correction procedure for the one-dimensional cutting stock problem with multiple stock lengths. Engineering Optimization, 46 (10), pp. 1352-1368, 2014.
Brandão, F., Pedroso, J.P. Fast pattern-based algorithms for cutting stock. Computers and Operations Research, 48, pp. 69-80, 2014.
Arbib, C.a , Marinelli, F.b , Ventura, P.c. One-dimensional cutting stock with a limited number of open stacks: Bounds and solutions from a new integer linear programming model. International Transactions in Operational Research, 23 (1-2), pp. 47-63, 2016.
Cui, Y., Cui, Y.-P., Zhao, Z. Pattern-set generation algorithm for the one-dimensional multiple stock sizes cutting stock problem. Engineering Optimization, 47 (9), pp. 1289-1301, 2015.
Arenales, M.N.a , Cherri, A.C.b , Do Nascimento, D.N.c , Vianna, A.c. A new mathematical model for the cutting stock/leftover problem. Pesquisa Operacional, 35 (3), pp. 509-522, 2015.
Kallrath, J.a b , Rebennack, S.c , Kallrath, J.d , Kusche, R.a. Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges. European Journal of Operational Research, 238 (1), pp. 374-389, 2014.
Cui, Y., Cui, Y.-P., Yang, L. Heuristic for the two-dimensional arbitrary stock-size cutting stock problem. Computers and Industrial Engineering, 78, pp. 195-204, 2014.
Song, X.a , Bennell, J.A.b. Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem. Journal of the Operational Research Society, 65 (7), pp. 1037-1052, 2014.
MirHassani, S.A., Jalaeian Bashirzadeh, A. A GRASP meta-heuristic for two-dimensional irregular cutting stock problem. International Journal of Advanced Manufacturing Technology, 81 (1-4), pp. 455-464, 2105.
Wenshu, L., Dan, M., Jinzhuo, W. Study on cutting stock optimization for decayed wood board based on genetic algorithm. Open Automation and Control Systems Journal, 7 (1), pp. 284-289, 2015.
Wenshu, L., Dan, M., Jinzhuo, W. Study on cutting stock optimization for decayed wood board based on genetic algorithm. Open Automation and Control Systems Journal, 7 (1), pp. 284-289, 2015.
Wenshu, L., Dan, M., Jinzhuo, W. Study on cutting stock optimization for decayed wood board based on genetic algorithm. Open Automation and Control Systems Journal, 7 (1), pp. 284-289, 2015.
De Araujo, S.A.a , Poldi, K.C.b , Smith, J.c. A genetic algorithm for the one-dimensional cutting stock problem with setups. Pesquisa Operacional, 34 (2), pp. 165-187, 2014.
Lu, H.-C.a , Huang, Y.-H.b. An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry. European Journal of Operational Research, 246 (1), pp. 51-65, 2015.
Cheng, C.a , Bao, L.b , Bao, C.a. Hybrid artificial fish algorithm for two-dimensional non-guillotine cutting stock problem. Liaoning Gongcheng Jishu Daxue Xuebao (Ziran Kexue Ban)/Journal of Liaoning Technical University (Natural Science Edition), 33 (7), pp. 965-969, 2014.
Ben Lagha, G.a , Dahmani, N.b , Krichen, S.a. Particle swarm optimization approach for resolving the cutting stock problem. 2014 International Conference on Advanced Logistics and Transport, 2014.
Andrade, R.a , Birgin, E.G.a , Morabito, R.b. Two-stage two-dimensional guillotine cutting stock problems with usable leftover. International Transactions in Operational Research, 23 (1-2), pp. 121-145, 2016.
Dusberger, F., Raidl, G.R. A scalable approach for the k-staged two-dimensional cutting stock problem with variable sheet size. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9520, pp. 384-392, 2015.
Dusberger, F., Raidl, G.R. A scalable approach for the k-staged two-dimensional cutting stock problem with variable sheet size. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9520, pp. 384-392, 2015.
Jin, M., Ge, P., Ren, P. A new heuristic algorithm for two-dimensional defective stock guillotine cutting stock problem with multiple stock sizes. Tehnicki Vjesnik, 22 (5), pp. 1107-1116, 2015.
Lu, Q., Zhou, X. GPU parallel ant colony algorithm for the dynamic one-dimensional cutting stock problem based on the on-line detection. Yi Qi Yi Biao Xue Bao/Chinese Journal of Scientific Instrument, 36 (8), pp. 1774-1782, 2015.
Dusberger, F., Raidl, G.R. A variable neighborhood search using very large neighborhood structures for the 3-staged 2-dimensional cutting stock problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8457 LNCS, pp. 85-99, 2014.
Cui, Y., Zhong, C., Yao, Y. Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost. European Journal of Operational Research, 243 (2), pp. 540-546, 2015.
Savsani, V., Savsani, P., Arya, P. Effect of applying advanced optimization techniques for the one-dimensional cutting stock problem. ASME International Mechanical Engineering Congress and Exposition, Proceedings, 2014.
Díaz, D., Valledor, P., Areces, P., Rodil, J., Suárez, M. An ACO Algorithm to Solve an Extended Cutting Stock Problem for Scrap Minimization in a Bar Mill. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8667, pp. 13-24, 2014.
Wang, F.-K., Liu, F.-T. Flexible stock allocation and trim loss control for cutting problem in the industrial-use paper production. Mathematical Problems in Engineering, 2014.
Awais, A.a , Naveed, A.b. Width-Packing Heuristic for Grouping in Two-Dimensional Irregular Shapes Cutting Stock Problem. Arabian Journal for Science and Engineering, 40 (3), pp. 799-816, 2015.
Poldi, K.C.a , de Araujo, S.A.b. Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem. Annals of Operations Research, 238 (1-2), pp. 497-520, 2016.
Descargas
Publicado
Número
Sección
Licencia
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
- Los autores/as ceden los derechos de autor y dan a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative Commons, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado (vea The Effect of Open Access).
Instrucciones para el llenado de la Certificación de Originalidad y la Cesión de Derechos de Autor.
- Haga click aquí y baje el formulario de Certificación de Originalidad y la Cesión de Derechos de Autor.
- En cada uno de los campos para rellenar haga click y complete lo correspondiente.
- Una vez llenos los campos, copie al final su firma escaneada o firma digital. Favor ajustar el tamaño de la firma en el formulario.
- Finalmente, lo puede guardar como pdf y enviarlo a través de la palataforma OJS, como archivo complementario.
Si tiene dudas contáctenos, por favor.
