On the optimal stochastic scheduling of out-forests. (English) Zbl 0764.90042

Coffman, E. G. jun.; Liu, Zhen

Oper. Res. 40, No. 1, Suppl. 1, S67-S75 (1992).

Summary: This paper presents new results on the problem of scheduling jobs on \(K\geq 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\geq 2\).

MSC:

90B35	Deterministic scheduling theory in operations research
93E03	Stochastic systems in control theory (general)

Keywords:

parallel processors; makespan; out-forest precedence constraints; greedy policy