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

Peter Brucker, Johann L. Hurink, Sigrid Knust

Research output: Book/ReportReportOther research output

8 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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Faculty of Mathematical Sciences
Publication statusPublished - 2001

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Faculty of Mathematical Sciences
No.1566
ISSN (Print)0169-2690

Fingerprint

Preemption
Polynomial Algorithm
Release Dates
Identical Parallel Machines
Total Completion Time
Scheduling Problem
Verify
Unit

Keywords

  • MSC-90B35
  • IR-65753
  • EWI-3386

Cite this

Brucker, P., Hurink, J. L., & Knust, S. (2001). A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \Sigma C_j$. (Memorandum / Department of Applied Mathematics; No. 1566). Enschede: University of Twente, Faculty of Mathematical Sciences.
Brucker, Peter ; Hurink, Johann L. ; Knust, Sigrid. / A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \Sigma C_j$. Enschede : University of Twente, Faculty of Mathematical Sciences, 2001. (Memorandum / Department of Applied Mathematics; 1566).
@book{24f1365b6ac141a4b13fc5bf7d3f43b6,
title = "A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \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.",
keywords = "MSC-90B35, IR-65753, EWI-3386",
author = "Peter Brucker and Hurink, {Johann L.} and Sigrid Knust",
note = "Imported from MEMORANDA",
year = "2001",
language = "English",
series = "Memorandum / Department of Applied Mathematics",
publisher = "University of Twente, Faculty of Mathematical Sciences",
number = "1566",

}

Brucker, P, Hurink, JL & Knust, S 2001, A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \Sigma C_j$. Memorandum / Department of Applied Mathematics, no. 1566, University of Twente, Faculty of Mathematical Sciences, Enschede.

A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \Sigma C_j$. / Brucker, Peter; Hurink, Johann L.; Knust, Sigrid.

Enschede : University of Twente, Faculty of Mathematical Sciences, 2001. (Memorandum / Department of Applied Mathematics; No. 1566).

Research output: Book/ReportReportOther research output

TY - BOOK

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

AU - Brucker, Peter

AU - Hurink, Johann L.

AU - Knust, Sigrid

N1 - Imported from MEMORANDA

PY - 2001

Y1 - 2001

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.

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.

KW - MSC-90B35

KW - IR-65753

KW - EWI-3386

M3 - Report

T3 - Memorandum / Department of Applied Mathematics

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

PB - University of Twente, Faculty of Mathematical Sciences

CY - Enschede

ER -

Brucker P, Hurink JL, Knust S. A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ and $P | p_j = 1,r_j, outtree, pmtn | \Sigma C_j$. Enschede: University of Twente, Faculty of Mathematical Sciences, 2001. (Memorandum / Department of Applied Mathematics; 1566).