Sonia Archetti – Modelli di ottimizzazione per lo scheduling su macchina singola con tempi di set-up

Con il termine scheduling si intende un’ampia classe di problemi, diversi tra di loro per struttura e complessità. Oggi i problemi di scheduling più complicati non possono essere risolti con un unico approccio, ma a volte è preferibile impiegare euristiche piuttosto che algoritmi. In generale si possono definire come problemi decisionali in cui il tempo riveste un’importanza fondamentale, in quanto fattore scarso da allocare a determinate attività in modo ottimale.
Questa tesi si occupa di affrontare i metodi di ottimizzazione per lo scheduling correlato al settore produttivo. Un processo di produzione è caratterizzato da un insieme di operazioni che richiedono l’impiego di risorse quali macchinari e manodopera. L’obiettivo è allocare le operazioni alle risorse disponibili, determinare la sequenza di esecuzione dei lavori ed infine determinare gli istanti di inizio dei lavori che devono essere processati.
È stato analizzato un caso pratico: grazie a dati aziendali, si risolverà un problema di ottimizzazione della produzione riferito ad una macchina singola con l’aggiunta dei tempi di setup. Sono stati ricavati i dati relativi ad una settimana lavorativa, e sono state confrontate soluzioni ottenute applicando metodi euristici al variare dell’obiettivo del decisore, e proposto un modello per la sua risoluzione.
Il fine ultimo della tesi è quello di poter confrontare, grazie all’utilizzo di software quali Lekin e MPL, la soluzione ottenuta grazie all’analisi, con quella aziendale.
In ogni processo di scheduling è necessario conoscere in modo dettagliato sia il tipo di risorsa disponibile, che può consistere in manodopera o macchinari, sia la sua quantità per poter quindi affermare quando un’operazione può essere realizzata. Inoltre bisogna definire il compito in termini di richiesta di risorse, di durata, di tempo al più presto in cui può cominciare e di tempo in cui deve essere completato. Possono essere individuati in aggiunta dei vincoli, generati per esempio dalla limitata disponibilità di risorse, che devono essere necessariamente rispettati, tra cui:
– Vincoli di capacità delle macchine;
– Restrizioni tecnologiche per quanto riguarda l’ordine di lavorazione degli ordini.
Una soluzione del problema di scheduling si considera ammissibile se rispetta entrambi i vincoli e risponde alle seguenti domande: “quali risorse devono essere allocate per realizzare un ordine?” e “quando deve essere realizzato l’ordine?”.
Il problema di scheduling più semplice prevede una sola risorsa, ovvero una macchina, che deve lavorare diversi ordini con tempi di processamento definiti a priori. Questo tipo di problema può essere unico o può essere inserito all’interno di un problema più grande di scheduling, quindi è molto importante analizzarlo in modo dettagliato.
Il problema base è caratterizzato dalle seguenti condizioni:
– Al tempo zero vi sono n operazioni singole che sono disponibili per essere processate;
– La macchina può eseguire un solo lavoro alla volta;
– I tempi di set up sono indipendenti dalla sequenza di lavoro e sono inclusi nei tempi di processamento;
– I lavori e le loro caratteristiche sono conosciuti in anticipo;
– La macchina è sempre disponibile;
– Se un’operazione viene avviata, questa procede senza interruzioni, quindi non è ammessa la preemption. Lo scopo di questa tesi è stato presentare dei metodi di ottimizzazione dei problemi di schedulazione su macchina singola con tempi di setup.
Per poter fare ciò è stato proposto un caso applicativo aziendale relativo ad una settimana lavorativa, composta da 5 giorni. Per ogni giorno sono stati definiti i lavori da realizzare su macchina singola, i tempi di processamento, i tempi di setup e le scadenze. Al fine di rendere l’analisi coerente, si è evitato di considerare eventi straordinari che non permettono il naturale svolgimento del lavoro, quali ad esempio mancanza di energie elettrica, le prove per i miglioramenti, interventi di manutenzione, problemi di qualità, sciopero, ferie, festività ed infine pulizie della macchina.
L’obiettivo iniziale era quello di valutare la soluzione proposta dall’azienda con i valori ottenuti grazie al software di scheduling Lekin, che proponeva soluzioni diverse a seconda dell’obiettivo del decisore tramite euristiche.
Successivamente, sono stati proposti dei modelli di programmazione matematica per poter offrire dei termini di paragone rispetto ai valori ottenuti grazie al software Lekin, non considerando tuttavia i tempi di setup in quanto il modello sarebbe stato troppo complesso.
Si è notato che, a seconda dell’obiettivo che si vuole raggiungere e quindi della funzione che si va a minimizzare, si ottengono soluzioni diverse tra loro. Se ad esempio si vuole minimizzare il Makespan si ottiene una sequenza diversa da quella ottenibile in caso di minimizzazione del Max Tardiness.
Il generale è stato possibile osservare che l’azienda realizza la pianificazione della produzione non in maniera ottimale, ma comunque si avvicina a valori molto buoni rispetto a quelli ottenibili grazie all’euristica SB Routine.