Aprendizaje reforzado aplicado a la programación de tareas bajo condiciones reales/Reinforcement learning applied to scheduling under real constraints

Yunior César Fonseca-Reyna, Yailen Martínez-Jiménez, Ann Nowé

Resumen


La variante de flujo regular o flow shop scheduling es un problema clásico de programación de la producción. Las primeras publicaciones científicas sobre este problema aparecieron hace más de medio siglo. Sin embargo, muchos autores han reconocido una brecha entre la literatura especializada y la problemática en entornos reales. En este trabajo se modeló el flow shop considerando los tiempos de configuración inicial de las máquinas, tiempos de montaje dependientes de la secuencia, precedencia entre trabajos, omisión de etapas por los trabajos y como función objetivo minimización del tiempo total de procesamiento o makespan. Hasta el momento no existen métodos computacionales que solucionen este problema teniendo en cuenta todas las características mencionadas. Para la solución se adaptó un enfoque del Aprendizaje Reforzado conocido como Q-Learning. Finalmente, se usaron instancias de problemas de diferentes tamaños y complejidad demostrando la efectividad de este método en cuanto a la calidad de las soluciones.

Abstract

The flow shop scheduling is a classic problem of production scheduling. The first scientific publications on production scheduling appeared more than half a century ago. However, many authors have recognized a gap between the specialized literature and the real environment problems. In this paper, the flow shop is modeled taking into account preparation time machines, setup-time between two jobs, precedence between jobs, the possibility to skip stages and as objective function minimizing the total processing time or make span. At this moment, there are no computational methods that can solve this problem taking into account all the mentioned elements. The Reinforcement Learning approach known as Q-Learning was adapted to use it in the solution of this problem. Finally, the algorithm was tested with problems of different levels of complexity in order to obtain satisfactory results in terms of solutions quality.


Palabras clave


aprendizajere forzado; flow shop scheduling; optimización combinatoria; q-learning, flow shop, optimization; q-learning; reinforcement learning.

Texto completo:

PDF


 

 

 

 

 

 

 

 

Dirección editorial:

Facultad de Ingeniería Industrial, Instituto Superior Politécnico José Antonio Echeverría, Cujae,

Calle 114 No. 11901. e/ Ciclovía y Rotonda. Marianao 15.

La Habana, Cuba. CP 19390. Telf: (537) 266 3521

E-mail: revistaii@ind.cujae.edu.cu

URL: http://rii.cujae.edu.cu