scheduling a macchina singola

Sistemi Organizzativi
docente: Stefano Smriglio
[email protected]
Pre-requisiti:
Classi di complessità
Programmazione Lineare (Intera)
Metodo branch-and-bound
Cammini minimi su grafi
Materiale didattico:
• M. Pinedo, Scheduling (Systems, Models and Algorithms) –
Prentice Hall
• A. Agnetis, dispense http://www.dii.unisi.it/~agnetis/didattica
• Trasparenti dalle lezioni http://www.di.univaq.it/~oil
Parte I:
Scheduling a macchina singola
Indice
1. Introduzione: esempi, elementi di un problema di
scheduling, notazione. Formulazioni PLM, PLB
2. Problemi a macchina singola
• 1//ΣwjCj
algoritmo WSPT
• 1/chain/ΣwjCj
algoritmo polinomiale
• 1/prec/hmax
algoritmo di Lawler
• 1/rj,prmp/Lmax regola preemptive EDD
• 1/rj/Lmax
complessità, branch-and-bound
• 1//ΣUj
algoritmo di Moore
• 1//Σhj
Programmazione dinamica
• 1//ΣTj
algoritmo pseudo-polinomiale
• 1//ΣwjTj
branch-and-bound
Introduzione
problemi di scheduling
esempi
classificazione
Esempio
Silvia (S) e Francesca (F) giungono nello stesso
momento ad una macchina fotocopiatrice. F deve fare 1
fotocopia, S ne deve fare 100.
Il galateo imporrebbe a S di lasciar passare per prima F,
che ha un compito molto più breve.
È una buona idea?
Analisi. Supponiamo che l’esecuzione di una fotocopia
richieda 3 secondi. Due casi:
S precede F
0
303
300
Attesa totale = 300 + 303 = 603
3
0
F precede S
303
Attesa totale = 3 + 303 = 306
Esempio
E se Francesca F arrivasse all’istante rf?
S
0
F
303
300
rf
Attesa totale = 300 + 303 – rf =
= 603 – rf
Di nuovo, il galateo imporrebbe a Silvia di interrompere le
proprie copie in favore di Francesca:
rf + 3
Attesa totale = 3 + 303 = 306
0
rf
303
Ricapitolando
• Attività: 2 blocchi di fotocopie (di durata nota)
• Risorse: una macchina fotocopiatrice
• Vincoli:
Capacità: al più una fotocopia alla volta
(caso 2) F non può iniziare prima dell’istante rf
• Misura: attesa complessiva presso la macchina
fotocopiatrice
• Rappresentazione di una soluzione: diagramma di Gantt
S
0
303
F
300
CPU scheduling
• Il sistema operativo disciplina l’accesso alla CPU dei
diversi programmi di calcolo.
• tecnica time-sharing (Linux): il tempo di CPU è suddiviso
in intervalli (definiti dal timer interrupt) e, in ogni intervallo, è
possibile eseguire al più un processo.
• diversi obiettivi: rispondere prontamente a ciascun
processo, evitare interruzioni prolungate, evitare ritardi nei
processi più urgenti.
• Linux attribuisce dinamicamente una priorità ai processi.
Ad es., la priorità è proporzionale all’attesa del processo
CPU scheduling
• Attività: programmi
• Risorse: CPU
• Vincoli: Capacità: al più un programma in ciascun
intervallo per ciascuna CPU
• Misure:
• tempo massimo di attesa di un programma
• tempo di completamento di tutti i programmi
• ritardi nei processi “urgenti”
Scheduling dei velivoli in atterraggio
• La torre di controllo (ATC) ha il compito di assegnare
una pista ed un istante di atterraggio a ciascun velivolo
nel proprio campo radar (area terminale)
• Ogni velivolo ha una finestra temporale [r,s] definita da
due istanti di atterraggio estremi, a seconda che il
velivolo viaggi:
- alla sua massima velocità (istante r)
- in modalità di minimo consumo (istante s)
• Un velivolo in atterraggio impegna la pista per un
tempo noto ma genera turbolenza: quello successivo
deve attendere un tempo di “separazione” (funzione
delle dimensioni dei velivoli)
Scheduling dei velivoli in atterraggio
• Ad ogni velivolo è associato un orario di atterraggio
predeterminato (e pubblicato nelle tabelle)
• “L’importanza” di un velivolo dipende da fattori quali la
dimensione, la compagnia, la distanza percorsa…
• Attività: atterraggi
• Risorse: k piste
• Vincoli:
•Capacità: su ogni pista, al più un atterraggio in un
certo istante
• finestre temporali di atterraggio
• separazione fra atterraggi consecutivi
• Misura:
• somma (pesata in base all’importanza) dei ritardi
rispetto all’orario pubblicato
Ancora nella vita quotidiana…
Aldo (A), Bruno (B), Carlo (C), Duilio (D) condividono un
appartamento e, ogni mattino, ricevono 4 giornali:
Financial Times (FT), Guardian (G), Daily Express (DE),
Sun (S).
Ognuno ha i propri gusti…inizia la lettura ad una certa
ora, legge i giornali nella sua sequenza preferita e
(ciascuno) per un tempo prefissato:
lettore inizio
Aldo
Sequenza giornali (min.)
8.30 FT(60)
G (30)
DE (2)
S(5)
Bruno 8.45
G(75)
DE(3)
FT(25)
S(10)
Carlo
8.45
DE(5)
G(15)
FT(10)
S(30)
Duilio
9.30
S(90)
FT(1)
G(1)
DE(1)
Ancora nella vita quotidiana…
inoltre, ciascun lettore:
rilascia un giornale solo dopo averlo letto
completamente.
termina la lettura di tutti i giornali prima di uscire.
infine, i quattro lettori attendono che tutti abbiano
terminato di leggere prima di uscire di casa
Problema:
A che ora A, B, C, D riescono (finalmente!) ad
uscire?
Interpretazione
lettore inizio
Aldo
Sequenza giornali (min.)
8.30 FT(60)
G (30)
DE (2)
S(5)
Bruno 8.45
G(75)
DE(3)
FT(25)
S(10)
Carlo
8.45
DE(5)
G(15)
FT(10)
S(30)
Duilio
9.30
S(90)
FT(1)
G(1)
DE(1)
A
FT
G
B
D
S
DE
C
determinare in quale
sequenza
ciascun
giornale
“accetta”
i
lettori in modo da
minimizzare il tempo di
lettura totale.
Soluzioni
lettore inizio
Aldo
Sequenza giornali (min.)
8.30 FT(60)
G (30)
DE (2)
S(5)
Bruno 8.45
G(75)
DE(3)
FT(25)
S(10)
Carlo
8.45
DE(5)
G(15)
FT(10)
S(30)
Duilio
9.30
S(90)
FT(1)
G(1)
DE(1)
una possibile soluzione:
giornale Sequenza lettori
FT
A
D
C
B
G
B
C
A
D
DE
C
B
A
D
S
D
A
C
B
ESERCIZIO:
valutare l’ora in cui A,B,C
e D escono di casa
giornale Sequenza lettori
ESERCIZIO:
data la soluzione in tabella
valutare l’ora in cui A,B,C
e D escono di casa
FT
A
D
C
B
G
B
C
A
D
DE
C
B
A
D
S
D
A
C
B
D
FT
A
C B
D
B
G
C A
B
DE
A D
C
A
D
S
8.30
9.0
9.00
10.00
C B
11.00
11.51
Enumerazione totale
• Il numero di soluzioni è (4!)4 = 331.776
• per un problema con n lettori e m giornali diventa (n!)m.
• esaminando 10.000 soluzioni al secondo (4 giornali e n
lettori):
n
tempo
5
354 min
10
2 · 1017
giorni
In generale
Con il termine scheduling si indica l’allocazione
temporale di risorse scarse ad attività
Elementi di un problema di scheduling:
job: attività da svolgere – insieme J = {1,…,n}
Fotocopia, esecuzione di un programma di calcolo
Un job può rappresentare una singola attività o un
insieme di attività (task) tecnologicamente legate
macchine: risorse che eseguono le attività – insieme
M={1,…,m}
Fotocopiatrice, CPU, giornali
Attributi dei job
• tempo di processamento pij durata
processamento del job j sulla macchina i
del
• release date rj tempo in cui j arriva nel sistema,
rendendosi disponibile al processamento
• due date dj tempo entro il quale si desidera che il
job j sia completato (data di consegna)
• peso wj indica l’importanza del job j
Classificazione
Il processamento di un job su una macchina è detto
operazione.
I problemi di scheduling si classificano in base alle
caratteristiche dei task e all’architettura delle
macchine
Notazione a tre campi: α/β
β/γγ:
α descrive il sistema di macchine
β rappresenta vincoli e modalità di processamento (0,
1 o più componenti)
γ indica l’obiettivo
Campo α
Macchina singola (1) : ciascun job richiede una singola
operazione da eseguirsi sull’unica macchina disponibile
Macchine identiche parallele (Pm) : ciascun job richiede
una singola operazione da eseguirsi su una qualunque delle
m macchine identiche.
1
2
m
Campo α
Flow shop (Fm) : Ciascun job è composto di m task,
ciscuno da eseguirsi su una macchina secondo una
sequenza fissata, uguale per tutti i job.
1
2
m
Job shop (Jm) : Ciascun job j è composto di m(j) task,
ciscuno da eseguirsi su una macchina secondo una
sequenza fissata, dipendente da j
Campo β
• Release dates (rj): il job j non può iniziare il
processamento prima dell’istante rj
• Preemption
(prmp):
è
ammesso
interrompere
un’operazione per iniziarne una nuova. Il processamento
eseguito prima dell’interruzione non va perso: quando
l’operazione viene ripresa, essa richiede solo il tempo
rimanente di processamento
job
1
2
pj
3
4
2
1
1
1
5
7
schedule ammissibile
Campo β
prec: è dato un grafo G = (N, A) diretto e aciclico che
rappresenta una relazione di precedenza fra job. Un job j
può iniziare solo se tutti i suoi predecessori sono stati
completati
2
4
1
1
3
5
2
4
3
5
schedule non ammissibile
chain: caso speciale in cui ogni componente connessa
del grafo è un cammino orientato (catena)
Campo β
•Tempi di set-up (sjk): tempo richiesto per il
riattrezzaggio delle macchine fra i job j e k. Se dipende
dalla macchina i, si esprime con sijk
• breakdown (brkdwn): le macchine non sono sempre
disponibili, ma hanno periodi fissati di interruzione del
servizio
Definizioni
tempo di completamento del job j
Cj
Lj = Cj–dj
lateness del job j
Tj = max(Lj,0)
tardiness del job j
Uj = 1 se Cj>dj e 0 altrimenti
1
job
1
2
pj
7
8
dj
9
11
0
2
7
15
C1= 7
L1= −2
T1 = 0
C2= 15
L2= 4
T2 = 4
U1= 0
U2= 1
Campo γ: funzioni obiettivo
• Makespan (Cmax) : max (C1, …, Cn) tempo di
completamento dell’ultimo job
• Massima Lateness (Lmax) : Lmax =max (L1, …, Ln)
• Tempo totale pesato di completamento (ΣwjCj)
o (weighted flow-time)
• Tardiness totale pesata (ΣwjTj)
• Numero di tardy job (ΣUj)
tutte funzioni obiettivo regolari cioè non-decrescenti
in C1, …, Cn
Esempio
job
1
2
wj
2
3
pj
7
8
dj
9
11
1
0
2
7
15
Lmax= 4
ΣwjTj = 12
ΣwjCj = 59
ΣUj = 1
Sequenze e schedule
• Si definisce sequenza una permutazione dei job
che definisce l’ordine con cui i job sono processati su
una certa macchina
• Si definisce schedule un assegnamento di un
istante di inizio a ciascuno dei task di ogni job (se
prmp, istanti di inizio di ciascuna delle parti in cui
viene suddiviso un task)
Schedule nondelay
uno schedule ammissibile è detto nondelay se
nessuna macchina è ferma quando esiste
un’operazione disponibile al processamento
In molti casi (sempre se prmp) le soluzioni ottime
sono nondelay. Ciò non è vero in generale
ESERCIZIO: schedule nondelay
dato il seguente problema P2/prec/Cmax
2
10
1
job
1
2
3
4
5
6
7
8
9 10
pj
7
6
6
1
2
1
1
7
7 14
3
5
8
4
costruire uno schedule nondelay
e verificarne l’ottimalità
6
7
9
ESERCIZIO: schedule nondelay
Soluzione nondelay:
M2
M1
1
46 5 7
2
8
9
3
10
32
0
10
20
30
Soluzione ottima:
1
M2
M1
46 5 7
2
8
3
9
10
27
0
10
fermo macchina “forzato”
20
30
1.1 Scheduling a macchina singola
Formulazioni di Programmazione Lineare
Booleana e Mista (PL(0-1)-PLM)
Formulazione disgiuntiva
Variabili decisionali “naturali”:
t j ∈ Rn
istante di inizio del job j, j = 1, …, n
Macchina a capacità unitaria:
i precede j ⇒
t j ≥ ti + pi
j precede i ⇒
ti ≥ t j + p j
valgono in
alternativa !!
Variabili aggiuntive (binarie):
1

yij = 
0

se i precede j
se j precede i
Formulazione disgiuntiva (PLM)
i precede j ⇒ yij = 1 ⇒
t j ≥ ti + pi
j precede i ⇒ yij = 0 ⇒ ti ≥ t j + p j
Formulazione disgiuntiva
(1 − yij )M + t j − ti ≥ pi
yijM + ti − t j ≥ pj
tj ≥0
∀i, j ∈ J
∀i, j ∈ J
∀j ∈ J
yij ∈ { 0,1}
∀i , j ∈ J
M costante grande (quanto?)
Problemi minsum: 1//∑j wjCj
min
∑ w (t
j
i
+ pi ) =
j ∈J
∑w t +∑w p
j j
j ∈J
j ∈J
(1 − yij )M + t j − ti ≥ pi
yijM + ti − t j ≥ pj
tj ≥0
n2+n variabili
2n2 vincoli
∀i, j ∈ J
∀i, j ∈ J
∀j ∈ J
yij ∈ { 0,1}
j
∀i , j ∈ J
j
Esercizio
Formulare come problema di PLM la seguente istanza del
problema 1/rj/∑j wjCj
job
1
2
3
pj
3
1
2
rj
0
2
0
wj
3
2
4
Problemi minsum: 1//∑j wjTj
min
∑w
j
max{ t j + p j − d j ,0 }
j ∈J
(1 − yij )M + t j − ti ≥ pi
yijM + ti − t j ≥ pj
tj ≥0
∀i, j ∈ J
∀j ∈ J
yij ∈ { 0,1}
∀i , j ∈ J
∀i , j ∈ J
RICHIAMO: Funzioni convesse lineari a tratti
c 3x + d3
max (c iT x + di )
c1x + d1
i =1,...,m
c 2 x + d2
x
min
max (c iT x + di )
i =1,...,m
Ax ≥ b
è il più piccolo valore z per cui
z ≥ c iT x + di i = 1,..., m
min
z
Ax ≥ b
c iT x + di ≤ z
i = 1,..., m
Formulazione PLM
max{ t j + p j − d j ,0 }
tj
0
dj − pj
min
min ∑w j max{t j + p j − d j ,0}
j ∈J
∑w f
j
j
f j ≥ t j + pj − dj , j ∈ J
fj ≥ 0
Formulazione PLM
min
∑w f
j
j
f j − t j ≥ pj − dj ,
j ∈J
(1 − yij )M + t j − ti ≥ pi
yijM + ti − t j ≥ pj
tj ≥0
fj ≥ 0
∀i, j ∈ J
∀j ∈ J
yij ∈ { 0,1}
∀i , j ∈ J
∀i , j ∈ J
Problemi min-max: Lmax
min f
f − t j ≥ pj − dj ,
j ∈J
(1 − yij )M + t j − ti ≥ pi
yijM + ti − t j ≥ pj
tj ≥0
f ≥0
∀i, j ∈ J
∀j ∈ J
yij ∈ { 0,1}
∀i , j ∈ J
∀i , j ∈ J
Formulazioni Time-indexed
Orizzonte temporale [0,T] discretizzato in periodi di durata
unitaria. Il periodo t concide con l’intervallo di [t − 1, t]
Variabili binarie: xjt =1 se j inizia nel periodo t; 0 altrimenti
vincolo 1 (Completezza): ogni job inizia in un qualche t
T − p j +1
∑ x jt = 1,
j = 1,..., n
t =1
j
j
j
j
1
2
3
4
5
T≥Σpj
Formulazioni Time-indexed
vincolo 2 (Capacità): al più un job processato nel periodo t
un job occupa il periodo t se inizia nell’intervallo [t − pj+1, t]
j
j
j
t
quindi:
n
min( t ,T − p j + 1 )
j =1
js
s = max( 1 , t − p j + 1 )
∑
∑x
≤ 1,
t = 1,..., T
Formulazione PL(0-1)
n T − p j +1
min
∑
∑ c jt x jt
j =1
t =1
T − p j +1
∑ x jt = 1,
t =1
n
min( t ,T − p j + 1 )
j =1
js
s = max( 1 , t − p j + 1 )
∑
∑x
x jt ∈ { 0,1}, j = 1,...,n;
nT variabili; n + T vincoli
cjt costo di assegnazione
del job j all’istante t
j = 1,..., n
≤ 1,
t = 1,..., T
t = 1,...,T − p j + 1
Funzioni obiettivo (min-sum)
se j inizia nel periodo t si ha Cj = t+pj−1
j
t+pj−1
t
tempo totale di completamento:
n T − p j +1
cjt = wj(t+pj−1)⇒
∑ ∑w (t + p
j
j =1
n
j
− 1)x jt = ∑w jC j
t =1
j =1
tardiness totale:
c jt = w j max{ 0, t + p j − d j − 1} ⇒
n
T − p j +1
∑ ∑w
j =1
t =1
n
j
max( 0, t + p j − d j − 1)x jt =
∑w T
j
j =1
j
Esercizio
Formulare come problema di PL(0-1) la seguente istanza
del problema 1/rj/∑j wjCj
job
1
2
3
pj
3
1
2
rj
0
2
0
wj
3
2
4
Vincoli di precedenza
vincolo 3 (Precedenza i→j): se il job i non è iniziato nei
periodi 1,2,…,t allora il job j non può iniziare nei periodi 1,
2,…, t + pi
j
i
t
quindi:
t + pi
∑x
s =1
t
js
≤
∑x
r =1
ir
,
t = 1,..., T − pi − p j + 1
1.2 Tempo totale pesato di completamento
Σ w jC j
nondelay schedule
Proprietà 0.1 Dato un problema del tipo 1//γ con γ
funzione obiettivo regolare, esiste uno schedule
ottimo in cui la macchina processa ininterrottamente
dall’istante 0 all’istante Cmax= Σpj
Tempo totale pesato di completamento
1// ΣwjCj
Definiamo Weighted Shortest Processing Time
(WSPT) una regola che ordina i job per valori non
crescenti del rapporto wj/pj
Sussiste il seguente
Teorema 1.1 La regola WSPT calcola una soluzione
ottima del problema 1//ΣwjCj
Dimostrazione. (Per contraddizione)
Assumiamo che S sia uno schedule ottimo e che non
rispetti WSPT
Dimostrazione
Allora devono esserci in S due job adiacenti, diciamo j
seguito da k tali che
wj/pj < wk/pk
Assumiamo che il job j inizi all’istante t.
Eseguiamo uno scambio dei job j e k ottenendo un
nuovo schedule S'
S
j
k
t+pj
k
S′
t
j
t+pk
t+pj+pk
Dimostrazione
S
j
k
k
S′
t
j
t+pj+pk
Il tempo totale (pesato) di completamento dei job che
precedono e seguono la coppia (j,k) non è modificato
dallo scambio. Il contributo dei job j e k in S è:
(t+pj)wj + (t+pj+pk)wk
mentre in S' è:
(t+pk)wk + (t+pk+pj)wj
Dimostrazione
in S]
(t+pj)wj + (t+pj+pk)wk
in S']
(t+pk)wk + (t+pk+pj)wj
Eliminando i termini uguali:
in S]
pjwk
in S']
pkwj
Quindi, se wj/pj < wk/pk, risulta pk wj < pj wk, cioè il
tempo totale pesato in S' è strettamente inferiore a quello
in S, contraddizione
Vincoli di precedenza
1/prec/ ΣwjCj
Nel caso generale il problema è NP-Hard.
Consideriamo invece il caso in cui le precedenze sono
rappresentate da un insieme di catene in parallelo:
1/chain/ΣwjCj
Per questo caso esiste un algoritmo di soluzione polinomiale.
Catene non interrompibili
Date due catene:
1→2→…→k
k+1 → k+2 → … → n
Minimizziamo ΣwjCj con il vincolo che i job di ciascuna
catena debbano essere processati consecutivamente.
Lemma 1.2 Se
k
n
∑wj
j =1
k
∑ pj
j =1
∑ wj
>
j =k +1
n
∑ pj
j =k +1
allora la catena 1, …,k precede la catena k+1, …, n
Dimostrazione
• Per la sequenza 1,2,…,k,k+1,k+2,…,n (S1) il tempo totale
di completamento è
k
k
n
j =1
j =1
j =1
w1 p1 + K + wk ∑ p j + wk +1( ∑ p j + pk +1 ) + K + wn ∑ p j
• Per la sequenza k+1,k+2,…,n,1,2,…,k (S2) il tempo totale
di completamento è
n
n
n
j =k +1
j =k +1
j =1
wk +1pk +1 + K+ wn ∑ pj + w1( ∑ pj + p1) + K+ wk ∑ pj
Semplificando
• S1
k
k
n
k
j =1
j =1
j = k +1
n
n
k
n
j =k +1
j =k +1
j =1
j =k +1
w k +1 ∑ p j + K + w n ∑ p j = ( ∑
w j )( ∑ p j )
j =1
• S2
w1 ∑ p j + K + wk ∑ p j = ( ∑ w j )( ∑ p j )
• Quindi, ricordando l’ipotesi:
k
∑w
n
j =1
k
∑p
j =1
∑w
j
>
j
j
⇒ (
j = k +1
n
∑p
j = k +1
n
k
∑ w )( ∑ p
j
j = k +1
j =1
k
j
) < ( ∑ w j )(
j =1
j
cioè, S1migliore di S2
n
∑p
j = k +1
j
)
Coefficiente ρ di una catena
L’idea
chiave
dell’algoritmo
è
ricondurre
1/chain/ΣwjCj al problema di sequenziare catene
non-interrompibili, in modo da utilizzare il Lemma 1.2.
Definizione 1.3 Data una catena 1→ 2 → … →k
definiamo coefficiente ρ della catena il seguente
rapporto:
l

∑wj
∑wj

max j =1
j =1

ρ(1,K,k ) = l *
=
l
1
≤
l
≤
k

∑ pj
 ∑ pj
j =1
 j =1
l*






Esempio
job
1
2
3
4
pj
3
4
2
6
wj
10
4
17
8
1
2
 ∑l w
max  j =1 j
 l
ρ(1,K,4) =
1 ≤ l ≤ 4 ∑ p
j

 j =1
3
4


10
14
31
39

 =  , , , 
  3 7 9 15 


l* = 3
Proprietà del coefficiente ρ
Proprietà 1.4 Se un job l* determina il coefficiente
ρ(1,...,k) allora per qualunque 1<u<l* risulta:
l*
u
∑ wj
j =u +1
l*
∑ pj
j =u +1
∑wj
>
j =1
u
∑ pj
j =1
Dimostrazione
Per definizione:
l*
∑wj
∑wj
j =1
l*
j =1
u
∑ pj
j =1
da cui:
l*
p1 ∑ w j + K + pu
j =1
p1
u
>
∑ pj
j =1
l*
u
u
j =1
j =1
j =1
∑ w j > p1 ∑ w j + K + pl * ∑ w j
l*
l*
u
u
j =u +1
j =u +1
j =1
j =1
∑ w j + K + pu ∑ w j > pu +1 ∑ w j + K + pl * ∑ w j
u
l*
l*
j =1
j = u +1
j = u +1
( ∑ p j )( ∑ w j ) > ( ∑
u
p j )( ∑ w j )
j =1
Proprietà dello schedule ottimo
Lemma 1.5 Si consideri una generica catena (1, ..., k) e
sia l* il job che determina il suo coefficiente ρ(1,...,k).
Allora esiste uno schedule ottimo che processa i job 1, …,
l* consecutivamente.
Dimostrazione. (per contraddizione) Assumiamo che in una
sequenza ottima la sequenza 1,…,l* sia interrotta da un job
v ∉(1,...,k), cioè, contenga la sottosequenza
(S)
1,…,u,v,u+1,…l*
Proprietà dello schedule ottimo
(S) 1,…,u,v,u+1,…l*.
Consideriamo le sottosequenze:
(S')
v,1,…,u,u+1,…,l*
(S'')
1,…,u,u+1,…l*,v
Mostriamo che per almeno una fra S' e S'' il tempo di
completamento è non superiore a quello di S.
Dimostrazione
• Applicando il Lemma 1.2 alle catene (v) e (1,…,u) si ha che
se il valore (∑wjCj) di S è inferiore a quello di S', allora:
wv w1 + w2 + K + wu
<
pv
p1 + p2 + K + pu
• Applicando il Lemma 1.2 alle catene (v) e (u+1,…,l*) si ha
che se il valore (∑wjCj) di S è inferiore a quello di S'', allora:
wv wu +1 + wu + 2 + K + wl *
>
pv
pu +1 + pu + 2 + K + pl *
Dimostrazione
• Per la Proprietà 1.4 risulta inoltre:
wu +1 + wu + 2 + K + wl * w1 + w2 + K + wu
>
pu +1 + pu + 2 + K + pl *
p1 + p2 + K + pu
• Quindi, se S è meglio di S'', allora:
wv wu +1 + wu +2 + K + wl * w1 + w2 + K + wu
>
>
pv
pu +1 + pu +2 + K + pl *
p1 + p2 + K + pu
Contraddizione (avendo assunto S meglio di S'). Lo stesso
argomento si applica quando la catena è interrotta da
molteplici job.
Algoritmo
I due lemmi precedenti sono il fondamento di un algoritmo
polinomiale:
Algoritmo 1.6
In ogni istante in cui la macchina è libera, seleziona fra le
rimanenti catene quella con il massimo coefficiente ρ e la
processa senza interruzione fino al job che definisce ρ
(incluso)
L’algoritmo ha complessità O(n2)
Esempio
job
1
2
3
4
5
6
7
wj
6
18
12
8
8
17
18
pj
3
6
6
5
4
8
10
1
5
2
3
6
4
7
step1.
ρ(1,2,3,4) = (6+18)/(3+6) = 24/9, l*=2
ρ(5,6,7) = (8+17)/(4+8) = 25/12, l*=6
1
2
Esempio
job
1
2
3
4
5
6
7
wj
6
18
12
8
8
17
18
pj
3
6
6
5
4
8
10
step2.
ρ(3,4) = 12/6, l*=3
ρ(5,6,7) = (8+17)/(4+8) = 25/12, l*=6
1
2
5
6
3
4
5
6
7
Esempio
job
1
2
3
4
5
6
7
wj
6
18
12
8
8
17
18
pj
3
6
6
5
4
8
10
3
7
step3.
ρ(3,4) = 12/6, l*=3
ρ(7) = 18/10, l*=7
1
2
5
6
3
4
Esempio
job
1
2
3
4
5
6
7
wj
6
18
12
8
8
17
18
pj
3
6
6
5
4
8
10
4
7
step4.
ρ(4) = 8/5, l*=4
ρ(7) = 18/10, l*=7
1
2
5
6
3
7
4
Release date e preemption
L’introduzione delle release date complica il problema. Nel
caso in esame, il problema 1/rj/ΣwjCj è NP-hard. [Ex1]
Richiamo. Dato un problema di ottimizzazione P =(z,S) (di
minimo), si definisce rilassamento di P un nuovo problema
RP=(w,Φ) tale che:
(i) S ⊆ Φ
(ii) ∀ x ∈ S risulta w(x) ≤ z(x)
Rilassamento preemptivo
Il problema1/rj, prmp/ΣwjCj si dice rilassamento (perché
lo è?) preemptivo.
Per esso è interessante valutare il comportamento della
naturale estensione della regola WSPT:
Preemptive WSPT: in ogni istante (intero) di tempo, si
processa il job disponibile con il massimo rapporto
peso / tempo residuo di processamento
Esempio
job
1
2
3
4
5
wj
1
4
3
5
3
pj
2
3
3
2
1
rj
0
2
3
1
4
28
15
1
4
4
2
5
2
2
33
1
15
3
8
ZPWSPT=99
3
3
PWSPT non è ottima per
1/rj ,prmp /∑ wj Cj
108
2
1 1 2 2 2 2 2 2 2 2 2 2 3 3
job
1
2
3
wj
1
9
8
pj
2
10
2
rj
0
1
11
112
ZPWSPT=222
99
104
1 2 2 2 2 2 2 2 2 2 2 3 3 1
14
ZOPT=217
Complessità
PWSPT si esegue in tempo O(n log n)
Si mantiene la lista ordinata per valori decrescenti del
rapporto wj/pj(t) e la lista ordinata dei job per release date
crescenti.
Gli eventi significativi sono di due tipi: (i) completamento di un
job e (ii) rilascio di un nuovo job. Quindi, ci sono O(n) eventi.
In corrispondenza di ciascun evento si deve:
• aggiornare la lista, richiede tempo O(log n)
• calcolare l’evento successivo, calcolando min(t + pj(t), rj1),
che richiede tempo costante
Pesi unitari
Nel caso di pesi tutti unitari PWSPT schedula, in ogni
istante (intero) di tempo, il job disponibile con il minimo
tempo residuo di processamento (Shortest Remaining
Processing Time, SRPT)
Si ha il seguente:
Lemma 1.6
La regola SRPT è ottima per 1/rj, prmp/ΣCj
Dimostrazione. Mostriamo che, comunque preso uno
schedule S che non rispetta SRPT, ne esiste uno S' che la
rispetta con un tempo di completamento non peggiore.
Dimostrazione
Se S non rispetta SRPT, deve esserci un istante t in cui è
processata una unità del job j pur esistendo k tale che
pj(t) > pk(t)
Costruiamo un nuovo schedule S' in cui le rimanenti pk(t) unità
del job k sono scambiate con le prime pk(t) del job j.
S
j
S′
k
t
k
t'
Dimostrazione
S
j
S′
k
t
k
t'
• i job diversi da j e k non subiscono alcuna variazione;
• primo caso: Ck(S ) > Cj(S )
− Essendo pj(t) > pk(t) si ha che Ck(S ′) ≤ Cj(S);
− inoltre, per costruzione, Cj(S ′) = Ck(S );
Quindi: Ck(S ′) + Cj(S ′) ≤ Ck(S ) + Cj(S )
Dimostrazione
S
j
S′
k
t
k
t'
• secondo caso: Ck(S) < Cj(S)
− Ck(S ′) ≤ Ck(S);
− Cj(S ′) = Cj(S);
Quindi: Ck(S′) + Cj(S ′) ≤ Ck(S) + Cj(S )
Esercizi
Esercizio 1
Dimostrare che la regola SPT non è ottima per il problema
1/rj/∑ Cj
z(SPT) = 12
1
job 1
rj 3
pj 1
2
0
4
3
2
4
z(OPT) = 9
1
2
1
8
4
5
5
Esercizio 2
Dimostrare che la regola WSPT non è ottima per il
problema 1/brkdwn/∑ wj Cj
z(WSPT) = 85
1
job
1
2
wj
10 15
pj
1
2
2
1
2
3
4
10
75
z(OPT) = 70
1
2
1
5
2
30
3
4
40
5
Esercizio 3
Dimostrare o confutare che la regola SPT è ottima per il
problema 1/brkdwn/∑ Cj
job
1
2
3
pj
3
2
4
z(SPT) = 22
2
3
1
2
4
5
12
8
z(OPT) = 21
3
2
4
5
1
7
10
1.3 Problemi min-max
(Massima Lateness Lmax)
1/prec/hmax
Forma della funzione obiettivo:
hmax = max (h1(C1), …, hn(Cn))
hj(Cj) è una arbitraria funzione non decrescente di Cj
Esempi:
hj(Cj)= Cj – dj = Lj
⇒
hj(Cj) = max (0,Lj) = Tj
hmax = Lmax
⇒
hmax = Tmax
Precedenza: GP generico grafo aciclico.
• Dato che le soluzioni ottime sono nondelay, l’ultimo job
termina all’istante C max = ∑nj=1 p j
Algoritmo di Lawler
Costruisce lo schedule a partire dal fondo
•J
job già schedulati nell’intervallo [C max − ∑ j ∈J p j ,C max ]
• Jc = {1, …, n} \ J
• J′
job schedulabili immediatamente prima di J (= tutti i
successori sono in J)
Inizializzazione:
J = ∅, Jc = {1, …, n}, J′ insieme dei job privi di successori
Loop: while (Jc ≠ ∅ )
Schedula in ultima posizione il job j* tale che
h j * ( ∑ p j ) = min (h j ( ∑ p j ))
j ∈J c
j ∈J ′
J := J ∪{j*}, Jc := Jc \{j*}, aggiorna J′
Endloop.
j ∈J c
Corretezza
Teorema 1.7 L’algoritmo di Lawler restituisce uno
schedule ottimo per 1/prec/hmax
Dimostrazione. (Per contr.) Sia S una sequenza ottima
per cui, ad una generica iterazione, è selezionato il job
j**∈
∈J′ ma esiste ∃ j* (schedulabile) tale che
h j * ( ∑ p j ) < h j ** ( ∑ p j )
j ∈J c
S
j*
j ∈J c
j**
Quindi, j* è schedulato prima di j**
J
Dimostrazione (continua)
j*
j**
S
hj **
hj **
hj *
hj *
j**
j*
S′
Consideriamo un nuovo schedule S′ ottenuto da S spostando
il job j** subito dopo j*. [L’unico job che peggiora è j*]
Dimostrazione (continua)
j*
hj **
hj **
hj *
hj *
j**
j**
j*
S′
S
h j * ( ∑ p j ) < h j ** ( ∑ p j ) ⇒ costo di j* in S′ inferiore al costo di
c
c
j∈J
j∈J
j** in S. Quindi S′ meglio di S, contraddizione.
Esempio
job
1
2
3
4
pj
3
4
2
6
1+C2
10
hj
Iter 1.
1.5 C3 2
Gp
4
(C4/5)
2
∑ p j = 15
j ∈J c
J
∅
Jc
{1,2,3,4}
J′
{1,2,3}
job
1
3
costo 10 16 22.5
1
0
2
12
15
Esempio
job
1
2
3
4
pj
3
4
2
6
hj
10
1+C2
Iter 2.
1.5 C3 2
Gp
4
(C4/5)
2
∑ p j = 12
j ∈J c
J
{1}
job
2
3
Jc
{2, 3,4}
costo
13
18
J′
{2,3}
2
0
8
1
12
15
Esempio
job
1
2
3
4
pj
3
4
2
6
hj
10
1+C2
1.5 C3 2
(C4/5)
∑ pj = 8
Iter 3.
j ∈J c
J
{1,2}
Jc
{3,4}
J′
{3,4}
3
S*
0
job
costo
4
2
2
8
3
12 3.03
1
12
z(S*) = max(10, 13, 3.03, 3)
4
15
Algoritmo di Lawler: caso speciale
L’algoritmo di Lawler si esegue in tempo O(n2)
Infatti, assumendo che il calcolo del valore delle funzioni hj
richieda tempo costante, l’algoritmo richiede n passi,
ciascuno basato su n confronti
• Nel caso 1//Lmax l’algoritmo di Lawler si specializza:
h j (C j ) = C j − d j
min (h j ( ∑ c p j )) = max (d j )
j ∈J ′
j ∈J
j ∈J ′
Equivale alla regola EDD (Earliest Due Date)
Esercizio
Dimostrare che la regola EDD non è ottima per il problema
1//∑ Lj
Controesempio:
job
1
2
3
pj
3
4
2
dj
6
4
5
3
1
2
0
3
0
6
4
1
2
4
9
2
5
1
9
1/rj/Lmax: complessità
Teorema 1.8 1/rj /Lmax è NP-hard in senso forte
Dimostrazione. Riduzione polinomiale da 3-PARTITION
3t
Istanza: interi a1, …,a3t ,b tali che b/4<aj<b/2, ∑ a j = tb
j =1
Problema: ∃ partizione in t terne tutte di peso b?
Costruiamo la seguente istanza di 1/rj/Lmax con n = 4t−1
rj =jb + (j−1), pj=1, dj=jb +j,
rj = 0, pj = aj−t+1,
dj =tb + (t − 1),
j =1,…,t−1
j =t,…,4t−1
Problema (target): ∃ uno schedule di valore z ≤ 0?
1/rj/Lmax : complessità
rj=jb+(j−1),
pj=1,
dj=jb+j,
j=1,…,t−1
∃ schedule con Lmax ≤ z =0 se e solo se ogni job j, j
=1,…,t –1, è processato fra rj e dj = rj+pj
r1
d1
r2
d2
r3
d3
rt − 2 dt-2
rt−1 dt − 1
b
0
b
b+1 2b+1
3b+2
2b+2
3b+3
Fissando i primi t−1 job “bloccanti”, rimangono t
intervalli di lunghezza b
tb+t −1
1/rj/Lmax : complessità
r1
d1
r2
d2
r3
d3
rt-2 dt-2
rt-3
dt-3
b
0
b
3b+2
b+1 2b+1
2b+2
tb+t−1
3b+3
∃ schedule con Lmax ≤ 0 se e solo se i restanti 3t job:
dj=tb +(t − 1), j =t,…,4t−1
rj = 0, pj =aj-t+1,
per cui vale:
4 t −1
4 t −1
∑ p = ∑a
j
j =t
j −t +1
= tb
j =t
possono essere schedulati negli t intervalli di lunghezza b.
1/rj/Lmax : complessità
dj=tb +(t − 1), j=t,…,4t−1
rj = 0, pj =aj-t+1,
r1
d1
r2
d2
r3
d3
rt− 2 dt−2
rt−3 dt−3
b
0
b
b+1 2b+1
3b+2
2b+2
tb+t−1
3b+3
• Essendo b/4<aj , in ciascun intervallo di lunghezza b non
entrano più di tre job
• essendo aj<b/2 e
4t −1
4t −1
j =1
j =1
∑ p j = ∑ a j −t +1 = tb
mettendo meno di tre job in un intervallo, almeno un job è
schedulato in ritardo
1/rj/Lmax : complessità
dj=tb +(t − 1), j=t,…,4t−1
rj = 0, pj =aj-t+1,
r1
d1
r2
d2
r3
d3
rt-2 dt-2
rt-3
dt-3
b
0
b
b+1 2b+1
3b+2
2b+2
3b+3
tb+t-1
Quindi, i job t,…, 4t−1 possono essere schedulati negli t
intervalli di lunghezza b sse possono essere suddivisi in t
terne di lunghezza b, cioè, sse 3-PARTITION ha soluzione
Esercizio
Risolvere la seguente istanza di 3-partition:
A={27,27,29,33,33,33,35,35,35,37,37,39}
b=100
1/rj,prmp/Lmax
Preemptive EDD: ad ogni istante t, si processa il job
disponibile con la minima due date
R(t) = {j: rj ≤ t} insieme dei job disponibili al tempo t
Teorema 1.9 La regola PEDD calcola una soluzione
ottima del problema 1/rj, prmp/Lmax.
Dimostrazione. Consideriamo uno schedule S che viola
PEDD:
Al tempo t è schedulato un job k∈
∈R(t) per cui esiste un
job j∈
∈R(t) disponibile e non ancora terminato
tale che dk > dj
PEDD - correttezza
Poiché j non è terminato, ∃ istante t ′ > t in cui j è in
esecuzione
S
k
t t+1
j
t′
t′ + 1
dk > dj
Consideriamo il nuovo schedule S ′ ottenuto da S
scambiando j e k nei due intervalli di figura:
j
S′
t
k
t+1
t′
t′ +1
Il contributo dei job diversi da j e k non cambia
PEDD - correttezza
S
k
t t+1
S′
j
t′
j
t
t′ + 1
dk > dj
k
t+1
t′
t′ + 1
Definiamo Cj e Ck i tempi di completamento di j e k nello
schedule S.
Dimostriamo che Lmax(S ′) ≤ Lmax(S). Tre casi:
1.
C j > t′ + 1, Ck > t′ + 1
2.
C j = t′ + 1, Ck > t′ + 1
3.
C j ≥ t ′ + 1, Ck < t ′ + 1
PEDD - correttezza
caso 1.
S
C j > t ′ + 1,
k
t t+1
S′
Ck > t ′ + 1
j
t′
j
t
t′ + 1
k
t+1
t′
t′ + 1
Poiché entrambi i job terminano dopo t′+1 lo scambio
non ha alcun effetto: Lmax(S ′) = Lmax(S)
PEDD - correttezza
caso 2.
C j = t ′ + 1,
S
Ck > t ′ + 1
k
j
C j = t′ + 1
S′
j
t
k
t+1
t′
t′ + 1
Essendo Ck > t′+1 il tempo di completamento di k in S′
rimane inalterato; al contrario, quello di j diminuisce.
Quindi, Lmax(S ′)≤Lmax(S)
PEDD - correttezza
caso 3.
C j ≥ t ′ + 1,
Ck < t ′ + 1
S
k
j
S′
j
k
t
t+1
t′
t′ + 1
Il tempo di completamento di k aumenta fino a t′+1.
La lateness di k in S′ è, quindi, pari a:
dk>dj
t ′ + 1 − dk < t ′ + 1 − d j ≤ C j − d j = L j
ed è quindi inferiore alla lateness di j in S
1/rj/Lmax
Algoritmo branch-and-bound
Branch-and-bound: nozioni di base
Dato
un
problema
combinatoria: P0=(z, S)
di
ottimizzazione
z* = min {z(x) : x ∈ S}
S ={x1, …, xm}
Enumerazione totale
Algoritmo banale:
1. Enumera tutte le soluzioni ammissibili (sono in
numero finito) e calcolane il costo
2. Scegli la soluzione di costo minimo
Sfortunatamente questo algoritmo può essere usato solo
quando il numero di soluzioni ammissibili non è elevato.
Ad esempio, il numero di schedule ammissibili per un
problema a macchina singola (senza precedenze) è n!
Quindi, per un problema con 20 job, eseguendo una
valutazione in 10−9 sec, impiegheremmo più di 77 giorni
Decomposizione
Proposizione1. Sia {S1,…,Sp}, una decomposizione dell’insieme
S in sottoinsiemi
Si ⊂ S per i = 1, …, p.
∪i=1, ..., p Si = S
sia zi* il valore ottimo del sottoproblema (Si, c), i = 1,…, p.
Allora,
z* = mini =
1,…,p
Osservazione:
i
sottoinsiemi
necessariamente una partizione di S
zi*
non
costituiscono
Albero di enumerazione
applichiamo ricorsivamente il procedimento:
Nodo radice
Esempio:
S = {0,1}3
S
x1=0
x1=1
S1
S0
x3=0
S000
x2=0
x2=1
x2=0
x2=1
S00
S01
S10
S11
x3=1
S001
x3=0
S010
x3=1
S011
x3=0
S100
x3=1
S101
x3=0
S110
Caso peggiore: 2n foglie + 2n −1 nodi intermedi
x3=1
S111
Potatura
• Il metodo branch-and-bound si basa sull’idea di ridurre il più
possibile il numero di sottoproblemi “valutati” (= per cui si risolve
il rilassamento lineare)
• Diversi criteri, basati sulla soluzione di un rilassamento, ci
permettono di “potare un sottoproblema” (Si, c), cioè di NON
procedere all’esplorazione del sottoalbero di radice (Si, c)
Si
Limitazioni inferiori di zi*
Proposizione 1. Sia S = S1 ∪ S2 ∪…∪ Sp una
decomposizione della regione ammissibile S in p insiemi.
Sia z*i = min {cTx : x ∈ Si} .
Se ziLB è un lower bound per il valore ottimo z*i
Allora,
zLB = mini ziLB è un lower bound per z*
S
z LB= 5
S1
z 1LB= 10
S2
z 2LB= 5
S3
z 3LB= 7
Soluzioni ammissibili: limitazioni superiori di
zi*
Proposizione 2. Sia S = S1 ∪ S2 ∪… ∪ Sp una decomposizione
della regione ammissibile S in p insiemi.
Sia z*i = min {cTx : x ∈ Si} e
x i ∈ Si
(soluzione ammissibile)
naturalmente, ziUB = cT xi è un upper bound per il valore ottimo z*i
Allora,
zUB = mini ziUB è un upper bound per z*
S
z UB= 9
S1
z 1UB= 15
S2
z 2UB= 9
S3
z 3UB= 13
Potatura per bound
• Sia z UB = c T x un upper bound del valore ottimo z*
• Sia ziLB un lower bound per il valore ottimo z*i di (Si, c)
Se
LB
zi
≥z
LB
zi
UB
UB
z
z*
allora Si non contiene soluzioni ammissibili migliori di
e il sottoproblema (Si, c) è potato
x
Calcolo di ziLB
Dato un problema di ottimizzazione P=(z,S) (di minimo),
si definisce rilassamento di P un nuovo problema
RP=(w,Φ) tale che:
(i) S ⊆ Φ
(ii) ∀ x ∈ S risulta w(x) ≤ z(x)
• Il calcolo di ziLB si effettua risolvendo in modo esatto
un opportuno rilassamento di (z,Si).
• La scelta del rilassamento si basa su due esigenze,
spesso contrastanti:
o Ottenere buone approssimazioni di zi*
o Richiedere tempi di calcolo non elevati
Potatura per ottimalità
Può accadere che risolvendo il rilassamento si ottenga
una soluzione ottima del sottoproblema.
In questo caso, ovviamente, il sottoproblema
non va ulteriormente suddiviso.
Se z = w, ogni soluzione ammissibile di RP che sia
anche ammissibile per P, è anche ottima per P.
Branch-and-bound per 1/rj/Lmax
branching: al livello h dell’albero di enumerazione si fissa
in tutti i modi possibili il job in posizione h
----1-…-
1, 2 - … -
2-…-
1, n - … -
radice: nessun job è fissato
n-…-
n, 1 - … -
Livello n : n! sottoproblemi
n, n-1 - … -
Vincoli di branching: schedule parziali
Un sottoproblema S(k−1) al livello k−1 contiene
l’insieme delle schedule in cui le prime k−1 posizioni
sono assegnate
schedule parziale
j1 , … , jk−1
0
t
Un
vincolo
(di
branching) fissa un
certo job jk nella k-ma
posizione
j1 , … , jk−1
0
jk
t
…
jk
j1 , … , jk−1
0
t
Calcolo di ziLB
• Rilassamento preemptivo: 1/rj,prmp/Lmax
• la regola PEDD è ottima (ed efficiente)
j1 , … , jk−1
j1 , … , jk−1
jk
…
lower bound (livello k):
- eredita dal nodo padre
LB
- ricalcola, essendo z k −1
j1 , … , jk−1
≤
LB
zk
jk
Dominanza fra sottoproblemi
Consideriamo uno schedule parziale al livello k-1: il
sottoproblema j1, …, jk-1 , jk deve essere generato solo se:
r jk < min (max(t ,rl ) + pl ) = max(t ,rl * ) + pl *
l ∈J
j1 , … , jk−1
j1 , …, jk-1
0
jk
rjk
t
altrimenti si otterrebbe un sottoproblema dominato da:
0
l*
j1 , …, jk-1
t
jk
rjk
branch-and-bound
Caso 1: potatura per Bound
Sia ziLB il valore ottimo di RP.
Se ziLB ≥ zUB elimina Si , vai a Test
Inizializzazione
L={S}, zUB = + ∞
Test: L = ∅?
Scegli un problema Si
dalla lista
Risolvi il Rilassamento
su Si
STOP
→ zUB
Caso 2: potatura per Ottimalità
Se la soluzione ottima xiUB di RPi
è ottima anche per Pi, allora elimina Si.
Aggiorna ottimo corrente:
Se ziUB < zUB allora zUB =ziUB, vai a Test
Genera ed aggiunge ad L
i figli di Si corrispondenti a
schedule parziali ammissibili e
non dominati di Si
Esercizio
job
1
2
3
4
pj
4
2
6
5
rj
0
1
3
5
dj
8
12
11
10
1
2
3
4
nodo radice:
-4
1
0
3
4 5
4
4
3
10
zLB(----) = 5
5
2
15
17
Branching
job
1
2
3
4
pj
4
2
6
5
rj
0
1
3
5
dj
8
12
11
10
ottimo corrente: (1,2,3,4)
z =7
----
1---
2 ---
5
3 ---
r3 > r2 + p2
4 ---
r4 > r2 + p2
Eliminati per dominanza
Valutazione di (1 - - -)
job
1
2
3
4
pj
4
2
6
5
rj
0
1
3
5
dj
8
12
11
10
-4
1
0
3
4 5
4
4
3
10
zLB(1,---) = 5
5
2
15
17
Valutazione di (1 - - -)
-4
1
0
3
4
4
4 5
3
10
5
2
15
zLB(1,---) = 5
la condizione di potatura per bound fallisce
----
5
12--
13--
1---
5
7
2 ---
14--
17
Valutazione di (1 2 - -)
-4
1
job
1
2
3
4
pj
4
2
6
5
rj
0
1
3
5
dj
8
12
11
10
-6
2
4
-1
4
6
6
3
11
zLB(1,2--) = 6 Soluzione ammissibile
17
z =6
Valutazione di (1 2 - -)
-4
1
-6
2
-1
4
3
6
4
6
11
17
zLB(1,2--) = 6
sottoproblema potato per ottimalità
----
5
6
1---
13--
7
6
2 ---
6
1243
5
14--
Valutazione di (1 3 - -)
job
1
2
3
4
pj
4
2
6
5
rj
0
1
3
5
dj
8
12
11
10
-4
1
-1
3
4
zLB(1,3--) = 5
5
4
10
Soluzione ammissibile
5
2
15
z =5
17
Arresto
6
----
5
1---
5
2 ---
1243
1342
6
5
6
5
14--
5
Soluzione ammissibile di valore pari al lower bound globale: ottima
Scelte implementative
• Riassumendo, l’implementazione di un branch-andbound consiste delle seguenti scelte:
• regola di branching
• rilassamento
• regole di dominanza
• strategia di visita dell’albero di enumerazione
(selezione del nuovo sottoproblema da valutare)
• euristiche (in particolare al nodo radice)
Esercizio
Calcolare la soluzione ottima del seguente problema
1/prec/∑wjCj
Regola di selezione del sottoproblema FIFO (visita in
ampiezza)
job
1
2
3
4
5
wj
1
4
1
6
3
pj
3
7
1
5
4
1
2
4
5
Grafo delle precedenze
3
Valutazione di (-, -, -, -, -)
2
1
3
ρ(1,2,3*)=max(1/3,5/10,6/11)=6/11
4
ρ(4*,5) = max(6/5, 9/9)=6/5
5
ρ(5)=3/4
4
5
5
1
9
2
zLB= 165
3
19
12
20
Soluzione del rilassamento chain: non ammissibile (5 precede 2)
1
2
3
3
4
5
10 11
16
Soluzione iniziale
z = 210
20
Branching al nodo radice
zUB= 210
-----
1----
zLB= 165
4----
Lista dei problemi candidati: {(1, - - - -), (4, - - - -)}
Valutazione di (1, -, -, -, -)
2
4
3
job
1
2
3
4
5
wj
1
4
1
6
3
pj
3
7
1
5
4
ρ(2,3*) = max(4/7, 5/8)=5/8
5
ρ(4*,5) = max(6/5, 9/9)=6/5
ρ(5) = 3/4
1
4
3
L= 183
5
8
2
12
3
19 20
5 precede 2: soluzione non ammissibile
Branching
zUB= 210
-----
zLB = 183
12---
zLB = 165
4----
1----
14---
Lista dei problemi candidati: {(1, 2, - - -), (1, 4, - - -), (4, - - -)}
Valutazione di (4, -, -, -, -)
2
1
3
ρ(1, 2,3*) = max(1/3, 5/10,
6/11)=6/11
ρ(5) = 3/4
5
4
5
5
L= 165
1
9
2
12
3
19 20
5 precede 2: soluzione non ammissibile
Branching
zUB= 210
-----
zLB = 183
12---
zLB = 165
4----
1----
zLB = 165
14--41---
Lista dei problemi candidati: {(1, 2, - - -), (1, 4, - - -), (4, 1 - -)}
Valutazione di (1, 2, -, -, -)
3
ρ(3) = max(1/1)= 1
ρ(4*,5) = max(6/5,9/9)=6/5
4
5
Soluzione del rilassamento chain: ammissibile
1
2
3
4
10
aggiornamento dell’ottimo corrente
3
5
15 16
20
zLB = 209 = zUB
zUB= 210
-----
L= 183
12---
zLB = 165
4----
1----
(1, 2, 4, 3, 5)
zUB= 209
zUB= 209
14---
41---
potato per ottimalità
Lista dei problemi candidati: {(1, 4, -, - -), (4, 1, -, - -)}
L= 165
Valutazione di (1, 4, -, -, -)
2
3
Solo il job 2 è schedulabile:
l’unico figlio è (1 4 2 - -)
5
Valutazione di (1, 4, 2, -, -)
3
5
ρ(5) =3/4
ρ(3) = max(1/1)= 1
1
4
3
2
8
3
5
20
15 16
Soluzione del rilassamento chain: ammissibile
L= 187
zUB= 209
-----
L= 183
12---
zLB = 165
4----
1----
(1, 2, 4, 3, 5)
zUB= 209
potato per ottimalità
zUB= 187
14---
41---
(1, 4, 2, 3, 5)
zUB= 187
potato per ottimalità
14---
Lista dei problemi candidati: {(4, 1, - - -)}
L= 165
Valutazione di (4, 1, -, -, -): fixing
2
1
3
Solo il job 1 è schedulabile:
l’unico figlio è (4 1 - - -)
5
Valutazione di (4, 1, 2, -, -)
3
5
ρ(5) =3/4
ρ(3) = max(1/1)= 1
4
1
3
2
8
3
15 16
Soluzione del rilassamento chain: ammissibile L= 174
5
20
-----
zUB= 187
zUB= 174
4----
L= 165
1---41--12---
14---
zUB= 174
potato per ottimalità
142--
412--
potato per ottimalità
L=∅: STOP
potato per ottimalità
scelta del sottoproblema: FIFO (visita in ampiezza)
# problemi valutati = 8
L= 183
4----
1----
12---
123--
-----
14---
L= 165
41---
124-142--
412--
ottima
12435
12345
41235
12453
14253
14253
z*= 174
41253
scelta del sottoproblema: least lower bound
# problemi valutati = 5 (!)
L= 183
4----
1----
12---
123--
-----
14---
L= 165
41---
124-142--
412--
ottima
12435
12345
41235
12453
14253
14253
z*= 174
41253
Gerarchia di rilassamenti
z
Schedule ammissibili
(risp. alle precedenze)
z*
LB2
schedule non ammissibili
rimozione archi
LB1
LB1 = eliminati i vincoli di precedenza O(n log n)
LB2 = eliminato solo l’arco (2,5) O(n2)
Relazioni fra funzioni obiettivo
Definizione. Due funzioni obiettivo si dicono equivalenti se
uno schedule ottimo per la prima lo è anche per la seconda
e viceversa.
Esempio. 1//ΣCj. e 1//ΣLj. sono equivalenti
Infatti, Lj = Cj − dj
quindi ΣLj = ΣCj − Σdj
ma l’ultimo termine è costante e non dipende dallo schedule
Lmax vs. Tmax
Uno schedule che minimizza Lmax minimizza anche Tmax
infatti,
Tmax = max {max(0,L1), …,max(0,Ln)} = max{0,
L1,…,Ln} = max {0,Lmax}.
non vale il veceversa:
-1
1
1
2
pj
1
5
dj
7
6
Tmax=Lmax=0
6
-1
-1
0
2
1
job
2
1
5 6
Lmax=-1
Osservazione
Sia P un generico problema e RP un suo rilassamento.
• se P ed RP hanno la stessa funzione obiettivo, allora
qualunque soluzione ottima di RP che sia anche
ammissibile per P è ottima per P;
• al contrario, se P ed RP hanno funzioni obiettivo diverse
questo non è vero: consideriamo la seguente istanza di
1//ΣwjCj ed il suo rilassamento 1//ΣCj.
1
job
1
2
pj
1
2
wj
1
10
30
2
1
1
20
2
3
3
1
2
3
C1+C2=4*
C1+C2=5
w1C1+w2C2=31
w1C1+w2C2=23*
Numero di tardy job
1//ΣUj
Struttura delle soluzioni ottime
• ogni schedule ottimo è composto da un insieme di job
che arrivano in tempo e da un secondo insieme di job in
ritardo (rispetto alle proprie due date)
• il primo insieme rispetta EDD, in modo che Lmax sia
minimizzata (e minore o uguale a zero).
• l’ordine dei job del secondo insieme non ha impatto
sulla funzione obiettivo
job in tempo (EDD)
job in ritardo (qualsiasi ordine)
Algoritmo di Moore
• Costruisce lo schedule in avanti
• J job già schedulati (schedule parziale, secondo EDD)
• Jd job già esaminati e fissati come tardy job
• Jc job ancora non esaminati
Inizializzazione:
J = ∅, Jd = ∅, Jc = {1, …, n}.
Repeat:
1. Sia j* il job in Jc con la minima due date:
J:=J ∪ {j*}; Jc:=Jc \{j*}
2. Se j* è in ritardo, cioè ∑ p j > d j *
j ∈J
sia k* il job in J più lungo:
J:=J \{k*} Jd:=Jd ∪{k*}
Until (Jc ≠ ∅)
Correttezza
Teorema. L’algoritmo di Moore restituisce una soluzione
ottima di 1//ΣUj
Dimostrazione. Senza perdita di generalità si può assumere
d1≤ d2≤… ≤dn
Sia Jk un sottoinsieme di {1,…,k} che soddisfa le seguenti
proprietà:
1.ha il massimo numero Nk di job in tempo
2.fra tutti i sottoinsiemi di {1,…, k} con Nk job in tempo, Jk ha il
minimo tempo totale di processamento
Per definizione, Jn corrisponde ad uno schedule ottimo.
Dimostriamo per induzione che l’algoritmo di Moore
restituisce Jn
Induzione
•
•
l’algoritmo costruisce J1 in modo da rispettare (1) e (2).
Assumiamo che (1) e (2) valgano per k, cioè che Moore
costruisca Jk e mostriamo che esse valgono per k+1
Due casi:
Caso a. Il job k+1 è aggiunto all’insieme Jk ed è completato in
tempo. Ovviamente, è impossibile avere un maggior numero
di job in tempo fra quelli in {1,…,k+1}, quindi vale (1).
Inoltre, il job k+1 deve appartenere all’insieme. Quindi, il
tempo di processamento totale è minimo fra tutti gli insiemi
che soddisfano (1). Quindi vale (2).
Induzione
Caso b. Il job k+1 è aggiunto all’insieme Jk ed è
completato in ritardo. Dato che Jk soddisfa (1) e (2)
deve essere Nk = Nk+1.
Quindi, aggiungere il job k+1 a Jk non aumenta il
numero di job in tempo. Ma aggiungere k+1 e
cancellare il job più lungo fra quelli di Jk ∪{k+1}
mantiene uguale il numero di job in tempo e riduce il
tempo di processamento complessivo. Questo completa
la prova.
Esempio
job
1
2
3
4
5
pj
7
8
4
6
6
dj
9
17
18
19
21
iter 1.
1
0
iter 2.
7
1
0
iter 3.
2
7
15
1
0
2
7
1
0
15
3
7
3
11
19
Esempio
job
1
2
3
4
5
pj
7
8
4
6
6
dj
9
17
18
19
21
iter 5.
1
7
3
Soluzione
7
11
4
11
17
5
4
17
23
5
10
4
3
0
4
4
3
1
3
0
0
iter 4.
5
16
1
2
1.4 Problemi min-sum con due date
(Tardiness totale ΣTj)
Problema dello zaino binario
Zaino di capacità C ∈ Ζ+
Insieme N = {1,…,n} di oggetti. Per ogni oggetto:
ingombro aj ∈ Ζ+
profitto pj ∈ Ζ+
Problema: scegliere un insieme di oggetti di profitto
massimo tale che l’ingombro totale non ecceda la capacità.
Sia S una soluzione ottima e S′ una soluzione ottenuta da S
eliminando l’elemento i.
S′ è sol. ottima per il problema N′ = N \{i} e C′=C−ai
Altrimenti, detta S′′ una sol ottima, S*= S′′ ∪ {i} sarebbe
ammissibile e migliore di S, contraddizione.
Formula ricorsiva
P(i, λ) = massimo profitto ottenibile con i primi i oggetti
ed uno zaino di capacità λ
consideriamo l’elemento i e valutiamo le due possibilità:
i è tenuto nello zaino: P(i, λ) = P(i −1, λ − ai) + pi
i è scartato: P(i, λ) = P(i −1, λ),
Quindi:
P(i, λ) = max(P(i −1, λ − ai)+ pi , P(i −1, λ))
il problema consiste nel determinare P(n, C)
Divide et impera vs.PD
il metodo divide et impera procede per decomposizioni
successive (top-down) e combina successivamente le
soluzioni dei sottoproblemi per ottenere la soluzione del
problema originario.
È possibile (anzi, frequente) che molti sottoproblemi siano
uguali, quindi si esegue molto lavoro inutile!
La programmazione dinamica risolve i sottoproblemi in
modo bottom-up, memorizzando le soluzioni in una tabella
e utilizzandole ogni volta che servono alla soluzione di un
problema più grande
Complessità spaziale
i−1
i
P(i−1,λ−ai)
+ pi
λ
P(i−1, λ)
P(i, λ)
• ogni valore P(i, λ) è calcolato solo con elementi della
colonna precedente
• Quindi, per calcolare il valore ottimo, è sufficiente
memorizzare la colonna precedente ⇒ spazio O(C)
Ricostruire la soluzione
i−1
i
P(i−1,λ−ai)
+ pi
λ
P(i−1, λ)
P(i, λ)
• Per ciascun valore calcolato serve un puntatore
all’elemento della riga precedente da cui è derivato
• Quindi, è necessario mantenere l’intera tabella ⇒
spazio O(nC)
Programmazione dinamica nello
scheduling
Motivazione: Il branch-and-bound valuta diversi
sottoproblemi in cui lo schedule parziale contiene gli
stessi job (!)
- - - j1- - j1 j2 - -
j2 - - j2 j1 - -
Ereditarietà della struttura ottima
Consideriamo un problema del tipo:
1//Σj=1,…,n hj(Cj)
In cui hj(Cj) è una arbitraria funzione non decrescente di Cj
Ereditarietà: in uno schedule ottimo i primi K job (per un
qualunque K∈{1,…,n}) formano uno schedule ottimo per
il sottoproblema composto esclusivamente da tali job.
j1
j2
jK
jn
Ereditarietà della struttura ottima
S
j1
j2
jK
jn
per un qualunque K ∈{1, …, n} il valore della funzione
obiettivo ha la seguente forma:
n
∑h
k =1
K
jk
(C jk ) =
∑h
k =1
n
jk
(C jk ) +
∑h
jk
(C jk ) = A + B
k = K +1
Consideriamo il problema composto dai job {j1,…,jK}: la
sequenza (j1,…,jK) è ottima. Altrimenti, potremmo ridurre A
senza modificare B, contraddicendo l’ottimalità di S.
Metodo di Held e Karp
z(J) valore ottimo del problema in cui l’insieme dei job è J.
Se J = { j } allora z(J) = hj(pj)
Se |J | > 1, l’ultimo job è completato al tempo Σpj ed i primi
|J| −1 job devono essere schedulati in modo ottimo nel
sottoproblema associato.
Quindi:



z (J ) = min z (J \ { j }),h j  ∑ pk  
j ∈J
 k ∈J  

Metodo di Held e Karp
Per risolvere la formula ricorsiva



z (J ) = min z (J \ { j }),h j  ∑ pk  
j ∈J
 k ∈J  

L’algoritmo procede in modo bottom-up iniziando a
calcolare le soluzioni ottime dei problemi con un solo
job, quindi utilizzando queste per risolvere i problemi
con due job, e via di seguito.
Esempio: 1//ΣTj
job
1
2
3
4
pj
8
6
10
7
dj
14
9
16
16
Soluzioni per i quattro insiemi di un singolo
elemento:
z({ j }) = Tj = max (0, pj − dj)
J
{1} {2}
{3}
{4}
pj−dj
−6
−3
−6
−9
z(J)
0
0
0
0
Esempio: insiemi di due elementi
Soluzioni per i sei insiemi di due elementi:
z({j1,j2}) =
= min(z({j1})+(pj1+pj2)− dj2, z({j2})+(pj1+pj2)− dj1)
J
{1,2}
{1,3}
{1,4}
{2,3}
{2,4}
{3,4}
C(J)
14
18
15
16
13
17
last
1
2
1
3
1
4
2
3
2
4
3
4
Tj(C(J))
0
5
4
2
1
0
7
0
4
0
1
1
z({J\{j}})
+Tj(C(J))
0
5
4
2
1
0
7
0
4
0
1
1
min
*
*
*
z(J)
*
0
2
*
0
*
0
0
1
Esempio: insiemi di tre elementi
Soluzioni per i quattro insiemi di tre elementi. Esempio:
J={1, 2, 3}, C(J) = p1+p2+p3
z({j1,j2,j3})=min(z({j1,j2})+C(J)−dj3,
z({j1,j3})+C(J)−dj2,z({j2,j3})+C(J)−dj1)
J
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
C(J)
24
21
25
23
Last
1
2
3
1
2
4
1
3
4
2
3
4
Tj(C(J))
10
15
8
7
12
5
11
9
9
14
7
7
z({J\{j}}+Tj(C(J)))
10
17
8
7
12
5
12
9
11
15
7
7
min
z(J)
*
8
*
5
*
9
*
7
Esempio: insieme di quattro elementi
J
{1,2,3,4}
31
C(J)
Last
Tj(C(J))
z({J\{j}}+Tj(C(j)))
Min
z(J)
1
17
24
2
22
31
3
15
20
*
20
Ricostruzione della soluzione ottima:
{1,2,3,4} ⇒ job 3 schedulato per ultimo;
{1,2,4} ⇒ job 4 schedulato per ultimo;
{1,2} ⇒ job 1 schedulato per ultimo;
(2,1,4,3) soluzione ottima
4
15
23
Complessità
Tempo: numero di sottoproblemi valutati
n  n  n 
n 
  +   +   +K+  
 1  2   3
n 
⇒ O(2n)
Spazio: 2n * da memorizzare.
DP vs. branch&bound
----
1- - 3 --12--
14--
31--
13-1423
1324
34-32--
1432
4 ---
2---
41--
43--
42-1342
21--
24-23--
2134
2413
2431
2143
ottima
2341
2314
4312
4321
Applicabilità I
Il principio di ereditarietà della struttura ottima si basa sul fatto
che un risequenziamento dei job (j1,…,jK) non cambia il
termine B.
S
j1
j2
n
∑h
k =1
jK
K
jk
(C jk ) =
∑h
k =1
jn
n
jk
(C jk ) +
∑h
jk
(C jk ) = A + B
k = K +1
Mantenendo la stessa struttura della funzione obiettivo, questo
non è vero se le release date sono non tutte nulle.
Controesempio
job
1
2
3
4
pj
5
5
5
5
rj
0
1
9
15
dj
11
9
15
20
0
1
1
5
4
10
0
6
15
0
11
20
1
3
1
2
0
3
2
0
1
0
1
4
16
Σ Tj = 1
T1+T2=1
21
Σ Tj = 2
T1+T2=0
Applicabilità II
Il metodo di Held e Karp si applica anche a problemi
min-max.
Ad esempio se consideriamo 1//Lmax la ricorsione
diventa:



z (J ) = min max  z (J \ { j }), ∑ p j − d j  

j ∈J 
j
∈
J




1//ΣTj
Tardiness totale
algoritmo pseudo-polinomiale
Struttura della sequenza ottima
Lemma 1.10 Se pj≤pk e dj≤dk, esiste una sequenza
ottima in cui j precede k.
Ipotesi: d1 ≤ …≤ dn , pk = max (p1 , …, pn )
Quindi, esiste una sequenza ottima in cui i job {1, …, k −1}
precedono, in un qualche ordine, il job k.
{1,2,…,k−
−1,…}
{k}
i rimanenti job {k+1, …, n} possono precedere o seguire k
Analisi di sensibilità
Prendiamo un job k qualunque e poniamo:
dk = max(dk ,Ck' )
Dove Ck' è il massimo tempo di completamento del job k in
una (qualsiasi) soluzione ottima.
Otteniamo 2 istanze, entrambe con n job e tempi di
processamento p1, …, pn
I1]
d1, …,dn
I2]
d1,… ,dk−1, max(dk,Ck'), dk+1 ,…,dn
Analisi di sensibilità
I1] d1,…,dn
I2] d1,…,dk-1, max(dk,Ck'),dk+1 ,…,dn
Lemma 1.11
Ogni sequenza ottima per I2 è ottima per I1
Dimostrazione. Siano:
• S' uno schedule ottimo di I1 in cui k è completato al
tempo Ck'
• S'' uno schedule ottimo di I2 e Ck′′ il relativo tempo di
completamento di k.
Dimostrazione I
Siano:
•
V'(S) la tardiness totale della sequenza S rispetto ad I1
•
V ′′(S) la tardiness totale della sequenza S rispetto ad I2
Valutiamo le due sequenze S' e S'' rispetto a I1 e I2.
Per costruzione:
1. V' (S') = V ′′ (S') + Ak
2. V' (S ′′) = V ′′ (S ′′) + Bk
Dimostriamo il teorema facendo vedere che:
• V ′′ (S') > V ′′ (S ′′) e
• Ak > Bk
Dimostrazione II: consideriamo S'
Se Ck' ≤ dk , allora I1 e I2 coincidono ed il lemma è provato;
altrimenti: la due date di k in I2 è proprio Ck', cioè coincide col
suo tempo di completamento in S'.
Quindi:
1. V' (S' ) = V′′ (S' ) + Ak
I1
I2
dk
Ck '
Ak = Ck'−
− dk
Dimostrazione III: consideriamo S''
2. V'(S ′′) = V ′′ (S ′′) + Bk
consideriamo la sequenza S”, in cui il job k è completato in Ck”
Bk = Tk'−Tk”=max(0,Ck”−dk)−max(0,Ck”−Ck')
2 casi:
Bk = max(0, Ck” − dk ) se Ck” ≤ Ck'
Bk = Ck”−dk−Ck ” +Ck'=Ck'−dk se Ck” > Ck'
quindi:
Bk = max(0, min(Ck”, Ck’) − dk )
Dimostrazione IV
1. V'(S') = V” (S') + Ak
2. V'(S”) = V” (S”) + Bk
S′ ] Ak = Ck' − dk
S''] Bk = max(0, min(Ck”, Ck′ ) − dk )
quindi: Ak ≥ Bk
Essendo S” ottima per I2, deve essere V”(S' )≥V”(S”)
da cui:
V ' (S' ) ≥ V ' (S”)
Struttura della sequenza ottima
Lemma 1.10 Se pj≤pk e dj≤dk, esiste una sequenza
ottima in cui j precede k.
Ipotesi: d1 ≤ …≤ dn , pk = max (p1 , …, pn )
Quindi, esiste una sequenza ottima in cui i job {1, …, k −1}
precedono, in un qualche ordine, il job k.
{1,2,…,k−
−1,…}
{k}
i rimanenti job {k+1, …, n} possono precedere o seguire k
Posizione dei job {k+1, …, n}
Lemma 1.12
Esiste un intero δ, 0 ≤ δ ≤ n − k, tale che esiste una
sequenza ottima S in cui il job k è preceduto da tutti i job j
con j ≤ k + δ e seguito da tutti i job j per cui j > k + δ
Ck' : massimo tempo di completamento del job k in una
soluzione ottima dell’istanza I1
S” : schedule ottimo di I2 tale da soddisfare Lemma 1.10
Ck” : tempo di completamento del job k in S”
Dal Lemma 1.11: S” è ottima anche per I1, quindi
Ck” ≤ max(Ck',dk)
Dimostrazione I
Affermazione 1. Si può assumere che k non sia preceduto in
S'' da alcun job j con
dj ≥ max(Ck',dk) ≥ Ck"
Infatti, lo swap:
j
k
k
Ck′′
dj
Ck ′′
dj
j
produrrebbe una sequenza ammissibile non peggiore di
quella di partenza
Dimostrazione II
Affermazione 2.
il job k in I2 ha una due date pari a max(Ck',dk). Quindi,
per il Lemma 1.10, deve essere preceduto in S” da tutti i
job j con
dj ≤ max(Ck',dk).
Quindi: scegliendo δ come il più grande intero tale che
dk + δ ≤ max(Ck',dk)
Ed essendo S'' ottima per I1, la prova è completa
Programmazione Dinamica
Insieme di job {1, …, l} che inizia all’istante t.
Dal Lemma 2, esiste un δ, 0 ≤ δ ≤ l − k, per cui uno schedule
ottimo è dato dalla concatenazione di tre insiemi di job:
1. in qualche ordine
2
3. in qualche ordine
{1,2,…,k−
−1,k+1,…,k+ δ} {k} {k+ δ +1,k+ δ +2,…,l}
t
Ck(δ) = t + Σj≤ k+δ pj
tempo di completamento di k
Affinché l’intera sequenza sia ottima devono essere ottime le
sottosequenze relative agli insiemi 1 e 3 ⇒ ricorsione
Programmazione Dinamica
Il Lemma 2, purtroppo non fornisce un metodo di calcolo di δ
(perché?), ma solo un certificato di esistenza.
Tuttavia, 0 ≤ δ ≤ l − k, quindi, possiamo enumerare tutti i
possibili valori di δ e scegliere quello che produce la sol.
migliore
1. in qualche ordine
2
3. in qualche ordine
{1,2,…,k−
−1,k+1,…,k+ δ} {k} {k+ δ +1,k+ δ +2,…,l}
t
Ck(δ) = t + Σj≤ k+δ pj
tempo di completamento di k
Struttura del sottoproblema
Definiamo
J(j, l, k) ⊆ { j, j + 1, … , l – 1, l}
l’insieme di job di durata minore o uguale a pk. L’insieme non
contiene il job k anche se j ≤ k ≤ l.
V(J (j, l, k), t) tardiness totale dell’insieme J(j, l, k) in una
soluzione ottima quando l’insieme è iniziato al tempo t
condizioni al contorno:
V(∅, t) = 0,
V({j}, t) = max (0, t + pj − dj)
Ricorsione
V (J (j, l, s), t) = min0≤ δ ≤ l −k {V (J (j, k+δ, k), t) +
+ max (0, Ck(δ) − dk) + V(J (k+δ+1, l, k) , Ck(δ) ) }
in cui:
pk = max (pr| r ∈ J(j, l, s))
valore ottimo:
V({1, …, n}, 0)
Esempio
job
1'
2'
3
4
job
1
2
3
4
pj
8
6
10
7
pj
6
8
10
7
dj
14
9
16
16
dj
9
14
16
16
V({1, 2, 3, 4}, 0) = min (
δ= 0 V(J(1, 3, 3), 0) + max (0, 24 – 16) + V(J(4, 4, 3), 24),
δ = 1 V(J(1, 4, 3), 0) + max (0, 31 – 16) )
δ=0
1,2
3
14
δ=1
1,2,4
4
24
31
21
3
Esempio
job
1
2
3
4
pj
6
8
10
7
dj
9
14
16
16
V({1, 2, 3, 4}, 0) = min (
δ= 0 V(J(1, 3, 3), 0) + max (0, 24 – 16) + V(J(4, 4, 3), 24),
δ = 1 V(J(1, 4, 3), 0) + max (0, 31 – 16) )
V(J(1, 3, 3), 0) = max (0, 6 – 9) + max (0, 14 – 14) = 0
V(J(4, 4, 3), 24)) = 24 + 7 – 16 = 15
⇒ V({1, 2, 3, 4}, 0) = min ((0 + 8 + 15), V(J(1, 4, 3), 0) + 15)
Esempio
job
1
2
3
4
pj
6
8
10
7
dj
9
14
16
16
V(J(1, 4, 3), 0) = min(
δ= 0 V(J(1, 2, 2), 0) + max (0, 14 − 14) + V(J(3, 4, 2), 14),
δ=1 V(J(1, 3, 2), 0) + max (0, 14 − 14) + V(J(4, 4, 2), 14),
δ=2 V(J(1, 4, 2), 0) + max (0, 21 − 14))
δ = 0,1
1
2
6
δ=2
1,4
4
14
2
21
Esempio
job
1
2
3
4
pj
6
8
10
7
dj
9
14
16
16
V(J(1, 4, 3), 0) = min(
δ= 0 V(J(1, 2, 2), 0) + max (0, 14 − 14) + V(J(3, 4, 2), 14),
δ=1 V(J(1, 3, 2), 0) + max (0, 14 − 14) + V(J(4, 4, 2), 14),
δ=2 V(J(1, 4, 2), 0) + max (0, 21 − 14))
J(1, 2, 2) = {1} → V(J(1, 2, 2), 0) = max (0, 6 − 9) = 0
J(3, 4, 2) = {4} → V(J(3, 4, 2), 14) = max (0, 21 − 16) = 5
J(1, 3, 2) = {1} → V(J(1, 3, 2), 0) = max (0, 6 - 9) = 0
J(4, 4, 2) = {4} → V(J(4, 4, 2), 14) = max (0, 21 − 16) = 5
J(1, 4, 2) = {1,4} → V(J(1, 4, 2), 0) = max (0, 6 − 9)
+ max (0, 13 - 16)= 0
Esempio
job
1'
2'
3
4
job
1
2
3
4
pj
8
6
10
7
pj
6
8
10
7
dj
14
9
16
16
dj
9
14
16
16
V(J(1, 4, 3), 0) = min(
* δ = 0, δ = 1 0 + 0 + 5,
δ= 2
0 + 7) = 5
Esempio
job
1
2
3
4
pj
6
8
10
7
dj
9
14
16
16
V({1, 2, 3, 4}, 0) = min ((0 + 8 + 15), V(J(1, 4, 3), 0) + 15)
δ = 0 23,
*δ = 1 20) = 20
{1, 2, 4}
V(J(1, 4, 3), 0) = min(
* δ = 0, δ = 1 0 + 0 + 5,
δ= 2
0 + 7) = 5
{1, 2}
1
2
3
4
3
4
3
Complessità
Tempo:
O(n3) sottoinsiemi J(j, l, k) e Σpj possibili istanti t.
Quindi, il numero di equazioni ricorsive da risolvere è
pari a O(n3 Σpj). Ciascuna di esse richiede un tempo
O(n).
Quindi, l’algoritmo richiede tempo O(n4 Σpj)
Tardiness totale pesata
1//ΣwjTj
1//Σ wjTj
Teorema. Il problema 1//Σ wjTj
forte.
è NP-hard in senso
Lemma. Se pj ≤ pk e dj ≤ dk, e wj ≥ wk allora esiste una
sequenza ottima in cui j precede k.
Rilassamento preemptivo: ciascun job j di durata pj è
suddiviso in pj job di durata unitaria.
Variabili decisionali:
xjk=1 se una unità del job j è eseguita nell’intervallo
[k −1,k] e 0 altrimenti
1/prmp/Σ wjTj
[0,1]
j
job
xjk
intervalli
[k−1, k]
[Cmax−1, Cmax]
C max
∑ x jk = p j , j = 1,K,n
k =1
n
∑ x jk = 1,k = 1,K,C max
j =1
1/prmp/Σ wjTj: formulazione PL0-1
n C max
max ∑ ∑ c jk x jk
j =1 k =1
occorre determinare cjk tali da
rappresentare la tardiness
totale (o un suo rilassamento)
C max
∑x
jk
= pj,
j = 1,K,n
k =1
n
∑x
jk
= 1,
k = 1,K,C max
j =1
x jk ∈ {0,1},
j = 1,..., n; k = 1,..., Cmax
problema dei trasporti
Richiamo: Problema dei trasporti
s località sorgente e t destinazioni. Ciascuna sorgente
i∈{1,...,s} dispone di di unità di prodotto ed ogni destinazione
j ∈{1,...,t} ne richiede almeno rj unità.
Il costo unitario di trasporto da i a j è cij.
Determinare una politica di trasporto di costo minimo.
s
t
min ∑∑ c ij x ij
i =1 j =1
xij quantità
trasportata
da i a j
t
∑x
ij
= di
i ∈ {1,K, s }
∑x
= rj
j ∈ {1,K, t }
j =1
s
ij
i =1
x ij ≥ 0,
int ere
Coefficienti cjk
Determinare cjk tali che, per ogni schedule non
preemptivo, risulti:
n C max
∑ w jT j ≥ ∑ ∑ c jk x jk
j =1 k =1
Definiamo i coefficienti di costo in modo che:
l
∑
k =l − p j +1
c jk ≤ w j max(l − d j , 0)
per j = 1,…,n; l = 1,…,Cmax
Funzione obiettivo
Allora, per una qualunque soluzione non preemptiva
risulta, per ogni j:
Cmax
Cj
k =1
k =C j − p j +1
∑ c jk x jk =
∑
Cj−pj+1
Possibile scelta:
c jk ≤ w j max(C j − d j , 0)
dj
c jk
Cj
0, per k ≤ d j
=
w j , altrimenti