Analisi e sperimentazione di algoritmi di scheduling bicriterio

 2
     Un’allocazione di uno o più intervalli di tempo su una o più macchine, per ogni lavoro, 
è comunemente detto schedule. Uno schedule si dice ammissibile se, ad ogni istante di 
tempo, ogni lavoro è processato da esattamente una macchina. Uno schedule è detto 
ottimale se minimizza (o massimizza) un dato criterio. 
     Un problema di scheduling può essere descritto utilizzando la notazione γβα || , dove 
α  rappresenta il numero di macchine, β  descrive le caratteristiche dei lavori, e γ  il 
criterio da ottimizzare o funzione obiettivo. 
 
1.2.1    Dati relativi ai lavori 
 
     Prima di tutto, i seguenti dati sono specificati per ogni lavoro 
j
J :  
 
• tempo di esecuzione 
j
p  nel caso di modello a singola operazione, oppure una 
collezione di tempi di esecuzione 
ij
p  nel caso di modello multi - operazione; 
• data di rilascio 
j
r , dopo la quale il lavoro può essere eseguito; 
•  funzione costo reale non decrescente 
j
f , che misura il costo )(tf
j
 dovuto al 
completamento del lavoro 
j
J  all’istante t; 
• data di consegna 
j
d , dopo la quale il lavoro è considerato in ritardo, e che può 
essere usata per definire
j
f ; 
• peso 
j
w , che definisce l’importanza del lavoro 
j
J , relativa agli altri lavori, e che 
può essere usata per definire 
j
f . 
 
1.2.2    Caratteristiche delle macchine 
 
     Il primo campo 
21
ααα =  specifica le caratteristiche delle macchine. Sia ο  il simbolo 
vuoto. Sia inoltre 
ij
p  il tempo di esecuzione del lavoro 
j
J  sulla macchina 
i
M . 
     Se {}RQP ,,,
1
οα ∈ , ogni lavoro
j
J  è composto da una singola operazione, che può 
essere processata su ogni macchina 
i
M , e più precisamente: 
 
• οα =
1
 : singola macchina; 
jj
PP =
1
 per ogni j; 
 3
• P=
1
α  : macchine parallele identiche; 
jij
PP =  per ogni 
i
M  e 
j
J ; 
• Q=
1
α  : macchine uniformi; ogni macchina 
i
M  ha una velocità 
i
s , cioè 
ijij
spp /=  per ogni 
i
M  e 
j
J ; 
• R=
1
α  : macchine indipendenti; la macchina 
i
M  processa il lavoro 
j
J  con una 
velocità dipendente dal lavoro 
ij
s , cioè 
ijjij
spp /=  per ogni 
i
M  e 
j
J . 
      
     Se {}OFJ ,,
1
∈α  ogni lavoro 
j
J  è composto da un insieme di operazioni 
{ }
jmjj
j
OOO
,,2,1
,...,, , e più precisamente: 
 
• J=
1
α : job shop; le operazioni di ogni lavoro 
j
J  formano una sequenza 
{ }
jmjj
j
OOO
,,2,1
,...,,  che deve essere processata in questo preciso ordine, ed ogni 
operazione 
ij
O  deve essere processata su una data macchina 
ij
µ , richiedendo 
ij
p  
unità di tempo; 
• F=
1
α : flow shop; caso particolare del job shop, dove mm
j
=  e 
iij
M=µ  per 
ogni lavoro 
j
J ; 
• O=
1
α : open shop; simile al flow shop, eccetto che le operazioni di ogni lavoro
j
J   
possono essere processate in un ordine qualsiasi. 
 
     Se 
2
α  è un intero positivo, allora m è costante ed uguale a 
2
α  (problema modello). Se 
οα =
2
, allora m è una variabile ; il valore di m è specificato come parte del problema. 
Notare che οα =
1
 se e solo se 1
2
=α . 
 
1.2.3 Caratteristiche dei lavori 
 
     Il secondo campo { }
precj
rpmtn ββ ,,∈  indica le seguenti caratteristiche dei lavori: 
 
• se pmtn è presente, è consentita l’interruzione (in inglese preemption) 
dell’esecuzione dei lavori. Questo vuol dire che, una volta interrotta, l’esecuzione 
può riprendere in seguito. In caso contrario, cioè se l’interruzione non è consentita, 
una volta iniziata l’esecuzione di un lavoro su una macchina, essa deve essere 
necessariamente completata; 
 4
• se 
j
r  è presente, ad ogni lavoro può essere associata una data o istante di rilascio. 
In caso contrario, per ogni lavoro 
j
J , 
j
r = 0; 
• se è presente un vincolo di precedenza 
prec
β , esiste una relazione di precedenza p  
fra i lavori, cioè se 
kj
JJ p , allora 
j
J  deve essere completato prima che inizi 
l’esecuzione del lavoro
k
J . Se chain
prec
=β , la relazione di precedenza forma una 
catena. Se tree
prec
=β , la relazione p  forma un albero. Se prec
prec
=β , allora p  
è un ordinamento parziale arbitrario. Se 
prec
β  non è presente, i lavori possono 
essere processati in un ordine qualsiasi. 
 
1.2.4    Funzioni obiettivo 
 
     Il terzo campo γ  specifica il valore da ottimizzare o funzione obiettivo. Dato uno 
schedule ammissibile, possiamo calcolare per ogni lavoro 
j
J  i seguenti valori: 
 
• il tempo di completamento 
j
C , cioè l’istante di tempo nel quale l’esecuzione del 
lavoro 
j
J  è completata; 
• il flow time 
jjj
rCF −= , cioè l’intervallo di tempo nel quale il lavoro 
j
J  rimane 
nel sistema; 
• il ritardo o lateness 
jjj
dCL −= , cioè la quantità di tempo della quale il lavoro 
j
J  
eccede la sua due date 
j
d ; la lateness può essere negativa se il lavoro è completato 
prima della sua due date; 
• la tardiness { }0,max
jj
LT = , che è pari alla lateness se essa è non negativa, mentre 
vale zero altrimenti; 
• la unit penalty  
0
1
jjj
j
UseCd
U altrimenti
=≤
⎧
⎪
⎨
=
⎪
⎩
  
            cioè un’unità che penalizza i lavori in ritardo rispetto alla due date. 
 
     Il costo 
j
f  per ogni lavoro 
j
J  di solito è calcolato considerando una delle variabili 
descritte in precedenza, oppure il prodotto fra il peso 
j
w  ed una di esse. La funzione 
 5
obiettivo può essere una qualunque funzione dei costi 
j
f , nj ,...,1= . Comuni funzioni 
obiettivo sono tipicamente espresse nella forma 
∑
j
j
f , oppure 
jj
fmax . 
     Esempi di comuni criteri sono il total weighted completion time 
jj
j
wc
∑
, il massimo 
tempo di completamento o makespan 
max
max
jj
CC= , e la massima lateness 
max
max
jj
LL= . 
 
1.2.5    Esempi di problemi di scheduling 
 
     Consideriamo alcuni esempi di problemi di scheduling utilizzando la notazione a tre 
campi. Nel problema 
∑ jjj
Cwr ||1  si vuole minimizzare la somma pesata dei tempi di 
completamento su una macchina, con date di rilascio. Nel problema 
max
3| , |PpmtnprecL 
si vuole minimizzare la massima lateness, su tre macchine parallele identiche, con vincoli 
di precedenza generici fra i lavori, ed interruzione consentita. 
 
 
1.3     Complessità asintotica 
 
1.3.1    Introduzione 
 
     In questa sezione saranno introdotte alcune nozioni basilari sui problemi di 
ottimizzazione e sulle classi di complessità, che saranno utili per classificare molti dei 
problemi di scheduling come problemi “difficili”. 
     Un problema di ottimizzazione di qualsiasi tipo, può essere rappresentato tramite la 
coppia 
()
,I S , dove I è un insieme di istanze del problema, e S è un insieme di soluzioni. 
Più precisamente, un problema è detto: 
• di decisione, se 
{ }
0,1S = , ovvero bisogna decidere se l’istanza di input verifica o 
no una determinata proprietà; 
• di ricerca, se bisogna determinare una qualsiasi soluzione per l’istanza di input; 
• di ottimizzazione, se bisogna minimizzare o massimizzare una determinata misura 
della soluzione restituita. 
 6
     La complessità di un problema è di solito espressa come funzione della dimensione 
dell’input, intesa come grandezza correlata in modo polinomiale alla lunghezza di una 
qualsiasi codifica naturale dell’input che sia semplice e concisa (senza ridondanze), con 
numeri in base maggiore o uguale a 2. 
     Definiamo ora la nozione di complessità di un algoritmo. 
 
Definizione 1.1 
     Sia 
()
A
tx il tempo di esecuzione di un algoritmo A per un input x. Il tempo di 
esecuzione di A nel caso peggiore è: 
 
( ) ( )
{ }
max |
AA
tn tx x n= ≤ . 
 
Quindi, un algoritmo A ha complessità: 
 
• 
()
(
Ogn se 
() ( )
( )
{ }
00
(): , 0 () (),
A
tn Ogn fn cntaliche fn cgn nn==∃ ≤≤⋅∀≥; 
• 
()
(
gnΩ se 
() ( )
( )
{ }
(): , 0 () (),
A
t n g n f n c n tali che c g n f n n n=Ω = ∃ ≤ ⋅ ≤ ∀ ≥ ; 
• 
()
(
gnΘ  se 
() ( )
( )
A
tn gn=Θ  cioè 
( ) ( )
( )
A
tn Ogn=  e 
( )()
(
A
tn gn=Ω . 
 
Definiamo ora la nozione di complessità di un problema. 
 
Definizione 1.2 
     Un problema Π  ha complessità: 
  
• 
()
(
Ogn  se esiste un algoritmo A che lo risolve, avente complessità 
( )
(
Ogn ; 
• 
()
(
gnΩ  se ogni algoritmo A che lo risolve, ha complessità 
()
(
gnΩ ; 
• 
()
(
gnΘ  se Π  ha complessità 
( )
( )
gnΩ  e 
( )
( )
Ogn . 
 
 7
1.3.2     Problemi di decisione 
 
     I problemi di decisione, per convenzione sono espressi nella forma istanza e 
“domanda” sull’istanza stessa. 
 
Esempio: (SAT) 
 
Istanza = Formula CNF  f , definita su un insieme di variabili V. 
Domanda = Esiste un assegnamento di verità 
( )
:0,1Vτ →  che soddisfa f ? 
 
L’insieme di istanze I di un problema di decisione, è definito nel seguente modo: 
 
I YN= ∪  
dove: 
 
• Y = insieme di istanze positive, ovvero con soluzione 1; 
• N = insieme di istanze negative, ovvero con soluzione 0. 
 
Definizione 1.3 
     Un algoritmo A risolve un problema Π , se e solo se per ogni istanza x I∈ , A risponde 
1 se e solo se x Y∈ . 
 
Definizione 1.4 (Algoritmo non deterministico) 
     Un algoritmo non deterministico è composto da due fasi fondamentali. 
 
Fase 1 :  
Genera non deterministicamente una soluzione, o più in generale una struttura di soluzione 
y. 
 
Fase 2 : 
A partire dall’istanza x e dalla struttura y, verifica se x è un’istanza positiva. 
La complessità di un algoritmo non deterministico, è il costo della fase 2. 
 
 
 8
Definizione 1.5 
     Un algoritmo non deterministico A risolve Π  se e solo se esiste una struttura y tale per 
cui A risponde 1 se e solo se x Y∈ . 
 
Osservazioni 
1) Un algoritmo deterministico è meno potente perché non esegue la fase 1. 
2) Dato un qualsiasi algoritmo deterministico A che risolve Π , esiste un algoritmo 
non deterministico, avente la stessa complessità, che risolve Π  nel seguente modo: 
Esegue la fase 1, e coincide con A nella fase 2, ignorando la struttura y. 
 
     Un algoritmo non deterministico può essere definito come una procedura che, per le 
istanze con risposta affermativa o positive, verifica in tempo polinomiale se tale risposta è 
effettivamente affermativa. 
 
1.3.3    Classi di complessità 
 
     Definiamo ora le più importanti classi di complessità. Sia 
()
(
Time f n  la classe dei 
problemi di decisione risolubili in tempo 
( )
( )
Ofn  da algoritmi deterministici. Sia inoltre 
()
(
NTime f n  la classe dei problemi di decisione risolubili in tempo 
( )
(
Ofn  da 
algoritmi  non deterministici. 
 
Definizione 1.6 (Classe P) 
     La classe P, è la classe di tutti i problemi di decisione risolubili in tempo polinomiale 
deterministicamente, ossia: 
 
()
0
k
k
PTimen
∞
=
=
U
. 
 
Definizione 1.7 (Classe NP) 
     La classe NP, è la classe di tutti i problemi di decisione risolubili in tempo polinomiale 
non deterministicamente, ossia: 
 
 9
()
0
k
k
NP NTime n
∞
=
=
U
. 
 
     Le classi P e NP sono “robuste” rispetto allo schema di codifica dell’input ed al 
modello di calcolo utilizzati. 
     Si presume che le due classi P e NP non coincidano, poiché nessuno fino ad oggi è 
riuscito a dimostrare il contrario. 
 
Definizione 1.8 (NP - Completezza) 
     I problemi NP-Completi sono i più “difficili” in NP, e tali che se PNP≠ , allora non 
appartengono a P. Se si riuscisse a trovare un problema NP-completo appartenente a P, 
questa sarebbe la dimostrazione di P=NP. 
 
Definizione 1.9 (Riduzione polinomiale) 
     Siano A e B due problemi in forma di decisione. AB→ , ovvero A si riduce a B, se per 
ogni istanza aA∈  esiste un algoritmo polinomiale che trasforma l’istanza a in un’istanza 
bB∈  tale che se l’istanza b è positiva, allora anche a è positiva. Lo stesso vale se l’istanza 
b è negativa. 
     Un problema Π  si dice NP-Completo se ,QNPQ∀ ∈→Π, dove →  è la riduzione 
polinomiale fra problemi appena definita, cioè Π  è almeno tanto difficile quanto tutti i 
problemi in NP. 
 
1.3.4     Problemi di ottimizzazione 
 
     Un problema di ottimizzazione è caratterizzato da una quadrupla (I , S , M , goal), dove: 
1) I  =  Insieme delle istanze di input; 
2) S  = Insieme delle soluzioni ammissibili per le istanze in input; 
3) M = Funzione obiettivo che associa ad ogni input x I∈ , e soluzione ammissibile 
()
ySx∈ , un valore 
( )
,mxy N∈ ; 
4) Goal = 
{ }
min, max . 
 
Definizione 1.10 
     
()
*
Sx è l’insieme delle soluzioni ottime per x, ossia tali che se 
()
**
ySx∈ , allora:  
 10
()
( ) ( )
{ }
*
,min,|mxy mxy y Sx=∈; 
oppure:  
()
( ) ( )
{ }
*
,max,|mxy mxy y Sx=∈. 
     Indichiamo con 
()
*
mx la misura di una soluzione ottima per x, ossia 
()
( )
**
,mx mxy=  
per qualche 
()
**
ySx∈ . 
 
0sservazione 
     Ad ogni problema di ottimizzazione è associato un problema di decisione soggiacente, 
definito nel seguente modo: 
1) Si introduce nell’istanza di input un valore intero k. 
2) Ci si chiede se esiste una soluzione ammissibile, la cui misura è minore o uguale a k 
se goal=min, oppure maggiore o uguale a k se goal=max. 
 
     Risolvere un problema di ottimizzazione  è difficile almeno quanto risolvere il problema 
di decisione soggiacente ad esso associato. Infatti, se si possiede un algoritmo efficiente 
che risolve il problema di ottimizzazione, allora si possiede anche un algoritmo efficiente 
per il problema di decisione soggiacente, che consiste semplicemente nell’eseguire il 
primo, e nel chiedersi se la misura della soluzione restituita è minore o uguale a k (min), 
oppure maggiore o uguale a k (max). Viceversa, se il problema di decisione soggiacente 
non è risolubile efficientemente, nemmeno il problema di ottimizzazione può esserlo. 
  
Definizione 1.11 
     Definiamo ora le seguenti classi di complessità per problemi di ottimizzazione: 
 
PO = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente 
appartiene alla classe P. 
 
NPO = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente  
                appartiene alla classe NP. 
 
NP-Hard = Classe dei problemi di ottimizzazione il cui problema di decisione soggiacente  
è NP-completo. 
 
 11
Definizione 1.12 (Min Multiprocessor Scheduling) 
     Il problema denominato Min Multiprocessor Scheduling, può essere definito nel 
seguente modo: 
 
Istanza :  Insieme di task (lavori) T, numero di macchine o processori h, e lunghezza o 
tempo di esecuzione 
j
p  associato ad ogni task. 
Soluzione : Uno schedule per T, ossia una funzione 
[ ]
:1,f Th→ . 
Misura : Tempo di completamento dello schedule, ossia: 
 
[]
()
1,
|
max
jj
j
ih
tft i
p
∈
=
∑
. 
 
     Questo problema appartiene alla classe NP-Hard, poiché il problema di decisione 
soggiacente è NP-completo. Ciò si dimostra utilizzando la tecnica di riduzione 
polinomiale, a partire dal famoso problema denominato PARTITION, che a sua volta è 
NP-completo. 
     Ovviamente anche l’estensione al caso bicriterio del problema Min Multiprocessor 
Scheduling  che sarà definito in seguito, appartiene alla classe NP-Hard. 
 
 
1.4     Algoritmi di approssimazione ed algoritmi On Line 
 
     In questa sezione, saranno descritti e confrontati gli algoritmi di approssimazione, gli 
algoritmi on line, ed i metodo più comuni utilizzati per valutarne le prestazioni. 
In primo luogo, diamo alcune semplici definizioni. 
     L’estremo superiore di un insieme non vuoto A di numeri reali, denotato con  
Sup A, è il più piccolo numero reale u, tale che xu ≥ , per ogni Ax∈ . 
     L’estremo inferiore di A, denotato Inf A, è il più grande numero reale l, tale che xl ≤  
per ogni Ax∈ .  
     Se A è finito, allora sia Sup A che Inf A appartengono ad A. In questo caso, essi sono 
chiamati minimo e massimo di A, denotati con min A e max A rispettivamente.