Programmazione Lineare – Schedulazioni vincenti, labirinti tenebrosi, con il bastone da...

Programmazione Lineare – Schedulazioni vincenti, labirinti

tenebrosi, con il bastone da maresciallo nello zaino ing. R. Turco ([email protected])

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

dipendenza 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 |.

mailto:[email protected]

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:

algoritmi tipici della teoria dello scheduling

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 po’ 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 occorre

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

restituisca 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.

Problema 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 )

Programmazione Lineare – Schedulazioni vincenti, labirinti tenebrosi, con il bastone da...

Documents

Transcript of Programmazione Lineare – Schedulazioni vincenti, labirinti tenebrosi, con il bastone da...