Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays

We present hardness and approximation results for the problem of preemptive scheduling of $n$ independent jobs on $m$ identical parallel machines subject to a migration delay $d$ with the objective to minimize the makespan. We give a sharp threshold on the value of $d$ for which the complexity of the problem changes from polynomial time solvable to $NP$-hard. Next, we give initial results supporting a conjecture that there always exists an optimal schedule with at most $m-1$ job migrations. Finally, we provide a $O(n)$ time $(1+1/\log_2n)$-approximation algorithm for $m=2$.

Presented by the member of Editorial Board: A. A. Lazarev