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

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/63172
Official URL:https://doi.org/10.1007/s001860200228
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page