Skip to content
Torna ai risultati

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

Dimensione del carattere

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

1

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

2

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.

3

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.

4

Utilizzare meta-euristiche (simulated annealing, tabu search, algoritmi genetici, ant colony optimization) per migliorare la pianificazione attraverso ricerca locale o metodi basati su popolazioni.

5

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

  1. Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.

    Apri il riferimento DOI
    Copiato.
  2. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.

    Apri il riferimento DOI
    Copiato.