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

A.V. Fishkin, K. Jansen, S.V. Sevastyanov, R.A. Sitters

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    3 Citations (Scopus)
    3 Downloads (Pure)

    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.
    Original languageEnglish
    Title of host publicationAlgorithms - ESA 2005 (Proceedings 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005)
    EditorsS. Leonardi
    Place of PublicationBerlin
    PublisherSpringer
    Pages580-591
    ISBN (Print)3-540-29118-0
    DOIs
    Publication statusPublished - 2005

    Publication series

    NameLecture Notes in Computer Science
    Volume3669
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays'. Together they form a unique fingerprint.

    Cite this