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

Thumbnail Image
JEMI_Vol_8_Issue_2_2012_Article_2.pdf (385.68 KB)
Authors
Chung, Chia-Shin
Flynn, James
Rom, Walter
Staliński, Piotr
Date
2012
Journal Title
Journal ISSN
Volume Title
Publisher
Wyższa Szkoła Biznesu - National Louis Univeristy
License
Creative Commons License
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Poland License
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.
Description
Keywords
genetic algorithm    scheduling    permutation flowshop    tardiness
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
URI
https://depot.ceon.pl/handle/123456789/14247
Belongs to collection
Artykuły / Articles