Teoria della schedulazione

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

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

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 (set-up), qualora esista un tempo di attrezzaggio questo si suppone che non dipenda dall’ordine dei lotti da lavorare: se il tempo di set-up 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:

• il tempo medio di completamento dei lotti, ‘’completion time’’
• il flow-time medio, ‘’mean flowtime’’
• il tempo totale di attesa dei lotti in coda alla macchina, ‘’waiting time’’
• il ritardo totale medio rispetto alle date di consegna fissate per ogni lotto, ‘’mean tardiness’’
• il massimo ritardo tra i lotti‘’maximum job lateness’’

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 set-up 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 set-up. Il tipico esempio di attività dipendente da set-up 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

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

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

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

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

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.

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

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.

Bibliografia

• 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