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 <>
Submitted on : Wednesday, May 24, 2006 - 6:09:04 PM
Last modification on : Friday, October 2, 2020 - 1:14:01 PM
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