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