Chung, Chia-ShinFlynn, JamesWalter, RomStaliński, Piotr2013-06-132013-06-132012Chung, Ch., Flynn, J., Walter, R., Staliński, P., A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems. Journal of Entrepreneurship, Management and Innovation (JEMI), 2012, vol. 8, nr 2 : Contemporary Management Concepts. Ed. by P. Staliński, s. 26-432299-7326http://hdl.handle.net/11199/153The 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.enUznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polskagenetic algorithmschedulingpermutation flowshoptardinessalgorytm genetycznyplanowaniepermutacjaopóźnieniaarticle