An optimal algorithm for preemptive on-line scheduling

B. Chen, A. Vliet, van, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    61 Citations (Scopus)

    Abstract

    We investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. We derive an approximation algorithm with worst-case guarantee mm/(mm - (m - 1)m) for every m 2, which increasingly tends to e/(e - 1) ˜ 1.58 as m ¿ 8. Moreover, we prove that for no m 2 there does exist any approximation algorithm with a better worst-case guarantee.
    Original languageEnglish
    Pages (from-to)127-131
    Number of pages5
    JournalOperations Research Letters
    Volume18
    Issue number3
    DOIs
    Publication statusPublished - 1995

    Fingerprint

    Dive into the research topics of 'An optimal algorithm for preemptive on-line scheduling'. Together they form a unique fingerprint.

    Cite this