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

• Authors: Chia-Shin Chung , James Flynn , Walter Rom , Piotr Staliński
• Languages of publication: EN

Abstracts

EN

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.

Keywords

EN

genetic algorithm; scheduling; permutation flowshop; tardiness

• Publisher: Fundacja Upowszechniająca Wiedze i Naukę "Cognitione" / Wyższa Szkoła Biznesu – National-Louis University
• Journal: Journal of Entrepreneurship, Management and Innovation
• Year: 2012
• Volume: 8
• Issue: 2
• Pages: 26-43

Contributors

author

Chia-Shin Chung

• Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115

author

James Flynn

• Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115

author

Walter Rom

• Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115

author

Piotr Staliński

• Department of Quantitative Methods in Management, Wyższa Szkoła Biznesu-National Louis University, 33-300 Nowy Sącz