A polynomial algorithm for P|pj=1, rj, outtree|Σ Cj

被引：12

作者：

Brucker, P ^{[1
]}

Hurink, J

Knust, S

机构：

[1] Univ Osnabruck, Fachbereich Math Informat, D-49069 Osnabruck, Germany

[2] Univ Twente, Fac Math Sci, NL-7500 AE Enschede, Netherlands

来源：

MATHEMATICAL METHODS OF OPERATIONS RESEARCH | 2003年 / 56卷 / 03期

关键词：

scheduling; parallel machines; outtree; complexity results;

D O I：

10.1007/s001860200228

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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

引用

页码：407 / 412

页数：6

共 5 条

[1] On preemption redundancy in scheduling unit processing time jobs on two parallel machines
Baptiste, P
Timkovsky, VG
[J]. OPERATIONS RESEARCH LETTERS, 2001, 28 (05) : 205 - 212
[2] Brucker P., Complexity results for scheduling problems
[3] SCHEDULING CHAIN-STRUCTURED TASKS TO MINIMIZE MAKESPAN AND MEAN FLOW TIME
DU, JZ
LEUNG, JYT
YOUNG, GH
[J]. INFORMATION AND COMPUTATION, 1991, 92 (02) : 219 - 236
[4] PARALLEL SEQUENCING AND ASSEMBLY LINE PROBLEMS
HU, TC
[J]. OPERATIONS RESEARCH, 1961, 9 (06) : 841 - 848
[5] SCHEDULING WITH DEADLINES AND LOSS FUNCTIONS
MCNAUGHTON, R
[J]. MANAGEMENT SCIENCE, 1959, 6 (01) : 1 - 12

← 1 →