A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$

P. Brucker; Johann L. Hurink; S. Knust

doi:10.1007/s001860200228

A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$

P. Brucker, Johann L. Hurink, S. Knust

Discrete Mathematics and Mathematical Programming

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

16 Citations (Scopus)

35 Downloads (Pure)

Abstract

A polynomial algorithm is proposed for two scheduling problems for which the complexity status was open. A set of jobs with unit processing times, release dates and outtree precedence relations has to be processed on parallel identical machines such that the total completion time $\sum C_j$ is minimized. It is shown that the problem can be solved in $O(n^2)$ time if no preemption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste and Timkovsky [1].

Original language	English
Pages (from-to)	407-412
Number of pages	6
Journal	Mathematical methods of operations research
Volume	56
Issue number	3
DOIs	https://doi.org/10.1007/s001860200228
Publication status	Published - 2002

Keywords

2023 OA procedure

Access to Document

10.1007/s001860200228

ArticleFinal published version, 99.4 KBLicence: Taverne

Cite this

@article{be24d72232d74aec99a7384c86c77256,

title = "A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$",

abstract = "A polynomial algorithm is proposed for two scheduling problems for which the complexity status was open. A set of jobs with unit processing times, release dates and outtree precedence relations has to be processed on parallel identical machines such that the total completion time $\sum C_j$ is minimized. It is shown that the problem can be solved in $O(n^2)$ time if no preemption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste and Timkovsky [1].",

keywords = "2023 OA procedure",

author = "P. Brucker and Hurink, {Johann L.} and S. Knust",

year = "2002",

doi = "10.1007/s001860200228",

language = "English",

volume = "56",

pages = "407--412",

journal = "Mathematical methods of operations research",

issn = "1432-2994",

publisher = "Physica-Verlag",

number = "3",

}

TY - JOUR

T1 - A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$

AU - Brucker, P.

AU - Hurink, Johann L.

AU - Knust, S.

PY - 2002

Y1 - 2002

N2 - A polynomial algorithm is proposed for two scheduling problems for which the complexity status was open. A set of jobs with unit processing times, release dates and outtree precedence relations has to be processed on parallel identical machines such that the total completion time $\sum C_j$ is minimized. It is shown that the problem can be solved in $O(n^2)$ time if no preemption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste and Timkovsky [1].

AB - A polynomial algorithm is proposed for two scheduling problems for which the complexity status was open. A set of jobs with unit processing times, release dates and outtree precedence relations has to be processed on parallel identical machines such that the total completion time $\sum C_j$ is minimized. It is shown that the problem can be solved in $O(n^2)$ time if no preemption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste and Timkovsky [1].

KW - 2023 OA procedure

U2 - 10.1007/s001860200228

DO - 10.1007/s001860200228

M3 - Article

SN - 1432-2994

VL - 56

SP - 407

EP - 412

JO - Mathematical methods of operations research

JF - Mathematical methods of operations research

IS - 3

ER -

A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$

Abstract

Keywords

Access to Document

Fingerprint

Cite this