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/log2 n)-approximation algorithm for m = 2