Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-15T21:13:57.943Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions

Published online by Cambridge University Press:  14 July 2016

Gideon Weiss  and
Michael Pinedo
Gideon Weiss*
Affiliation:
Tel-Aviv University
Michael Pinedo*
Affiliation:
Instituto Venezolano de Investigaciones Cientificas
*
∗Postal address: Department of Statistics, Tel-Aviv University, Ramat-Aviv, Tel-Aviv, Israel.
∗∗Postal address: Instituto Venezolano de Investigaciones Cientificas (IVIC), Apartado 1827, Caracas 101, Venezuela.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider preemptive scheduling of N tasks on m processors; processors have different speeds, tasks require amounts of work which are exponentially distributed, with different parameters. The policies of assigning at every moment the task with shortest (longest) expected processing time among those not yet completed to the fastest processor available, second shortest (longest) to the second fastest etc., are examined, and shown to minimize expected values of various cost functions. As special cases we obtain policies which minimize expected flowtime, expected makespan and expected lifetime of a series system with m component locations and N spares.

Keywords

EXPONENTIAL DISTRIBUTIONDYNAMIC PROGRAMMINGMULTIPROCESSORSSTOCHASTIC PREEMPTIVE SCHEDULINGRELIABILITY OF SERIES SYSTEM WITH SPARES
Type
Research Papers
Information
Journal of Applied Probability , Volume 17 , Issue 1 , March 1980 , pp. 187 - 202
Copyright
Copyright © Applied Probability Trust 1980 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This work was done while the authors were at the University of California, Berkeley, in the Department of Statistics and the Department of Industrial Engineering and Operations Research, respectively.

References

[1] Bruno, J. and Downey, P. (1977) Sequencing tasks with exponential service times on two machines. Technical Report, Department of Computer Sciences, University of California, Santa Barbara.Google Scholar
[2] Frederickson, G. N. (1978) Sequencing tasks with exponential service times to minimize the expected flow time or makespan. Department of Computer Sciences, Pennsylvania State University Report CS–78–07.Google Scholar
[3] Pinedo, M. and Weiss, G. (1979) Scheduling stochastic tasks on two parallel processors. Naval. Res. Logist. Quart. 26, 527–535.Google Scholar
[4] Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
[5] Strauch, R. (1966) Negative dynamic programming. Ann. Math. Statist. 37, 871–890.CrossRefGoogle Scholar
[6] Van Der Heyden, L. (1979) A note on scheduling jobs with exponential processing times on identical processors so as to minimize makespan. Math. Operat. Res. Google Scholar
[7] Weber, R. R. (1979) Scheduling stochastic jobs on parallel machines.Google Scholar