Summary
In this paper we extend the work of Chandy and Reynolds in which they considered the problem of scheduling tasks on two identical processors. The processing times of the tasks are independent, identically distributed exponential random variables. The tasks are subject to in-tree precedence constraints. Chandy and Reynolds have shown that the expected value of the makespan is minimized if and only if the scheduling policy is Highest-Level-First (HLF). We extend their result by showing that a policy maximizes the probability that all tasks finish by some time t≧0 if and only if the policy is HLF. Additionally, we show that a policy maximizes the probability that the sum of the finishing times of all the tasks is less than some value s≧0 if and only if the policy is HLF.
Similar content being viewed by others
References
Brucker, P., Garey, M.R., Johnson, D.S.: Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Lateness. Math. Oper. Res. 2, 275–284 (1977)
Bruno, J.: Deterministic and Stochastic Scheduling Problems with Treelike Precedence Constraints. In: Deterministic and Stochastic Scheduling. Dempster, M.A.H. (J.K. Lenstra, A.H.G. Rinnooy Kan, eds.), pp. 367–374. Boston, USA: D. Reidel Publishing Co. 1982
Chandy, K.M., Reynolds, P.F.: Scheduling Partially Ordered Tasks with Negative Exponentially Distributed Times. Technical Report TR-104, Dep. Comput. Sci. University of Texas at Austin
Davida, G.I., Linton, D.J.: A New Algorithm for the Scheduling of Tree Structured Tasks. Proc. Conf. Inf. Sci. Syst., pp. 543–548 Johns Hopkins University (1976)
Hu, T.C.: Parallel Sequencing and Assembly Line Problems. Oper. Res. 9, 841–848 (1961)
Papadimitrious, C.H.: Games Against Nature. 24th Symp. Found. Comput. Sci., pp. 446–450 (1983)
Author information
Authors and Affiliations
Additional information
This work has been partially supported by a Lady Davis Fellowship at the Technion, Haifa Israel; by the Research Institute for Advanced Computer Science at the NASA Ames Research Center, Moffett Field CA; and by NSF Grant MCS 80-04257.
Rights and permissions
About this article
Cite this article
Bruno, J. On scheduling tasks with exponential service times and in-tree precedence constraints. Acta Informatica 22, 139–148 (1985). https://doi.org/10.1007/BF00264227
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00264227