Running summarizing tools on a new article
Check the paper below, then start its synthesis.
Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays
Sergey V. Sevastyanov (Russian Academy of Sciences, Novosibirsk State University), René A. Sitters (Vrije Universiteit Amsterdam), Aleksei V. Fishkin (Siemens (Germany))
Abstract: 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.