Il vantaggio di usare strumenti LP è di astrarsi dalla programmazione software e concentrarsi solo sulla formulazione matematica. Ciò non toglie che si può programmare in progetti più grandi con C/C++/Java e librerie LP disponibili (come le API offerte da GNUWin32 o anche per Linux/Unix con l'uso di Database).
Vediamo un classico: dovete fare con Microsoft Project un diagramma di GANTT con risorse, task in cascata o parallelizzabile e le milestone con ogni opportuna data e descrizione; poi vi hanno richiesto il diagramma di Pert per comprendere i task critici. Sapete l'inizio e la fine desiderata, quanto serve per ogni attività, quante persone, ma occorre far entrare il tutto nel periodo richiesto. E' possibile o impossibile? Come e quali attività si devono parallelizzare? Quello ottenuto è il meglio possibile o esistono anche altre soluzioni?
Al di là di ulteriori elementi che dipendono dal tipo di lavoro in gioco, stiamo parlando di un problema di pianificazione o scheduling, che rientra tra i problemi NP-completi!
In sostanza le stesse informazioni accennate sopra, come barre nel GANTT e le timeline si possono tradurre in un grafo matematico dove i nodi possono essere i nomi dei task, gli archi orientati il cambio di sequenza da un task ad un altro (e la dipedendenza anche tra essi sequenziale), mentre i pesi sugli archi possono rappresentare il tempo necessario allo svolgimento del task. Nel grafo potremmo avere anche parallelizzazioni di task , cioè situazioni in cui da un nodo escono contemporaneamente più archi verso altri nodi.
Con un grafo, quindi, si possono formulare varie tipologie di problemi. Per grafo pesato orientato intendiamo
una struttura G(N, A), con N insieme dei nodi e cardinalità | N |, ed A insieme degli archi e cardinalità | A |.
L'insieme degli archi, A, è caratterizzato da un orientamento da nodo origine ad uno destinazione i,j.
In generale l'obiettivo di un "problema di scheduling" matematico è di ottimizzare una o più grandezze di
performance tra le seguenti:
- minimizzare la massima "lateness" o il massimo ritardo (non dite che ve l'ho detto io!)
- minimizzare i costi/tempi del setup
- minimizzare il "makespan" (la massima lunghezza temporale o l'elapsed time totale)
Per risolvere, nel miglior modo possibile, un tale problema sono possibili varie strategie:
1 - algoritmi tipici della teoria dello scheduling
2 - algoritmi legati ai grafi
Un algoritmo tipico della teoria dello scheduling è quello MST (Minimum Spanning Tree) o minimo albero ricoprente. Nel MST il problema è definito nel seguente modo: sia dato un grafo orientato pesato G(N, A), con un insieme di interi senza segno definito sugli archi, allora l'obiettivo è quello di determinare una struttura che connetta tutti i nodi del grafo con archi di peso minimo.
Un albero ricoprente di costo minimo è tipicamente una struttura con un unico nodo origine, detto radice, ed una serie di rami; il "cammino" da individuare è composto dall'insieme dei nodi in una sequenza tale che la somma dei pesi sui rami sia la minima possibile.
E' evidente che l'MST ci porta a minimizzare il "makespan". Poichè abbiamo a che fare con un grafo a numero di nodi fissi, (ricordate cosa abbiamo detto circa il problema di Steiner?) allora è possibile usare l'algoritmo di Kruskal (vi rimando al blog precedente per tale algoritmo).
Ma dobbiamo aprire una parentesi sui labirinti per comprendere il punto 2 precedente e concludere il discorso sullo scheduling. Quindi c'è un interrupt e salvate un attimo il contesto sullo stack.
Come vedremo le tecniche di ottimizzazione congiunte spesso vengono utilizzate per risolvere problemi complessi che non ricadono in una branca specifica dell'ottimizzazione.
Un tipico algoritmo per trattare i labirinti è l'algoritmo di Tremaux. Ne esistono anche altri per la robotica, euristici e random (vedi Wikipedia) ma qui è sufficiente quello classico.
L'algoritmo di Tremaux consiste nel seguire un percorso, scelto a caso all'interno del labirinto, fino a raggiungere un incrocio, marcando la via che è stata percorsa fino a quel momento (nel caso in cui il corridoio conduca a un vicolo cieco è necessario tornare indietro fino all'incrocio precedente, marcando la via all'andata e al ritorno).
Quando si giunge a un incrocio di più corridoi si prende preferibilmente una via che non è stata segnata come percorsa in precedenza, e se ciò non è possibile si prende una via percorsa una sola volta. In ogni caso non è permesso scegliere una via che è stata già marcata due volte. Iterando il procedimento per ogni incrocio che si trova sul proprio percorso, l'algoritmo permette di raggiungere l'uscita (o se il labirinto non ha altre uscite oltre a quella imboccata per entrare, di tornare all'entrata).
La "tecnica di backtracking" è una tecnica euristica generale utilizzabile nei grafi e negli alberi; serve a tracciarsi i percorsi e durante esso appena si ottiene una informazione che il cammino fatto è peggiore di un altro si scarta e si ritorna indietro per un ramo non percorso. Alla fine si rimane col miglior percorso tracciato.
Se ci riflettiamo, una pianificazione assomiglia un pò all'attraversamento di un labirinto, dove ci sono un ingresso/inizio ed una uscita/fine, e dove occorre scegliere i percorsi e marcandoli, in che direzione li percorriamo (grafo orientato) e se una o due volte.
Il percorso o cammino in effetti è l'insieme dei rami/task da scegliere da legare insieme; mentre lungo il ramo del percorso troviamo degli oggetti di un certo peso da mettere in uno zaino, che potrebbero essere anche dei job da fare per ottenere un oggetto finito.
Mi direte ma nel labirinto non c'è parallelismo ... non è detto: dipende da quante persone lo percorrono contemporaneamente.
E' come se il problema dello scheduling fosse riconducibile a vari sottoproblemi:
- teoria dei grafi e dei labirinti
- algoritmi della teoria scheduling
- il problema dello zaino
In effetti di un labirinto, almeno inizialmente, nessuno ne conosce i percorsi, così come nelle pianificazioni che occorre studiare bene come ottenere una pianificazione decente e coerente.
Da quanto detto un labirinto è rappresentabile con un grafo orientato ed in esso occorre:
- individuare il percorso
- individuare gli elementi secondo una tecnica di backtracking
In particolare durante l'attraversamento di un labirinto ci si segna i nodi e gli archi orientati e il relativo peso.
Una volta individuato il labirinto occorre iniziare a vedere quale oggetto/task ooccorre estrarre per arrivare alla successiva lavorazione. Occorre stare attenti a semplificare il problema altrimenti si arriva ad aggiungere molte condizioni e vincoli che aumentano il costo dell'elaborazione. La strategia di scelta degli oggetti/task deve essere, difatti, quella che è in relazione alla sequenza ottima che minimizza il makespan, il peso degli oggetti e i tempi di computazione.
Non si può usare prima la tecnica dello zaino e poi la tecnica del MST perchè si arriverebbe ad una soluzione non necessariamente la migliore in termini di schedulazione; per cui la soluzione migliore è di fare prima un algoritmo che restittuisca il makespan a cui si applica la tecnica dello zaino.
Supponiamo che ci siano n task che m macchine possono lavorare in parallelo, col vincolo di preemption, e che un task startato su una macchina può continuare su una macchina differente, a seguito di interruzione sulla macchina precedente.
Chiamiamo Cmax il tempo massimo di lavorazione in cui le m macchine devono completare gli n task:
Cmax = max(1<=j<=n) Cj
Mentre xij= frazione di task j lavorata sulla macchina i, col vincolo che Sum(i=1,m, xji) = 1 (Che esprime che una sola macchina per volta lavora un task: non è consentita la preemption). In particolare xji={0,1}.
Il tempo totale di lavoro della macchina i è: ki=Sum(j=1,n,pj*xji).
Riassumendo la formulazione in LP è:
min Cmax
Sum(j=1,n,pj*xji) <= Cmax
Sum(i=1,m, xij) = 1
xji>=0
E' vera la seguente affermazione: Sia x* una soluzione che soddisfa tutte le condizioni e vincoli, allora x* è la soluzione ottima.
Infatti rispetto a x* tutte le macchine hanno lo stesso carico e terminano in Cmax. Se x* non fosse la soluzione ottima e le macchine lavorassero con carico sbilanciato, significa che si potrebbe ridurre lo stesso il makespan ridistribuendo il lavoro sulle varie macchine il carico che era maggiore su una delle macchine. Ma questo ci riporterebbe a dire che x* non era ottimo ma che ne esiste un altro valore ottimo (ma che soprattutto non erano soddisfatte bene tutte le condizioni).
In particolare Cmax(x*) = 1/m * Sum(j=1,m,pj). Quindi siamo alla ricerca di un vettore x* delle variabili decisionali e una volta trovato x* si può passare a studiare il problema del sacco (knapsack).
Il problema, come già più volte evidenziato, può essere formulato nel seguente modo. Si hanno a disposizione n oggetti, ciascuno con valore vi e costo ci; nella fattispecie, tali parametri possono essere rivisti come tempo di processamento e peso. In questo caso il problema può essere espresso come massimizzazione del valore, nel rispetto della sequenza makespan e minimizzazione del peso, visto che dovranno essere effettuati diversi viaggi.
Se C è la disponibilità massima del trasporto, si avrà:
max F = Sum(i=1,n,vi*xi)
Sum(i=1,n,ci*xi)<=C con xi={0,1}
La programmazione dinamica si può espletare nel seguente modo:
- determinare il cammino e la lista di oggetti;
- implementare il makespan e determinare la sequenza di schedulazione;
- entrare nel labirinto e con la procedura di knapsack riempire il sacco, uscire ed avviare il processamento; mentre ciò avviene, rientrare nel labirinto e prelevare un altro sottoinsieme di oggetti fintantochè tutti gli oggetti non sono stati rimossi dal labirinto stesso.
Un'ulteriore complicazione può essere data dall'inserimento nel vincolo di rispetto della sequenza, e che negli intervalli di tempo in cui l'operatore sta asportando gli oggetti dal labirinto, almeno un processamento sia in atto; cioè l'insieme delle macchine non deve mai essere inoperoso. Chiaramente tale fatto complica notevolmente la soluzione del problema.
Per fissare i concetti di sopra vediamo però un esempio concreto in LP di una pianificazione di task e risorse umane, potrebbe essere anche un orario scolastico ad esempio.
Si possono risolvere problemi molto complessi (in questi ambiti basta poco per complicarli) e realizzare sistemi con Database Oracle, PL/SQL e con un motore risolutore GPLK. Nel seguito esamineremo un
problemino di schedulazione semplice.
Problemino di schedulazione
In un impianto di produzione di tutti i giorni un certo numero di personale è necessario. Il personale può essere essere assunto per un minimo fino ad un numero massimo di giorni consecutivi, richiede un numero minimo di giorni di ferie prima di poter essere nuovamente utilizzati. Il compito è di trovare
l'orario di lavoro riducendo al minimo salario totale da pagare.
Ecco come formuliamo il problemqa in CMLP:
# Personnel assignment problem
#
#
# workload (day, workload)
set L, dimen 2;
# workers (name, min workdays, max workdays, minimum leave, wage)
set W, dimen 5;
# names of workers
set V := setof{(v, b, c, d, e) in W} v;
# periods
set B := ( (min{(b,c) in L} b) .. (max{(b,c) in L} b) );
# minimum number of workdays in row
param ri{v in V} := min{(v, b, c, d, e) in W} b;
# maximum number of workdays in row
param ra{v in V} := min{(v, b, c, d, e) in W} c;
# minimum leave days in row
param ml{v in V} := min{(v, b, c, d, e) in W} d;
# wage
param wa{v in V} := min{(v, b, c, d, e) in W} e;
# work offer [worker, start, duration]
# (for large problems consider column generation to create work offers)
set O := setof{ v in V, s in B, d in {ri[v]..ra[v]}}( v, s, d);
# workday
param wd{b in B, (v, s, d) in O} :=
if b < s then 0 else if b - s > d - 1 then 0 else 1;
# leaveday
param ld{b in B, (v, s, d) in O} :=
if b < s + d then 0 else if b - s > d + ml[v] - 1 then 0 else 1;
# work offer used
var x{(v,s,d) in O}, binary;
# minimze total wage
minimize wage :
sum{b in B, (v,s,d) in O} x[v,s,d] * wd[b,v,s,d] * wa[v];
# worker can do one job only
s.t. j1{b in B, v in V} :
sum{(v,s,d) in O} x[v,s,d] * ( wd[b,v,s,d] + ld[b,v,s,d] ) <= 1;
# do all jobs
s.t. ja{b in B} :
sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] >= sum{(b, w) in L} w;
solve;
# output solution
printf "\n%-10s", "Day";
for {v in V}
printf "| %-10s", v;
printf "\n";
printf "%-10s", '----------';
for {v in V}
printf "+-%-10s", '----------';
printf "\n";
for {b in B}
{
printf "%9i ", b;
for {v in V}
printf "| %-9s ",
if sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] then "working"
else "on leave";
printf "\n";
}
printf "\n";
data;
# workload
set L := # day, workload
( 1, 3)
( 2, 1)
( 3, 1)
( 4, 1)
( 5, 1)
( 6, 2)
( 7, 2)
( 8, 2)
( 9, 3)
(10, 2)
(11, 2)
(12, 2)
(14, 1)
(15, 2)
(17, 3)
(18, 3)
(19, 2)
(21, 3)
(23, 1)
(24, 3)
(25, 3)
(26, 3)
(27, 2)
(28, 1)
(29, 1)
(30, 2)
(31, 1)
(32, 3)
(33, 2)
(35, 3)
(36, 3)
(37, 1)
(38, 3)
(39, 2)
(40, 3)
(43, 1)
(44, 1)
(45, 2)
(46, 2)
(47, 3)
(48, 2)
(49, 1)
(50, 2);
# workers
set W := # name, min workdays, max workdays, minimum leave, wage
( 'Anna', 5, 8, 2, 470 )
( 'Isabel', 5, 8, 2, 500 )
( 'Jack', 1, 8, 2, 1000 )
( 'John', 5, 8, 2, 600 )
( 'Lisa', 3, 5, 3, 640 );
end;
Ora eseguiamo il file scritto.
K:\Work\LP>glpsol --model workload.txt
Reading model section from workload.txt...
Reading data section from workload.txt...
147 lines were read
Generating wage...
Generating j1...
Generating ja...
Model has been successfully generated
ipp_basic_tech: 8 row(s) and 8 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 293 rows, 1142 columns, 13200 non-zeros
glp_intopt: 1142 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 293
Solving LP relaxation...
0: obj = 0.000000000e+000 infeas = 8.700e+001 (0)
* 100: obj = 8.699000000e+004 infeas = 0.000e+000 (0)
* 200: obj = 5.981000000e+004 infeas = 6.106e-016 (0)
* 338: obj = 5.253000000e+004 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+ 338: mip = not found yet >= -inf (1; 0)
+ 361: >>>>> 5.263000000e+004 >= 5.254000000e+004 0.2% (3; 0)
+ 371: mip = 5.263000000e+004 >= tree is empty 0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used: 0.2 secs
Memory used: 20.6 Mb (21554667 bytes)
Day | Anna | Isabel | Jack | John | Lisa
----------+-----------+-----------+-----------+-----------+-----------
1 | on leave | working | working | on leave | working
2 | on leave | working | on leave | on leave | working
3 | on leave | working | on leave | on leave | working
4 | on leave | working | on leave | on leave | on leave
5 | on leave | working | on leave | on leave | on leave
6 | working | working | on leave | on leave | on leave
7 | working | working | on leave | on leave | on leave
8 | working | on leave | on leave | working | on leave
9 | working | on leave | working | working | on leave
10 | working | on leave | on leave | working | on leave
11 | working | on leave | on leave | working | on leave
12 | working | on leave | on leave | working | on leave
13 | on leave | on leave | on leave | on leave | on leave
14 | on leave | working | on leave | on leave | on leave
15 | working | working | on leave | on leave | on leave
16 | working | working | on leave | on leave | on leave
17 | working | working | on leave | on leave | working
18 | working | working | on leave | on leave | working
19 | working | on leave | on leave | on leave | working
20 | working | on leave | on leave | on leave | on leave
21 | working | working | working | on leave | on leave
22 | on leave | working | on leave | on leave | on leave
23 | on leave | working | on leave | on leave | on leave
24 | working | working | on leave | on leave | working
25 | working | working | on leave | on leave | working
26 | working | working | on leave | on leave | working
27 | working | working | on leave | on leave | on leave
28 | working | on leave | on leave | on leave | on leave
29 | working | on leave | on leave | on leave | on leave
30 | working | on leave | on leave | on leave | working
31 | on leave | on leave | on leave | on leave | working
32 | on leave | working | on leave | working | working
33 | on leave | working | on leave | working | on leave
34 | on leave | working | on leave | working | on leave
35 | working | working | on leave | working | on leave
36 | working | working | on leave | working | on leave
37 | working | working | on leave | on leave | on leave
38 | working | working | on leave | on leave | working
39 | working | on leave | on leave | on leave | working
40 | working | on leave | working | on leave | working
41 | on leave | on leave | on leave | on leave | on leave
42 | on leave | on leave | on leave | on leave | on leave
43 | working | on leave | on leave | on leave | on leave
44 | working | on leave | on leave | on leave | on leave
45 | working | on leave | on leave | on leave | working
46 | working | on leave | on leave | on leave | working
47 | working | working | on leave | on leave | working
48 | working | working | on leave | on leave | on leave
49 | on leave | working | on leave | on leave | on leave
50 | on leave | working | on leave | working | on leave
Model has been successfully processed
Un consiglio. E' ovvio che lo strumento vi calcola il tutto in base ai dati che gli avete fornito e funziona benissimo quando la durata del tempo è ben fissata da regole, come nell'organizzazione di orari, turni etc.
Mentre nelle pianificazioni di lavori come realizzazione di un software, molto della pianificazione dipende da voi nel saper ben valutare il tempo, le persone disponibili e l'organizzazione e professionalità necessarie per svolgere un task, etc. Per questo vi affiderete a statistiche che avete raccolto nel tempo nell'effettuare quel lavoro o a metodologie specifiche o a regolamentazioni previste per quel lavoro.
Alla prox
Iscriviti a:
Commenti sul post (Atom)
Post
0 commenti:
Posta un commento