Algoritmo discreto del búfalo africano para resolver el problema de corte de material

• Autores: Irving Barragán Vite, Leonardo Javier Montiel Arrieta, Juan C. Seck Tuoh Mora, Norberto Hernández Romero, Joselito Medina Marín
• Localización: Pädi Boletín Científico de Ciencias Básicas e Ingenierías del ICBI, ISSN-e 2007-6363, Nº. Extra 11, 2023 (Ejemplar dedicado a: Special 5 (December)), págs. 123-132
• Idioma: español
• DOI: 10.29057/icbi.v11iEspecial3.11489
• Títulos paralelos:
  • Discrete African buffalo algorithm to solve the cutting stock problem
• Enlaces
  • Texto completo (pdf)
• Resumen
  • español

    El problema de corte abordado en este documento consiste en minimizar el desperdicio total producido al cortar un conjunto de piezas pequeñas en una secuencia determinada a partir de piezas de material más grandes. El algoritmo del búfalo Africano ha sido empleado exitosamente para resolver problemas de tipo combinatorio. Una de las dificultades de este algoritmo es generar soluciones discretas para esta clase de problemas discretos. En este trabajo se emplea una variante discreta del algoritmo del búfalo Africano en la que se compara una técnica de cruza así como la técnica del valor del orden clasificado para obtener soluciones discretas. Se usa un conjunto de diez instancias de diferente complejidad para realizar la comparación de estas técnicas. Los resultados muestran que la técnica de cruza supera a las otras en cuanto a la calidad de las soluciones. Luego estos resultados se comparan contra otros algoritmos para evaluar su desempeño.

  • English

    The cutting stock problem addressed in this document consists of minimizing the total waste produced by cutting a set of small parts in a given sequence from larger pieces of material. The African buffalo algorithm has successfully solved combinatorial problems. One of the difficulties of this algorithm is generating discrete solutions for this class of discrete problems. In this work, a discrete variant of the African buffalo algorithm is used, in which crossover technique and the ranked order value technique are compared to obtain discrete solutions. A set of ten instances of different complexity is used to compare these techniques. The results show that the crossover technique surpasses the others in terms of the quality of the solutions. Then these results are compared against other algorithms to evaluate their performance.

• Referencias bibliográficas
  • Alfares, H. K., & Alsawafy, O. G. (2019). A least-loss algorithm for a biobjective one-dimensional cutting-stock problem. International...
  • Araujo, S. A. d., Poldi, K. C., & Smith, J. (2014). A genetic algorithm for the one-dimensional cutting stock problem with setups. Pesquisa...
  • Asvany, T., Amudhavel, J., & Sujatha, P. (2017). One-dimensional cutting stock problem with single and multiple stock lengths using DPSO....
  • Ben Lagha, G., Dahmani, N., & Krichen, S. (2014). Particle swarm optimization approach for resolving the cutting stock problem. In 2014...
  • Berberler, M., & Nuriyev, U. (2010). A new heuristic algorithm for the one-dimensional cutting stock problem. Applied and Computational...
  • Chen, W.-N., & Tan, D.-Z. (2018). Set-based discrete particle swarm optimization and its applications: a survey. Frontiers of Computer...
  • Chen, Y.-H., Huang, H.-C., Cai, H.-Y., & Chen, P.-F. (2019). A genetic algorithm approach for the multiple length cutting stock problem....
  • Chiong, R., & Beng, O. K. (2007). A comparison between genetic algorithms and evolutionary programming based on cutting stock problem....
  • Delorme, M., Iori, M., & Martello, S. (2016). Bin packing and cutting stock problems: Mathematical models and exact algorithms. European...
  • Evtimov, G., & Fidanova, S. (2018). Ant colony optimization algorithm for 1D cutting stock problem. In Georgiev, K., Todorov, M., &...
  • Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 5–30.
  • Fang, J., Rao, Y., Luo, Q., & Xu, J. (2023). Solving one-dimensional cutting stock problems with deep reinforcement learning. Mathematics,...
  • Foerster, H., & Wascher, G. (2000). Pattern reduction in one-dimensional cutting stock problems. International Journal of Production Research,...
  • Gherboudj, A. (2019). African buffalo optimization for one-dimensional bin packing problem. International Journal of Swarm Intelligence Research...
  • Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859.
  • Gilmore, P. C., & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem—Part II. Operations Research, 11(6),...
  • Gradišar, M., Kljajić, M., Resinovič, G., & Jesenko, J. (1999). A sequential heuristic procedure for one-dimensional cutting. European...
  • Haessler, R. W. (1992). One-dimensional cutting stock problem problems and solution procedures. Mathematical and Computer Modelling, 16(1),...
  • Hinterding, R., & Khan, L. (1995). Genetic algorithms for cutting stock problems: With and without contiguity. In Yao, X. (Ed.), Progress...
  • Jahromi, M. H., Tavakkoli-Moghaddam, R., Makui, A., & Shamsi, A. (2012). Solving a one-dimensional cutting stock problem by simulated...
  • Jiang, T., Zhang, C., & Sun, Q.-M. (2019). Green job shop scheduling problem with discrete whale optimization algorithm. IEEE Access,...
  • Jiang, T., Zhu, H., & Deng, G. (2020). Improved African buffalo optimization algorithm for the green flexible job shop scheduling problem...
  • Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4), 366–422.
  • Krisnawati, M., Sibarani, A. A., Mustikasari, A., & Aulia, D. (2020). African buffalo optimization for solving flow shop scheduling problem...
  • Lee, D., Son, S., Kim, D., & Kim, S. (2020). Special-length-priority algorithm to minimize reinforcing bar-cutting waste for sustainable...
  • Levine, J., & Ducatelle, F. (2004). Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the...
  • Li, Y., Zheng, B., & Dai, Z. (2007). General particle swarm optimization based on simulated annealing for multi-specification one-dimensional...