Introduzione alla Flow Shop Scheduling

La pianificazione del flusso è un problema fondamentale nella ricerca operativa e nell'ingegneria industriale che comporta la sequenziamento di un insieme di posti di lavoro attraverso una serie di macchine in ordine fisso. Ogni lavoro deve visitare ogni macchina esattamente una volta, e l'ordine di elaborazione è identico per tutti i lavori. L'obiettivo è tipicamente minimizzare il fapan (tempo di completamento totale), il tempo di flusso totale, o altre misure di prestazioni come ritardo o tempo di corsa.

Gli euristici sono algoritmi di risoluzione dei problemi che sacrificano l'ottimalità per la velocità. Levorano la conoscenza del dominio, le regole del pollice, o la ricerca stocastica per esplorare lo spazio della soluzione in modo efficiente. Flow shop pianificazione euristica sono stati studiati ampiamente dal 1950, con le regole iniziali come l'algoritmo di Johnson per due macchine e successive generalizzazioni.

Metodi euristici comuni

L'euristica Flow Shop rientra in due categorie: euristica costruttiva, che costruisce un programma da zero, e euristica migliorata, che parte da un programma fattibile e lo migliora iterativamente. Alcuni metodi combinano entrambe le strategie.

Regole di dismissione prioritarie

Le regole prioritarie sono le più semplici euristica costruttiva, che assegnano ad ogni lavoro una priorità basata su attributi come il tempo di elaborazione, la data di scadenza o l'orario di arrivo e i lavori di sequenza in ordine di priorità.

  • Tempo di elaborazione più breve (SPT)[: I lavori con il più piccolo tempo di elaborazione totale sono programmati per primo. SPT minimizza il tempo di flusso medio ma può aumentare il fapan.
  • Prima come First Serve (FCFS)[]: I lavori vengono elaborati in ordine di arrivo.
  • Data di scadenza (EDD)[: I lavori con le prime date sono prioritari, spesso utilizzati per ridurre al minimo il ritardo.
  • Tempo di elaborazione più lungo (LPT)[: Di fronte a SPT, usato in alcuni scenari per bilanciare il carico.

Le regole prioritarie sono estremamente veloci ([]O(n log n)]]) e facili da implementare, rendendole adatte per la programmazione in tempo reale. Tuttavia, raramente producono soluzioni ottimali e possono eseguire in modo cattivo su istanze grandi o complesse.

Quartiere più vicino (NEH) Euristico

L'Euristica NEH (Nawaz, Enscore, & Ham) è uno dei metodi costruttivi più efficaci per la minimizzazione del flusso.

  1. Inizial ordering[[]: Ordinare posti di lavoro in ordine non crescente di tempo di elaborazione totale (somma su tutte le macchine).
  2. Inserzione[]: Prendere il primo lavoro come la sequenza iniziale. Quindi inserire iterativamente ogni lavoro successivo nella posizione migliore (quello che minimizza il fapan) nella sequenza parziale corrente.

La forza di NEH è nella sua capacità di generare soluzioni di alta qualità rapidamente. Spesso è usato come punto di riferimento e punto di partenza per migliorare l'euristica. La complessità è O(m n]3]) esistono per ]]]] macchine e accelera

Algoritmi genetici (GA)

Gli algoritmi genetici sono metaheuristici basati sulla popolazione ispirati alla selezione naturale, codificano i programmi come cromosomi (ad esempio, permutazione dei posti di lavoro) e li evolvono nelle generazioni che utilizzano gli operatori:

  • Selezione[]: Scegli i genitori in base al fitness (ad esempio, valore di makepan).
  • Crossover[[]: Combina due sequenze genitori per produrre prole.Per problemi di permutazione, gli operatori come crossover parzialmente mappato (PMX) o crossover ordine (OX) conservano l'ordine relativo.
  • Mutation[]: Modifica casualmente un cromosoma (ad esempio, scambia due posti di lavoro, sposta un lavoro in una nuova posizione) per mantenere la diversità.
  • Elitismo[]: Conservare i migliori individui per evitare la perdita di soluzioni di alta qualità.

I GA esplorano un ampio spazio di soluzione e possono sfuggire all'ottimizzazione locale, sono flessibili e possono gestire obiettivi complessi (ad esempio, negozi di flusso multi-oggettivi), ma richiedono un'attenta messa a punto dei parametri (dimensione della popolazione, velocità di crossover, tasso di mutazione) e possono essere calcolativamente costosi per grandi istanze.

Annealing simulato (SA)

[T6] similmente similmente il processo fisico di ricottura dove un materiale viene riscaldato e quindi lentamente raffreddato per ridurre i difetti. In programmazione, SA inizia con una soluzione iniziale (spesso da NEH) e genera in modo iterativo una soluzione vicina da piccole perturbazioni (ad esempio, swap o inserimento).

Il vantaggio principale di SA è la capacità di sfuggire all’Otima locale, soprattutto alle alte temperature, che è stata applicata con successo a molti problemi di flow shop. La performance è sensibile al programma di raffreddamento e alla scelta dell’operatore locale. Con un lento tasso di raffreddamento, SA può avvicinarsi all’ottimo globale ma diventa lento.

Ricerca Tabu (TS)

La ricerca Tabu è un miglioramento euristico che utilizza strutture di memoria (tabu list) per evitare di rivisitare soluzioni recentemente esplorate. A partire da una soluzione iniziale, TS esplora il quartiere e seleziona la migliore soluzione non-tabu (o accettabile se soddisfa un criterio di aspirazione).

TS offre un buon equilibrio tra esplorazione e sfruttamento, produce spesso soluzioni di alta qualità con tempi di calcolo moderati. Le variabili includono la ricerca di tabu reattiva (adattando dinamicamente la dimensione dell'elenco tabu) e il TS ibrido con altre euristiche.

Altri metodi euristici

Oltre ai classici, sono state sviluppate diverse altre euristica per la programmazione del negozio di flusso:

  • Ant Colony Optimization (ACO)[]: Modelli il comportamento foraging delle formiche. Le formiche artificiali costruiscono soluzioni selezionando con probabilità sequenze di lavoro basate su percorsi di feromoni e informazioni euriche (ad esempio, tempo di elaborazione).
  • Ottimizzazione delle armi da bagno (PSO)[]: Utilizza una popolazione di particelle che si muovono attraverso lo spazio di soluzione, regolando le loro posizioni in base a posizioni personali e globali.
  • Ricerca locale (ILS)[]: Si basa su una ricerca locale (ad esempio, discesa più ripida) da una soluzione di partenza, quindi perturba l'ottimo locale per generare un nuovo punto di partenza, ripetendo più volte.
  • Variable Quartiere Search (VNS)[: Sistematicamente cambia le strutture del quartiere durante la ricerca per sfuggire all'optima locale.

Analisi comparativa

La scelta di un'euristica dipende dalla scala dei problemi, dai requisiti di qualità delle soluzioni e dalle risorse computazionali disponibili. Di seguito è un confronto sommario basato su istanze standard di riferimento (ad esempio, i set di test di Taillard per la programmazione del negozio di flusso).

Qualità della soluzione

Le regole prioritarie e le semplici euristica costruttiva tipicamente raggiungono falatti di espansione del 10-20% rispetto alla soluzione ottimale o più nota. NEH si esibisce molto meglio, spesso entro il 3–5% dell'ottimo. La metaheuristica (GA, SA, TS) può raggiungere lacune dello 0–1% dato un tempo di esecuzione sufficiente.

Tempo di calcolo

Le regole prioritarie sono le più veloci (millisecondi per centinaia di posti di lavoro). NEH è leggermente più lenta ma ancora pratica (secondi per istanze moderate). La metaheuristica varia ampiamente: un tipico GA con popolazione 100 e 1000 generazioni può funzionare per minuti per grandi istanze (ad esempio, 100 posti di lavoro, 20 macchine), mentre SA con un programma di raffreddamento lento può essere simile veloce. TS è generalmente più veloce di GA per iterazione, ma può avere molti problemi critici.

Robustezza

La robustezza si riferisce alla consistenza della qualità della soluzione in diversi casi di problemi. NEH è molto robusta per la minimizzazione del fapan. GA e SA possono essere sensibili alle impostazioni dei parametri; GA scarsamente sintonizzato può convergere prematuramente o non riuscire ad esplorare. Le prestazioni di TS sono meno sensibili ai parametri rispetto a SA, anche se le dimensioni dell'elenco dei tabu.

Misurazioni di prestazione

Quando si valutano le euristica, vengono utilizzate diverse metriche:

  • Makespan (C[]max]]][]]: Tempo totale dall'inizio del primo lavoro al completamento dell'ultimo lavoro sull'ultima macchina.
  • Tempo di flusso totale[]: Somma di tempi di completamento di tutti i lavori.
  • Crescienza massima[[]: ritardo del caso rispetto alle date date, spesso utilizzato in ambienti orientati al cliente.
  • Numero di Tardy Jobs[: Conteggio di lavori che terminano dopo la data di scadenza.
  • Tempo di posa[[]: Tempo di posa totale della macchina; minimizzando aumenta l'utilizzo della macchina.

L'euristica NEH è progettata per il makepan, mentre l'EDD e altre regole a due tempi sono la destinazione di destinazione. L'ottimizzazione multi-oggettiva (ad esempio, Pareto front) è un'area di ricerca attiva.

Approcci ibridi e recenti progressi

Nessun singolo euristico domina tutte le istanze di problemi. I metodi ibridi combinano più tecniche per sfruttare le rispettive forze.

  • NEH + Ricerca locale[[]: Usa NEH per generare una buona soluzione iniziale, quindi applica la ricottura simulata o la ricerca di tabu per il miglioramento.
  • L'Algoritmo Genetico + Ricerca Locale (Algoritmo Memetico): Applicare la ricerca locale a ogni prole prima dell'inserimento nella popolazione, garantendo una buona convergenza.
  • Controllo del parametro adattivo[[]: Regolare i parametri GA o SA durante la corsa in base al comportamento di ricerca (ad esempio, ri-annealing della temperatura, tassi di mutazione adattativa).
  • Integrazione di apprendimento della macchina[[[]: Modelli di regressione del treno o agenti di apprendimento del rinforzo per prevedere buone mosse o selezionare l'euristica dinamicamente. Ad esempio, utilizzando reti neurali per guidare posizioni di inserimento in euristica costruttiva.

La ricerca recente esplora anche cloud e calcolo parallelo[] per accelerare la metaheuristica basata sulla popolazione, e hyper-heuristics[] che scelgono tra euristica a basso livello ad ogni passo. Il campo continua ad evolversi, con nuovi benchmark e varianti di problemi (ad esempio, negozio di flusso senza onde).

Scegliere la giusta euristica

La selezione di un euristico per la programmazione del negozio di flusso dipende da diversi fattori pratici:

  • Dimensioni e complessità del prodotto[[]: Per istanze piccole e medie (10–50 posti di lavoro, fino a 20 macchine), possono essere fattibili metodi esatti, ma se non, NEH o un semplice metaheuristico come TS funziona bene.
  • Requisiti di qualità della valutazione[[]: Se le soluzioni quasi ottimali sono obbligatori (ad esempio, nella produzione ad alto rendimento), un ibrido GA o TS con tempi di esecuzione più lunghi è giustificato.
  • Risorse computazionali disponibili[[]: Il cloud computing o le workstation potenti consentono l'uso di metodi più computazionalmente intensivi come GA con grandi popolazioni.
  • Sforzo di attuazione[[]: Le regole di priorità e NEH sono banali al codice. SA e TS richiedono uno sforzo moderato; GA è più complesso ma ben documentato. ACO e PSO richiedono scelte di progettazione aggiuntive per problemi discreti.
  • Ambienti dinamici[[[]: Alcuni sistemi di produzione affrontano nuovi lavori che arrivano nel tempo (programmazione online).

Molti ricercatori utilizzano il punto di riferimento []Taillard flow shop []] o ]OR-Library istanze[] per confrontare le prestazioni.

Conclusioni

La pianificazione del Flow Shop rimane un problema di ottimizzazione combinatoria impegnativo con una notevole rilevanza industriale. I metodi euristici offrono un ponte pratico tra la fattibilità computazionale e la qualità della soluzione. Mentre le regole di priorità semplici e l'euristica NEH forniscono soluzioni rapide e accettabili per molti scenari, metaheuristica come algoritmi genetici, ricottura simulata e risultati di ricerca tabu quasi ottimali a costo di una maggiore computazione.

I praticanti dovrebbero considerare gli obiettivi specifici, le dimensioni dei problemi e il budget computazionale quando si seleziona un euristico. I progressi in corso nel design metaheuristico, l'integrazione dell'apprendimento automatico e il calcolo parallelo continuano a spingere i confini di ciò che è realizzabile, facendo che il flusso shop programma un campo vibrante sia per lo studio teorico che per l'applicazione pratica.

Per ulteriori informazioni, vedere l'indagine completa da Framinan et al. (2015)[] su flow shop pianificazione euristica, e il testo classico da Pinedo (2016)] sulla teoria e gli algoritmi di pianificazione.