### 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$*. (Memorandum / Department of Applied Mathematics; No. 1566). Enschede: University of Twente, Faculty of Mathematical Sciences.

}

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

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 -