Single machine group scheduling with family setups to minimize total tardiness

This paper considers the single machine scheduling problem with independent family (group) setup times where jobs in each family are processed together. A sequence-independent setup is required to process a job from a different family. The objective is to minimize total tardiness. A mixed-integer linear programming model capable of solving small-sized problems is described. In view of the NP-hard nature of the problem, two-phase heuristics including simulated annealing algorithms are proposed to find optimal or near-optimal schedules. Empirical results show that the proposed heuristic algorithms are quite effective in minimizing total tardiness for a single machine group scheduling problem with family setup times.