A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems
A Genetic Algorithm to Minimize the Total Tardiness for M-Machine Permutation Flowshop Problems
Author(s): James Flynn, Walter Rom, Chia-Shin Chung, Piotr Stalinski Subject(s): Economy
Published by: Fundacja Upowszechniająca Wiedzę i Naukę "Cognitione"
Keywords: genetic algorithm; scheduling; permutation flowshop; tardiness
Summary/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.
Journal: Journal of Entrepreneurship, Management and Innovation
- Issue Year: 8/2012
- Issue No: 2
- Page Range: 26-43
- Page Count: 18
- Language: English
