On minimizing the sum of k tardiness

G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)


    We consider the problem of minimizing the sum of the k maximum tardiness of n jobs on a single machine without preemption. The problem is shown to be polynomially solvable for any fixed value k. Moreover, we present an O(n log n) algorithm for the case k = 2.
    Original languageEnglish
    Pages (from-to)253-256
    JournalInformation Processing Letters
    Issue number5
    Publication statusPublished - 1991


    Dive into the research topics of 'On minimizing the sum of k tardiness'. Together they form a unique fingerprint.

    Cite this