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

Share/Save/Bookmark

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
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:
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

 

Repository Staff Only: item control page