Hostname: page-component-7bb8b95d7b-s9k8s Total loading time: 0 Render date: 2024-09-13T08:55:02.557Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime

Published online by Cambridge University Press:  14 July 2016

R. R. Weber ,
P. Varaiya  and
J. Walrand
R. R. Weber*
Affiliation:
University of Cambridge
P. Varaiya*
Affiliation:
University of California, Berkeley
J. Walrand*
Affiliation:
University of California, Berkeley
*
∗Postal address: Department of Engineering, Control and Management Systems Division, Mill Lane, Cambridge, CB2 1RX, UK.
∗∗Postal address: Dept. of Electrical Engineering and Computer Sciences and Electronic Research Laboratory, University of California, Berkeley, CA 94720, USA.
∗∗Postal address: Dept. of Electrical Engineering and Computer Sciences and Electronic Research Laboratory, University of California, Berkeley, CA 94720, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A number of jobs are to be processed using a number of identical machines which operate in parallel. The processing times of the jobs are stochastic, but have known distributions which are stochastically ordered. A reward r(t) is acquired when a job is completed at time t. The function r(t) is assumed to be convex and decreasing in t. It is shown that within the class of non-preemptive scheduling strategies the strategy SEPT maximizes the expected total reward. This strategy is one which whenever a machine becomes available starts processing the remaining job with the shortest expected processing time. In particular, for r(t) = – t, this strategy minimizes the expected flowtime.

Keywords

STOCHASTIC SCHEDULING
Type
Short Communications
Information
Journal of Applied Probability , Volume 23 , Issue 3 , September 1986 , pp. 841 - 847
Copyright
Copyright © Applied Probability Trust 1986 

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

Research supported by the Office of Naval Research Contract N00014-80-C-0507.

References

Conway, R. W., Maxwell, W. L. and Miller, L. W. (1967) The Theory of Scheduling. Addison-Wesley, Reading, MA.Google Scholar
Glazebrook, K. D. (1979) Scheduling tasks with exponential service times on parallel processors. J. Appl. Prob. 16, 685–689.CrossRefGoogle Scholar
Weber, R. R. (1980) Optimal Organization of Multi-server Systems. Ph.D. Dissertation. Cambridge University.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.CrossRefGoogle Scholar
Weiss, G. and Pinedo, M. (1980) Scheduling taks with exponential service times on non-identical processors to minimize various cost functions. J. Appl. Prob. 17, 187–202.CrossRefGoogle Scholar