Un Squirrel Search Algorithm discreto aplicado al problema Job Shop con operadores calificados

  • César Andrés López Martínez Universidad Pontificia Bolivariana. Montería, (Colombia) https://orcid.org/0000-0003-2750-7699
  • Helman Enrique Hernández Riaño Universidad de Córdoba. Montería, (Colombia) https://orcid.org/0000-0003-3042-2573
  • Manuel Jesús Soto de la Vega Universidad Tecnológica de Bolivar. Cartagena, (Colombia)

Resumen

Introducción: El problema Job Shop Con Operadores Calificados o Job Shop With Skilled Operators (JSSO) es una extensión del problema clásico Job Shop en el cual, una operación debe ser ejecutada por un conjunto limitados de trabajadores, con el objetivo de minimizar el tiempo de terminación total de los trabajos o Makespan, situación que puede representar distintas aplicaciones en la vida cotidiana. Es un problema complejo y es catalogado como NP-HARD.

Objetivo: En este artículo, se aborda el problema JSSO desde la adaptación de un algoritmo conocido como Squirrel Search Algorithm (SSA).

Metodología: Se propone un esquema de codificación discreto para el algoritmo SSA utilizando el método Smallest Position Value (SPV). Además, para evitar soluciones que violen las relaciones de precedencia; se corrigen con el método Valid Particle Generator (VPG), el cual garantiza soluciones factibles. Dos versiones del algoritmo se colocan a prueba en 28 instancias propuesta en la literatura para validar su rendimiento.

Resultados: Los experimentos computacionales realizados muestran que los dos algoritmos propuestos alcanzan soluciones óptimas en 25 de las 28 instancias analizadas. Además, para las instancias en donde no se logró soluciones óptimas, el gap promedio no supera el 2% para ambas versiones de los algoritmos propuestos.

Conclusiones: El esquema de codificación propuesto garantiza la discretización del algoritmo, generando soluciones que convergen hacia el óptimo. Además, la codificación propuesta, permite utilizar de manera natural los operadores de movimiento propuestos originalmente para el algoritmo utilizado. El rendimiento obtenido por los algoritmos es adecuado y de alta calidad.

Palabras clave: Inteligencia de enjambres, Secuenciación Con Operadores, Posición Del Valor Más Pequeño, Generador Válido De Partículas, Optimización Combinatoria

Referencias

A. Agnetis, G. Murgia, and S. Sbrilli, "A job shop scheduling problem with human operators in handicraft production," Int. J. Prod. Res., vol. 52, no. 13, pp. 3820-3831, Jul. 2014. DOI: https://doi.org/10.1080/00207543.2013.831220

M. Abdel-Basset, L. Abdel-Fatah, and A. K. Sangaiah, Metaheuristic Algorithms: A Comprehensive Review. Elsevier Inc., 2018. DOI: https://doi.org/10.1016/B978-0-12-813314-9.00010-4

M. Jain, V. Singh, and A. Rani, "A novel nature-inspired algorithm for optimization: Squirrel search algorithm," Swarm Evol. Comput., vol. 44, no. June 2017, pp. 148-175, Feb. 2019. DOI: https://doi.org/10.1016/j.swevo.2018.02.013

L. Gao, X. Li, X. Wen, C. Lu, and F. Wen, "A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem," Comput. Ind. Eng., vol. 88, pp. 417-429, 2015. DOI: https://doi.org/10.1016/j.cie.2015.08.002

K. Z. Gao, P. N. Suganthan, T. J. Chua, C. S. Chong, T. X. Cai, and Q. K. Pan, "A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion," Expert Syst. Appl., vol. 42, no. 21, pp. 7652-7663, 2015. DOI: https://doi.org/10.1016/j.eswa.2015.06.004

K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, C. S. Chong, and T. X. Cai, "An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time," Expert Syst. Appl., vol. 65, pp. 52-67, 2016. DOI: https://doi.org/10.1016/j.eswa.2016.07.046

A. Maroosi, R. C. Muniyandi, E. Sundararajan, and A. M. Zin, "A parallel membrane inspired harmony search for optimization problems: A case study based on a flexible job shop scheduling problem," Appl. Soft Comput. J., vol. 49, pp. 120-136, 2016. DOI: https://doi.org/10.1016/j.asoc.2016.08.007

A. Ahmadi-Javid and P. Hooshangi-Tabrizi, "Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an Anarchic Society Optimization algorithm," Comput. Oper. Res., vol. 84, no. 2017, pp. 73-91, 2017. DOI: https://doi.org/10.1016/j.cor.2016.11.017

H. Piroozfard, K. Y. Wong, and A. D. Asl, "An improved biogeography-based optimization for achieving optimal job shop scheduling solutions," Procedia Comput. Sci., vol. 115, pp. 30-38, 2017. DOI: https://doi.org/10.1016/j.procs.2017.09.073

N. Sharma, H. Sharma, and A. Sharma, "Beer froth artificial bee colony algorithm for job-shop scheduling problem," Appl. Soft Comput. J., vol. 68, pp. 507-524, 2018. DOI: https://doi.org/10.1016/j.asoc.2018.04.001

B. Marzouki, O. B. Driss, and K. Ghédira, "Solving Distributed and Flexible Job shop Scheduling Problem using a Chemical Reaction Optimization metaheuristic," Procedia Comput. Sci., vol. 126, pp. 1424-1433, 2018. DOI: https://doi.org/10.1016/j.procs.2018.08.114

A. Agnetis, M. Flamini, G. Nicosia, and A. Pacifici, "A job-shop problem with one additional resource type," J. Sched., vol. 14, no. 3, pp. 225-237, 2011. DOI: https://doi.org/10.1007/s10951-010-0162-4

M. R. Sierra, C. Mencía, and R. Varela, "New schedule generation schemes for the job-shop problem with operators," J. Intell. Manuf., vol. 26, no. 3, pp. 511-525, 2015. DOI: https://doi.org/10.1007/s10845-013-0810-6

B. Giffler and G. L. Thompson, "Algorithms for Solving Production-Scheduling Problems," Oper. Res., vol. 8, no. 4, pp. 487-503, Aug. 1960. DOI: https://doi.org/10.1287/opre.8.4.487

R. Mencia, M. R. Sierra, C. Mencia, and R. Varela, "Genetic Algorithm for Job-Shop Scheduling with Operators," in New Challenges on Bioinspired Applications, 2011, pp. 305-3014. DOI: https://doi.org/10.1007/978-3-642-21326-7

R. Mencía, M. R. Sierra, C. Mencía, and R. Varela, "A genetic algorithm for job-shop scheduling with operators enhanced by weak Lamarckian evolution and search space narrowing," Nat. Comput., vol. 13, no. 2, pp. 179-192, 2014. DOI: https://doi.org/10.1007/s11047-013-9373-x

F. Barber, J. Escamilla, C. Mencia, M. Rodriguez-Molins, M. A. Salido, and M. R. Sierra, "Robust solutions to job-shop scheduling problems with operators," Proc. - Int. Conf. Tools with Artif. Intell. ICTAI, 2012. DOI: https://doi.org/10.1109/ICTAI.2012.48

M. F. Tasgetiren, M. Sevkli, Yun-Chia Liang, and G. Gencyilmaz, "Particle swarm optimization algorithm for single machine total weighted tardiness problem," pp. 1412-1419, 2005. DOI: https://doi.org/10.1109/CEC.2004.1331062

R. Chaudhry, S. Tapaswi, and N. Kumar, "Forwarding Zone enabled PSO routing with Network lifetime maximization in MANET," Appl. Intell., vol. 48, no. 9, pp. 3053-3080, 2018. DOI: https://doi.org/10.1007/s10489-017-1127-5

I. Dubey and M. Gupta, "Uniform mutation and SPV rule based optimized PSO algorithm for TSP problem," Proc. 2017 4th Int. Conf. Electron. Commun. Syst. ICECS 2017, vol. 17, pp. 168-172, 2017. DOI: https://doi.org/10.1109/ECS.2017.8067862

N. Kumar and D. P. Vidyarthi, "A model for resource-constrained project scheduling using adaptive PSO," Soft Comput., vol. 20, no. 4, pp. 1565-1580, 2016. DOI: https://doi.org/10.1007/s00500-015-1606-8

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, "Optimization and approximation in deterministic machine scheduling: a survey," Ann. Discret. Math., vol. 5, pp. 287-326, 1979. DOI: https://doi.org/10.1016/S0167-5060(08)70356-X

R Core Team, "R: A language and environment for statistical computing." R Foundation for Statistical Computing, 2019. Disponible : https://www.r-project.org/

Descargas

La descarga de datos todavía no está disponible.

Acerca de los Autores

César Andrés López Martínez, Universidad Pontificia Bolivariana. Montería, (Colombia)

César Andrés López Martínez es graduado del programa de Ingeniería Industrial en el año 2010 de la Universidad De Córdoba (Montería, Colombia).  Es candidato a Magister en Ingeniería De Producción de la Universidad Tecnológica De Bolívar (Cartagena De Indias, Colombia). Sus intereses investigativos incluyen tópicos en Metaheurísticas, Investigación De Operaciones, Programación De Producción, Optimización. Actualmente es Docente interno en la facultad de Ingeniería Industrial de la Universidad Pontificia Bolivariana (Montería, Colombia). https://orcid.org/0000-0003-2750-7699

Helman Enrique Hernández Riaño, Universidad de Córdoba. Montería, (Colombia)

Helman Enrique Hernández Riaño es graduado del programa de Ingeniería Industrial en el año 1999 de la Universidad Distrital (Bogotá, Colombia). Es Magister en Gestión de Organizaciones de la Universidad EAN (Bogotá, Colombia). Es Doctor en Ingeniería Industrial de la Universidad del Norte (Barranquilla, Colombia). Sus intereses investigativos incluyen tópicos en Metaheurísticas, Investigación de Operaciones, Programación de Producción, Logística y Optimización. Actualmente es Profesor Titular del Departamento de Ingeniería Industrial de la Universidad de Córdoba (Montería, Colombia). https://orcid.org/0000-0003-3042-2573

Manuel Jesús Soto de la Vega, Universidad Tecnológica de Bolivar. Cartagena, (Colombia)

Manuel Jesús Soto de la Vega es graduado del programa de Ingeniería Industrial en el año 2012 de la Universidad de Córdoba. Es Magister en Ingeniería Industrial de la Universidad de los Andes (Bogotá, Colombia). Actualmente profesor de la Universidad Tecnológica De Bolívar vinculado al programa de Ingeniería Industrial. Áreas de trabajo en investigación de operaciones, incluyendo trabajos en optimización y simulación de procesos.

 

Publicado
2019-12-02
Cómo citar
López Martínez, C., Hernández Riaño, H., & Soto de la Vega, M. (2019). Un Squirrel Search Algorithm discreto aplicado al problema Job Shop con operadores calificados. INGE CUC, 15(2), 143-154. https://doi.org/10.17981/ingecuc.15.2.2019.14