SCHEDULING FAMILIES OF JOBS WITH SETUP TIMES

We review the current state of scheduling theory concerning the proces sing of several families of jobs on single or parallel facilities, whe re a setup time may be incurred whenever there is a switch from proces sing 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 sched uled contiguously. Using available results from the literature, we cla ssify the different problems as NP-hard, efficiently solvable or open. We refine some old results and present several new ones. In particula r, we show that under the group technology assumption, even with seque nce-independent setup times, minimizing the number of late jobs on a s ingle machine is NP-hard. We investigate the complexity of single mach ine scheduling with interfamily setup times, when we seek to minimize the maximal cost, where the cost for each job is a nondecreasing funct ion of its completion time. We also prove that, when scheduling on par allel machines under the group technology assumption with sequence-ind ependent setup times, minimizing total completion times is NP-hard unl ess all families contain the same number of jobs.