On the Optimal Stochastic Scheduling of Out-Forests

E. G. Coffman and Zhen Liu
Additional contact information
E. G. Coffman: AT&T Bell Laboratories, Murray Hill, New Jersey
Zhen Liu: INRIA, Valbonne, France

Operations Research, 1992, vol. 40, issue 1-supplement-1, S67-S75

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. 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 ≥ 2.

Keywords: network/graphs: tree algorithms; production/scheduling: stochastic sequencing (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S67 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s67-s75

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().