The m-machine, n-job, permutation flowshop problem with the total tardiness objective
is a common scheduling problem, known to be NP-hard. Branch and bound, the usual
approach to finding an optimal solution, experiences difficulty when n exceeds 20.
Here, we develop a genetic algorithm, GA, which can handle problems with larger n.
We also undertake a numerical study comparing GA with an optimal branch and bound
algorithm, and various heuristic algorithms including the well known NEH algorithm and
a local search heuristic LH. Extensive computational experiments indicate that LH is an
effective heuristic and GA can produce noticeable improvements over LH.
Permutacyjny problem przepływowy (ang. permutation flowshop problem) z
m
maszynami
i n zadaniami oraz minimalizacją sumy opóźnień jest znanym zagadnieniem z zakresu
szeregowania zadań. Zagadnienie to należy do kategorii NP-trudnych problemów
optymalizacji kombinatorycznej. Metoda podziału i ograniczeń (ang. branch and bound),
popularne podejście do rozwiązania problemu, doświadcza trudności (biorąc pod
uwagę czas potrzebny dla znalezienia rozwiązania optymalnego) gdy n przekracza 20.
W
niniejszej pracy, proponujemy algorytm genetyczny GA dla rozwiązywania zagadnienia
dla dużych wartości n. Przytaczamy wyniki obszernego studium obliczeniowego, które
porównuje fukcjonowanie algorytmu GA z metodą podziału i ograniczeń oraz metodami
heurystycznymi - znanym algorytmem NEH i
heurystyką lokalnego przeszukiwania
LH. Rezultaty obliczeniowe wskazują, że metoda LH jest wydajnym algorytmem
heurystycznym i że metoda GA oferuje możliwość poprawy wyników w porównaniu
z
algorytmem LH.