Algoritmi di Rollout per il problema del Job Shop Scheduling

Introduzione 1
termini di qualità della soluzione e tempi computazionali hanno dato finora risultati 
soddisfacenti. Recentemente, è stato proposto da Bertsekas un nuovo approccio 
euristico per la soluzione di problemi di ottimizzazione combinatoria, noto come 
algoritmo di rollout. Data un’euristica (euristica di base) per il problema in esame, 
l’algoritmo di rollout costruisce iterativamente una soluzione usando l’euristica di base 
per scegliere, ad ogni iterazione, tra le diverse opzioni di ricerca disponibili. 
L’esperienza accumulata nell’uso del rollout nel campo dei problemi di ottimizzazione 
combinatoria ha mostrato che questo metodo migliora significativamente le 
prestazioni, in termini di qualità della soluzione, dell’euristica di base impiegata e che 
esso è più robusto di altre tecniche come il tabu search ed il simulated annealing, dal 
momento che non esistono parametri da definire i cui valori possono influire sulle 
prestazioni dell’algoritmo. 
L’obiettivo del lavoro di tesi è quello di definire, progettare ed implementare algoritmi 
di rollout  per la soluzione del problema del job shop scheduling e di valutarne le 
prestazioni in termini di qualità della soluzione e di tempi computazionali.  
Il lavoro di tesi è strutturato in 5 capitoli.  
Nel capitolo I vengono introdotti i problemi di scheduling, definendo alcuni concetti 
fondamentali e descrivendo la notazione comunemente adottata in letteratura. In 
particolare, si fa riferimento al problema del job shop scheduling, ai modelli 
matematici utilizzati per la sua rappresentazione formale ed ai metodi di soluzione 
proposti in letteratura.  
Introduzione 2
Nel capitolo II vengono introdotte le tecniche di programmazione dinamica e neuro-
dinamica dalle quali ha avuto origine l’algoritmo di rollout. Vengono, inoltre, descritte 
le fasi e le proprietà teoriche principali dell’algoritmo di rollout e di una sua versione 
modificata (fortified rollout). Infine, viene presentato l’algoritmo di rollout proposto 
per risolvere il problema del job shop scheduling. 
Nel capitolo III viene illustrata l’implementazione dell’algoritmo di rollout e della 
versione modificata.  
Nel capitolo IV sono riportati i risultati computazionali ottenuti dall’applicazione degli 
algoritmi di rollout ad un insieme di istanze del problema del job shop scheduling, 
analizzandoli in termini di qualità della soluzione calcolata e di tempi di esecuzione. 
Il capitolo V è dedicato alle conclusioni ed agli sviluppi futuri del presente lavoro. 
Introduzione 3
 
Capitolo I 
1.  
Il problema del job shop scheduling 
 
In questo capitolo vengono introdotti i problemi di scheduling, definendone i concetti 
fondamentali e descrivendo la notazione adottata per classificarli. In particolare, si fa  
riferimento al problema del job shop scheduling, descrivendo i modelli matematici utilizzati 
per la sua rappresentazione formale ed i metodi di soluzione proposti in letteratura.  
 
1.1. Definizioni e concetti fondamentali  
I problemi di scheduling sono da ricondursi alla determinazione di una distribuzione 
temporale di attività da svolgere su delle macchine.  
Nei problemi di scheduling su macchine, le risorse e le attività vengono indicate con i 
termini macchina e task, mentre il termine job si riferisce, in genere, ad un insieme di task 
tecnologicamente legati tra loro, ossia, un job è composto da più task che devono essere 
processati affinché il job risulti completo. Diverse informazioni possono essere associate ad 
ogni job: 
 
Introduzione 4
Tempo di processamento  Ω
ij
 : rappresenta il tempo necessario al completamento del job i-
esimo sulla  j-esima macchina. Se il job i è composto da più task, esso si riferisce al tempo 
necessario per completare il j-esimo task che compone il job. 
Tempo di rilascio (release date) r
j
: indica l'istante di tempo (rispetto a un tempo iniziale) 
prima del quale non è possibile iniziare l'esecuzione del job j-esimo.  
Tempo di consegna (due date) d
j
: indica l'istante di tempo (rispetto a un tempo iniziale) 
entro il quale l'esecuzione del j-esimo job dovrebbe essere terminata. In genere, la 
violazione di un tempo di consegna comporta dei costi. 
Peso w
j
: è un valore associato ad ogni job e rappresenta l'importanza relativa di un job 
rispetto agli altri; ad esempio, può rappresentare il costo di tenere il job nel sistema. 
 
Oltre alle caratteristiche relative ai job, è necessario considerare anche quelle relative al 
sistema. A tal proposito è utile ricordare che esiste una grande varietà di architetture di 
sistemi, che differiscono per numero di macchine e per l’ordine con cui i job vengono 
eseguiti.  
In particolare, è possibile considerare: 
 
Macchina singola: questo è evidentemente il caso più semplice, in cui i job richiedono tutti 
la stessa risorsa per essere eseguiti. In questo caso, in genere, ciascun job consiste di un 
singolo task e, dunque, si può parlare indipendentemente di job o task. 
Flow shop: in questo caso il sistema consiste di m macchine e ciascun job deve essere 
eseguito da ciascuna delle macchine successivamente, ossia l'ordine in cui i job visitano le 
macchine è lo stesso per tutti i job. 
Introduzione 5
Job shop: anche in questa architettura vi sono m macchine, ma ciascun job ha un proprio 
ordine con cui visitarle. Si noti che il Job shop è una generalizzazione del Flow shop. 
Open shop: in questo caso ciascun job può essere processato sulle m macchine senza alcun 
ordine specifico.  
 
Oltre alle caratteristiche dei job e delle macchine, vi sono ulteriori specifiche che 
contribuiscono a definire esattamente un problema di scheduling.  
Tali specifiche possono comprendere: 
 
Tempi di set-up: questa caratteristica è presente soprattutto nei problemi su singola 
macchina, e indica il tempo necessario a riconfigurare la macchina per eseguire un job dopo 
che se ne è completato un altro. Il tempo di set-up può essere indipendente o meno dalla 
sequenza con cui i job vengono assegnati alla macchina. 
Preemption: questa caratteristica indica che è consentito interrompere un job per permettere 
l'esecuzione di uno con priorità più alta. 
 
Gli obiettivi secondo i quali vengono prese le decisioni sull’assegnamento dei job alle 
macchine possono essere diversi. Per esprimerli formalmente, occorre introdurre le seguenti 
funzioni associate ai vari job: 
 
Tempo di completamento c
j
: indica il tempo in cui l'ultimo task del j-esimo job  termina. Se 
non sono ammesse interruzioni, c
j
  è dato dalla somma dell'istante di inizio dell'ultimo task 
di quel job più il tempo di processamento richiesto dal task. 
Introduzione 6
Lateness L
j
: rappresenta la differenza tra il tempo di completamento e la data di consegna 
del job j. Si noti che se è positiva, la “lateness” indica un ritardo, se negativa un anticipo 
rispetto al tempo di consegna. Si ha dunque:
jjj
dcL     . 
 
Diverse funzioni obiettivo possono costruirsi con queste grandezze, ad esempio: 
 
Massimo tempo di completamento o makespan (Cmax): è pari al tempo in cui l’ultimo job 
lascia il sistema di macchine; rappresenta, quindi, la misura del tempo necessario a 
completare tutte le attività. 
Massima lateness (Lmax): individua la violazione maggiore delle date di consegna, cioè lo 
scarto maggiore tra il tempo in cui si finisce di lavorare un job e quello in cui il job 
dovrebbe essere già consegnato. Si noti che potrebbe anche essere negativo, e in tal caso 
rappresenta un anticipo del job che termina prima della data di consegna prevista. 
 
In letteratura, per distinguere e classificare le varie tipologie di problemi di scheduling, si 
usa la classica notazione a tre campi di Graham (  ∆ |  Ε |  ϑ ) [22]; con  ∆ si identifica 
l’architettura del sistema ed il numero di macchine che lo compongono, con Ε le eventuali 
caratteristiche del problema di scheduling e con ϑ la funzione obiettivo.  
Per quanto concerne il sistema, le possibili architetture (Job shop, Flow shop e Open shop) 
sono indicate con le lettere J, F ed O, seguite dal numero che rappresenta le macchine che 
compongono il sistema. Ad esempio, il problema di job shop scheduling su m macchine, che 
ha come obiettivo la minimizzazione del makespan, verrà indicato con  Jm |  | Cmax.  
 
Introduzione 7
1.2. Definizione di schedule 
Una soluzione di un problema di scheduling prende il nome di schedule. In termini generali, 
uno schedule è una descrizione completa dell'utilizzo temporale delle macchine da parte dei 
job che devono essere processati.  
Nel caso in cui i task che compongono i job non possano essere interrotti, uno schedule è 
completamente specificato da un assegnamento di istanti di inizio a tutti i task.  
Spesso si distingue il concetto di sequenza da quello di schedule; la sequenza specifica solo 
l'ordine in cui i job devono essere eseguiti da ciascuna macchina, lo schedule ne specifica 
anche gli istanti d'inizio.  
Nell’esempio riportato nel seguito si considera un problema su singola macchina con tre 
job, ognuno dei quali è composto da un solo task; i relativi tempi di processamento (τ
i
) si 
trovano in tabella 1.1.  
Dato uno schedule S, indicheremo con S(j) l'istante di inizio di un job j. 
Introduzione 8
 
job τ
i 
1 10 
2 4 
3 5 
Tabella 1.1: Tempi di processamento 
 
Una possibile sequenza per il problema è σ = (3, 1, 2), ossia, supponendo che ciascun job 
inizi non appena il precedente è concluso, si ha lo schedule S definito da S(1) = 5, S(2) = 15, 
S(3) = 0.  
Uno schedule che rispetta tutti i vincoli del problema (vincoli tecnologici o l’impossibilità 
di interrompere un job durante il processamento) si definisce  schedule ammissibile. Gli 
schedule ammissibili possono essere suddivisi in quattro classi: inadmissible, semi-active, 
active e non-delay e la figura 1.1 illustra le relazioni che intercorrono tra esse. 
Si possono avere un numero infinito di schedule inadmissible, che corrispondono a 
soluzioni in cui le macchine sono caratterizzate da tempi di inattività. 
Uno schedule semi-active è ottenuto sequenziando le operazioni prima possibile, esso, 
quindi, non contiene tempi di inattività e nessuna operazione può essere completata prima 
senza cambiare la sequenza su una macchina. 
Uno schedule active è un sottoinsieme del precedente ed è caratterizzato dal fatto che 
nessuna operazione può essere completata prima cambiandone l’ordine, senza che un’altra 
operazione sia ritardata.  
Gli schedule non-delay sono un sottoinsieme degli schedule active; uno schedule di questo 
tipo è caratterizzato dal non avere macchine inoperose se esiste un’operazione disponibile al 
processamento.