A polynomial-time approximation scheme for maximizing the minimum machine completion time

G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    157 Citations (Scopus)
    3 Downloads (Pure)

    Abstract

    We consider the problem of assigning a set of n jobs to a system of m identical parallel machines so as to maximize the earliest machine completion time (without using idle times). This problem has applications in the sequencing of maintenance actions for modular gas turbine aircraft engines. Up to now, only approximation algorithms were known whose worst case ratio was bounded strictly away from one. In this note, we derive the first polynomial-time approximation scheme for this problem. The time complexity of our algorithms is O(cnlogm), where c is a constant that depends on the desired precision .
    Original languageEnglish
    Pages (from-to)149-154
    Number of pages6
    JournalOperations Research Letters
    Volume20
    Issue number4
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'A polynomial-time approximation scheme for maximizing the minimum machine completion time'. Together they form a unique fingerprint.

    Cite this