Preemptive scheduling on two parallel machines with a single server

• We investigate a preemptive parallel machine scheduling with a single server.
• The goal is to minimize the makespan.
• The structures of the optimal schedules are analyzed.
• We propose a 4/3-approximation algorithm for the general case.
• The algorithm is shown to be optimal for two special cases.

This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version.