A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems

Abstract

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.