Heuristics for flowshop scheduling problems minimizing mean tardiness

Several heuristics are presented for the flowshop scheduling problem with the objective of minimizing mean tardiness. The paper considers the cases in which job sequences on all machines are the same (permutation flowshop) and in which they may be different. For the former case, the various methods that have been devised for minimizing the makespan are modified for the present objective, while the list scheduling algorithm is used for the latter case. These heuristics are tested and compared with each other on randomly-generated test problems.