Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

Sintesi Tecnica: Approssimazione con Apprendimento per lo Scheduling della Makespan su Macchine Non Correlate

Definizione del Probleo
Il documento affronta il problema dello Scheduling della Makespan su Macchine Non Correlate, indicato come $R\|C_{\max}$. Dato un insieme di $n$ lavori e $m$ macchine, dove ogni lavoro $j$ ha un tempo di elaborazione dipendente dalla macchina $p_{ij}$, l'obiettivo è assegnare ogni lavoro a una macchina per minimizzare il carico massimo (makespan) su tutte le macchine. Questo problema è notoriamente NP-hard; Lenstra et al. (1990) hanno stabilito un 2-approssimazione in tempo polinomiale e hanno dimostrato che migliorare il fattore al di sotto di $3/2$ è NP-hard. Sebbene esista un $(1+\epsilon)$-approssimazione per un numero fisso di macchine $m$, essa si basa sulla ricerca esaustiva di assegnazioni "pesanti" (lavori con tempo di elaborazione $> \epsilon T$), risultando in una complessità temporale non polinomiale quando $m$ fa parte dell'input.

Metodologia
Gli autori propongono un algoritmo di approssimazione con apprendimento aumentato che incorpora le predizioni delle assegnazioni dei lavori pesanti per colmare il divario tra il classico 2-approssimazione e il $(1+\epsilon)$-approssimazione. L'algoritmo opera sul classico paradigma di decomposizione pesante/breve, ma localizza lo spazio di ricerca utilizzando le predizioni.

1. Modello di Predizione: L'algoritmo riceve un'assegnazione parziale predetta $\hat{\phi}$, che suggerisce li assegnazioni alle macchine per un sottoinsieme di lavori. I lavori non predetti sono contrassegnati come $\perp$.
2. Struttura a Due Livelli:
   • Livello Interno (Completamento Guidato dalla Predizione): Per un target di makespan $T$ fissato, l'algoritmo filtra la predizione per mantenere solo le assegnazioni "T-pesanti" (dove $p_{ij} > \epsilon T$). Successivamente, esegue una ricerca locale per trovare al massimo $K$ assegnazioni pesanti mancanti (augumentazioni) che sono state omesse dalla predizione. Per ogni insieme candidato di assegnazioni pesanti fisse, risolve un Programma Lineare (LP) residuo per i lavori rimanenti e applica il rounding di Shmoys–Tardos.
   • Livello Esterno (Ricerca della Soglia): Inveve della ricerca binaria, l'algoritmo enumera un numero polinomiale di "soglie critiche" dove cambia la classificazione pesante/breve. Esegue il livello interno su queste soglie e restituisce il miglior programma trovato, garantendo che il risultato non superi mai il baseline del 2-approssimazione classico.
3. Misure di Errore: L'analisi definisce metriche di errore specifiche:
   • Falsi Negativi ($R^-_{OPT}$): Il tempo di elaborazione massimo dei lavori pesanti mancanti alla predizione.
   • Falsi Positivi ($R^+_{OPT}$): Il sovraccarico massimo causato dalle assegnazioni pesanti predette che sono in disaccordo con lo schema ottimale.
   • Errore Residuo $K$ ($R^-_{OPT,K}$): L'errore rimanente dopo il recupero ottimale di fino a $K$ lavori pesanti mancanti.

Contributi Chiave

• Estensione dei Framework di Approssimazione con Apprendimento: Il lavoro affronta una domanda aperta posta da Antoniadis et al. (2025) riguardante l'estensione dei garanti di predizione-dipendenti "smooth" dai problemi di selezione con obiettivi lineari ai problemi di scheduling con obiettivi di makespan.
• Garanzie di Tradeoff Smooth: L'algoritmo raggiunge una garanzia di $(1+\epsilon)OPT$ quando le predizioni sono accurate. Man mano che l'errore di predizione aumenta, la garanzia decade in modo fluido (smooth), limitata da termini additivi relativi ai falsi negativi e ai falsi positivi. Fondamentalmente, le prestazioni nel caso peggiore non sono mai peggiori del classico 2-approssimazione.
• Efficienza in Tempo Polinomiale: A differenza dei classici schemi $(1+\epsilon)$ che richiedono un tempo esponenziale in $m$, questo algoritmo opera in tempo polinomiale in $m$ e $n$ (specificamente $O((mn)^K \cdot \text{poly}(\dots))$) per qualsiasi budget di ricerca $K$ fisso. Il parametro $K$ controlla il tradeoff tra tempo di esecuzione e capacità di correggere le predizioni dei falsi negativi.
• Asimmetria degli Errori: L'analisi rivela un'asimmetria: i falsi negativi possono essere recuperati tramite ricerca locale (al costo della complessità temporale $K$), mentre i falsi positivi contribuiscono direttamente al limite della makespan e non possono essere "ricercati via" senza alterare il modello di fiducia della predizione.

Risultati

• Limiti Teorici: Il Teorema 5.2 stabilisce che la makespan $C_{\max}(S)$ soddisfa:
  $$C_{\max}(S) \le \min \left\{ (1+\epsilon)OPT + R^-_{OPT,K} + R^+_{OPT}, \ 2OPT \right\}$$
  Ciò conferma la consistenza (prestazioni ottimali su predizioni accurate), la robustezza (limitata al 2-approssimazione su predizioni scarse) e la fluidità (degradazione proporzionale all'errore).
• Validazione Empirica: Esperimenti numerici su istanze sintetiche dimostrano che:
  • Con predizioni accurate, l'algoritmo supera significativamente il baseline del 2-approssimazione classico in termini di qualità della makespan.
  • L'algoritmo è ordini di grandezza più veloce dei baseline di tipo $(1+\epsilon)$ classici (che diventano impraticabili al crescere di $m$), eguagliando la velocità del 2-approssimazione.
  • Aumentare il budget di ricerca $K$ migliora la qualità della makespan in presenza di falsi negativi, validando il tradeoff teorico.
  • L'algoritmo mostra l'asimmetria prevista: aumentare $K$ aiuta con i falsi negativi ma ha un effetto trascurabile sui falsi positivi.

Significatività e Rivendicazioni
Il documento sostiene di fornire il primo framework di approssimazione con apprendimento aumentato per $R\|C_{\max}$ che offre garanzie smooth e dipendenti dalla predizione, mantenendo al contempo la complessità temporale polinomiale indipendente dal numero di macchine. Localizzando la ricerca strutturale costosa (assegnazioni pesanti) in un vicinato definito dalle predizioni, il metodo permette agli algoritmi di scheduling di sfruttare predizioni di machine learning di alta qualità per superare i classici baseline del caso peggiore senza sacrificare la robustezza. Gli autori posizionano questo lavoro come un passo verso l'estensione delle garanzie di apprendimento aumentato a problemi di ottimizzazione in cui gli algoritmi classici si affidano a costose ipotesi strutturali.