Scheduling families of jobs with setup times

We review the current state of scheduling theory concerning the processing of several families of jobs on single or parallel facilities, where a setup time may be incurred whenever there is a switch from processing a job in one family to a job in another family. We also consider cases with the group technology assumption that the jobs must be scheduled contingously. Using available results from the literature, we classify the different problems as NP-hard, efficiently solvable or open. We refine some old results and present several new ones. In particular, we show that under the group technology assumption, even with sequence-independent setup times, minimizing the number of late jobs on a single machine is NP-hard. We investigate the complexity of single machine scheduling with interfamily setup times, when we seek to minimize the maximal cost, where the cost for each job is a nondecreasing function of its completion time. We also prove that, when scheduling on parallel machines under the group technology assumption with sequence-independent setup times, minimizing total completion times is NP-hard unless all families contain the same number of jobs.