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.
Type de document :
Rapport
[Research Report] RR-1156, INRIA. 1990
Liste complète des métadonnées

https://hal.inria.fr/inria-00075402
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:09:04
Dernière modification le : samedi 27 janvier 2018 - 01:31:05
Document(s) archivé(s) le : mardi 12 avril 2011 - 22:57:54

Fichiers

Identifiants

  • HAL Id : inria-00075402, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

88

Téléchargements de fichiers

87