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 [J].
COFFMAN, EG ;
LIU, Z .
OPERATIONS RESEARCH, 1992, 40 :S67-S75
[4]   SCHEDULING PRECEDENCE GRAPHS OF BOUNDED HEIGHT [J].
DOLEV, D ;
WARMUTH, MK .
JOURNAL OF ALGORITHMS, 1984, 5 (01) :48-59
[5]   SCHEDULING FLAT GRAPHS [J].
DOLEV, D ;
WARMUTH, M .
SIAM JOURNAL ON COMPUTING, 1985, 14 (03) :638-657
[6]   PROFILE SCHEDULING OF OPPOSING FORESTS AND LEVEL ORDERS [J].
DOLEV, D ;
WARMUTH, MK .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (04) :665-687
[7]   A STOCHASTIC SCHEDULING PROBLEM WITH IN-TTREE PRECEDENCE CONSTRAINTS [J].
FROSTIG, E .
OPERATIONS RESEARCH, 1988, 36 (06) :937-943
[8]   SCHEDULING OPPOSING FORESTS [J].
GAREY, MR ;
JOHNSON, DS ;
TARJAN, RE ;
YANNAKAKIS, M .
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 [J].
KULKARNI, VG ;
CHIMENTO, PF .
OPERATIONS RESEARCH, 1992, 40 :S263-S271
[10]   PREEMPTIVE SCHEDULING WITH VARIABLE PROFILE, PRECEDENCE CONSTRAINTS AND DUE-DATES [J].
LIU, Z ;
SANLAVILLE, E .
DISCRETE APPLIED MATHEMATICS, 1995, 58 (03) :253-280
12