Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-31T20:52:03.783Z Has data issue: false hasContentIssue false
  • English
  • Français

On the optimality of static priority policies in stochastic scheduling on parallel machines

Published online by Cambridge University Press:  14 July 2016

Thomas Kämpke
Thomas Kämpke*
Affiliation:
Universität Passau
*
∗Postal address: Lehrstuhl für Informatik und Operations Research, Universität Passau, Postfach 2540, 8390 Passau, W. Germany.
Get access Rights & Permissions [Opens in a new window]

Abstract

n jobs are to be preemptively scheduled for processing on n machines. The machines may have differing speeds and the jobs have processing requirements which are distributed as independent exponential random variables with different means. Holding cost g(U) is incurred per unit time that the set of uncompleted jobs is U and it is desired to minimize the total expected holding cost which is incurred until all jobs are complete. We show that if g satisfies certain simple conditions then the optimal policy is one which takes the jobs in the order 1, 2, ···, n and assigns each uncompleted job in turn to the fastest available machine. In the special case in which the objective is to minimize the expected weighted flowtime, where there is a holding cost of wi while job i is incomplete, the sufficient condition is simply w1 ≧ … ≧ wn and λ1 w1 ≧ … ≧ λn wn.

Keywords

PREEMPTIVE AND ΝΟΝ-PREEMPTIVE SCHEDULINGEXPONENTIAL DISTRIBUTIONMARKOVIAN COST FUNCTIONPRIORITY POLICIESMACHINE IDLENESS
Type
Research Papers
Information
Journal of Applied Probability , Volume 24 , Issue 2 , June 1987 , pp. 430 - 448
Copyright
Copyright © Applied Probability Trust 1987 

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

The paper includes main results from the author's dissertation at the Technical University of Aachen, Germany, May 1985.

References

Bruno, J., Downey, P. and Frederickson, G. N. (1981) Sequencing tasks with exponential service times to minimize the expected flow time or makespan. J. Assoc. Comput. Mach. 28, 100–113.Google Scholar
Glazebrook, K. D. (1979) Scheduling tasks with exponential service times on parallel processors. J. Appl. Prob. 16, 685–689.Google Scholar
Lovasz, L. (1983) Submodular functions and convexity. In Mathematical Programming, The State of the Art, eds. Bachem, A. et al. Springer-Verlag, Berlin, 235–257.Google Scholar
Möhring, R. H. and Radermacher, F. J. (1985) Introduction to stochastic scheduling problems. In Contributions to Operations Research, Proceedings of the Oberwohlfach Conference on Operations Research, eds Neumann, K. and Pallaschke, D., Springer-Verlag, Heidelberg, 72–130.Google Scholar
Möhring, R. H., Radermacher, F. J. and Weiss, G. (1985) Stochastic scheduling problems II: set strategies. Z. Operat. Res. 29, 65–104.Google Scholar
Prasad, V. R. (1982) Letter to the editor. J. Appl. Prob. 19, 741.Google Scholar
Trivedi, K. S. (1982) Probability and Statistics with Reliability, Queuing and Computer Science Applications. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Weber, R. R. (1982) Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flowtime. J. Appl. Prob. 19, 167–182.Google Scholar
Weber, R. R., Varaiya, P. and Walrand, J. (1986) Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. J. Appl. Prob. 23, 841–847.Google Scholar
Weiss, G. and Pinedo, M. (1980) Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Prob. 17, 187–202.CrossRefGoogle Scholar