Minimizing total tardiness for scheduling identical parallel machines with family setups

•It is shown how to improve an existing tabu search for the problem.•New tabu searches are presented.•Two genetic algorithms are presented.•The results show the genetic algorithms are most effective.

This paper presents several procedures for scheduling identical parallel machines with family setups when the objective is to minimize total tardiness. These procedures are tested on several problem sets with varying numbers of families, jobs and machines, varying setup time distributions and various levels of due date tightness and variability. The results show that genetic algorithms are the most effective algorithms for the problem.