A polynomial algorithm for P vertical bar p(j)=1, r(j), outtree vertical bar Sigma C-j

Autor(en): Brucker, P
Hurink, J
Knust, S 
Stichwörter: complexity results; Mathematics; Mathematics, Applied; Operations Research & Management Science; outtree; parallel machines; scheduling
Erscheinungsdatum: 2003
Herausgeber: PHYSICA-VERLAG GMBH & CO
Journal: MATHEMATICAL METHODS OF OPERATIONS RESEARCH
Volumen: 56
Ausgabe: 3
Startseite: 407
Seitenende: 412
Zusammenfassung: 
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 Sigma C-j is minimized. It is shown that the problem can be solved in O(n(2)) time if no pre-emption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste Timkovsky [1].
ISSN: 14322994
DOI: 10.1007/s001860200228

Show full item record

Page view(s)

3
Last Week
0
Last month
0
checked on Mar 3, 2024

Google ScholarTM

Check

Altmetric