A Caltech Library Service

Scheduling partially ordered tasks with probabilistic execution times

Chandy, K. M. and Reynolds, P. F. (1975) Scheduling partially ordered tasks with probabilistic execution times. ACM SIGOPS Operating Systems Review, 9 (5). pp. 169-177. ISSN 0163-5980.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The objective of this paper is to relate models of multi-tasking in which task times are known or known to be equal to models in which task times are unknown. We study bounds on completion times and the applicability of optimal deterministic schedules to probabilistic models. Level algorithms are shown to be optimal for forest precedence graphs in which task times are independent and identically distributed exponential or Erlang random variables. A time sharing system simulation shows that multi-tasking could reduce response times and that response time is insensitive to multi-tasking scheduling disciplines.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1975 ACM. This research was supported by NSF Grant DCR74-13302.
Funding AgencyGrant Number
Subject Keywords:deterministic models, probabilistic models, multi-tasking, multiprocessing
Issue or Number:5
Classification Code:CR categories: 4.3, 4.32, 4.34, 4.35, 5.3, 5.32, 5.4, 5.42, 8.1
Record Number:CaltechAUTHORS:20190114-104559390
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92251
Deposited By: Tony Diaz
Deposited On:14 Jan 2019 20:21
Last Modified:03 Oct 2019 20:42

Repository Staff Only: item control page