(Nowy Sacz School of Business – National-Louis University, 2012) Chung, Chia-Shin; Flynn, James; Walter, Rom; Staliński, Piotr
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.