Abstract
| Original language | English |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente, Faculty of Mathematical Sciences |
| Publication status | Published - 2001 |
Publication series
| Name | Memorandum / Department of Applied Mathematics |
|---|---|
| Publisher | University of Twente, Faculty of Mathematical Sciences |
| No. | 1566 |
| ISSN (Print) | 0169-2690 |
Fingerprint
Keywords
- MSC-90B35
- IR-65753
- EWI-3386
Cite this
}
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/Report › Report › Other 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 -