Stochastic scheduling with variable profile and precedence constraints

被引：5

作者：

Liu, Z ^{[1
]}

Sanlaville, E ^{[1
]}

机构：

[1] UNIV PARIS 06,LAB LITP IBP,F-75252 PARIS 05,FRANCE

来源：

SIAM JOURNAL ON COMPUTING | 1997年 / 26卷 / 01期

关键词：

stochastic scheduling; profile scheduling; makespan; precedence constraint; interval order; in-forest; out-forest; uniform processors; stochastic ordering;

D O I：

10.1137/S0097539791218949

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider the stochastic profile scheduling problem of a partially ordered set of tasks on uniform processors. The set of available processors varies in time. The running times of the tasks are independent random variables with exponential distributions. We obtain a sufficient condition under which a list policy stochastically minimizes the makespan within the class of preemptive policies. This result allows us to obtain a simple optimal policy when the partial order is an interval order, an in-forest, or an out-forest.

引用

页码：173 / 187

页数：15

共 17 条

[1] BRUNO J, 1985, ACTA INFORM, V22, P139, DOI 10.1007/BF00264227
[2] Chandy K. M., 1975, Operating Systems Review, V9, P169, DOI 10.1145/1067629.806534
[3] ON THE OPTIMAL STOCHASTIC SCHEDULING OF OUT-FORESTS
COFFMAN, EG
LIU, Z
[J]. OPERATIONS RESEARCH, 1992, 40 : S67 - S75
[4] SCHEDULING PRECEDENCE GRAPHS OF BOUNDED HEIGHT
DOLEV, D
WARMUTH, MK
[J]. JOURNAL OF ALGORITHMS, 1984, 5 (01) : 48 - 59
[5] SCHEDULING FLAT GRAPHS
DOLEV, D
WARMUTH, M
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (03) : 638 - 657
[6] PROFILE SCHEDULING OF OPPOSING FORESTS AND LEVEL ORDERS
DOLEV, D
WARMUTH, MK
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (04): : 665 - 687
[7] A STOCHASTIC SCHEDULING PROBLEM WITH IN-TTREE PRECEDENCE CONSTRAINTS
FROSTIG, E
[J]. OPERATIONS RESEARCH, 1988, 36 (06) : 937 - 943
[8] SCHEDULING OPPOSING FORESTS
GAREY, MR
JOHNSON, DS
TARJAN, RE
YANNAKAKIS, M
[J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (01): : 72 - 93
[9] OPTIMAL SCHEDULING OF EXPONENTIAL TASKS WITH IN-TREE PRECEDENCE CONSTRAINTS ON 2 PARALLEL PROCESSORS SUBJECT TO FAILURE AND REPAIR
KULKARNI, VG
CHIMENTO, PF
[J]. OPERATIONS RESEARCH, 1992, 40 : S263 - S271
[10] PREEMPTIVE SCHEDULING WITH VARIABLE PROFILE, PRECEDENCE CONSTRAINTS AND DUE-DATES
LIU, Z
SANLAVILLE, E
[J]. DISCRETE APPLIED MATHEMATICS, 1995, 58 (03) : 253 - 280

← 1 2 →