We present hardness and approximation results for the problem of scheduling n independent jobs on m identical parallel machines subject to a migration delay d so as 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. We give initial results supporting a conjecture that there always exists an optimal schedule in which at most m – 1 jobs migrate. Further, we give a O(n) time O(1+1/log2 n)-approximation algorithm for m = 2, and show that there is a polynomial time approximation scheme for arbitrary m.
|Title of host publication||Algorithms - ESA 2005 (Proceedings 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005)|
|Place of Publication||Berlin|
|Publication status||Published - 2005|
|Name||Lecture Notes in Computer Science|