Scheduling jobs with equal processing times and a single server on parallel identical machines

This paper studies the parallel-machine scheduling problem with a single server. There is a set of jobs to be processed on a set of m parallel and identical machines. Prior to processing on a machine, each job has to be loaded by a single server, which takes both the server and the machine a certain time. Preemption is not allowed. We consider the objective of minimizing the sum of jobs' completion times. This problem has been shown to be NP-hard even when all jobs have equal processing times (Brucker et al., 2002). We prove in this paper that the SPT algorithm has a worst case ratio of 1+m−1m+m−1<1.5 for the equal-processing-time problem.