Dr. Chia-Shin Chung, Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115, This email address is being protected from spambots. You need JavaScript enabled to view it..
Dr. James Flynn, Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115, This email address is being protected from spambots. You need JavaScript enabled to view it..
Dr. Walter Rom, Department of Operations and Supply Chain Management, Cleveland State Univesity, Cleveland, Ohio, 44115, This email address is being protected from spambots. You need JavaScript enabled to view it..
Dr. Piotr Staliński, Department of Quantitative Methods in Management, Wyższa Szkoła Biznesu-National Louis University, 33-300 Nowy Sącz, This email address is being protected from spambots. You need JavaScript enabled to view it..

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.

Keywords: genetic algorithm, scheduling, permutation flowshop, tardiness.