Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Resumen Técnico: Aproximación Aumentada por Aprendizaje para el Makespan de Máquinas No Relacionadas

Definición del Problema
El artículo aborda el problema de Programación de Makespan en Máquinas No Relacionadas, denotado como $R\|C_{\max}$. Dado $n$ trabajos y $m$ máquinas, donde cada trabajo $j$ tiene un tiempo de procesamiento dependiente de la máquina $p_{ij}$, el objetivo es asignar cada trabajo a una máquina para minimizar la carga máxima (makespan) en todas las máquinas. Este problema es notoriamente NP-duro; Lenstra et al. (1990) establecieron una 2-aproximación en tiempo polinomial y demostraron que mejorar el factor por debajo de $3/2$ es NP-duro. Aunque existe una $(1+\epsilon)$-aproximación para un número fijo de máquinas $m$, esta depende de una búsqueda exhaustiva sobre asignaciones "pesadas" (trabajos con tiempo de procesamiento $> \epsilon T$), lo que resulta en una complejidad de tiempo no polinomial cuando $m$ es parte de la entrada.

Metodología
Los autores proponen un algoritmo de aproximación aumentado por aprendizaje que incorpora predicciones de asignaciones de trabajos pesados para cerrar la brecha entre la 2-aproximación clásica y la $(1+\epsilon)$-aproximación. El algoritmo opera bajo el paradigma clásico de descomposición pesado/corto, pero localiza el espacio de búsqueda utilizando las predicciones.

1. Modelo de Predicción: El algoritmo recibe una asignación parcial predicha $\hat{\phi}$, que sugiere asignaciones de máquinas para un subconjunto de trabajos. Los trabajos no predichos se marcan como $\perp$.
2. Estructura de Dos Capas:
   • Capa Interna (Completado Guiado por Predicción): Para un makespan objetivo fijo $T$, el algoritmo filtra la predicción para retener solo las asignaciones "T-pesadas" (donde $p_{ij} > \epsilon T$). Luego realiza una búsqueda local para encontrar como máximo $K$ asignaciones pesadas faltantes (aumentaciones) que fueron omitidas por la predicción. Para cada conjunto candidato de asignaciones pesadas fijas, resuelve un Programa Lineal (LP) residual para los trabajos restantes y aplica el redondeo de Shmoys–Tardos.
   • Capa Externa (Búsqueda de Umbral): En lugar de una búsqueda binaria, el algoritmo enumera un número polinomial de "umbrales críticos" donde cambia la clasificación pesado/corto. Ejecuta la capa interna en estos umbrales y devuelve el mejor esquema encontrado, asegurando que el resultado nunca exceda la línea base de la 2-aproximación clásica.
3. Medidas de Error: El análisis define métricas de error específicas:
   • Falsos Negativos ($R^-_{OPT}$): El tiempo de procesamiento máximo de los trabajos pesados omitidos por la predicción.
   • Falsos Positivos ($R^+_{OPT}$): La sobrecarga máxima causada por las asignaciones pesadas predichas que discrepan con el esquema óptimo.
   • Error Residual-$K$ ($R^-_{OPT,K}$): El error restante después de recuperar óptimamente hasta $K$ trabajos pesados omitidos.

Contribuciones Clave

• Extensión de Marcos de Trabajo Aumentados por Aprendizaje: El trabajo aborda una pregunta abierta planteada por Antoniadis et al. (2025) sobre la extensión de las garantías de dependencia de la predicción suave desde problemas de selección de objetivo lineal hacia problemas de programación con objetivos de makespan.
• Garantías de Compromiso Suave (Smooth Tradeoff): El algoritmo logra una garantía de $(1+\epsilon)OPT$ cuando las predicciones son precisas. A medida que el error de predicción aumenta, la garantía se degrada suavemente, acotada por términos aditivos relacionados con los falsos negativos y falsos positivos. Crucialmente, el rendimiento en el peor de los casos nunca es peor que la 2-aproximación clásica.
• Eficiencia en Tiempo Polinomial: A diferencia de los esquemas clásicos de $(1+\epsilon)$ que requieren tiempo exponencial en $m$, este algoritmo se ejecuta en tiempo polinomial en $m$ y $n$ (específicamente $O((mn)^K \cdot \text{poly}(\dots)$) para cualquier presupuesto de búsqueda fijo $K$. El parámetro $K$ controla el compromiso entre el tiempo de ejecución y la capacidad de corregir las predicciones de falsos negativos.
• Asimetría de Errores: El análisis revela una asimetría: los falsos negativos pueden recuperarse mediante búsqueda local (a costa de la complejidad temporal $K$), mientras que los falsos positivos contribuyen directamente al límite del makespan y no pueden "buscárse de eliminar" sin alterar el modelo de confianza de la predicción.

Resultados

• Límites Teóricos: El Teorema 5.2 establece que el makespan $C_{\max}(S)$ satisface:
  $$C_{\max}(S) \le \min \left\{ (1+\epsilon)OPT + R^-_{OPT,K} + R^+_{OPT}, \ 2OPT \right\}$$
  Esto confirma la consistencia (rendimiento óptimo con predicciones precisas), la robustez (acotado por la 2-aproximación con predicciones pobres) y la suavidad (degradación proporcional al error).
• Validación Empírica: Experimentos numéricos en instancias sintéticas demuestran que:
  • Con predicciones precisas, el algoritmo supera significativamente la calidad del makespan de la línea base de 2-aproximación clásica.
  • El algoritmo es órdenes de magnitud más rápido que las líneas base clásicas de tipo $(1+\epsilon)$ (que se vuelven inviables a medida que $m$ crece), igualando la velocidad de la 2-aproximación.
  • Aumentar el presupuesto de búsqueda $K$ mejora la calidad del makespan en presencia de falsos negativos, validando el compromiso teórico.
  • El algoritmo exhibe la asimetría predicha: aumentar $K$ ayuda con los falsos negativos pero tiene un efecto insignificante en los falsos positivos.

Significado y Reivindicaciones
El artículo afirma proporcionar el primer marco de aproximación aumentado por aprendizaje para $R\|C_{\max}$ que ofrece garantías suaves dependientes de la predicción mientras mantiene la complejidad de tiempo polinomial independiente del número de máquinas. Al localizar la búsqueda estructural costosa (asignaciones pesadas) en un vecindario definido por las predicciones, el método permite que los algoritmos de programación aprovechen las predicciones de alta calidad del aprendizaje automático para superar las líneas base clásicas del peor caso sin sacrificar la robustez. Los autores posicionan esto como un paso hacia la extensión de las garantías aumentadas por aprendizaje a problemas de optimización donde los algoritmos clásicos dependen de una suposición estructural costosa.