ON THE OPTIMAL STOCHASTIC SCHEDULING OF OUT-FORESTS
成果类型：
Article
署名作者：
COFFMAN, EG; LIU, Z
署名单位：
AT&T; Nokia Corporation; Nokia Bell Labs
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.1.S67
发表日期：
1992
页码：
S67-S75
关键词：
摘要：
This paper presents new results on the problem of scheduling jobs on K greater-than-or-equal-to 1 parallel processors to stochastically minimize the makespan. The jobs are subject to out-forest precedence constraints, i.e., each job has at most one immediate predecessor, and job running times are independent samples from a given exponential distribution. We define a class of uniform out-forests in which all subtrees are ordered by an embedding relation. We prove that an intuitive greedy policy is optimal for K = 2, and that if out-forests satisfy an additional, uniform root-embedding constraint, then the greedy policy is optimal for all K greater-than-or-equal-to 2.