Processi di cost management
-Programmazione multiperiodale
Queste slide (scritte da Carlo Mannino) riguardano il problema di
gestione delle attività di un progetto allorché i costi di esecuzione sono legati all’istante di inizio delle attività. Non siamo cioè nel caso in cui I costi sono legati alla durata: le durate delle attività saranno considerate fisse e note a priori. Inoltre, non supporremo presenti vincoli di risorsa. Supporremo invece che tra le attività possono sussistere relazioni di precedenza geenralizzate.
In queste slide è presentata una formulazione del problema, e la sua riduzione a un problema di minimo taglio (o sezione) su un grafo orientato, problema notoriamente semplice, risolubile ad esempio tramite l’algoritmo di Ford-Fulkerson.
2
Piani con costi dipendenti da start-time
• Trattiamo ora il caso in cui il costo di un’attività dipende dall’istante iniziale • Questo è il caso, per esempio, quando le attività comportano dei flussi di cassa.Assunzioni:
le attività sono rappresentate da un AoN con precedenze generalizzate G = (V,A) Le relazioni di precedenza generalizzate sono normalizzate (si + lij sj ij A ) L’orizzonte temporale è 0,1,…,T.
Per ogni attività iV e ogni istante t {0,1,…,T}, si indica con wit il costo di iniziare l’attività i all’istante t.
L’obiettivo è determinare un piano che minimizzi la somma dei costi.
6
Formulazione multiperiodale
Il problema della scelta del piano in presenza di costi dipendenti dall’istante di attivazione può essere formulato come problema di programmazione 0,1
• i V e t {0, …, T} definiamo una variabile binaria xit
Variabili V i x T t it
¦
1 0 Vincoli- L’attività i comincia in un singolo istante di tempo [5.1]
1 se l’attività i comincia nel periodo t (si = t) xit =
0 altrimenti
- Per ogni attività i si può calcolare un ESTi e un LSTi
1 , 0 t i it i V t LST x 1 , 0 d i it i V t EST x
- Se esiste l’arco (i,j) di peso lij e l’attività i comincia all’istante t, l’attività j non può cominciare prima di t + lij.
i lij j T t E ij x xit t
¦
lij jq d , 1 1 [5.2]8
Riassumendo la formulazione
min 1 0¦¦
n i T t it it x w V i x T t it ¦
1 0 T t E ij x x t lij q jq it¦
d , 1 1 0 [5.1] [5.2] 1 , 0 d i it i V t EST x 1 , 0 t i it i V t LST x T t V i xit {0,1} , 0,...,OSS. Le variabili fissate a 0 possono essere direttamente eliminate dai vincoli in cui sono presenti e dalla f.o. Quindi, non serve introdurle.
Esempio
lji= -SSijmax lij= SFijmin - d j lij= dj - SFijmax lji= -di- FSijmax lij= di + FSijmin lij= di- di+ FFijmin lji= dj- di- FFijmax 1 2 3 5 4 1 SFmin(0) 2 FSmin(0) 2 2 FSmin(0) FSmin(1) 1 1 2 3 5 4 1 -2 2 3 0 6 2 0 0 0 1 Fissiamo la deadline T = 6 j durata EST LST 1 1 0 3 2 1 1 4 3 2 0 3 4 2 0 2 5 1 3 514
Esempio
1 2 3 5 4 1 -2 2 3 0 6 2 0 0 0 1 Deadline T = 6 j durata EST LST 1 1 0 3 2 1 1 4 3 2 0 3 4 2 0 2 5 1 3 5 6 0 5 6 Soluzione ammissibile x10= x23= x30= x40= x53= 1 Costi w j\t 0 1 2 3 4 5 1 2 3 4 5 2 5 3 4 4 3 4 3 4 1 4 5 2 1 5 1 3 7 Costo soluzione: 2 + 4 + 4 + 5 + 1 = 16OSS. Il problema di programmazione 0,1 è difficile
Tuttavia il nostro problema può essere risolto efficientemente mediante opportuna rappresentazione
Tagli nel grafo
Dato un grafo orientato H=(W,A) due nodi speciali a,bW
Def. Taglio a-b: partizione dell’insieme W in due insiemi Q e R con a Q e b Q
Def. Capacità dell’arco uv A: reale non negativo cuv
Def. Capacità del taglio a-b c(Q, R): somma delle capacità degli archi uscenti da nodi in Q ed entranti in nodi in R.
¦
Q v R u uvc
R
Q
c
,)
,
(
16
Esempio di Taglio
a
7
2
b
3
6
4
5
4
2
2
6
1
4
5
2
1
3
7
6
3
4
2
Q = {a, 2, 7}
R = {b, 3, 4, 5, 6}
c(Q,R) = c
a3+ c
a4+ c
76+ c
7b= 21
PROBLEMA del minimo taglio a-b: trovare un taglio a-b (Q, R) di capacità minima • Equivalente al problema del massimo flusso inviabile da a a b.
17
Trasformazione in min-cut
• In primo luogo si costruisce un grafo orientato H = (W, A) con capacità caper aA. - Per ogni i V, sia Wi = {vit: ESTi d t d LSTi + 1} ovvero, per ogni attività i c’è un nodo per ogni possibile istante iniziale + un nodo finale.
Insieme dei nodi W = iWi {a, b}, ovvero tutti i nodi associati alle attività, più due nodi fittizi che saranno sorgente e pozzo del grafo.
- Archi A: unione di tre insiemi di archi
archi di assegnamento: {(vit, vit+1): i
V, vit,vit+1 Wi}: quindi ogni attività definisce un cammino (vi,EST(i), vi,EST(i)+1), …, (vi,LST(i), vi,LST(i)+1)archi di temporali: {(vit, vjt+l(i,j)): vit Wi vjt+l(i,j) Wj} sono gli archi che rappresentano le relazioni temporali fra attività
archi fittizi:
{(a,vi,EST(i)): i V} un arco dalla sorgente a al primo nodo del cammino associato all’attività i
{(vi,LST(i)+1, b): i V} un arco dall’ultimo nodo del cammino associato all’attività i al pozzo b
- Capacità: capacità degli archi assegnamento (vit, vit+1) pari a wit. Tutte le altre capacità pari a +.
18
Esempio di grafo orientato
1 2 3 5 4 1 -2 2 3 j durata EST LST 1 1 0 3 2 1 1 4 3 2 0 3 4 2 0 2 5 1 3 5 6 0 5 6 j\t 0 1 2 3 4 5 1 2 3 4 5 2 5 3 4 4 3 4 3 4 1 4 5 2 1 5 1 3 7 v22 a v10 v11 v12 v13 v14 b v21 v23 v24 v25 v30 v31 v32 v33 v34 v40 v41 v42 v43 v53 v54 v55 v56 2 3 4 5 5 3 4 4 4 3 4 1 1 3 7 1 2 5 + + + w
OSS. Possono essere omessi gli archi temporali entranti nel primo nodo e uscenti dall’ultimo nodo di ogni attività.
19
Equivalenza piani/tagli
Lemma 1. Ogni soluzione ammissibile di costo pari a corrisponde a un taglio (Q ,R) nel grafo H di capacità pari a c(Q,R) = .
x wT x
x wT
Dim. Per ogni attività i V esiste un solo t(i) T per cui xit(i) 1 (si t(i)) Poni Q = {vit: i V, t d si}, R = W-Q.
Quali archi attraversano il taglio da Q a R?
• Nessun altro arco.
n s n s s T x w w w w ... 2 1 2 1
• Gli i archi (di assegnamento) da vit(i)a vit(i)+1di capacità pari a wit(i) . La capacità complessiva di questi archi è proprio pari a
V i x T it
¦
1 [5.1]c. viq Q, implica si t q. vjp R implica sj< p sj- si < p – q. contrad. b. Poiché (viqvjp) attraversa da Q a R, viq Q, e vjp R
a. Poiché c’è un arco (viqvjp), esiste un vincolo sj- si t lij = p – q.
• Grazie a [5.1], per ogni attività i esiste vitQ con EST(i) d t d LST(i) mentre si ha sempre vi,LST(i)+1R.
• Per assurdo, se un arco temporale (viqvjp) attraversa il taglio:
20
Esempio di grafo orientato
v22 v10 v11 v12 v13 v14 b v21 v23 v24 v25 v30 v31 v32 v33 v34 v40 v41 v42 v43 v53 v54 v55 v56 2 3 4 5 5 3 4 4 4 3 4 1 1 3 7 1 2 5 + + + R a Q Soluzione ammissibile x10= x23= x31= x40= x53= 1 s1= s3= s4= 0, s2= 3, s5= 3
Equivalenza tagli/piani
Lemma 2. Sia (Q ,R) un taglio di capacità finita nel grafo H. Allora esiste una soluzione x’ di costo wTx’ d c(Q,R).
La dimostrazione costruttiva viene omessa. La costruzione consiste nel definire una soluzione x associata al taglio ponendo xit = 1 se vit è l’ultimo nodo
associato ad i in Q (ovvero se esiste vir
z
vitin Q, allora sarà r < t). Dai due lemmi precedenti si ricava:Teorema. Sia (Q* ,R*) un taglio di capacità minima nel grafo H e sia x* una soluzione ottima di P. Allora wTx* = c(Q*,R*).
• P può essere risolto utilizzando un algoritmo che calcola un taglio a capacità minima fra a e b in H.
• Il taglio a capacità minima può essere calcolato utilizzando l’algoritmo di Ford e Fulkerson per il flusso massimo da a a b. (capacità del taglio minimo = valore del flusso massimo).
