Pianificazione di officina
- Introdotto da
- Pinedo, M. L.
- Anno
- 2016
- Tipo
- Combinatorial scheduling problem
- Famiglia
- Optimization
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La pianificazione di officina (job shop scheduling) è il problema di assegnare un insieme di commesse (task) a un insieme di macchine (risorse) nel tempo, soggetti a vincoli di precedenza e capacità, con l'obiettivo di ottimizzare metriche di performance quali il makespan (tempo totale di completamento), il ritardo o il costo.
Il problema del job shop è un classico problema di ottimizzazione combinatoria nella ricerca operativa, affrontato tramite euristiche (regole di dispatching greedy, simulated annealing, algoritmi genetici) e algoritmi esatti (branch-and-bound, constraint programming). È fondamentale nella produzione, nella gestione di progetti e nella pianificazione computazionale.
L’intuizione alla base del metodo
Immagina una piccola officina con 10 macchine. Un ordine cliente (commessa) consiste in 5 parti, ognuna delle quali richiede una sequenza di operazioni su macchine diverse: la Parte 1 necessita di lavorazione sulla Macchina A, poi foratura sulla Macchina C. La Parte 2 necessita di foratura sulla Macchina B, poi saldatura sulla Macchina D. Tutte le parti convergono per l'assemblaggio finale. La sfida: pianificare tutte le operazioni per minimizzare il tempo totale di completamento, senza superare la capacità delle macchine, rispettando la sequenza operativa per ogni parte. Se assegni la Parte 1 alla Macchina A troppo tardi, la Macchina C rimane inattiva. Se sovraccarichi la Macchina C, tutto si accumula. Il problema del job shop cattura questa complessità: con 100 commesse e 20 macchine, il numero di possibili pianificazioni è astronomico, rendendo impraticabile la soluzione esatta. Invece, si utilizzano euristiche per trovare rapidamente una pianificazione buona (non necessariamente ottimale).
Storia
Il problema della pianificazione di officina è emerso negli anni '50 come problema di ricerca nella ricerca operativa. Lavori seminali di Johnson (1954) hanno risolto il problema a due macchine in modo ottimale; Fisher e Thompson (1963) hanno creato problemi benchmark ancora in uso oggi. Il problema è NP-hard (dimostrato negli anni '70), stimolando lo sviluppo di euristiche e meta-euristiche. Approcci moderni includono constraint programming (anni '90-2000), algoritmi genetici e metodi ibridi. La pianificazione di officina è ora un campo maturo con applicazioni che si estendono oltre la produzione al cloud computing, telecomunicazioni e trasporti.
Quando usarlo
La pianificazione di officina si applica a qualsiasi ambiente di produzione o servizio con più macchine/risorse e commesse con sequenze operative distinte. Applicazioni tipiche includono officine meccaniche, tipografie, fabbricazione di wafer di semiconduttori, ospedali (pianificazione sale operatorie) e pianificazione di progetti. Usala quando la complessità delle commesse è elevata (molteplici operazioni per commessa), l'utilizzo delle macchine è critico, o le date di consegna sono stringenti. Meno critica in ambienti di linea di assemblaggio (flusso lineare) o operazioni semplici su singola macchina.
Limiti e considerazioni
- Complessità combinatoria: trovare soluzioni ottimali è NP-hard; le soluzioni pratiche richiedono euristiche che potrebbero non essere globalmente ottimali
- Le soluzioni euristiche dipendono dal contesto; una regola che funziona bene per un'officina potrebbe performare male in un'altra, richiedendo tuning e validazione
- Assume input statici (commesse e macchine fisse); le officine reali sperimentano arrivi dinamici, cancellazioni e guasti alle apparecchiature, richiedendo frequenti ri-pianificazioni
- Stabilità della pianificazione: frequenti modifiche alle pianificazioni (dovute a nuove commesse o interruzioni) possono aumentare i costi e complicare il coordinamento con lavoratori e clienti
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Accomoda vincoli complessi e realistici (precedenze, capacità macchina, date di consegna) che le semplici regole di pianificazione non possono gestire
- Ottimizza per metriche di business rilevanti (makespan, ritardo, utilizzo macchine) anziché regole ad hoc
- Consente una risposta rapida alle interruzioni; algoritmi di ri-pianificazione possono generare piani rivisti quando una macchina si guasta o arriva una commessa urgente
- La formulazione matematica consente analisi di sensitività ed esplorazione di trade-off (es. ritardo vs. makespan)
- Supportata da strumenti software efficienti e algoritmi meta-euristici maturi
Applicazioni
- Un'officina di precisione utilizza la pianificazione di officina con simulated annealing per pianificare oltre 200 parti personalizzate su 15 macchine CNC, riducendo il makespan del 15% e migliorando la puntualità delle consegne dall'85% al 95%
- Un impianto di fabbricazione di semiconduttori applica la pianificazione basata su vincoli per gestire oltre 500 passaggi di processo su 50 strumenti, minimizzando il tempo di ciclo dei wafer e riducendo l'inventario in lavorazione del 20%
- Un'azienda di stampa utilizza la pianificazione dinamica di officina per assegnare lavori di stampa a 8 macchine da stampa con diverse capacità, ottimizzando per il mix di lavori (alto volume vs. specialità) e minimizzando i tempi di cambio
- Un team di pianificazione ospedaliera implementa algoritmi di job shop per la pianificazione delle sale operatorie, coordinando chirurghi, team chirurgici e attrezzature, migliorando l'utilizzo delle sale operatorie dal 65% all'82%
Come funziona
Come funziona
Definire le commesse (ordini, task) con sequenze operative, requisiti macchina, tempi di lavorazione e date di consegna. Definire le macchine disponibili e le loro finestre di disponibilità.
Specificare i vincoli: precedenza delle operazioni (la Parte 1 deve completare l'operazione A prima di iniziare l'operazione B), capacità (ogni macchina può processare un solo job alla volta), e opzionalmente, tempi di rilascio e date di consegna.
Applicare una regola di dispatching (es. shortest processing time, earliest due date, critical ratio) per sequenziare le commesse su ciascuna macchina, generando una pianificazione iniziale.
Utilizzare meta-euristiche (simulated annealing, tabu search, algoritmi genetici, ant colony optimization) per migliorare la pianificazione attraverso ricerca locale o metodi basati su popolazioni.
Valutare la qualità della pianificazione (makespan, ritardo, tempo di inattività, tempo di buffer). Se accettabile, implementare; altrimenti, aggiustare i parametri e ri-ottimizzare.
Errori comuni
- Ottimizzazione per la metrica sbagliata; massimizzare l'utilizzo delle macchine può aumentare il ritardo delle commesse, mentre rispettare tutte le date di consegna può richiedere un significativo tempo di inattività
- Ignorare tempi di setup e cambi; una pianificazione che minimizza il tempo di inattività ma richiede frequenti e lunghi setup può essere subottimale in pratica
- Eccessiva fiducia nelle pianificazioni euristiche senza validazione rispetto al comportamento reale dell'officina; i vincoli sono spesso più complessi di quanto il modello catturi
Domande frequenti
Cos'è il makespan e perché è importante?
Il makespan è il tempo totale dall'inizio della prima operazione al completamento dell'ultima operazione. Correlato direttamente all'utilizzo delle attrezzature, al flusso di cassa (completamento più rapido = pagamento più rapido) e alla soddisfazione del cliente. Minimizzare il makespan è un obiettivo primario comune nella pianificazione di officina.
Qual è la differenza tra pianificazione di officina statica e dinamica?
La pianificazione statica assume che tutte le commesse siano note in anticipo; si ottimizza un insieme fisso. La pianificazione dinamica gestisce commesse che arrivano nel tempo; le pianificazioni vengono riviste man mano che arrivano nuove commesse o si verificano interruzioni. La maggior parte delle officine reali sono dinamiche, richiedendo algoritmi di ri-ottimizzazione rapidi.
Quale regola di dispatching dovremmo usare?
Nessuna regola singola domina. Shortest Processing Time (SPT) minimizza il makespan; Earliest Due Date (EDD) minimizza il ritardo; Critical Ratio bilancia entrambi. Testa le regole con dati storici o simulazione per trovare la migliore corrispondenza per le priorità e i vincoli della tua officina.
La pianificazione di officina può gestire competenze dei lavoratori e cross-training?
Sì, espandendo il modello di risorsa: invece di solo 'Macchina A', specifica 'Macchina A con Lavoratore 1' o 'Macchina A con Lavoratore 2'. Tuttavia, ciò aumenta la complessità del problema; assicurati che il tuo software di pianificazione supporti vincoli multi-risorsa.
Metodi correlati
Fonti
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
Apri il riferimento DOICopiato.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Apri il riferimento DOICopiato.