Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

Sintesi Tecnica: Programmazione di Progetti con Risorse Limitate con Tariffe Energetiche Time-of-Use e Stati delle Macchine

1. Definizione del Problema

Il documento affronta una variante del Problema di Programmazione di Progetti con Risorse Limitate (RCPSP) che integra tariffe energetiche Time-of-Use (TOU) e transizioni di stato delle macchine. Il problema riguarda la programmazione di un insieme di attività non preemptive soggette a vincoli di precedenza e capacità limitate delle risorse.

Le caratteristiche chiave includono:

• Risorsa ad alta intensità energetica: Una risorsa specifica ($R_0$) ha una capacità unitaria ed è energivora. Può esistere in tre stati: proc (elaborazione), idle (inattivo) o off (spento).
• Transizioni di Stato: Le transizioni tra gli stati comportano durate e costi energetici specifici. Ad esempio, accendere o spegnere una macchina consuma energia e tempo significativi. La macchina deve iniziare e terminare nello stato off.
• Classificazione delle Attività: Le attività sono divise in attività ad alta intensità energetica (che richiedono $R_0$ nello stato proc) e attività a bassa intensità energetica (che non utilizzano $R_0$).
• Obiettivo: L'obiettivo è minimizzare una combinazione convessa del Costo Energetico Totale (TEC) e del Makespan ($C_{max}$). Il TEC è calcolato sulla base delle tariffe TOU, che possono variare nel tempo e assumere anche valori negativi. La funzione obiettivo è normalizzata utilizzando i limiti inferiori derivati da ottimizzazioni indipendenti dei componenti TEC e $C_{max}$.

2. Metodologia

Gli autori propongono e confrontano tre distinti approcci di modellazione:

A. Modelli Monolitici
Due modelli compatti sono formulati per risolvere il problema nel suo insieme:

1. ILP Monolitico: Un modello di Programmazione Lineare Intera che utilizza variabili indicizzate nel tempo. Incorpora i costi di transizione ottimali precalcolati (tramite l'algoritmo SPACES) tra gli intervalli di elaborazione per gestire gli stati della macchina.
2. CP Monolitico: Un modello di Programmazione a Vincoli che utilizza variabili di intervallo opzionali. Questo approccio rappresenta l'elaborazione delle attività e le transizioni di stato ottimali come variabili di intervallo, consentendo al solver di determinare dinamicamente il numero e la collocazione delle transizioni.

B. Decomposizione di Benders basata sulla Logica (LBBD)
Il contributo principale è un approccio LBBD ibrido che decompone il problema in due sottoproblemi accoppiati:

• Problema Master (ILP): Risolve l'ottimizzazione dello stato della macchina e del costo energetico. Determina i tempi di inizio delle attività ad alta intensità energetica e la sequenza delle transizioni di stato. Utilizza un grafo SPACES modificato per calcolare i costi di transizione.
• Sottoproblema (CP): Un controllo di fattibilità per la componente RCPSP. Dato i tempi di inizio fissi delle attività ad alta intensità energetica dal Problema Master, esso tenta di programmare tutte le restanti attività non energivore rispettando le capacità delle risorse e i vincoli di precedenza.
• Tagli (Cutting Planes):
  • Tag di Fattibilità: Generati quando il sottoproblema è infattibile, impedendo al Master di selezionare lo stesso insieme conflittuale di tempi di inizio delle attività ad alta intensità energetica.
  • Tag di Ottimalità: Generati quando il sottoproblema è fattibile ma produce un makespan differente dalla stima del Master. Questi tagli utilizzano il percorso critico del grafo di flusso delle risorse per imporre un limite inferiore sul makespan nel problema Master.

3. Contributi Chiave

1. Formulazione del Problema: L'introduzione di una nuova variante dell'RCPSP che accoppia la dinamica degli stati delle macchine (proc, idle, off) con le tariffe TOU, estendendo i precedenti studi su singola macchina a un contesto di programmazione di progetti multi-risorsa.
2. Nuovo Framework LBBD: Lo sviluppo di una strategia di decomposizione che separa la gestione dell'energia (Master) dalla programmazione combinatoria (Sottoproblema). Gli autori derivano tagli di Benders specifici adattati all'interazione tra gli stati delle macchine e i vincoli RCPSP.
3. Generalizzazione: Dimostrazione che l'architettura LBBD è applicabile ad altri problemi di programmazione, specificamente:
   • RCPSP con tempi di blocco e un obiettivo di tardività totale ponderata.
   • Flexible Job Shop Scheduling (FJSP).

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su istanze derivate dal dataset PSPLIB, categorizzate in base alla densità delle attività ad alta intensità energetica (Sparse, Standard, Dense) e variando i parametri di ponderazione ($\alpha$) tra costo energetico e makespan.

• Performance rispetto ai Modelli Monolitici:
  • Entrambi gli approcci monolitici (ILP e CP) sono superati dall'LBBD nella maggior parte degli scenari, in particolare per istanze di grandi dimensioni (fino a 480 attività) e quando il criterio del makespan è meno dominante ($\alpha \to 1$).
  • L'approccio LBBD risolve le istanze verso l'ottimo significativamente più velocemente del CP monolitico, che fatica con spazi di ricerca elevati.
  • L'ILP monolitico performa ragionevolmente bene ma è generalmente più lento dell'LBBD.
• Impatto dei Parametri:
  • $\alpha = 1$ (Solo Energia): L'LBBD performa eccezionalmente bene, poiché il sottoproblema si riduce a un puro controllo di fattibilità, che i solver CP gestiscono efficientemente.
  • $\alpha < 1$ (Obiettivi Misti): L'LBBD rimane superiore nelle istanze Standard e Dense. Tuttavia, nelle istanze Sparse con basso $\alpha$ (alto peso del makespan), il CP monolitico talvolta supera l'LBBD perché i limiti di tempo del sottoproblema nell'LBBD possono ostacolare l'esplorazione dello spazio di ricerca.
• Risultati di Generalizzazione:
  • Nell'RCPSP con tempi di blocco, l'LBBD ha trovato soluzioni ottime per quasi il 90% delle istanze entro 30 minuti, rispetto a meno del 5% per il CP monolitico.
  • Nel problema Flexible Job Shop, l'LBBD ha trovato soluzioni fattibili più frequentemente (107/120 volte) rispetto all'ILP monolitico (83/120 volte) sotto vincoli temporali.

5. Significato e Rivendicazioni

Il documento sostiene che l'approccio LBBD proposto rappresenti un avanzamento significativo per i problemi di programmazione consapevole dell'energia che coinvolgono stati di macchina complessi. Il suo significato primario risiede nella capacità di decomporre l'ottimizzazione continua del costo energetico dai vincoli discreti di programmazione combinatoria, permettendo a ciascuno di essere risolto dal solver più adatto (ILP per l'energia, CP per la programmazione).

Gli autori affermano che questa decomposizione non è solo efficace per il problema specifico RCPSP-TOU, ma è un framework generalizzabile per qualsiasi problema di programmazione in cui le attività ad alta intensità energetica possano essere separate dalla restante logica di allocazione delle risorse. Il lavoro evidenzia come, mentre i modelli monolitici siano intuitivi, essi spesso non riescano a scalare con la dimensione e la complessità del problema, mentre l'approccio LBBD mantiene robustezza attraverso diverse densità di istanza e pesature degli obiettivi.

Il documento conclude notando che i lavori futuri potrebbero esplorare molteplici risorse ad alta intensità energetica, transizioni di stato più complesse e l'integrazione di sistemi di accumulo energetico o generazione on-site, nonché l'impatto dell'incertezza nelle tariffe energetiche.