Diseño de una Estructura de Vecindad Variable en Función de su Línea de Tiempo Para el Problema de Talleres de Manufactura

El problema de Calendarización para Talleres de Manufactura (Job Shop Scheduling Problem) es un problema de optimización combinatoria que busca programar un conjunto de tareas en distintas máquinas de manera óptima, respetando restricciones como secuencialidad, capacidad de recursos y no interrupciones. Este problema, es de gran relevancia en entornos industriales, está orientado a minimizar criterios como el tiempo de producción. El JSSP pertenece a los problemas NP, ya que no existe un método exacto que lo pueda resolver en tiempo polinomial. Además, su complejidad lo ubica dentro de los problemas NP más difíciles conocidos como NP-duros. En esta tesis se aborda la implementación de una nueva estructura de vecindad variable para el problema del JSSP. La estructura propuesta se centra en permutar únicamente pares adyacentes que forman parte de una o varias rutas críticas y que pasan por una línea de tiempo, identificadas mediante el método del CPM (Critical Path Method). La Estructura de Vecindad Variable en Función de su Línea de Tiempo (EVVFLT) se caracteriza por su rapidez, ya que al enfocarse en operaciones adyacentes dentro de una o varias rutas críticas, reduce significativamente el número de evaluaciones necesarias en cada iteración de esta forma se realizan generalmente permutaciones en la ruta crítica. Aunque logra impactar directamente en varias operaciones críticas, esta estrategia también revela ciertas limitaciones.