Algorytmy matematyczne minimalizujące całkowite opóźnienie w planowaniu przepływu w warsztacie

Oryginalny tytuł:

Matheuristic algorithms to minimize total tardiness in flow shop scheduling

Zawartość książki:

W problemie harmonogramowania permutacyjnego, zadania muszą być zaplanowane na zbiorze maszyn. Zadania są przetwarzane na maszynach w tej samej kolejności.

Celem tego badania jest zminimalizowanie całkowitego opóźnienia. Do rozwiązania tego problemu zaproponowano algorytmy heurystyczne i nowe algorytmy matematyczne. Metody matematyczne są przybliżonymi algorytmami, które zostały początkowo zaproponowane do rozwiązywania niektórych problemów optymalizacji kombinatorycznej.

Metody te osadzają dokładne rozwiązanie w podejściach (meta)heurystycznych. Tego typu metody zyskały duże zainteresowanie w literaturze ze względu na ich bardzo dobre wyniki w rozwiązywaniu niektórych trudnych problemów.

Autor rozważa również problem, w którym zintegrowano problem harmonogramowania m-maszynowego i problem wyznaczania trasy pojazdu, a celem jest zminimalizowanie całkowitego opóźnienia. Zaproponowano wprowadzenie bezpośredniego kodowania dla kompletnego rozwiązania oraz algorytmu Tabu dla znalezienia sekwencji produkcji i przejazdów.

Wyniki pokazują, że wyszukiwanie Tabu znacznie poprawia początkowe rozwiązanie podane przez heurystykę Earliest Due Date, gdzie każda podróż obsługuje tylko jedno zadanie na raz.