On minimizing the sum of k tardiness

G.J. Woeginger

doi:10.1016/0020-0190(91)90067-R

On minimizing the sum of k tardiness

G.J. Woeginger

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	253-256
Journal	Information Processing Letters
Volume	38
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(91)90067-R
Publication status	Published - 1991

Access to Document

10.1016/0020-0190(91)90067-R

Cite this

@article{774a94f7fbdc47589ea481d80f9740d6,

title = "On minimizing the sum of k tardiness",

abstract = "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.",

author = "G.J. Woeginger",

year = "1991",

doi = "10.1016/0020-0190(91)90067-R",

language = "English",

volume = "38",

pages = "253--256",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On minimizing the sum of k tardiness

AU - Woeginger, G.J.

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

U2 - 10.1016/0020-0190(91)90067-R

DO - 10.1016/0020-0190(91)90067-R

M3 - Article

SN - 0020-0190

VL - 38

SP - 253

EP - 256

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On minimizing the sum of k tardiness

Abstract

Access to Document

Fingerprint

Cite this