Scheduling PDF 2020

Scheduling 1 Introduzione Con il termine scheduling si intende una vasta classe di problemi, molto diversi tra loro per complessità e struttura. Diversi autori hanno tentato una sistematizzazione e una sintesi di tali problemi e ciò ha consentito di classificare molti modelli in modo organico e...

Scheduling 1 Introduzione Con il termine scheduling si intende una vasta classe di problemi, molto diversi tra loro per complessità e struttura. Diversi autori hanno tentato una sistematizzazione e una sintesi di tali problemi e ciò ha consentito di classificare molti modelli in modo organico e di unificare alcuni approcci algoritmici. Tuttavia, per i problemi di scheduling più difficili, non è possibile indicare un unico approccio nettamente preferibile, rispetto agli altri, per la loro soluzione. Possiamo definire problemi di scheduling tutti quei problemi decisionali in cui riveste importanza il fattore tempo, visto come risorsa scarsa da allocare in modo ottimo a determinate attività. I problemi di scheduling sono problemi di breve (brevissimo) periodo, a livello di singola macchina (dispatching list, sviluppate una volta al giorno). A differenza di MRP, gli schedulatori lavorano a capacità finita ma la soluzione di un problema di schedulazione è molto fragile a causa di incertezze, imprevisti, guasti, ...... Esempi di problemi di scheduling sono i seguenti: • Un’azienda produce sacchetti di carta. Il processo produttivo consiste di tre stadi ed in ogni stadio l’operazione è effettuata da un operaio. Ogni ordine di produzione consiste di un certo numero di sacchetti di un certo tipo che devono essere consegnati al cliente entro una certa data. Il costo legato ad un eventuale ritardo rispetto alla data di consegna dipende dall’entità del ritardo e dall’importanza dell’ordine (ovvero del cliente). Conoscendo i tempi richiesti dalle varie operazioni per ciascun ordine, un obiettivo della pianificazione è quello di organizzare le lavorazioni in modo tale da minimizzare queste penali. • Nell’industria meccanica, i centri di lavorazione devono effettuare lavorazioni (taglio, fresatura, tornitura) su vari pezzi che vengono montati sui centri stessi. Diverse operazioni richiedono tempi diversi, e/o diversi tipi di utensile, il che può comportare un certo tempo di riconfigurazione da parte delle macchine stesse. Il problema può consistere nel determinare l’ordinamento dei pezzi in modo da terminare tutte le lavorazioni il prima possibile. Nei problemi di scheduling, l’obiettivo è quello di assegnare certe attività alle risorse disponibili in modo da ottimizzare una determinata funzione obiettivo che dipende dal problema specifico. Vediamo nel dettaglio quali sono gli elementi caratterizzanti. Risorse ed attività vengono indicate con i termini macchina e task, mentre il termine job si riferisce in genere ad insiemi di task tecnologicamente legati tra loro (ad esempio, i tre task necessari a produrre uno stesso sacchetto di carta formano un job). Nel seguito indicheremo con m e n il numero di macchine e di job rispettivamente. Varie informazioni possono essere associate a un job: • Tempo di processamento del job j sulla macchina i, pji . • Tempo di rilascio (release date) rj . Indica l’istante di tempo in cui è possibile iniziare l’esecuzione del job j. • Tempo di consegna (due date) dj . Indica l’istante di tempo entro il quale l’esecuzione del job j dovrebbe essere terminata. Parliamo di due date se è possibile, a fronte di costi, violare la data di consegna, mentre parliamo di dead line se non è possibile violarla. 1 • Peso wj . Rappresenta l’importanza relativa del job j rispetto agli altri. Oltre alle caratteristiche relative ai job, vi sono quelle relative al sistema che rappresentano il modo in cui le risorse (macchine) sono tra loro collegate all’interno del sistema di produzione: • Macchina singola. In questo caso i job richiedono tutti la stessa risorsa per essere eseguiti. Se esistono più macchine, abbiamo il caso di macchine parallele (identiche o meno) ed i job devono passare su una sola di esse. In questo caso ho un problema di routing e scheduling che in genere è risolto affrontando prima l’assegnamento dei job alle macchine (routing) e quindi il sequenziamento dei job su ogni macchina (scheduling). • Flow shop. In questo caso il sistema consiste di m macchine disposte in serie e ciascun job deve essere eseguito da ciascuna delle m macchine successivamente. Parliamo di flow shop puro se tutti i job passano su tutte le macchine della linea mentre parliamo di flow shop generale se i job possono passare solo su alcune macchine della linea. • Job shop. Anche qui vi sono m macchine, ma ciascun job può visitare un diverso insieme di macchine (al limite tutte le m macchine) in un ordine diverso da ogni altro job nel sistema. Infine, vi sono particolari specifiche che contribuiscono a definire esattamente un problema di scheduling, quali ad esempio: • Tempi di set-up. Indica il tempo sjk necessario per riattrezzare la macchina se si vuole fare seguire la lavorazione del job k a quella del job j. • Preemption. La preemption indica la possibilità di interrompere la lavorazione di un job per lavorare un job diverso più urgente (con wj maggiore). • Vincoli di precedenza. In molti casi esistono vincoli di precedenza tra task di un job o tra diversi job. Questi sono vincoli che non dipendono dal sequenziamento, anzi, lo condizionano. Possiamo infine distinguere tra schedulazione statica, in cui tutti i job sono disponibili all’inizio del processo di schedulazione, e schedulazione dinamica, in cui nuovi job possono arrivare nel tempo. 2 Notazione La soluzione di un problema di scheduling prende il nome di schedule. In termini generali, uno schedule è una descrizione completa dell’utilizzo temporale delle macchine da parte dei job che devono essere eseguiti. Il concetto di sequenza è diverso da quello di schedule. La sequenza, infatti, specifica solo l’ordine in cui i job devono essere eseguiti da ciascuna macchina, mentre lo schedule ne specifica anche gli istanti d’inizio, ovvero, lo schedule è una sequenza temporizzata. Se, oltre alla temporizzazione, ho anche l’indicazione della risorsa (work centre), allora si parla di dispatching list. Ovviamente, siamo interessati solo a schedule ammissibili, che rispettino tutti i vincoli impliciti in qualsiasi problema di scheduling, quali ad esempio il fatto che una stessa macchina non può eseguire due job contemporaneamente, che uno stesso job non può essere eseguito da due macchine contemporaneamente, che un job non può essere interrotto (tranne che nei problemi preemptive), che eventuali precedenze devono essere rispettate. Come visto nei precedenti esempi, gli obiettivi di un problema di scheduling possono essere diversi. Per esprimerli formalmente, occorre introdurre alcune grandezze associate ai vari job in uno schedule ammissibile: 1. Tempo di completamento Cj . È l’istante in cui l’ultimo task del job j (e quindi l’intero job j) termina, misurato a partire dall’istante 0. 2 2. Lateness Lj . È la differenza tra il tempo di completamento e la data di consegna del job j. Si noti che se è positiva, la lateness indica un ritardo, se negativa un anticipo rispetto alla due date. Si ha dunque Lj = Cj − dj . 3. Tardiness Tj . Coincide con la lateness quando questa è positiva, ed è zero altrimenti, ossia Tj = max(0, Lj ). 4. Earliness Ej . Coincide con la lateness quando questa è negativa, ed è zero altrimenti, ossia Ej = max(0, −Lj ). 5. Flow time Fj . È la differenza tra il tempo di completamento e la data di rilascio, Fj = Cj − rj . Utilizzando queste grandezze è possibile costruire varie funzioni obiettivo, tra cui ricordiamo: • Massimo tempo di completamento o makespan Cmax . Cmax = maxj Cj e rappresenta la misura (rispetto all’istante 0) del tempo necessario a completare tutte le attività. • Massima lateness Lmax . Lmax = maxj Lj e rappresenta il ritardo del job che è maggiormente in ritardo rispetto alla propria data di consegna. (Si noti che potrebbe anche essere negativa, e in tal caso rappresenta l’anticipo del job che termina con minore anticipo rispetto alla propria data di consegna). • Massima tardiness Tmax . È definita come max(0, Lmax ). • Tempo di completamento totale (al limite pesato). È pari a P j Cj (o P j wj Cj ). Utilizzando gli elementi analizzati, possiamo dare una rappresentazione compatta dei problemi di scheduling. Tale notazione è una notazione a tre campi, nota come notazione di Graham, α/β/γ, ed i tre campi rappresentano rispettivamente: • α il sistema e il numero di macchine, • β le (eventuali) caratteristiche particolari, • γ la funzione obiettivo. Per quanto concerne il sistema, indicheremo le tre possibili strutture (singola macchina, flow shop, job shop) con 1, F e J rispettivamente. Ad esempio, il problema di minimizzare il massimo ritardo di un job su una macchina, con release date, verrà indicato con 1/rj /Lmax . Minimizzare il makespan in un flow shop con due macchine, senza ulteriori specifiche, verrà indicato con F 2//Cmax . Diverse funzioni obiettivo sono spesso in constrasto tra di loro e quindi, nella realtà, occorre valutare i tradeoff coinvolti oppure procedere ad una ottimizzazione multiobiettivo. In altri casi, invece, funzioni obiettivo diverse sono equivalenti (ad esempio la massimizzazione dell’utilizzo è equivalente alla minimizzazione del makespan; la dimostrazione è lasciata al lettore come esercizio). In generale, comunque, molte funzioni obiettivo tra le più comuni dipendono da Cj , nel senso che sono tali da forzare l’inizio dei job al più presto. In questo caso, lo schedule è facilmente ed immediatamente ricavabile dalla sequenza (perché?). Parliamo P poi di funzioni obiettivo regolari se aumentano all’aumentare di Cj , come ad esempio il flow time totale ( j Fj ), il makespan, la massima lateness. Esistono comunque anche misure di prestazione non legate a Cj , ma legate, ad esempio, a tempi o costi di setup, priorità dei job, etc. etc. Concludiamo questa parte introduttiva enumerando le ipotesi generali della cosidetta schedulazione classica: 1. lotti trattati come entità indivisibili, 2. no preemption, 3 3. non è possibile cancellare un job, 4. il tempo di processo pj non dipende dalla sequenza, 5. è possibile avere WIP, 6. le macchine lavorano un unico job alla volta, 7. ogni job visita una macchina al più una volta, 8. le macchine sono sempre disponibili, 9. le macchine sono le uniche risorse considerate, 10. il problema è deterministico e tutti i dati sono noti. Tratteremo casi in cui alcune di queste ipotesi non sono rispettate (ad esempio problemi con setup dipendenti dalla sequenza o con job che visitano una certa macchina più di una volta). Nel seguito vedremo alcuni metodi di soluzione per problemi di schedulazione e la modellizzazione MILP di alcuni problemi specifici. 3 Metodi di soluzione I problemi di schedulazione sono problemi concettualmente semplici ma difficili da un punto di vista di tempi di calcolo poiché, per raggiungere l’ottimo, spesso è necessaria una enumerazione completa. Se abbiamo ad esempio 20 job, le sequenze possibili sono 20! (ovvero 2,43*1018 ); se aumentiamo il numero dei job di 1, le sequenze possibili diventano 21 ∗ 2, 43 ∗ 1018 . Se fossimo capaci di generare un milione di sequenze al secondo, per generare tutte le sequenze ci impiegheremmo 2, 43 ∗ 1012 secondi, ovvero 77146 anni. È quindi evidente che una enumerazione completa di tutte le sequenze non è possibile ma occorre sviluppare metodi di soluzione più efficienti. I metodi di soluzione si distinguono in esatti ed euristici, secondo il seguente schema: • Metodi esatti: – costruttivi – enumerativi • Metodi euristici: – iterativi – one-shot La rappresentazione di una soluzione può essere fatta tramite il cosiddetto diagramma di Gantt, un grafico che rappresenta su un asse temporale le varie attività. È uno “strumento” facile da utilizzare e permette di ottenere risultati visibili, ma non è efficace se ci sono molti job perché in questo caso si perde il vantaggio della visibilità; inoltre è solamente uno strumento descrittivo, permette cioè di rappresentare graficamente una soluzione ma di per sè non genera alcuna soluzione. Tra i metodi esatti ricordiamo: • Branch-and-Bound (enumerativo); • alcune regole di priorità o algoritmi per problemi specifici (SPT per 1// F 2//Cmax ); questi sono tutti metodi costruttivi. Tra i metodi euristici: • regole di priorità in generale (one-shot); • metaeuristiche (iterativi) quali tabu search, simulated annealing. 4 P j Cj , Johnson per 3.1 Problemi di macchina singola In assenza di release date, per ogni funzione obiettivo P regolare, lo schedule ottimo è sempre uno tra quelli in cui la macchina è sempre attiva tra gli istanti 0 e j pj e non c’è preemption. Se infatti non ci sono motivi per tenere una macchina idle, il problema è una permutazione e diventa un problema di semplice sequencing. Quando invece la funzione obiettivo è non regolare, potrei avere vantaggi a tenere la macchina inattiva in alcuni periodi. Problemi di macchina singola risolti all’ottimo in modo semplice e senza l’utilizzo di metodi enumerativi sono: P • 1// j wj Cj , risolto con la regola di priorità WSPT; P • 1// j Cj , risolto con la regola di priorità SPT; • 1//Lmax , risolto con la regola di priorità EDD; • 1/prec/ maxj γj (Cj ), cioè problemi con vincoli di precedenza tra i job ed in cui la misura di prestazione è la minimizzazione del massimo di una qualche funzione dei tempi di completamento (es. Lmax , Cmax ...). Questi problemi sono risolti tramite l’algoritmo di Lawler. Tranne l’algoritmo di Lawler, che non non verrà discusso nel seguito, gli altri metodi sono tutte regole di priorità. Le regole di priorità sono metodi euristici (tranne che per problemi specifici in cui permettono di raggiungere l’ottimo) one-shot e molto semplici e possono essere utilizzate non solo per i problemi di macchina singola ma anche per problemi con più macchine (flow shop o job shop); anche in questi casi però le macchine sono trattate una alla volta e quindi le analizziamo nel contesto della macchina singola. 3.1.1 Regole di priorità Possiamo caratterizzare sinteticamente le regole di priorità osservando che: • simulano un processo di scheduling come se avvenisse in tempo reale; • hanno tempi di calcolo ridotti e sono semplici da utilizzare; • forniscono una soluzione, in genere, di qualità limitata, poiché sono miopi e la soluzione raggiunta può essere anche molto lontana dall’ottimo; • non considerano la capacità delle macchine. Possiamo distinguere tra regole statiche, in cui la priorità non cambia nel tempo e non tiene conto dell’istante temporale in cui la priorità viene calcolata, e regole dinamiche, in cui la priorità può variare nel tempo. Queste ultime sono utili se si vuole tenere conto delle due date. Tra le regole statiche ricordiamo: SPT, WSPT, EDD, LWKR e MWKR. Shortest Processing Time (SPT). Secondo questa regola, i job sono sequenziati in ordine non decrescente dei tempi di processo dei job. Il job con tempo di processo più piccolo ha la priorità maggiore. Si può facilmente dimostrare che questa regola di sequenziamento fornisce la soluzione ottima in caso di P minimizzazione del tempo di completamento totale ( j Cj ). Longest Processing Time (LPT). È il contrario della SPT ed è utilizzata per bilanciare il carico in caso di macchine parallele. Ha senso utilizzarla quando i buffer sono quasi pieni, in modo da dare tempo alle macchine successive di svuotare il buffer. Weighted Shortest Processing Time (WSPT). È analoga alla SPT ma considera anche i pesi wj dei job. La priorità è rappresentata dal rapporto (wj /pj ), cioè quanto maggiore è tale rapporto, (ovvero tanto minore è il tempo di processo e/o maggiore è il peso del job), tanto prima passa il job. Ordino quindi i job secondo (pj /wj ) non decrescenti. Si può facilmente dimostrare che questa regola di sequenziamento fornisce la P soluzione ottima in caso di minimizzazione del tempo di completamento totale pesato ( j wj Cj ). 5 Earliest Due Date (EDD). La priorità è inversamente proporzionale alla data di consegna dj del job, ovvero passa prima il job con la data di consegna più vicina. Ordino quindi i job secondo dj non decrescenti. Si può facilmente dimostrare che questa regola di sequenziamento fornisce la soluzione ottima in caso di minimizzazione della massima lateness (Lmax ). Least Work Remaining (LWKR). Viene data massima priorità al job con minimo carico rimanente; è la generalizzazione di SPT al caso in cui i job hanno più operazioni. LaPpriorità è inversamente proporzionale Pmn p . Fornisce buoni risultati rispetto al flow time totale ( j Fj ). a i=m ji i Most Work Remaining (MWKR). Viene data massima priorità al job con massimo carico rimanente; tende ad alimentare le macchine e ottiene buoni risultati in termini di makespan ed utilizzo (e quindi cattivi in termini di WIP). È l’opposto, come priorità, alla LWKR, in quanto è la generalizzazione di LPT al caso in cui i job hanno più operazioni. Tra le regole dinamiche abbiamo: SLACK, CR e COVERT. SLACK. La priorità maggiore è data al job con slack sj minore, con sj = dj − rkj − t, ove rkj è il lavoro residuo e t è l’istante corrente. Questa regola ha il limite di tenere conto solo dei tempi di processo e non delle attese in coda. Critical ratio (CR). È simile allo slack ma sceglie il job in base al rapporto rkj /(dj − t). A parità di carico rimanente, quanto più la data di consegna è lontana dall’istante corrente, tanto maggiore è il denominatore del rapporto sopra riportato e quindi tanto minore è la priorità. Cost Over Time (COVERT). Ordina i job j sulla macchina m in base alla priorità πjm calcolata come: πjm = wj δ (1 − δ(sjm )/p̄) pjm con sjm = dj − pjm − k mn X pji − t i=mm +1 mentre δ(x) è un operatore pari ad x se x > 0, 0 altrimenti, k è un parametro stimanto sulla base dell’affollamento (cioè dell’utilizzo), t è l’istante corrente e p̄ è il tempo medio di processo dei job in coda sulla macchina m (può includere o meno il tempo di processo del job j, a seconda delle convenzioni; nel nostro caso lo include). Si può facilmente osservare che • se sjm ≤ 0 allora πjm = wj /pjm ; • se sjm ≥ p̄ allora πjm = 0; • se sjm < p̄ allora πjm = 3.2 wj pjm  1− sjm p̄  . Problemi di flow shop Consideriamo ora un sistema di produzione a linea ed assumiamo che tra ogni macchina e la successiva esista un buffer in grado di ospitare tutti i job in attesa di essere processati. Parliamo di permutation schedule se la sequenza dei job è la stessa su tutte le macchine della linea, non-permutation schedule se la sequenza sulle varie macchine può essere diversa. La complessità dei problemi aumenta rispetto a problemi di macchina singola. Nel seguito vediamo algoritmi sviluppati per problemi molto semplici: • F 2//Cmax , risolto all’ottimo tramite l’algoritmo di Johnson; • F 3//Cmax , risolto in modo euristico con l’algoritmo di Campbell. 6 3.2.1 Algoritmo di Johnson Facciamo l’ipotesi di no-blocking sulla prima macchina, il che equivale ad avere un buffer infinito tra le due macchine (perché). Essendo Cmax una funzione obiettivo regolare, si può dimostrare che esiste sempre una soluzione ottima di tipo permutation (stessa sequenza su entrambe le macchine della linea). La minimizzazione di Cmax è equivalente alla massimizzazione dell’utilizzo. Poiché la prima macchina M 1 lavora senza interruzioni (non c’è limite di WIP), devo minimizzare l’inattività sulla seconda macchina M 2 e quindi processo prima i job con pj1 minori. Alla fine lavoro i job con pj2 minore, in modo da minimizzare la coda (M 1 ha finito di lavorare e quindi è inattiva). Construisco due insiemi, J1 con i job che hanno il tempo di processo su M 1 più piccolo di quello su M 2 e J2 con gli altri job (quelli con pj2 < pj1 ). Quindi sequenzio i job in J1 utilizzando la regola SPT ed i job in J2 utilizzando la regola LTP, ed infine concateno le due sequenze J1J2. 3.2.2 Algoritmo di Campbell È un algoritmo che posso utilizzare per il generico problema F m//Cmax , ovvero per la minimizzazione del makespan in una linea con un numero arbitrario m di macchine. L’algoritmo si basa sulla soluzione di (m−1) problemi a due macchine F 2//Cmax , utilizzando Johnson, e quindi tra le (m − 1) soluzioni scelgo quella migliore, con Cmax più piccolo. Schematizzando a passi, l’algoritmo funziona nel modo sequente: 1. Inizializzo l’indice k ad 1, k = 1, ed il migliore makespan CMAX ad infinito, CMAX = ∞; 2. Costruisco il problema F 2//Cmax virtuale aggregando i tempi di processo sulle varie macchine della linea in questo modo: Pk (k) • pj1 = i=1 pji Pm (k) • pj2 = i=k+1 pji 3. Risolvo il problema F 2//Cmax ; se Cmax < CMAX, assegno CMAX = Cmax ; 4. se k < m − 1, aggiorno k, k = k + 1 e GOTO 2; altrimenti STOP. La sequenza ottima è quella corrispondente a CMAX. 3.3 Problemi di job shop La rappresentazione più comune per i problemi di job shop è quella fornita dal grafo disgiuntivo. Questo è un grafo in cui: • i nodi coincidono con i task (le operazioni dei vari job sulle varie macchine); • gli archi rappresentano precedenze tecnologiche (archi congiuntivi) e precedenze di sequenziamento (archi disgiuntivi). Mentre gli archi congiuntivi sono archi direzionati, ovvero la direzione è determinata dalle precedenze tecnologiche, gli archi disgiuntivi rappresentano il sequenziamento delle operazioni dei vari job (e quindi dei job stessi) sulle risorse condivise. Sono archi non direzionati ed il determinare il loro verso coincide con il risolvere il problema di schedulazione, perché significa sequenziare i job sulle varie macchine. Se in un tale grafo esistono dei cicli, la soluzione non è ammissibile (significa che il job a precede b e contemporaneamente b precede a), mentre se il grafo è aciclico, Cmax corrisponde alla lunghezza del cammino critico (calcolato sul grafo pesato, in cui i pesi sono associati ai nodi e rappresentano la durata delle operazioni coincidenti con i nodi stessi). I problemi di job shop sono tra i più complessi e possono essere risolti con metodi ad hoc, dopo averli rappresentati con un modello MILP, oppure utilizziamo una tra le regole di priorità prima viste per ogni 7 macchina del job shop separatamente. Esistono però euristiche sviluppate appositamente per problemi particolari di job shop, quali: • J2//Cmax , risolto con l’algoritmo di Johnson, P • J// j wj Tj , risolto con la regola ATC (Apparent Tardiness Cost), • J//Cmax , risolto con l’algoritmo noto come shifting bottleneck. In questa sede vediamo solo l’algoritmo di Johnson, mentre ATC e shifting bottleneck, per gli interessati, sono trattati in Advance Model for Manufacturing System Management, Brandimarte, Villa, 1995 CRC Press. Essendo un problema di job shop, i job possono avere routing diversi. Definiamo i seguenti insiemi: • J1: insieme di job che devono essere lavorati solo su M 1; • J2: insieme di job che devono essere lavorati solo su M 2; • J12: insieme di job che devono essere lavorati prima su M 1 e poi su M 2; • J21: insieme di job che devono essere lavorati prima su M 2 e poi su M 1. Sequenzio arbitrariamente i job in J1 e J2, mentre i job in J12 sono sequenziati utilizzando l’algoritmo di Johnson sulla linea M 1 − M 2 ed i job in J21 utilizzando l’algoritmo di Johnson sulla linea M 2 − M 1. Alla fine concateno le sequenze trovate in modo che lo schedule finale su M 1 sia J12 − J1 − J21 e su M 2 sia J21 − J2 − J12. Questo algortimo genera WIP grande per massimizzare l’utilizzo. M 1 ed M 2 sono tenute sempre occupate in quanto M 1 lavora i job in J12 e poi li manda ad M 2 che cosı̀ ha WIP da smaltire mentre M 2 lavora i job in J21 e poi li manda ad M 1, cosı̀ anch’essa ha WIP da smaltire; quindi M 1 lavora J1 ed M 2 lavora J2 ed infine smaltiscono le code (il WIP residuo). 8