Scheduling parallel machines with a single server: some solvable cases andheuristics

This paper considers the problem of scheduling two identical parallel machi nes with a single server which is required to carry out the job setups. Job processing can then be carried out in parallel. The objective is to minimi se maximum completion time, that is makespan. The problem is NP-complete in the strong sense. An integer program formulation is presented. Two special cases: short processing times and equal length jobs are solved. Two simple but effective O(n log n) heuristics for the general case are given and the ir performance is tested.