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

Brucker, P. and Hurink, J.L. and Knust, S. (2003) A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$ . Mathematical methods of operations research, 56 (3). pp. 407-412. ISSN 1432-2994

PDF
Restricted to UT campus only: Request a copy
99Kb

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].
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63172
Official URL:	http://dx.doi.org/10.1007/s001860200228
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page