Facciamo un po’ di teoria. Purtroppo sarà un po’ più noioso di una passeggiata al supermercato, ma in compenso non ci sarà niente da comperare e il bancomat non correrà più alcun rischio.

Iniziamo con alcune definizioni generali.

Un task è un lavoro che viene eseguito su una risorsa, occupandola per un intervallo di tempo. A parte alcuni casi particolari (ad esempio un forno, uno stampo con più figure) l’occupazione avviene in modo esclusivo, vale a dire che, mentre si sta eseguendo un task, gli altri sono in coda che aspettano.

Il tempo in cui un task occupa una risorsa è dato dalla somma di due valori: il tempo di set-up (eventuale), vale a dire la preparazione della risorsa (attrezzaggio), ed il tempo di esecuzione vero e proprio.

La risorsa è quindi l’oggetto fisico che “smaltisce” i vari task.

Un insieme di task, che ha lo scopo finale di realizzare un oggetto, forma un job. I vari task possono essere in serie, oppure (a gruppi) paralleli, oppure, sempre a gruppi, a precedenza.

Questo job contiene tutti questi casi:

Task 10 Serie

Task 20 A precedenza

Task 30 A precedenza

Task 40 Serie

Task 60 Parallelo

Task 70 Parallelo

Task 80 Serie

Task 90 Serie

 

Come prima cosa viene eseguito il task 10.

Subito dopo, viene eseguito il primo che può essere fatto tra il task 20 e il 30. Un esempio è dato dalla verniciatura di due parti, fisicamente unite, dello stesso oggetto, compiuta da risorse diverse. Se viene pronta per prima la risorsa del task 30, viene eseguito, e il task 20 aspetta la fine: si costituisce una serializzazione dinamica.

Viene poi eseguito il task 40 quando sono terminati sia il 20 sia il 30.

Al termine vengono eseguiti contemporaneamente sia il task 60 sia il 70. In questo caso l’oggetto che si sta trattando è fisicamente, diviso in più parti, che possono essere lavorate contemporaneamente. Un esempio è il caso di due parti di un telaio, ciascuna delle quali deve essere trattata su una risorsa diversa, per poi essere assemblate insieme.

Il task 80, infine, viene eseguito quando sono terminati sia il 60 sia il 70, il 90 quando è terminato l’80: con la sua esecuzione termina il job.

I termini job e task, nella usuale terminologia della gestione della produzione corrispondono rispettivamente all’ordine di produzione e all’impegno di risorse.

 

Tipologie di processi produttivi

Descriviamo ora una classificazione dei processi produttivi, di complessità crescente, di uso comune quando si trattano argomenti di schedulazione o, più in generale, di programmazione e gestione della produzione.

Macchina Singola

Il modello più semplice è il caso della macchina singola: vi è una sola risorsa che tratta tutti i job, ciascuno dei quali è composto da un solo task. L’unico compito da svolgere è di mettere in sequenza i task da eseguire sulla macchina. Facciamo riferimento sempre ai task, anche se in questo caso coincidono con i job, in quanto sono i task i compiti che vengono “consumati” dalle macchine. Questo modello descrive, ad esempio, il caso di un industria di processo (chimica, farmaceutica, alimentare), in cui il lavoro è svolto, dall’inizio alla fine, da un unico impianto.

 

Macchine Parallele

Il modello successivo è costituito dalle macchine parallele: i job (sempre composti da un unico task) possono essere lavorati su una delle n macchine parallele dello stesso tipo. All’interno di questo modello si distinguono due casi: macchine parallele identiche (il tempo di esecuzione di un task è il medesimo su tutte le macchine) e macchine parallele generiche (i tempi di esecuzione di un task dipendono dalla macchina su cui viene eseguito il task). In questo caso è necessario decidere su quale macchina va eseguito ogni task, e in che ordine va eseguito. È il compito che dovremo svolgere in tutti i successivi modelli (e che comprende anche il caso di macchina singola): definire la coda di task da assegnare ad ogni macchina, vale a dire la loro sequenziazione. La schedulazione vera e propria (datazione dei singoli task, e, di conseguenza dell’intero job) ne è una diretta conseguenza, essendo noti gli orari di apertura di ogni macchina, il tempo di esecuzione di ogni task, e il suo istante di inizio “al più presto” (coincidente con l’istante di fine del task che lo precede nello stesso job, a meno che si attivi la sovrapposizione tra le fasi, in cui la fase successiva inizia dopo che è stata completata una quantità parziale della precedente, ad esempio quella che permette di riempire un contenitore).

Nei casi che ci apprestiamo a descrivere, ogni job può essere composto da più task. Da ora in poi riterremo assunta questa affermazione.

Nel seguito faremo inoltre riferimento genericamente ad una macchina (intesa come risorsa che esegue i task), comprendendo sia il caso di macchina singola sia di macchine parallele (sia identiche sia generiche).

Open Shop

Nell’open shop ogni job è composto da più task, ma non vi è un ordine di esecuzione predefinito. Siamo nel caso, descritto all’inizio, di operazioni a precedenza. Va precisato che è un caso di estrema rarità: possono esserci, all’interno di un job, alcune zone a open shop, ma che siano la totalità è quasi impossibile. Un esempio (molto sui generis) è costituito dalla tinteggiatura dell’esterno di un’abitazione, in cui ogni parete è un task dello stesso job  (e c’è un solo imbianchino).

Flow Shop

Il successivo modello di produzione è il flow shop, che invece è di estrema diffusione. In questo caso la sequenza del ciclo di ogni job prevede l’utilizzo delle macchine sempre nello stesso ordine. Si distingue in flow shop puro, quando ogni job visita tutte le macchine, e flow shop generico, se vi sono alcuni job che “saltano” qualche macchina.

Nel seguente esempio

Job 1      Task 1           Task 2             Task 3            Task 4              Task 5            Task 6

Job 2       —-                 Task 1              —-                  Task 2             Task 3             —-

                 Macchina1  Macchina2  Macchina3  Macchina 4  Macchina 5  Macchina 6

il job 1 è un caso di flow shop puro, mentre il job 2 è un caso di flow shop generico.

Come si può notare, nel flow shop generico non è necessario che un job inizi e finisca con la prima e con l’ultima macchina presenti.

Nel flow shop, oltre a non essere permesso ad un job di visitare le macchine in ordine diverso (un job non può visitare prima la macchina 3 e poi la macchina 1), è impedito ad un job di rivisitarne alcune: ad esempio il job 2, dopo il task 2 sulla macchina 4, non può eseguire un task successivo sulla macchina 2.

Per comprendere anche questi casi, si è definito il modello più generale: il job shop, nel quale ogni job può visitare un sottoinsieme delle macchine presenti, senza un ordine prestabilito, e soprattutto può visitarle più di una volta. È il caso prevalente delle lavorazioni meccaniche.

I modelli che abbiamo descritto possono essere presenti contemporaneamente nella stessa azienda. Deve naturalmente verificarsi la condizione per cui l’insieme dei job e delle macchine di ogni modello non abbia nessun elemento in comune con gli altri: ciò accade quando si possono individuare delle “sottoaziende” del tutto separate tra di loro.

Facciamo infine presente che i job possono avere dei vincoli di precedenza, che vanno naturalmente tenuti in considerazione nei processi che ci accingiamo a descrivere. Ciò accade, ad esempio, quando l’oggetto prodotto da un job costituisce un componente di un job successivo.

Ora che abbiamo classificato la natura dei processi in base alla loro complessità, ci resta da capire in che modo riusciremo a venire a capo, per ciascuno di essi, del compito che ci siamo prefissati fin dall’inizio, vale a dire definire le code di task sulle varie macchine.

 

Indici della schedulazione

Si definiscono degli indici (a livello di job e di risorsa) che contribuiscono a determinare i valori globali dell’intera schedulazione, che ne misurano la validità, e permettono di confrontarla con altre che hanno gli stessi dati ma diverse impostazioni (ad esempio forzature manuali). Riportiamo quelli di uso più comune, ricordando che, nel caso siano ottenuti come medie di altri valori, spesso se ne determina anche la deviazione standard per valutarne la dispersione.

Per ogni job si determinano:

  • la lateness, differenza tra la data di fine richiesta e la data di fine effettiva (l’anticipo porta ad un valore negativo)
  • la tardiness: si calcola come la lateness, ma in caso di un valore negativo (anticipo) si porta zero. È un indice più realistico del precedente in quanto un anticipo non recupera un ritardo (posto che non sia nocivo di suo)
  • l’earliness: si calcola come la lateness, ma in caso di un valore positivo (ritardo) si porta zero, in caso di un valore negativo (anticipo) la si cambia di segno.
  • il flowtime, differenza tra la data di fine effettiva e quella di ingresso nel sistema (è il lead time reale del job)

Per ogni risorsa si calcolano:

  • La saturazione, ottenuta come rapporto percentuale tra le ore in cui la risorsa è utilizzata e quelle in cui è disponibile
  • Il makespan, dato dalla differenza tra la data di fine utilizzo e quella di inizio disponibilità

Per l’intera schedulazione si determinano infine:

  • lateness, tardiness e flowtime totali e medie, ottenute come somma dei valori di ogni singolo job divisa per il numero di job. Talvolta può essere utile dare un’importanza diversa a ogni singolo job, e calcolare i valori medi pesati, in modo che, ad esempio, un ordine di mille pezzi di un articolo abbia più influenza di un ordine di tre pezzi del medesimo articolo. Si determinano anche i valori medi condizionali (riferiti unicamente agli ordini che contengono un valore significativo dell’indice che si intende calcolare): ad esempio la tardiness media condizionale viene ottenuta dividendo la tardiness totale per il numero di ordini in ritardo.
  • la saturazione, ottenuta come rapporto percentuale tra le ore in cui tutte le risorse sono utilizzate e quelle in cui sono disponibili
  • il makespan, ottenuto considerando il valore massimo tra quelli delle singole risorse
  • il numero (e la percentuale sul totale) dei job in anticipo, puntuali e in ritardo

Tipi di strategie

L’obiettivo è quindi, dato un indice, determinare la schedulazione che lo massimizza (o minimizza) a seconda che sia positivo o meno il fatto che cresca (la saturazione è un indice positivo crescente, la lateness no).

Una schedulazione viene detta ammissibile (oppure fattibile) se rispetta tutti i vincoli che le abbiamo imposto.

Una schedulazione viene detta ottima (oppure dominante) se è la migliore rispetto all’indice che si è preposta di massimizzare (o minimizzare).

Sono stati proposti metodi analitici (equazioni o sistemi di equazioni algebriche o differenziali) che permettono di ottenere la soluzione ottima. Purtroppo assai spesso richiedono tempi di esecuzione proibitivi.

In alternativa sono stati sviluppati metodi algoritmici che giungono alla soluzione con una serie di passi.

Tra gli algoritmi se ne possono utilizzarne di generali (programmazione lineare o dinamica, metodo del simplesso, ecc…) oppure specifici, che si applicano unicamente sotto certe ipotesi (ad esempio il modello di Hodgson, valido nel caso di macchina singola e costanza del tempo di attrezzaggio). Quest’ultima ipotesi è irrealistica, in quanto tempo di attrezzaggio spesso dipende dalla coppia di task (quello che era presente sulla macchina e quello che deve essere eseguito): nel caso più semplice (se l’articolo è lo stesso) è assai probabile che l’attrezzaggio (a meno di piccole regolazioni o pulizie) sia nullo.

Purtroppo questi metodi sono raramente applicabili nella realtà, in quanto spesso necessitano di ipotesi il cui rispetto inficia in modo pesante il risultato (ad esempio costanza dei tempi di attrezzaggio, ininfluenza della data di consegna, tutti i job devono essere pronti al tempo zero, assenza di legami di precedenza tra job, ecc…).

Il metodo di Johnson, uno dei più noti algoritmi di schedulazione, che si propone di minimizzare il makespan, si basa su queste ipotesi:

  • ambiente flow-shop costituito da due macchine sempre disponibili
  • un insieme di job, indipendenti tra di loro, tutti disponibili al tempo zero
  • la data di consegna non è rilevante
  • i tempi di setup sono indipendenti dalla sequenza

È stata proposta un’estensione a N macchine, ma rimangono le altre ipotesi a limitarne il campo di applicabilità.

Vi sono infine metodi euristici, che non hanno l’ambizione di raggiungere la soluzione ottima, ma si accontentano di una soluzione buona, oltre che ammissibile.

Si dividono in due tipi:

  • la ricerca locale nello spazio
  • la ricerca locale nel tempo.

Nel primo caso, si determina innanzitutto una soluzione ammissibile, che si modifica man mano localmente (variando solo alcuni valori della soluzione) nella direzioni in cui pare più promettente il miglioramento dell’obiettivo (neighborhood search).

La prossima puntata non avremo più tempo di giocare coi termini, ma dovremo incominciare a rimboccarci le maniche. Entreremo in dettaglio nella ricerca locale nel tempo, che è la strategia utilizzata da buona parte degli strumenti di schedulazione della produzione industriale.