Algoritmi matematici per minimizzare i ritardi totali nella programmazione di un flow shop

Titolo originale:

Matheuristic algorithms to minimize total tardiness in flow shop scheduling

Contenuto del libro:

Nel problema di programmazione del flow shop a permutazione, i lavori devono essere programmati su un insieme di macchine. I lavori vengono elaborati sulle macchine nello stesso ordine.

L'obiettivo di questo studio è minimizzare il ritardo totale. Per risolvere questo problema vengono proposti algoritmi euristici e nuovi algoritmi matematici. I metodi matematici sono algoritmi approssimati che sono stati proposti inizialmente per risolvere alcuni problemi di ottimizzazione combinatoria.

Questi metodi incorporano la risoluzione esatta in approcci (meta)euristici. Questo tipo di metodi di risoluzione ha ricevuto un grande interesse in letteratura a causa delle loro ottime prestazioni nella risoluzione di alcuni problemi difficili.

L'autore considera anche un problema in cui sono integrati un problema di programmazione di un flow shop a permutazione di m-macchine e un problema di instradamento di veicoli, con l'obiettivo di minimizzare il ritardo totale. Viene proposta l'introduzione di una codifica diretta per una soluzione completa e di un algoritmo di ricerca Tabu per trovare una sequenza di produzione e di viaggi.

I risultati mostrano che la ricerca Tabu migliora notevolmente la soluzione iniziale data dall'euristica Earliest Due Date, in cui ogni viaggio serve solo un lavoro alla volta.