Matheurisztikus algoritmusok a teljes késés minimalizálására flow shop ütemezésben

Eredeti címe:

Matheuristic algorithms to minimize total tardiness in flow shop scheduling

Könyv tartalma:

A permutációs áramlásos üzemütemezési problémában a munkákat egy sor gépre kell ütemezni. A munkákat a gépeken azonos sorrendben kell feldolgozni.

A cél a teljes késés minimalizálása. A probléma megoldására heurisztikus algoritmusokat és új matheurisztikus algoritmusokat javasolunk. A matheurisztikus módszerek olyan közelítő algoritmusok, amelyeket eredetileg néhány kombinatorikus optimalizálási probléma megoldására javasoltak.

Ezek a módszerek a pontos megoldást (meta)heurisztikus megközelítésekbe ágyazzák. Az ilyen típusú megoldási módszerek nagy érdeklődésre tartanak számot a szakirodalomban, mivel nagyon jó teljesítményt nyújtanak néhány nehéz probléma megoldására.

A szerző egy olyan problémát is vizsgál, ahol egy m-gépes permutációs flow shop ütemezési probléma és egy jármű útvonaltervezési probléma integrálódik, és a cél a teljes késés minimalizálása. A teljes megoldáshoz egy közvetlen kódolás és egy Tabu kereső algoritmus bevezetését javasolja a gyártási sorrend és az utak megtalálására.

Az eredmények azt mutatják, hogy a Tabu-keresés nagymértékben javítja a legkorábbi esedékességi időpont heurisztika által adott kezdeti megoldást, ahol minden út egyszerre csak egy munkát szolgál ki.