@inproceedings{fcf712b79b15455b87706846e116ef5a,
title = "Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays",
abstract = "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.",
author = "A.V. Fishkin and K. Jansen and S.V. Sevastyanov and R.A. Sitters",
year = "2005",
doi = "10.1007/11561071_52",
language = "English",
isbn = "3-540-29118-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "580--591",
editor = "S. Leonardi",
booktitle = "Algorithms - ESA 2005 (Proceedings 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005)",
address = "Germany",
}