A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems
| dc.contributor.author | Chung, Chia-Shin | |
| dc.contributor.author | Flynn, James | |
| dc.contributor.author | Walter, Rom | |
| dc.contributor.author | Staliński, Piotr | |
| dc.date.accessioned | 2013-06-13T07:48:53Z | |
| dc.date.available | 2013-06-13T07:48:53Z | |
| dc.date.issued | 2012 | |
| dc.description.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. | en_US |
| dc.description.abstract | 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. | |
| dc.identifier.citation | Chung, 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-43 | en_US |
| dc.identifier.issn | 2299-7326 | |
| dc.identifier.uri | http://hdl.handle.net/11199/153 | |
| dc.language.iso | en | en_US |
| dc.publisher | Nowy Sacz School of Business – National-Louis University | en_US |
| dc.rights | Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/pl/ | * |
| dc.subject | genetic algorithm | en_US |
| dc.subject | scheduling | en_US |
| dc.subject | permutation flowshop | en_US |
| dc.subject | tardiness | en_US |
| dc.subject | algorytm genetyczny | en_US |
| dc.subject | planowanie | en_US |
| dc.subject | permutacja | en_US |
| dc.subject | opóźnienia | en_US |
| dc.title | A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems | en_US |
| dc.type | article | en_US |