Synergy between machine learning and optimization models: forecasting outcomes in parallel machines scheduling problem

Abstract

Implementar un modelo de optimización para programar pedidos en la industria del hormigón, con la meta de minimizar atrasos, conlleva un alto costo computacional debido a la naturaleza NP-hard del problema. Esto limita su aplicabilidad en entornos operativos que requieren respuestas en tiempo real. Si bien las heurísticas ofrecen tiempos de ejecución más bajos, no garantizan soluciones de alta calidad dentro del marco temporal requerido. Esta tesis explora un enfoque híbrido que combina Investigación de Operaciones (OR) y Aprendizaje Automático (ML) para aproximar los resultados de los modelos de optimización, buscando preservar la calidad de las soluciones y reducir drásticamente el esfuerzo computacional. La investigación consta de dos etapas. En la primera, se diseña una metaheurística que integra heurísticas constructivas, para generar soluciones iniciales factibles, y heurísticas de mejora, para refinarlas mediante reasignación de tareas. Su desempeño se contrasta con una formulación de Programación Lineal Entera Mixta (MILP) y con una asignación aleatoria, utilizando datos sintéticos que simulan una semana de pedidos en una planta de hormigón. La metaheurística alcanza soluciones con un gap promedio de solo 8.3\% en comparación con el modelo exacto, lo que representa una mejora promedio de 2968.8\% respecto a la asignación aleatoria, requiriendo apenas un 10\% del tiempo de ejecución del MILP. En la segunda etapa, estas soluciones generadas por la metaheurística se usan para entrenar un modelo predictivo de ML con una estructura de ensamble híbrido (Random Forest, AdaBoost y XGBoost). El modelo de ML aproxima el mapeo entre instancias y valores de la función objetivo, alcanzando un gap promedio de 9.4\%. Además, produce predicciones en menos de un segundo, lo que representa una reducción del costo computacional de varios órdenes de magnitud en comparación con el modelo de optimización. La contribución teórica de esta tesis radica en demostrar que los modelos de ML funcionan como predictores de los resultados de optimización en problemas de calendarización NP-hard, logrando aprender la estructura latente del espacio objetivo del MILP. Esto avanza el campo de ML para la Investigación de Operaciones al mostrar que los datos generados por la optimización pueden aprovecharse para entrenar modelos de ML que entreguen soluciones casi óptimas en tiempo real. Más allá de su relevancia en la industria del hormigón, la metodología propuesta provee un marco generalizable para integrar enfoques de OR y ML en contextos de calendarización de gran escala.