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.

Classificazione dei problemi di schedulazione

Per classificare l'ampia varietà dei problemi di schedulazione si ricorre ad una notazione che fa uso di tre campi $\alpha |\beta |\gamma$ che riflettono le caratteristiche delle macchine, delle operazioni e specificano la misura di prestazione adottata per valutare la schedula, notazione per i problemi di schedulazione. Le macchine vengono classificate in parallele se sono in grado di eseguire tutte le medesime operazioni ; si dicono dedicate se sono specializzate nell'esecuzione di specifiche e determinate operazioni. Si individuano tre tipologie di macchine parallele in base alla loro velocità: identiche se la velocità di esecuzione dell'operazione è la medesima; uniformi se la velocità tra le macchine è diversa, ma la velocità di ogni singola macchina rimane costante indipendentemente dall'operazione che esegue; incorrelate se la velocità dipende dall'operazione da realizzare.

Nel caso di macchine dedicate esistono tre modelli per eseguire specifici classi di operazioni: flow shop, open shop e job shop. Si assuma che determinate classi di operazioni possano raggrupparsi in insiemi detti job e che due operazioni appartenenti al medesimo job si ritengono diverse se devono essere eseguite su macchine differenti. Nell’open shop il numero di operazioni è costante per ciascun job ed ogni operazione viene eseguita, senza vincoli di precedenza, dalla macchina ad essa dedicata: non esiste un ordine particolare da seguire e pertanto una schedula determina non solo l'ordine di esecuzione delle operazioni da parte delle macchine, ma anche l'ordinamento dei job tra le macchine. Il flow shop differisce dall'open shop per il fatto che si introducono dei vincoli di precedenza tra le operazioni e di conseguenza si viene a creare un ordinamento naturale delle macchine.

Nel job shop il flusso delle lavorazioni non è unidirezionale come nel flow-shop ed il numero di operazioni varia arbitrariamente tra un job e l'altro. Si fa osservare che solitamente si ipotizza che tra le macchine esista uno spazio di stoccaggio, 'buffer', dalla capacità illimitata. Il buffer rende così possibile ad un lotto appena lavorato da una macchina di attendere l'inizio della lavorazione sulla macchina successiva. Nel caso in cui il buffer presenta capacità nulla allora i lotti non dispongono dello spazio di attesa tra due macchine adiacenti e di conseguenza nessuna variabile temporale di attesa può assumere valore non nullo: un lotto che ha appena terminato un'operazione dovrà immediatamente incominciare la lavorazione sulla macchina successiva.

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 (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:

• 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 tardiness'’

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

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:

$minC_{max}$

soggetta ai seguenti vincoli:

$\left\{{\begin{array}{l}C_{max}-\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\geq 0\\\vdots \\C_{max}-\sum _{i=1}^{n}x_{i,m}\cdot \ p_{i}\geq 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 \left\{0;1\right\}\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}\geq 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 garantiscono una soluzione ottima del problema in quanto il loro fine è trovare in un tempo relativamente breve una soluzione ragionevolmente buona.

Rappresentazione del tempo

La rappresentazione del tempo costituisce un argomento fondamentale nei problemi di schedulazione. Le formulazioni matematiche dei problemi di schedulazione possono essere classificate in due macro-categorie in base proprio al tipo di rappresentazione adottata per descrivere il trascorrere del tempo. Una categoria rappresenta il tempo come grandezza discreta; l'altra come grandezza continua. Nel caso discreto l'idea di base consiste nel discretizzare il tempo considerando un insieme finito di istanti: $t_{j+1}=t_{j}+h_{j}$ con $j=0,1,...,T-1$; $h_{j}$ rappresenta il passo di discretizzazione. La scelta più naturale è considerare i passi $h_{j}$ costanti, cioè $h_{j}=h$ per $j=0,1,...$ In questo modo l'orizzonte del tempo viene suddiviso in un certo numero di intervalli di durata temporale eguale e costante: in generale il numero di finestre temporali ed il loro posizionamento vengono postulati a priori. Gli eventi che accadono nel modello matematico discreto non sono altro che variazioni di valore di una qualche variabile; tali eventi possono accadere solo agli estremi di uno degli intervalli con cui si è suddiviso l'orizzonte temporale ossia all'inizio o alla fine dell'intervallo stesso. Nel caso continuo invece gli eventi possono accadere in qualsiasi istante del continuo temporale sicché si può affermare che in un tale contesto il valore dei punti eventi non è noto a priori, ciò che viene postulato è un certo numero di variabili temporali idonee.

Modelli di programmazione lineare

Macchina singola

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\left\{\sum _{i=1}^{n}A_{i}+\sum _{i=1}^{n}x_{i,n}\cdot \ p_{i}\right\}$

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}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\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.

Schedulazione in presenza di tempi di set-up dipendenti dalla sequenza

Ipotizzare che il tempo di attrezzaggio per predisporre una macchina a lavorare il lotto successivo sia indipendente dal lotto che immediatamente lo precedeva consente di includere il tempo di attrezzaggio nel tempo di lavorazione dei lotti, $p_{i}$. Nel seguito si assume l’ipotesi di dipendenza dei tempi di set-up dalla sequenza. I tempi di set-up si denotano come $s_{i,j}$ , notazione che rappresenta il tempo per attrezzare una macchina per lavorare il lotto j quando la macchina era predisposta per lavorare il lotto i. Nella schedulazione di una macchina singola minimizzare il massimo flow-time o il makespan equivale a minimizzare la somma di tutti i tempi di set-up. Il problema di minimizzare la somma totale dei tempi di set-up è equivalente al problema del commesso viaggiatore, in gergo travelling salesman problem. Se ad ogni città si fa corrispondere un lotto e ad ogni distanza tra due città si fa corrispondere il tempo di set-up per attrezzare la macchina da un lotto all’altro allora l’equivalenza dei due problemi diviene evidente.

Esempio di schedulazione a tempo discreto per macchina singola

La scelta del numero di intervalli di tempo con cui suddividere l'orizzonte di pianificazione viene fatta in anticipo. Come passo di discretizzazione del tempo si può scegliere l'unità temporale utilizzata per rappresentare i tempi di lavorazione. Per ogni intervallo di tempo introdotto, si definiscono $n$ variabili binarie per indicare l'intervallo di tempo nel quale il lotto incomincia la lavorazione. Le variabili sono della forma $x_{i,j}$ dove il pedice $i=1,...,n$ indica il lotto ed il pedice $j=1,...,T$ indica l'intervallo di tempo. La generica stringa $x_{i,1}=0,...,x_{i,t}=1,...,x_{i,T}=0$ indica che il lotto i-esimo incomincia la lavorazione in corrispondenza dell'intervallo di tempo $j=t$. La soluzione al problema di sequenziamento ottimale è rappresentato dal valore di queste variabili binarie. Due o più lotti non possono essere lavorati dalla stessa macchina nella stessa finestra temporale, pertanto si introducono i vincoli per impedire assegnamenti conflittuali:

$\sum _{i=1}^{n}x_{i,j}\leq 1\forall \ j=1,...,T$

In ultimo i vincoli della forma

$\sum _{j=1}^{T}x_{i,j}=1\forall \ i=1,...,n$

impongono che la lavorazione di ogni lotto avvenga una volta ed una sola volta nell'orizzonte di pianificazione, in questo modo si evita che l'algoritmo risolutivo proponga la soluzione banale con tutte le variabili nulle.

Il fatto che nessuna operazione possa iniziare prima che la lavorazione sul precedente lotto sia stata completata è rappresentato matematicamente dai T-1 seguenti vincoli

$\left\{{\begin{array}{l}\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,2}\right)\cdot \ M+1\\A_{1}-1+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,3}\right)\cdot \ M+1\\\vdots \\A_{T-2}-1+\sum _{i=1}^{n}x_{i,T-1}\cdot \ p_{i}\leq \left(1-\sum _{i=1}^{n}x_{i,T}\right)\cdot \ M+1\\\end{array}}\right.$

dove $A_{1}=\sum _{i=1}^{n}x_{i,1}\cdot \ p_{i};A_{2}=A_{1}-1+\sum _{i=1}^{n}x_{i,2}\cdot \ p_{i};...$

La funzione obiettivo deve fare in modo che le lavorazioni incomincino il prima possibile, quindi si introducono coefficienti di costo che rendono più oneroso effettuare le lavorazioni sul finire dell'orizzonte di pianificazione.

Problema con date di consegna

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\left\{\sum _{i=1}^{n}C_{i}+\sum _{i=1}^{n}R_{i}\right\}$

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}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\forall \ i,k\end{array}}\right.$

Flow-shop a due macchine

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\left\{\sum _{i=2}^{n}L_{i}+\sum _{i=2}^{n}M_{i}\right\}$

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}\geq 0\forall \ i\\x_{i,k}\in \left\{0;1\right\}\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

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}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}$

Inoltre è necessario ricorrere ad un gran numero di vincoli per impedire l'esecuzione 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 pari a M(N(N-1))/2 laddove N(N-1)/2 rappresenta il numero di possibili confronti a coppie tra le lavorazioni su di una medesima macchina.

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

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

La variabile booleana $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}\leq \ \sum _{m=1}^{M}t_{k,m}\cdot \ x_{k,j+1,m}\\t_{j,m}\ +L\cdot \left(1-y_{i,j,m}\right)\geq \ t_{i,m}+p_{i,m}\cdot y_{i,j,m}\\t_{i,m}\ +L\cdot \ y_{i,j,m}\geq \ t_{j,m}+p_{j,m}\cdot \left(1-y_{i,j,m}\right)\\t_{i,m}\geq 0\forall \ i,m\\y_{i,j,m}\in \left\{0;1\right\}\forall \ i,j,m\\\end{array}}\right.$

Il modello appena descritto è noto come Modello di Manne .

Il problema della Cooperativa di compensati

Una Cooperativa sovietica di compensati sottopose nel 1938 al giovane Leonid Kantorovič, professore universitario dell’Università di San Pietroburgo, un problema di schedulazione della produzione. Il problema consisteva nell’assegnare cinque tipi di legno ad otto macchine sfogliatrici in modo da massimizzare la produzione complessiva dei compensati. Il vincolo cui era soggetta la cooperativa era costituito dal fatto che le quantità da produrre di ciascuno tipo di legno, il mix produttivo, era fissato. Il mix produttivo richiedeva di produrre tanti compensati del tipo 1 quanti quelli del tipo 2, del tipo 3, del tipo 4 e del tipo 5. Nel 1939 venne pubblicata la monografia Mathematical methods of Organizing and Planning Production (Matematicheskie metody organizatsii i planirovaniia proizvodstva) nella quale L. Kantorovič forniva la soluzione del problema, soluzione che può considerarsi come la prima formulazione in termini di programmazione lineare di un problema di schedulazione.

Funzione obiettivo:

$maxZ$

soggetta ai seguenti vincoli:

$\left\{{\begin{array}{l}Z=\sum _{i=1}^{8}a_{i,1}\cdot \ h_{i,1}=...=\sum _{i=1}^{8}a_{i,5}\cdot \ h_{i,5}\\\sum _{k=1}^{5}h_{i,k}=1\qquad \forall \ i=1,...,8\\0\leq h_{i,k}\leq 1\qquad \forall \ i,k\\\end{array}}\right.$

L’incognita del problema è rappresentata dal tempo di lavorazione, la variabile $h_{i,k}$ che indica il tempo espresso come frazione del giorno lavorativo, di utilizzo della macchina i-esima per produrre il compensato di tipo k. Il problema consiste proprio nel determinare la variabile tempo tale che il quantitativo di compensato prodotto sia massimo. La richiesta che la i-esima macchina venga impiegata per tutto il giorno lavorativo trova espressione nel vincolo $\sum _{k=1}^{5}h_{i,k}=1$, mentre il parametro che caratterizza la produzione giornaliera di ogni macchina per ogni tipo di compensato è $a_{i,k}$. Il prodotto $a_{i,k}\cdot \ h_{i,k}$ fornisce il quantitativo di compensato tipo k prodotto dalla macchina i-esima. La loro reciproca uguaglianza fa in modo che il quantitativo di un tipo di compensato eguagli quello degli altri.

Sistemi a coda

Gran parte della teoria della schedulazione assume come ipotesi di lavoro l'arrivo simultaneo dei lotti presso il centro di lavorazione, in altri termini si ipotizza che tutti i lotti siano pronti e disponibili ad incominciare le lavorazioni ad un preciso istante iniziale. Quando questa ipotesi non è applicabile o meglio ogniqualvolta i lotti arrivano in modo intermittente ed in momenti non noti a priori, il problema del loro sequenziamento ottimale viene affrontato in termini probabilistici. Il problema di arrivi casuali è inquadrato nella teoria delle code. Per i sistemi che generano code, cd sistemi a coda, particolar enfasi è posta sul criterio di selezione mediante il quale un lotto in attesa viene selezionato dalla coda ed inviato alla macchina che si è liberata della lavorazione precedente.

Schedulazione ottimale dei Progetti: il Metodo del Percorso Critico, CPM

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\left\{t_{f}\right\}$

soggetta ai seguenti vincoli:

$\left\{{\begin{array}{l}t_{j}\geq t_{i}\ +p_{i,j}\\t_{i}\geq 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}\geq 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}\geq 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.

Programmazione dei turni del personale

La schedulazione o programmazione del personale si pone l'obiettivo di redigere tabelle orarie per il personale in forza lavoro al fine di soddisfare una data domanda (di risorse umane, di beni o di servizi) senza violare i regolamenti contrattuali stabiliti per legge, i regolamenti interni all'impresa, le preferenze stesse del personale o le loro abilità. Le variabili sono tipicamente costituite dalla dimensione della forza-lavoro ed il numero di lavoratori assegnati ad ogni turno. La funzione obiettivo è generalmente rappresentata dalla minimizzazione del costo della forza lavoro oppure dalla massimizzazione dell'efficienza e degli impieghi. I vincoli sono generalmente costituiti da regolamenti cogenti. La formulazione del problema in termini di programmazione lineare intera prevede di schematizzare i turni candidati mediante una matrice. Tale matrice viene chiamata matrice di turnazione e consiste in una tabella costituita da m righe ed n colonne. La forma della matrice è intimamente connessa con il tipo di problema di turnazione da risolvere. I problemi di schedulazione del personale possono essere classificati in uno dei seguenti tre gruppi. Il primo gruppo accoglie i classici problemi di turnazione ciclica (cyclic staffing problem) e consiste nell'organizzare i turni all'interno di uno tabella ciclica del tipo (k, m) in modo che il personale lavori per k periodi consecutivi seguiti da m-k periodi di riposo. Generalmente un periodo rappresenta il giorno, sicché la notazione (5,7) tipica per i lavoratori giornalieri, indica un ciclo di sette giorni in cui ogni persona lavora 5 giorni consecutivi seguiti da due giorni di riposo. Al secondo gruppo di problemi appartiene la schedulazione dei giorni di riposo (days-off scheduling) nella quale si vuole determinare, in accordo ai regolamenti contrattuali, quando interporre i giorni di riposo tra i vari giorni lavorativi. Il terzo gruppo è costituito dalla schedulazione dei turni (shift scheduling) in cui è richiesto di garantire la continuità di servizio in fasce orarie di almeno dieci ore ed il servizio non può essere assicurato articolando periodi di lavoro da otto ore ossia organizzando fasce orarie del tipo 7-14/14-21. Il problema consiste nel determinare i tipi di turno (part-time di 6 ore, full-time, part-time di 4 ore, etc.) in modo che le risorse allocate rispettino una certa richiesta di prestazioni nelle diverse fasce orarie e che il numero di risorse impiegate sia minimo o minimo sia il corrispondente costo del lavoro.

In generale il problema di assegnare in modo equo i giorni festivi al personale non ha soluzione se il numero di turni presenti nel periodo in esame è un numero primo ed il numero di risorse a presidio di ogni turno è superiore a uno.

Esempio di modello base

In una matrice di turnazione le righe rappresentano $i=1,...,m$ intervalli di tempo o periodi: il problema consiste nel determinare il numero di risorse che deve essere presente in ciascun periodo in modo tale da soddisfare una certa richiesta di personale. Il numero di lavoratori necessari nel generico periodo $i$ si denota con $b_{i}$. Ogni colonna della matrice rappresenta invece un possibile turno di assegnazione e consiste in una sequenza di 0 e 1 lunga $m$. Il valore uno indica un periodo lavorativo, lo zero indica un periodo di riposo. Ad esempio la notazione $a_{ij}=1$ per il generico elemento della matrice di turnazione $A$ indica che il periodo i-esimo del turno j-esimo è lavorativo. Se il numero di schemi di turno possibile è pari ad $j=1,...,n$ ed $m$ sono i periodi in esame, la matrice di turnazione è una matrice di dimensione $m\times n$.

Ad esempio considerando 7 periodi corrispondenti rispettivamente a lunedì, martedì, mercoledì, giovedì, venerdì, sabato e domenica, si vogliono valutare due tipi di turnazione: una turnazione full-time da 48 ore settimanali, l'altra turnazione di tipo part-time orizzontale costituita da 4 ore giornaliere su 5 giorni lavorativi per un totale di 20 ore settimanali. La matrice dei turni ammissibili assume dunque la forma

$A={\begin{pmatrix}1&0&1&1&1&1&1&1&0&0\\1&1&0&1&1&1&1&1&1&0\\1&1&1&0&1&1&1&1&1&1\\1&1&1&1&0&1&1&1&1&1\\1&1&1&1&1&0&1&1&1&1\\1&1&1&1&1&1&0&0&1&1\\0&1&1&1&1&1&1&0&0&1\\\end{pmatrix}}$

La variabile decisionale $x_{j}$ indica il numero di risorse da assegnarsi al turno di tipo $j$ e costituirà l'incognita a variabile intera del problema.

Il vincolo che richiede il numero minimo di personale in ogni periodo è del tipo

$\ {\vec {a}}^{1}\ \cdot x_{1}+{\vec {a}}^{2}\ \cdot x_{2}+\cdots +{\vec {a}}^{m}\cdot x_{m}\geq \ {\vec {b}}\$

avendo fatto ricorso alla notazione di vettore colonna.

Se il costo dell'assegnazione di una risorsa al turno j-esimo si denota con $c_{j}$ allora la funzione obiettivo che minimizza il costo del lavoro è della forma:

$z=min\sum _{j=1}^{m}c_{j}\cdot x_{j}$

Schedulazione degli equipaggi - Crew Scheduling

La schedulazione del personale trova ampia applicazione nelle imprese che operano nei trasporti quali ad esempio le compagnie aeree e quelle ferroviarie. Per le compagnie aeree il costo degli equipaggi (salari, benefits e spese) costituisce la seconda componente di costo in ordine di grandezza dopo il costo per il carburante. L’obiettivo del problema della schedulazione degli equipaggi (crew scheduling problem) consiste nel determinare per ogni equipaggio (crew) una sequenza di tratte (pairing of flights) in modo tale che tutti i piani di volo vengano coperti e che il costo totale degli equipaggi sia minimo. Con il termine sequenza di tratte si intende una sequenza di voli che incomincia e termina nel medesimo punto di partenza (base di armamento), ossia la sequenza fa in modo di riportare l’equipaggio all’aeroporto dove risiede e per tale motivo è chiamata tour. La sequenza di tratte ottimale specifica date e ore per ogni giorno in esame. La soluzione del problema, se necessario, può assegnare anche più di un equipaggio ad un medesimo volo (deadheading) al fine di trasportare un equipaggio sino ad un certo nodo della rete. Pertanto se si rimuove la possibilità di “deadheading” sarà necessario introdurre vincoli che tengono conto del numero di equipaggi disponibili in ogni base aerea. I piloti, i macchinisti, gli assistenti di volo, gli assistenti a bordo treno vengono così assegnati ad una sequenza di tratte in modo tale che l’equipaggio operi su almeno due tratte ed in modo che l’orario di partenza di un viaggio nella sequenza scelta non anticipi l’orario di arrivo del viaggio precedente nella sequenza in oggetto. Il costo di una sequenza di tratte può essere espresso per semplicità come l’intervallo di tempo intercorrente tra la prima partenza e l’ultimo arrivo. Inoltre poiché la durata di un turno lavorativo è regolamentato da specifiche e cogenti normative quali ad esempio il divieto per i piloti di volare per più di 8 ore in un periodo di 24 ore, il divieto per gli aerei di essere utilizzati per più di 14 ore in un giorno, una formulazione realistica del problema richiede di formulare i vincoli espressi dalla normativa sindacale, nazionale e delle compagnie aeree.

Miscellanea

Il problema della schedulazione degli equipaggi può essere considerato come un particolare utilizzo del problema del flusso massimo attraverso una rete. Nel problema del flusso massimo viene assegnata una rete (ad esempio una rete ferroviaria, una rete idraulica o una rete di comunicazione) che connette un certo numero di città (i.e. nodi); ogni arco (i.e. tratta) della rete viene caratterizzato con un numero che ne rappresenta la capacità di trasporto; il problema consiste nel determinare la quantità massima di flusso che dal nodo di partenza è possibile trasportare fino al nodo di destinazione tenendo conto dei vincoli di capacità su tutti gli archi. Il problema del flusso massimo in forma standard ha come problema duale il problema di flusso a costo minimo detto anche problema del taglio minimo, il teorema del flusso massimo e del taglio minimo afferma che il valore del flusso massimo è uguale alla capacità del minimo taglio. Sotto questo punto di vista il problema del flusso a costo minimo può vedersi come il problema dell'individuazione del collo di bottiglia di una rete: il collo di bottiglia corrisponde al taglio che presenta il costo minimo. Eliminare dalla rete gli archi di un taglio fa sì che nessun flusso possa più passare dal nodo di partenza alla destinazione. In un conflitto bellico l’interdizione mirata della capacità del nemico di muovere uomini, mezzi ed informazioni attraverso le reti di trasporto riveste valenza strategica, da cui il notevole interesse delle varie forze armate a questi ambiti di ricerca. Poiché la disponibilità di una rete fisica di telecomunicazioni è vulnerabile ad attacchi, nel 1958 all’Agenzia governativa statunitense ARPA vennero assegnati diversi compiti tra i quali quello di progettare una rete militare finalizzata allo scambio sicuro delle informazioni. Il paradigma alla base di una comunicazione sicura doveva risiedere nella possibilità di rendere sempre possibile lo scambio di informazioni tra i terminali anche nel caso in cui un arco della rete fisica fosse andato distrutto: nell’eventualità doveva essere possibile ricorrere ad un “canale alternativo” la cui capacità massima di trasmettere dati (capacità di canale) potesse essere anche inferiore alla dimensione dei dati stessi (datagramma). Per superare il vincolo della capacità di canale, in ARPAnet fu ideato un protocollo di trasmissione basato su un meccanismo per frammentare il messaggio in pacchetti di dimensione ridotta (commutazione di pacchetto) per venire trasmessi ed instradati ognuno in modo indipendente ed infine per essere riassemblati nel nodo di destinazione.

Schedulazione dei trasporti

Distribuire beni significa servire un insieme di clienti per mezzo di una flotta di veicoli che sono caratterizzati da una certa capacità di trasporto (illimitata o limitata) e che sono localizzati presso uno o più depositi. I veicoli servono i punti vendita al dettaglio attraverso la rete stradale esistente. Per prima cosa lo spedizioniere determina i carichi per ciascuno veicolo ed il relativo percorso con l’obiettivo di minimizzare il numero di veicoli impiegati, in seconda istanza lo spedizioniere decide la sequenza nella quale i punti vendita verranno visitati al fine di minimizzare, o dal punto di vista temporale o spaziale, la lunghezza complessiva del percorso assegnato. Questi due tipi di problemi presuppongono che le unità di carico imballino la merce in colli di forma simmetrica e che questi vengano collocati a bordo del veicolo senza problemi di ingombro ossia può essere solo richiesto che la somma del peso dei beni non ecceda la capacità di trasporto del mezzo. I problemi di distribuzione che considerano l’orientazione dei colli e della loro unità individuale sono detti problemi di imballaggio (packing problems) ed hanno come obiettivo quello di minimizzare il numero di contenitori impiegati o quello di massimizzare i colli caricati. Esistono diversi modelli matematici a seconda delle proprietà basilari che il sistema di trasporto in esame gode; sebbene tali problemi siano certamente più semplici dei problemi reali, tuttavia possiedono il pregio di evidenziarne gli elementi essenziali. Il più semplice modello di trasporto è rappresentato dal ''problema del commesso viaggiatore'', travelling salesman problem. Il cosiddétto vehicle routing problem introduce il fatto che ad ogni cliente è associata una domanda di beni ed il veicolo presenta una data capacità di carico. Se si considera una finestra temporale entro cui ogni cliente può essere visitato si giunge al vehicle routing problem with time windows. Il VRPTW è una generalizzazione del VRP ed è in grado di modelizzare numerose situazioni reali.

• Traveling Salesman Problem, TSP: dal deposito parte un solo veicolo. L’obiettivo consiste nel determinare il percorso di consegna ottimo dell’unico veicolo per visitare una ed una sola volta i clienti.

• Vehicle Routing Problem, VRP: un insieme di punti vendita/clienti viene servito da una flotta di veicoli dalla capacità di trasporto illimitata. I veicoli inizialmente sono localizzati presso un unico deposito assegnato. Ogni cliente viene servito da un solo veicolo. Ogni percorso, itinerario incomincia dal deposito, visita un insieme di clienti e ritorna al deposito. L’obiettivo consiste nel trovare per ogni veicolo il percorso di lunghezza minima in modo che il costo logistico totale sia minimo.

• Capacited Vehicle Routing Problem, CVRP: un insieme di clienti viene servito da una flotta di veicoli dalla capacità di carico limitata. I veicoli inizialmente si trovano presso il deposito assegnato. Ogni itinerario incomincia dal deposito, visita un insieme di clienti e ritorna al deposito senza violare il vincolo di capacità del vettore. Se si ammette la possibilità di ripartire tra più veicoli la domanda di beni del cliente i- esimo allora il modello si dice CVRP a domande suddivise (split demands). In tale circostanza un cliente può riceve più consegne la cui somma complessiva eguaglia la domanda del cliente.

• Vehicle Routing Problem with Backhauls, VRPB: Una variante del VRP contempla il backhauls: ad ogni veicolo non solo è richiesto di consegnare i beni dal deposito ai clienti (linehaul), ma è anche richiesto di prelevare da qualche cliente (backhaul) della merce che deve essere riportata al deposito. In molte applicazioni pratiche i clienti linehaul hanno una priorità più alta dei clienti backhaul: i clienti backhaul di un itinerario vengono serviti solo dopo che tutti i clienti linehaul di quell’'tinerario sono stati serviti.

• Vehicle Routing Problem with Pick-up and Delivery, VRPPD: ogni veicolo parte dal deposito trasportando una quantità di merce pari alla quantità che dovrà essere consegnata e fa ritorno al deposito con una quantità di resi pari alla quantità totale raccolta. I punti di prelievo della merce e di consegna della merce o del materiale di scarto non coincidono necessariamente con il deposito.

• Vehicle Routing Problem with Time Window constraints, VRPTW: esiste una finestra temporale [a, b] entro la quale il veicolo può servire il deposito ed ogni cliente. Il tempo di inizio servizio in ogni destinazione deve essere non inferiore ad a, il tempo di arrivo in ogni destinazione deve essere non superiore a b. Se il veicolo arriva a destinazione ad un tempo anteriore ad a, il veicolo dovrà attendere prima di poter iniziare a servire il cliente.

Schedulazione stocastica

I modelli di programmazione lineare per la schedulazione dei sistemi produttivi sopra descritti presentano tutti una connotazione deterministica. In tale modelli si assume implicitamente che

• il numero di lotti da sequenziare è assegnato e non varia,

• i tempi di lavorazione sono noti e non cambiano,

• gli istanti in cui i lotti sono disponibili per iniziare le lavorazioni (arrivi o ready time) sono noti e non variano,

• le macchine non si guastano mai e sono sempre disponibili lungo tutto l’orizzonte di pianificazione

Incertezza e imprevedibilità non vengono minimamente prese in considerazione. I sistemi reali invece sono caratterizzati da elementi di incertezza che rendono i sistemi in esame complessi. Nei sistemi reali si assiste ad un continuo arrivo nel tempo degli ordinativi così come all’incertezza legata all’impossibilità di misurare senza errore i tempi di lavorazione delle macchine. Le stesse macchine poi sono soggette a guasti, malfunzionamenti. Si dicono stocastici i problemi di schedulazione in cui i parametri del modello non sono noti con certezza e l'incertezza associata può essere descritta da distribuzioni di probabilità note. Ad esempio in un modello stocastico di schedulazione della produzione gli ordini arrivano in modo casuale nel tempo o i tempi delle lavorazioni e le disponibilità delle macchine sono conoscibili con un certo grado di incertezza. Nei modelli di schedulazione stocastica l’incertezza ed il caso vengono rappresentati in termini probabilistici.

Schedulazione dinamica

Se il sistema in esame presenta elementi di incertezza ossia il decisore non dispone di informazioni sulla probabilità di accadimento degli eventi, ma eventi imprevisti ed ineludibili possono accadere allora si parla di schedulazione dinamica. Si definiscono dinamici tutti quei problemi di schedulazione che contemplano l’accadimento di eventi in tempo reale. I modelli di schedulazione statici assumo che tutte le caratteristiche del problema sono note e fisse nel tempo e pertanto sono in grado di determinare soluzioni ottimali in anticipo: in questo senso la schedulazione della produzione rappresenta il nocciolo delle attività di pianificazione della produzione. I modelli di schedulazione così detti statici non sono capaci di far uso delle informazioni che giungono in tempo reale: gli imprevisti determinano variazioni nel piano in precedenza programmato tali da renderlo non più praticabile (unfeasible) o perlomeno non più ottimale. Nell’ambiente produttivo esempi di eventi che possono accadere in tempo reale sono rappresentati dall’arrivo di un lotto urgente, dal verificarsi di un guasto in una macchina o dall’indisponibilità di un operatore, dal cambiamento nelle date di consegna, dalla mancanza dei materiali o da non conformità di questi ultimi, dalla cancellazione di uno o più ordini di produzione, etc.

La schedulazione dinamica si differenzia a seconda dei diversi approcci adottati. Un primo approccio si basa nel non generare in anticipo alcuna schedula, ma piuttosto nel prendere decisioni in tempo reale: le regole di dispaccio (dispatching rules) giocano un ruolo fondamentale e consistono nel selezionare quale lotto lavorare tra un insieme di lotti, in attesa che la macchina divenga nuovamente libera. Le dispatching rules più conosciute sono Shortest Process Time (SPT), Earliest Due Date (EDD) e First Come First Served (FCFS). La loro semplicità d’uso deriva dal fatto che sono facilmente applicabili a molti contesti e richiedono un tempo di calcolo davvero modesto. Un approccio alternativo ammette una pianificazione anticipata e la schedula prevista viene poi di volta in volta corretta, ri-schedulata, in risposta agli eventi che si presentano nel futuro. Ad esempio gli ordini di produzione vengono schedulati ad intervalli regolari (politica di riesame periodico) e vengono determinati grazie agli algoritmi di schedulazione statica. La schedula determinata viene eseguita e non rivista sino a quando inizia il periodo successivo: nel momento del riesame la schedula precedentemente determinata viene ri-schedulata sulla base delle nuove informazioni raccolte. Stabilire il periodo di ri-schedulazione (rolling time horizon) risulta essere un compito piuttosto difficile.

Schedulazione intelligente

La schedulazione dinamica può adottare anche tecniche di intelligenza artificiale allorquando esista un’ampia varietà di decisioni che possono essere prese davanti al verificarsi di eventi imprevisti che accadono in tempo reale. I sistemi basati sull’intelligenza artificiale (knowledge-based systems) si concentrano nel catturare le competenze e le esperienze passate e deducono attraverso metodi inferenziali quali decisioni è raccomandabile vengano intraprese. Ad esempio si può far ricorso a tecniche di machine learning supervisionato (reti neuronali, support vector machines, etc.) al fine di migliorare le prestazioni della schedulazione dinamica basata sulle regole di dispaccio. Proprio perché tra le regole di dispaccio non esiste una regola migliore di un’altra in senso assoluto, il ricorso alle tecniche di machine learning risulta essere promettente. L’approccio del machine learning supervisionato si basa sulla simulazione, su esempi noti ed il suo obiettivo consiste nel selezionare la miglior regola di dispaccio per una macchina a seconda delle condizioni che si possono presentare nel sistema produttivo. Le tecniche di programmazione matematica svolgono una sequenza di istruzioni esplicite e specificate per determinare la schedula corretta/ottimale, il machine learning invece determina quale regole di dispaccio sia migliore sulla base della prestazione da questa ottenuta in casi noti e/o simulati (il cd training set). Ad esempio come misura di prestazione si può scegliere la mean tardiness (il ritardo medio), successivamente si introduce quale varietà di azioni correttive un insieme di regole di dispaccio alternative. Si definiscono poi un certo numero di condizioni di funzionamento del sistema produttivo che costituiranno i parametri di input per il machine learning. Il funzionamento del sistema produttivo viene infine simulato al variare delle diverse combinazioni che questi parametri generano. La misura di prestazione adottata determinerà quale regola di dispaccio sia preferibile tra tutte quelle introdotte.

La risoluzione dei problemi di schedulazione

Metodologia tipica adottata in un processo di ottimizzazione

Una volta inquadrato il problema in una delle casistiche sopra esposte (problema a macchina singola, macchine parallele, etc) ed aver formulato il problema mediante un modello matematico, si procede alla risoluzione di quest’ultimo facendo ricorso a programmi informatici specifici. Il modello matematico viene dapprima tradotto nel linguaggio di modellizzazione proprio del programma adottato, esempi di sistemi di modellazione algebrico sono PuLP di Phyton, AMPL, FlopC++ o GAMS. Infine il modello viene risolto con un risolutore specifico in base alla categoria di appartenenza del problema di ottimizzazione (programmazione lineare intera, programmazione lineare, programmazione non lineare, programmazione stocastica, etc.). Esempi di risolutori di problemi lineari sono COIN-OR LP, CPLEX. Esistono anche risolutori che hanno i fogli elettronici di Excel come ambiente nel quale scrivere il modello matematico. Microsoft Excel contiene ad esempio un risolutore quale componente aggiuntivo denominato Risolutore (Solver sviluppato da Frontline System Inc.) grazie al quale un utilizzatore può scrivere il modello matematico di schedulazione direttamente in Excel e risolverlo determinando la soluzione ottimale. Tuttavia i problemi che possono essere trattati sono ostacolati dal fatto che la capacità di calcolo del Risolutore è artificialmente limitata ad un certo numero di variabili (200 celle variabili, 2018). Esiste poi un software open source, OpenSolver, in grado di risolvere problemi di ottimizzazione in ambito lineare, intero e non lineare in Excel che non ammette un numero massimo di variabili. OpenSolver utilizza COIN-OR CBC per generare la soluzione in Excel. Il metodo del simplesso che risolve i problemi di programmazione lineare presenta una complessità computazionale che non è polinomiale, questo significa che al crescere della complessità del problema, il tempo necessario per eseguire l'algoritmo e lo spazio di memoria occupato in un calcolatore cresce in modo esponenziale. Un Centro di Elaborazione Dati, in gergo Data Center, è capace di offrire un’enorme potenza di calcolo e la sua fruibilità via Web quale servizio di cloud computing fornirà sempre più impulso alla risoluzione dei problemi di schedulazione attraverso i metodi esatti.

Una prospettiva storica

Correva l’anno 1939 quando L. Kantorovich presentava le sue idee matematiche per perseguire il perfezionamento dell’organizzazione della pianificazione e della produzione, era il 1947 quando G. Dantzig propose il metodo del simplesso per risolvere i problemi di programmazione lineare includendo quindi i problemi di schedulazione. Tra gli inizi degli anni ’50 del ventesimo secolo ed il volgere degli anni '90 la diffusione degli algoritmi di risoluzione basati su metodi esatti (si ricordi il metodo del simplesso già citato) sono stati penalizzati dalla capacità di calcolo degli elaboratori all’epoca disponibile: fece così seguito il ricorso sempre più esteso ad algoritmi euristici che raggiunsero il loro apice negli anni ’90.

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
• M. Bazargan, Airline Operations and Scheduling, USA: Ashgate, 2010
• Jacek Blazewicz, Moshe Dror, Jan Weglarz, Mathematical programming formulations for machine scheduling: A survey, North Holland: European Journal of Operational Research 51, 1991
• Nasser A. El-Sherbeny, Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods, Journal of King Saud University, 2009
• Djamila Ouelhadj, Sanja Petrovic, A survey of dynamic scheduling in manufacturing systems, Springer Science+Business Media, 2008

Collegamenti esterni

• (EN) Fundamentals of a Method for evaluating Rail Net Capacities (PDF), su dtic.mil. URL consultato il 5 aprile 2017 (archiviato dall'url originale il 17 febbraio 2017).
• (EN) Improving Production Scheduling with Machine Learning, su researchgate.net. URL consultato il 12 febbraio 2018.