Métodos de solución para problemas de secuenciación en máquinas paralelas no relacionadas

En los entornos productivos se presentan constantemente situaciones en las
que se tiene un conjunto de actividades por realizarse, un conjunto de máquinas
capaces de realizar dichas tareas, y se debe decidir cómo se debe de repartir la
carga de trabajo y en qué orden se deben de realizar dichas actividades. Estos
sistemas se estudian en las disciplinas de optimización combinatoria bajo los
conceptos de secuenciación, y son relevantes en la industria debido a las grandes
implicaciones económicas asociadas al uso de recursos que dichas decisiones
impactan en diversas aplicaciones, como lo puede ser las industrias de impresión,
manufactura de herramentales o artículos personalizados y de alta precisión,
talleres de manufactura flexible, entre otras.
En este trabajo de investigación se estudian dos tipos de problemas de
secuenciación. El primero consiste en un problema de secuenciación en máquinas
paralelas no relacionadas con minimización de la tardanza total, mientras que el
segundo se encuentra relacionado con la secuenciación en máquinas paralelas no
relacionadas con minimización de makespan, tiempos de preparación dependientes
de la secuencia y recurso compartido.
Para el primer problema se presentan 2 metodologías de solución: la primera
utiliza un modelo de programación lineal entera mixta basado en variables de
posición, el cual no necesita de restricciones de gran M e incorpora desigualdades
válidas para acelerar su ejecución, y como segunda metodología se presenta un
algoritmo metaheurístico de búsqueda local iterada con estrategias de mejora
basadas en mecanismos de reinserción e intercambio de tareas.
El segundo problema bajo estudio considera una extensión del problema de
recursos compartidos, donde dicho recurso ejecuta todos los procesos de
preparación y debe de tener una secuencia propia de actividades. Esta secuencia,
a su vez, está ligada a las secuencias de las distintas máquinas del sistema,
visualizando así al recurso compartido como una máquina. Para este problema se exploran 2 metodologías de solución; primero un conjunto de modelos (6
específicamente) de programación lineal entera mixta que describen el sistema
desde varias perspectivas relacionadas a hitos de tiempo del sistema. La segunda
metodología de solución contempla un par de algoritmos metaheurísticos de
descenso por vecindarios variables (4 mecanismos de generación de vecindarios),
e incorpora dos mecanismos de diversificación.
Para el primer problema se tuvo la oportunidad de comparar el desempeño
del modelo matemático contra un modelo previamente presentado en la literatura,
demostrando su superioridad al obtener soluciones óptimas en instancias donde el
modelo previo reportaba soluciones factibles con hasta 74% de gap.
Adicionalmente, se mejoró el desempeño del modelo propuesto mediante la
inclusión de desigualdades válidas, resultando en reducciones de hasta un 30% en
tiempo de procesamiento.
Para el segundo problema se consideraron 6 formulaciones distintas,
basadas en diferentes momentos de referencia relevantes para el sistema, con lo
que se determinó que las formulaciones que usan como referencia el tiempo de
terminación del proceso de preparación tienen mejor desempeño.
Para ambos problemas se realizaron comparativas entre los modelos y los
algoritmos propuestos correspondientes, con el fin de determinar la capacidad de
los algoritmos para encontrar soluciones de alta calidad. Los resultados
experimentales muestran que los algoritmos propuestos son competitivos. Además,
para el primer problema se lograron abordar instancias de hasta 400 tareas
mediante dicho algoritmo, mientras que, para el segundo, se resuelven instancias
de hasta 60 tareas.

Capítulo 1. Marco teórico -- Capítulo 2. Problema de secuenciación de maquinas paralelas no relacionada con minimización de tardanza total -- Capítulo 3. Problema de máquinas paralelas no relacionadas con minimización de makespan, tiempos de preparación dependientes de la secuencia y recurso compartido