Single-server parallel-machine scheduling with loading and unloading times
We consider a scheduling problem in which jobs are processed on two identical parallel machines that share a common server that loads and unloads jobs on them. Each job has to be loaded by the server before being processed on one of the machines and unloaded immediately by the server after its processing. The goal is to minimize the makespan. We study non-preemptive variants of the problem where the loading and unloading times are both equal to one time unit. Since the non-preemptive variant of the problem is NP-hard, we apply two classical heuristics, namely list scheduling (LS) and longest processing time (LPT),to tackle the problem. We show that LS and LPT have tight worst-case ratios of 12/7 and 4/3, respectively.
scheduling server makespan worst-case ratio algorithm