Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Resumo Técnico: Aproximação Aumentada por Aprendizado para Escalonamento de Makespan em Máquinas Não Relacionadas

Definição do Problema
O artigo aborda o problema de Escalonamento de Makespan em Máquinas Não Relacionadas, denotado por $R\|C_{\max}$. Dado $n$ tarefas e $m$ máquinas, onde cada tarefa $j$ possui um tempo de processamento dependente da máquina $p_{ij}$, o objetivo é atribuir cada tarefa a uma máquina para minimizar a carga máxima (makespan) entre todas as máquinas. Este problema é notoriamente NP-difícil; Lenstra et al. (1990) estabeleceram uma 2-aproximação em tempo polinomial e provaram que melhorar o fator abaixo de $3/2$ é NP-difícil. Embora exista uma $(1+\epsilon)$-aproximação para um número fixo de máquinas $m$, ela depende de uma busca exaustiva sobre atribuições "pesadas" (tarefas com tempo de processamento $> \epsilon T$), o que resulta em complexidade de tempo não polinomial quando $m$ faz parte da entrada.

Metodologia
Os autores propõem um algoritmo de aproximação aumentado por aprendizado que incorpora previsões de atribuições de tarefas pesadas para reduzir a lacuna entre a 2-aproximação clássica e a $(1+\epsilon)$-aproximação. O algoritmo opera no paradigma clássico de decomposição pesado/curto, mas localiza o espaço de busca utilizando as previsões.

1. Modelo de Previsão: O algoritmo recebe uma atribuição parcial prevista $\hat{\phi}$, sugerindo atribuições de máquina para um subconjunto de tarefas. Tarefas não previstas são marcadas como $\perp$.
2. Estrutura de Duas Camadas:
   • Camada Interna (Conclusão Guiada por Previsão): Para um target de makespan $T$ fixo, o algoritmo filtra a previsão para reter apenas atribuições "T-pesadas" (onde $p_{ij} > \epsilon T$). Em seguida, realiza uma busca local para encontrar no máximo $K$ atribuições pesadas ausentes (aumentos) que foram perdidas pela previsão. Para cada conjunto candidato de atribuições pesadas fixas, resolve um Programa Linear (LP) residual para as tarefas restantes e aplica o arredondamento de Shmoys–Tardos.
   • Camada Externa (Busca de Limiar): Em vez de busca binária, o algoritmo enumera um número polinomial de "limiares críticos" onde a classificação pesado/curto muda. Ele executa a camada interna nesses limiares e retorna o melhor escalonamento encontrado, garantindo que o resultado nunca exceda a linha de base da 2-aproximação clássica.
3. Medidas de Erro: A análise define métricas de erro específicas:
   • Falsos Negativos ($R^-_{OPT}$): O tempo de processamento máximo das tarefas pesadas perdidas pela previsão.
   • Falsos Positivos ($R^+_{OPT}$): A sobrecarga máxima causada por atribuições pesadas previstas que discordam do escalonamento ótimo.
   • Erro Residual-$K$ ($R^-_{OPT,K}$): O erro restante após recuperar otimamente até $K$ tarefas pesadas perdidas.

Principais Contribuições

• Extensão de Estruturas de Aprendizado-Aumentadas: O trabalho aborda uma questão aberta proposta por Antoniadis et al. (2025) sobre a extensão de garantias suaves dependentes de previsão de problemas de seleção de objetivo linear para problemas de escalonamento com objetivos de makespan.
• Garantias de Tradeoff Suave: O algoritmo alcança uma garantia de $(1+\epsilon)OPT$ quando as previsões são precisas. À medida que o erro de previsão aumenta, a garantia degrada-se suavemente, limitada por termos aditivos relacionados a falsos negativos e falsos positivos. Crucialmente, o desempenho no pior caso nunca é pior que a 2-aproximação clássica.
• Eficiência de Tempo Polinomial: Diferente dos esquemas clássicos de $(1+\epsilon)$ que exigem tempo exponencial em $m$, este algoritmo roda em tempo polinomial em $m$ e $n$ (especificamente $O((mn)^K \cdot \text{poly}(\dots))$) para qualquer orçamento de busca $K$ fixo. O parâmetro $K$ controla o tradeoff entre o tempo de execução e a capacidade de corrigir previsões de falsos negativos.
• Assimetria de Erros: A análise revela uma assimetria: falsos negativos podem ser recuperados via busca local (ao custo da complexidade de tempo $K$), enquanto falsos positivos contribuem diretamente para o limite do makespan e não podem ser "buscados para longe" sem alterar o modelo de confiança da previsão.

Resultados

• Limites Teóricos: O Teorema 5.2 estabelece que o makespan $C_{\max}(S)$ satisfaz:
  $$C_{\max}(S) \le \min \left\{ (1+\epsilon)OPT + R^-_{OPT,K} + R^+_{OPT}, \ 2OPT \right\}$$
  Isso confirma consistência (desempenho ótimo em previsões precisas), robustez (limitado pela 2-aproximação em previsões ruins) e suavidade (degradação proporcional ao erro).
• Validação Empírica: Experimentos numéricos em instâncias sintéticas demonstram que:
  • Com previsões precisas, o algoritmo supera significativamente a linha de base da 2-aproximação clássica em qualidade de makespan.
  • O algoritmo roda ordens de magnitude mais rápido que as linhas de base clássicas do tipo $(1+\epsilon)$ (que se tornam inviáveis conforme $m$ cresce), igualando-se à velocidade da 2-aproximação.
  • Aumentar o orçamento de busca $K$ melhora a qualidade do makespan na presença de falsos negativos, validando o tradeoff teórico.
  • O algoritmo exibe a assimetria prevista: aumentar $K$ ajuda com falsos negativos, mas tem efeito negligenciável sobre falsos positivos.

Significância e Alegações
O artigo afirma fornecer a primeira estrutura de aproximação aumentada por aprendizado para $R\|C_{\max}$ que oferece garantias suaves dependentes de previsão enquanto mantém a complexidade de tempo polinomial independente do número de máquinas. Ao localizar a busca estrutural dispendiosa (atribuições pesadas) em uma vizinhança definida pelas previsões, o método permite que algoritmos de escalonamento aproveitem previsões de aprendizado de máquina de alta qualidade para superar as linhas de base clássicas de pior caso sem sacrificar a robustez. Os autores posicionam isso como um passo para estender as garantias de aprendizado-aumentado a problemas de otimização onde algoritmos clássicos dependem de suposições estruturais caras.