The exact LPT-bound for maximizing the minimum completion time

J. Csirik, H. Kellerer, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    66 Citations (Scopus)
    8 Downloads (Pure)

    Abstract

    We consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst case ratio at most 3/4. In this note we show that the exact worst case ratio of LPT is (3m - 1)/(4m - 2).
    Original languageEnglish
    Pages (from-to)281-287
    Number of pages7
    JournalOperations Research Letters
    Volume11
    Issue number5
    DOIs
    Publication statusPublished - 1992

    Fingerprint Dive into the research topics of 'The exact LPT-bound for maximizing the minimum completion time'. Together they form a unique fingerprint.

    Cite this