On the optimal stochastic scheduling of out-forests

On the optimal stochastic scheduling of out-forests

0.00 Avg rating0 Votes
Article ID: iaor19921722
Country: United States
Volume: 40
Start Page Number: 69
End Page Number: 77
Publication Date: Jan 1992
Journal: Operations Research
Authors: ,
Keywords: networks: scheduling
Abstract:

This paper presents new results on the problem of scheduling jobs on K≥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. The authors define a class of uniform out-forests in which all subtrees are are ordered by an embedding relation. They 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≥2.

Reviews

Required fields are marked *. Your email address will not be published.