Teoria della schedulazione

Da Wikipedia, l'enciclopedia libera.

Sequenziamento e schedulazione sono forme di processi decisionali, “decision-making”, che consistono nell’allocare risorse finite in modo tale che un dato obiettivo venga ottimizzato. Esempi tipici di risorse limitate sono le macchine di un’impresa manifatturiera, le ore di manodopera settimanali delle infermiere in un ospedale o delle commesse in un negozio, le piste di atterraggio-decollo di un aeroporto, mentre esempi di obiettivi da ottimizzare sono il tempo per completare un progetto, il tempo di attesa di un aereo in volo o di un lotto da lavorare davanti a una macchina operatrice, il costo delle ore straordinarie, il costo delle penali per ritardi nelle consegne di un bene-servizio-lavoro. La distinzione tra sequenziamento e schedulazione consiste nel fatto che la prima ha a che fare solo con l’ordinamento delle operazioni da eseguire, mentre la seconda sincronizza e tempifica la sequenza delle operazioni. La schedulazione contiene cioè anche informazioni temporali che specificano la tempistica delle singole attività, pertanto in generale la schedulazione include il sequenziamento. Un problema di sequenziamento o schedulazione contiene le seguenti informazioni:

  • le variabili decisionali
  • il criterio con il quale le variabili decisionali vengono valutate (misura di prestazione)
  • la regione ammissibile entro la quale le variabili decisionali possono variare

Una soluzione di un problema, sequenza o schedula, consiste nell’individuare la decisione ottima nel senso specificato dal particolare criterio adottato. La sequenza specifica solo l’ordine delle operazioni-attività da eseguire, mentre la schedula specifica anche l’istante di inizio e di fine di ciascuna attività-operazione.

Sequenziamento[modifica | modifica sorgente]

I problemi di sequenziamento intervengono ogniqualvolta si debba decidere l’ordine con il quale un dato numero di attività, ‘task’, debba essere svolto. Esempi di problemi di sequenziamento sono gli aerei in volo in attesa dell’autorizzazione all’atterraggio o al decollo, i clienti in coda davanti ad uno sportello o in attesa al telefono di un qualche call-center, i programmi di un computer da eseguire in un’unità di calcolo, i lotti da lavorare a bordo di una certa macchina operatrice, il giro delle consegne da parte di una società di distribuzione, le differenti partite di olio grezzo da distillare in una raffineria. A denominatore comune dei problemi di sequenziamento vi è il tempo interpretato come risorsa scarsa da allocare in modo ottimale ed in generale la loro risoluzione consiste nel determinare la permutazione delle variabili decisionali affinché il tempo venga minimizzato. In ultima analisi un problema di sequenziamento è un problema di ottimizzazione combinatoria. Ad esempio nel problema base del sequenziamento di n lotti per una macchina singola, il numero di sequenze distinte ammissibili è pari a n! cioè il numero di differenti permutazioni di n elementi.

One-machine sequencing problem[modifica | modifica sorgente]

Siano assegnate una macchina ed un insieme di n lotti che devono tutti essere lavorati a bordo della stessa. Ogni lavorazione richiede un certo tempo, non può essere interrotta (not preemption) e non richiede alcun tempo di attrezzaggio (setup), qualora esista un tempo di attrezzaggio questo si suppone che non dipenda dall’ordine dei lotti da lavorare: se il tempo di setup dipende solo da un particolare lotto allora può essere incluso nel tempo di lavorazione del lotto stesso. Inoltre si ipotizza che i lotti siano disponibili alla lavorazione nello stesso istante ovvero che la macchina possa iniziare una lavorazione con uno qualsiasi di essi. Il problema di sequenziamento per una macchina singola consiste nel determinare l’ordine con cui i lotti devono essere lavorati in modo tale da minimizzare uno dei seguenti criteri di valutazione:

Nel seguito si riportano i principali risultati della teoria della schedulazione per una macchina singola.

  • Il mean flowtime è minimizzato ordinando i lotti in sequenza non-decrescente dei tempi di processo (SPT-Shortest Processing Time).

Ricordando che il numero medio di scorte in un sistema è direttamente proporzionale al flow-time medio, ne consegue che la sequenza che minimizza il flow-time medio minimizza anche il numero medio di scorte in un sistema; pertanto il SPT risolve anche il problema di minimizzare le scorte di magazzino ed i relativi costi.

  • Le seguenti misure di prestazione sono equivalenti: il tempo medio di completamento dei lotti, il flow-time medio, il tempo totale di attesa dei lotti in coda alla macchina, il ritardo totale medio.

Questo teorema significa che se una sequenza è ottimale per un criterio allora è ottimale anche per i rimanenti criteri.

Nel caso i lotti siano soggetti a date di consegna (due date) allora per essi si applica la seguente regola di carico:

  • Il massimo ritardo tra i lotti è minimizzato ordinando i lotti in sequenza non-decrescente dei tempi di consegna (EDD-Earliest Due Date).

In aggiunta alla lampante situazione di un reparto manifatturiero che presenta una sola macchina, esistono numerosi casi in cui gli impianti si comportano come una macchina singola: si pensi all’industria chimica e di processo in cui l’intero stabilimento è un insieme integrato di processi che operano su numerosi diversi elementi in successione. In un sistema produttivo con più macchine può accadere che esista una macchina che presenti la capacità produttiva più bassa e ad essa ci si riferisce come collo di bottiglia in quanto il reparto è “dominato” da tale macchina. Ne consegue che l’ottimizzazione del processo produttivo per un ambiente con più macchine può essere semplificato in un problema di schedulazione per la macchina collo di bottiglia: la sequenza di lotti assegnata al collo di bottiglia determinerà la prestazione dell’intero sistema. Se si suppone che i tempi di setup dipendano dalla sequenza dei lotti, allora si è in presenza di un problema di schedulazione in quanto il tempo di completamento degli n lotti dipende da come effettivamente i lotti vengono ordinati. La sua soluzione è una schedula che minimizza gli n tempi di setup. Il tipico esempio di attività dipendente da setup si trova nei reparti di verniciatura o di stampaggio per pressofusione di pezzi in pvc colorati: ogniqualvolta il colore cambia, la tramoggia contenente il colore deve essere sostituita e la pressa ad iniezione deve essere pulita del colore residuo. Nella pratica si preferisce andare da colori chiari a colori scuri in quanto il tempo di pulitura è più breve.

Flow-shop scheduling problem[modifica | modifica sorgente]

Assegnate m macchine ed un insieme di n lotti, su questi ultimi si devono eseguire m lavorazioni: ogni macchina è dedicata a fare una sola lavorazione. Ogni lavorazione richiede un dato tempo, non può venire interrotta (not preemption) e può essere eseguita da ciascuna macchina una alla volta. Un flow-shop è una configurazione di macchine per cui il flusso dei lotti è unidirezionale, lineare e segue il medesimo ordine da una macchina all’altra, più precisamente se un lotto deve essere lavorato prima su una macchina e poi su un'altra questo ordine di lavorazione vale per tutti i lotti inoltre se una macchina lavora un lotto prima di un altro allora questo ordinamento dei lotti si conserva per tutte le rimanenti macchine. Un flow-shop contiene dunque un ordinamento naturale delle macchine. Se a priori non esistono vincoli di precedenza tra i diversi lotti, un problema di schedulazione per un flow-shop consiste nel trovare la sequenza dei lotti che minimizzano il tempo di completamento di tutte le lavorazioni oppure il tempo di ritardo complessivo oppure il flow-time massimo.


Macchine parallele[modifica | modifica sorgente]

Si supponga che siano presenti m risorse parallele ossia che esistano m macchine disponibili per lavorare contemporaneamente n lotti tutti pronti ad essere processati al tempo zero. In aggiunta si ipotizzi che ogni lotto possa essere lavorato al massimo da una macchina sola. Il problema consiste nell’allocare sia le risorse che nello schedulare i lotti. Le risorse possono essere costituite da: macchine identiche, uniformi o non correlate. Macchine identiche presentano tra loro il medesimo tempo di lavorazione, macchine uniformi hanno tempi di lavorazione proporzionali tra loro, infine le macchine non correlate hanno tempi di processo che variano in modo del tutto arbitrario. Indicato con il termine makespan il tempo intercorrente tra l’inizio della lavorazione del primo lotto e il completamento dell’ultimo lotto, nel problema a una macchina singola con sequenze indipendenti dal set-up tale grandezza è una costante, ovvero non dipende dalla particolare sequenza adottata. Nel caso di macchine parallele invece il makespan è variabile e pertanto può essere utilizzato come indicatore di prestazione. In generale un problema di scheduling con macchine parallele può essere risolto in due fasi soprattutto per situazioni con un elevato numero di combinazioni: in una prima fase si allocano i lotti nel modo più equo, più uniforme possibile tra tutte le macchine e poi per ciascuna macchina si determina separatamente la sequenza ottimale. Una formulazione in termini di programmazione lineare del problema per macchine identiche senza possibilità di preempiton è la seguente:

Funzione obiettivo:

 min C_{max}

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l} 
C_{max}  -  \sum_{i=1}^n x_{i,1} \cdot \ p_{i} \ge 0   \\ 
\vdots \\
C_{max}  -  \sum_{i=1}^n x_{i,m} \cdot \ p_{i} \ge 0   \\ 
\sum_{i=1}^n x_{i,k} = 1   \forall \ k \\
\sum_{k=1}^n x_{i,k} = 1   \forall \ i  \\
x_{i,k} \in \mathcal{f} 0 ; 1 \mathcal{g} \forall \ i, k
\end{array} \right.

Quando la preemption è permessa, la lavorazione di un lotto può essere interrotta e la rimanente lavorazione può essere eseguita più tardi, magari su una macchina diversa. Per modellizzare la preemption è sufficiente rimuovere, in gergo rilassare, il vincolo di interezza per le variabili decisionali  x_{i,j} e sostituirlo con  x_{i,j} \ge 0 \forall \ i,j  . Si osservi che il modello non fornisce una schedula dei tempi, ma semplicemente la ripartizione dei lotti tra le macchine in modo da minimizzare il makespan.

Job-shop scheduling problem[modifica | modifica sorgente]

Si consideri un sistema produttivo costituito da m macchine da utilizzarsi per lavorare n lotti: nei problemi di schedulazione di tipo job shop il flusso delle lavorazioni non è unidirezionale ed ogni lotto ha esattamente m operazioni da essere eseguite, una per ciascuna macchina. Questo significa che la sequenza delle operazioni non è definita dall’ordinamento delle macchine come nel flow-shop: non esiste una macchina k-esima dedicata ad eseguire solo la lavorazione k-esima su ogni lotto; pertanto è necessario caratterizzare ogni lavorazione con tre indici che specificano il lotto, la macchina e l’operazione. L’assegnazione delle operazioni alle macchine per un dato lotto rappresenta l’instradamento o percorso, in gergo routing, del lotto stesso.

Metodi risolutivi[modifica | modifica sorgente]

In generale trovare la soluzione ottima di un problema di schedulazione richiede di enumerare tutte le possibili soluzioni e di selezionare la migliore. I metodi di risoluzione si classificano in due macro-classi: i metodi esatti ed i metodi euristici. I metodi esatti si distinguono a loro volta in:

  • Metodi Costruttivi: si costruisce una soluzione ottima sulla base dei dati del problema seguendo una serie di semplici regole di priorità. Un esempio è rappresentato dalle regole di priorità SPT ed EDD.
  • Metodi Enumerativi: si enumerano tutte le possibili soluzioni, si eliminano quelle che non sono ottimali dalla lista e si seleziona la migliore schedula. La Programmazione dinamica consiste nel decomporre il problema in sotto-problemi più piccoli che vengono risolti in modo ricorsivo in modo da ridurre il tempo computazionale: la soluzione trovata per ogni sotto-problema contribuisce alla soluzione del problema successivo sino a quando si determina la soluzione del problema originale. La modelizzazione in forma stilizzata dei problemi di schedulazione come programmi lineari consente invece di ottenere la soluzione ottima mediante algoritmi esatti.

L’approccio con metodi esatti è tuttavia applicabile solo a problemi con un numero ridotto di lotti, mentre nella realtà i problemi sono di larga dimensione e quindi non possono essere risolti in modo esatto con tempi di calcolo ragionevoli. Si ricorre pertanto a metodi di soluzione euristici di ricerca locale quali ad esempio tabu search, simulated annealing, algoritmi genetici. I metodi euristici non determinano una soluzione ottima del problema, ma solo una soluzione sub-ottimale ottenuta con algoritmi approssimati.

Modelli di programmazione lineare[modifica | modifica sorgente]

Macchina singola[modifica | modifica sorgente]

Nel seguito si fornisce la formulazione in termini di programmazione lineare di un generico problema di sequenziamento a una macchina. Dati n lotti da sequenziare si introducono n variabili non negative  A_i ed n^2 variabili binarie x_{i,j}, in totale le variabili da gestire per un problema con n lotti sono n + n^2.

 A_i : indica il tempo di attesa tra il completamento del lotto in posizione i-1 e l’inizio della lavorazione del lotto successivo in posizione i-esima

 p_k : è il tempo per la lavorazione del lotto k-esimo

 r_k : è l’istante in cui il lotto k-esimo è disponibile per la lavorazione (ready time)

x_{1,1},…,x_{1,n}, …, x_{n,1},…,x_{n,n}: n^2 variabili binarie associate agli n lotti

Per ogni lotto quindi si introducono n variabili binarie x_{i,j} che indicano la posizione del lotto nella sequenza ottimale. La stringa x_{i,1}=0,…,x_{i,k}=1, …, x_{i,n}=0 significa che il lotto i-esimo viene lavorato in posizione k. La soluzione del problema di sequenziamento ottimale risiede proprio nel valore di queste variabili binarie.


Funzione obiettivo:

 min\sum_{i = 1}^n A_i

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l} 
A_1 =  \sum_{i=1}^n x_{i,1} \cdot \ r_{i}  \\ 
A_2 = A_1 +  \sum_{i=1}^n x_{i,2} \cdot \ r_{i} +  \sum_{i=1}^n x_{i,1} \cdot \ p_{i} \\ 
\vdots \\
A_n = A_{n-1} +  \sum_{i=1}^n x_{i,n} \cdot \ r_{i}  +  \sum_{i=1}^n x_{i,n-1} \cdot \ p_{i} \\
\sum_{i=1}^n x_{i,k} = 1   \forall \ k \\
\sum_{k=1}^n x_{i,k} = 1   \forall \ i  \\
A_i \ge 0   \forall \ i  \\
x_{i,k} \in \mathcal{f} 0 ; 1 \mathcal{g} \forall \ i, k
\end{array} \right.

La sommatoria  \sum_{i=1}^n x_{i,k} \cdot \ p_{i} rappresenta il tempo per la lavorazione del lotto k-esimo in posizione ottimale sulla macchina. La sommatoria  \sum_{i=1}^n x_{i,k} \cdot \ r_{i} rappresenta l’istante in cui il lotto k-esimo è pronto per la lavorazione. Il vincolo di non simultaneità delle lavorazioni è  \sum_{i=1}^n x_{i,k} = 1, equazione che impone che in posizione k venga lavorato uno ed un solo lotto. Il vincolo di non ammissibilità della preemption è  \sum_{k=1}^n x_{i,k} = 1, equazione che impone che il lotto i-esimo venga assegnato ad una e una sola posizione. Si osservi che per  r_k = 0 per ogni k ci si riconduce al problema in cui i lotti sono tutti disponibili ad essere lavorati all’istante iniziale 0.

Problema con date di consegna[modifica | modifica sorgente]

Per completezza si fornisce la formulazione in termini di programmazione lineare di un generico problema di sequenziamento di n lotti con assegnate n date di consegna (due date). Per tenere conto della data di consegna si contabilizza l’eventuale ritardo delle consegne   \sum_{i = 1}^n R_i originato da una data sequenza, in questo modo la funzione obiettivo determina la sequenza dei lotti in modo che vengano versati in magazzino per rispettare le date di consegna richieste, nell’eventualità di ritardi il modello matematico determina la sequenza che minimizza i ritardi.

 p_{i} : è il tempo per la lavorazione del lotto i-esimo

 C_{i} : indica il tempo in cui il lotto i-esimo è completato

 t_1, t_2, \dots, t_n : date di consegna di ciascun lotto da convertire in ore o giorni come quantitativo di tempo disponibile dall’inizio della schedulazione

 T_1, T_2, \dots, T_n : indica la data di consegna dei lotti sequenziati, verrà calcolato come il quantitativo di ore/giorni dalla data di schedulazione alla data di consegna richiesta dal cliente

 R_1, R_2, \dots, R_n : quantificano l’eventuale ritardo


Funzione obiettivo:

 min \mathcal{f} \sum_{i = 1}^n C_i  + \sum_{i = 1}^n R_i \mathcal{g}

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l} 
C_1 =  \sum_{i=1}^n x_{i,1} \cdot \ p_{i}  \\ 
C_2 = C_1 +  \sum_{i=1}^n x_{i,2} \cdot \ p_{i} \\ 
\vdots \\
C_n = C_{n-1} +  \sum_{i=1}^n x_{i,n} \cdot \ p_{i} \\
T_1 =  \sum_{i=1}^n x_{i,1} \cdot \ t_{i}  \\ 
\vdots \\
T_n = \sum_{i=1}^n x_{i,n} \cdot \ t_{i} \\
R_1 =  C_1 - T_1   \\ 
\vdots \\
R_n =  C_n - T_n   \\
\sum_{i=1}^n x_{i,k} = 1   \forall \ k \\
\sum_{k=1}^n x_{i,k} = 1   \forall \ i  \\
C_i \ge 0   \forall \ i  \\
x_{i,k} \in \mathcal{f} 0 ; 1 \mathcal{g} \forall \ i, k
\end{array} \right.

Flow-shop a due macchine[modifica | modifica sorgente]

In aggiunta si fornisce la formulazione in termini di programmazione lineare di un generico problema di tipo flow-shop a due macchine, l’estensione al caso con m macchine è immediata.

 p_{k,1} : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina 1

 p_{k,2} : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina 2

 C_{1,k} : indica il tempo di attesa per completare la lavorazione del lotto k-esimo sulla macchina 1

 C_{2,k-1} : indica il tempo di attesa per completare la lavorazione del lotto k-1 sulla macchina 2

 M_i : indica il tempo di attesa della macchina 2 per lavorare il lotto i-esimo affinché il lotto i-esimo venga completato sulla macchina precedente

 L_i : indica il tempo in coda del lotto i-esimo alla macchina 2 affinché questa termini la lavorazione del lotto precedente i-1


Funzione obiettivo:

 min \mathcal{f} \sum_{i = 2}^n L_i  + \sum_{i = 2}^n M_i \mathcal{g}

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l} 
C_{1,1} =  \sum_{i=1}^n x_{i,1} \cdot \ p_{i,1}  \\ 
C_{1,2} = C_{1,1} +  \sum_{i=1}^n x_{i,2} \cdot \ p_{i,1} \\ 
\vdots \\
C_{1,n} = C_{1,n-1} +  \sum_{i=1}^n x_{i,n} \cdot \ p_{i,1} \\ 
C_{2,1} = C_{1,1} +  \sum_{i=1}^n x_{i,1} \cdot \ p_{i,2} \\ 
C_{2,2} = C_{2,1} +  \sum_{i=1}^n x_{i,2} \cdot \ p_{i,2} \\ 
\vdots \\
C_{2,n} = C_{2,n-1} +  \sum_{i=1}^n x_{i,n} \cdot \ p_{i,2} \\ 
C_{1,2} + L_{2} = C_{2,1} + M_{2} \\
C_{1,3} + L_{3} = C_{2,2} + M_{3} \\
\vdots \\
C_{1,n} + L_{n} = C_{2,n-1} + M_{n} \\
\sum_{i=1}^n x_{i,k} = 1   \forall \ k \\
\sum_{k=1}^n x_{i,k} = 1   \forall \ i  \\
L_i, M_i  \ge 0   \forall \ i  \\
x_{i,k} \in \mathcal{f} 0 ; 1 \mathcal{g} \forall \ i, k
\end{array} \right.

Le equazioni del tipo C_{1,k} + L_{k} = C_{2,k-1} + M_{k} fanno corrispondere il tempo di fine lavorazione del generico lotto in posizione k sulla macchina 1 più il tempo di attesa che la macchina 2 completi la lavorazione del lotto precedente k-1 al tempo di fine lavorazione del lotto k-1 sulla macchina 2 più il tempo di attesa che il lotto k sia ultimato sulla macchina 1.

Job-shop[modifica | modifica sorgente]

Si consideri un sistema produttivo costituito da M macchine da utilizzarsi per lavorare N lotti, job-shop: per semplicità di trattazione e notazione si assuma che ogni lotto debba essere lavorato da ogni macchina una ed una sola volta.

 p_{k,m} : è il tempo per la lavorazione del lotto k-esimo a bordo della macchina m

 x_{k,j,m} : è pari a 1 se la lavorazione j-esima del lotto k-esimo viene svolta sulla macchina m-esima; è pari a 0 altrimenti

 t_{k,m} : è l’istante di inizio della lavorazione del lotto k sulla macchina m

Per rappresentare i vincoli di precedenza della lavorazioni sulle M macchine come ad esempio il fatto che l’operazione j sul lotto k richiede la macchina m e l’operazione j+1 sul lotto k richiede la macchina h, si introducono (M-1)N vincoli del tipo seguente:

 \sum_{m=1}^M \left ( t_{k,m} + p_{k,m} \right ) \cdot \ x_{k,j,m } \le \ \sum_{m=1}^M t_{k,m} \cdot \ x_{k,j+1,m}

Inoltre è necessario ricorrere ad un gran numero di vincoli per impedire la lavorazione simultanea di due operazioni sulla stessa macchina, ovvero che in ogni istante di tempo solo ed un solo lotto possa essere in lavorazione a bordo di una macchina. Si introducono i vincoli disgiunti in numero M(N(N-1))/2

 \left\{ \begin{array}{l} 
t_{i,m} + p_{i,m} \ge \ t_{j,m} \ +  L\cdot \ \left (1-y_{i,j,m}) \right)  \\
t_{j,m} + p_{j,m} \ge \ t_{i,m} \ + L\cdot \ y_{i,j,m} \\
\end{array} \right.

dove L è una costante scelta sufficientemente grande, per esempio L=  \sum_{k=1}^N \sum_{m=1}^M p_{k,m} .

Infine  y_{i,j,m} : è pari a 1 se il lotto i-esimo precede il lotto j-esimo sulla macchina m, altrimenti è pari a 0. In altri termini, poiché per ipotesi ogni lotto viene lavorato da una macchina una ed una sola volta, a bordo della macchina m l’operazione i viene svolta prima dell’operazione j.

Per M macchine ed N lotti il modello formulato in termini di programmazione intera è il seguente, dove si minimizza la somma dei tempi di inizio di ciascun lotto.

Funzione obiettivo:

 min \sum_{k=1}^N \sum_{m=1}^M t_{k,m} \cdot \ x_{k,j,m}

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l}
\sum_{m=1}^M \left ( t_{k,m} + p_{k,m} \right ) \cdot \ x_{k,j,m } \le \ \sum_{m=1}^M t_{k,m} \cdot \ x_{k,j+1,m} \\
t_{i,m} + p_{i,m} \ge \ t_{j,m} \ +  L\cdot \ \left (1-y_{i,j,m}) \right)  \\
t_{j,m} + p_{j,m} \ge \ t_{i,m} \ + L\cdot \ y_{i,j,m} \\
t_{i,m} \ge 0   \forall \ i, m  \\
y_{i,j,m} \in \mathcal{f} 0 ; 1 \mathcal{g} \forall \ i, j, m \\ 
\end{array} \right.

Schedulazione ottimale dei Progetti: il Metodo del Percorso Critico, CPM[modifica | modifica sorgente]

Un progetto è definito come un insieme costituito da un certo numero di attività dette anche task che devono essere svolte con un dato ordine. In altri termini esistono vincoli di precedenza sulle attività, tipicamente un’attività non può iniziare prima che altre vengano ultimate. Ogni attività è altresì caratterizzata da un tempo di esecuzione. Il "metodo del percorso critico" o Critical Path Method, in breve "CPM", permette di rispondere alle seguenti domande:

  • Qual è il tempo minimo richiesto per completare l’intero progetto?
  • Quali sono gli istanti di inizio e di fine delle singole attività?
  • Quali attività possono essere ritardate senza causare un ritardo all’intero progetto?
  • Per ridurre la durata del progetto su quali attività si dovrà intervenire?

Ad un progetto si associa una sua rappresentazione grafica costituita da un grafo orientato (diagramma reticolare): ogni attività è rappresentata da un arco i cui nodi estremi rappresentano l’inizio ed il termine dell’attività stessa. La durata del progetto è pari a  t_{f} - t_{0} dove  t_{f} è il tempo per completare al più tardi le attività che confluiscono nel nodo terminale. Posto convenzionalmente a zero l’istante d’avvio del progetto,  t_{0}=0 , il problema di determinare il tempo minimo richiesto per completare interamente un progetto costituito da n nodi ed m attività si formalizza come segue

 min \mathcal{f} \ t_{f} \mathcal{g}

soggetta ai seguenti vincoli:

 \left\{ \begin{array}{l} 
t_j \ge t_i  \ + p_{i,j} \\
t_i  \ge 0   \forall \ i=1,...,n  \\
\end{array} \right.

 t_{i} : tempo di inizio della o delle attività di cui il nodo i è diretto predecessore del nodo j.  t_{j} : tempo di fine della o delle attività che giungono al nodo j.  p_{i,j} : indica la durata dell’attività associata all’arco (i;j). Il vincolo  t_j \ge t_i  \ + p_{i,j} impone che un’attività j non possa iniziare prima che le attività i che la precedono vengano terminate. Si osservi che il tempo di inizio di un’attività uscente da un nodo coincide con il tempo di fine delle attività entranti nel nodo stesso. L’obiettivo del modello consiste nel minimizzare la durata complessiva del progetto e la soluzione del problema lineare fornisce i tempi di inizio di tutte le m attività nel rispetto degli m vincoli di precedenza. Una tempificazione così fatta del progetto determina l’istante in cui avviare ogni attività in modo da minimizzare la durata complessiva del progetto. La soluzione contenuta nella funzione obiettivo corrisponde al tempo di attraversamento minimo e viene misurata lungo il cammino o percorso critico; l’algoritmo identifica quali attività sono critiche nel senso che chiariremo tra breve. Il cammino critico è costituito da tutte e solo le attività che non possono essere ritardate senza causare un ritardo all’intero progetto e ad esse ci si riferisce come attività critiche. Introdotte la variabile ausiliaria di surplus, una per ogni vincolo di precedenza,  s_{i} \ge 0 così definita

 s_{i} = t_j  - t_i  - p_{i,j}

se  s_{i} > 0 allora l’attività non è critica in quanto esiste del tempo in eccesso: l’attività potrebbe venire ritardata proprio per un tempo pari a  s_{i} . Se  s_{i}=0 il vincolo è saturo e l’attività risulta critica. Il problema lineare formulato in forma standard è intimamente legato alla geometria del grafo orientato: il problema conterrà un certo numero k di incognite connesso al numero di nodi e, un certo numero m di equazioni (vincoli di precedenza) legato alla numerosità delle attività elementari con cui è stato disaggregato il progetto. Il numero di incognite k è proporzionale al numero di nodi, poiché ogni nodo non può presentare più di due variabili  t_{i} e  t_{j} ; tenuto conto che il numero di variabili di surplus  s_{i} è pari esattamente ad m, si ha n+m ≤ k ≤ 2n+m. Ricordando che il numero di equazioni risulta pari ad m, in generale dunque sì è in presenza di un sistema di equazioni indeterminato avendosi un numero di incognite maggiore del numero di equazioni, k>m. Il sistema di vincoli possiede pertanto più di una di soluzione,  \infty^{k-m} soluzioni. L’algoritmo del simplesso non esplorerà tutte le infinite soluzioni alla ricerca di quella ottimale, ma selezionerà solo quelle che costituiscono una soluzione di base ammissibile e che sono in numero finito. Le soluzioni di base ammissibili sono pertanto le soluzioni candidate a minimizzare il tempo di attraversamento: poiché tali soluzioni possiedono sempre almeno k-m componenti nulle; avendosi  p_{i,j} > 0 , rimane dimostrato che un grafo orientato presenta sempre almeno min (k-m;m) attività critiche. Il project manager, individuando le attività critiche, è in grado di riconoscere le attività che costituiscono il reale collo di bottiglia nell’esecuzione del progetto.

Bibliografia[modifica | modifica sorgente]

  • Richard Bellman, Mathematical aspects of scheduling theory, USA: RAND Inc., 1955
  • Kenneth R. Baker, Introduction to sequencing and scheduling, USA: John Wiley & Sons Inc., 1974
  • Simon French, Sequencing and scheduling: an introduction to the Mathematics of the Job-Shop, Great Britain: Ellis Horwood Limited, 1987
  • Paolo Brandimarte, Agostino Villa, Gestione della produzione industriale, Torino: UTET Libreria, 1995
  • Richard W. Conway, William L. Maxwell, Louis W. Miller, Theory of scheduling, USA: Dover Publications Inc., 2003
  • Michael L. Pinedo, Planning and Scheduling in Manufacturing and Services, USA: Springer, 2007