HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

On the optimal stochastic scheduling of out-forests

Abstract : This paper presents new results on the problem of scheduling jobs on K ³ 1 parallel processors so as to minimize stochastically 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 greddy policy is optimal for all K ³ 2.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 6:09:04 PM
Last modification on : Friday, February 4, 2022 - 3:22:03 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 10:57:54 PM


  • HAL Id : inria-00075402, version 1



Edward G. Coffman, Zhen Liu. On the optimal stochastic scheduling of out-forests. [Research Report] RR-1156, INRIA. 1990. ⟨inria-00075402⟩



Record views


Files downloads