Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T09:16:23.164Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines

Published online by Cambridge University Press:  27 July 2009

E.G. Coffman Jr ,
M. Hofri  and
G. Weiss
E.G. Coffman Jr
Affiliation:
AT&T Bell Laboratories Murray Hill, New Jersey07974
M. Hofri
Affiliation:
Computer Science Department The Technion Haifa, Israel
G. Weiss
Affiliation:
School of ISyE Georgia Institute of Technology Atlanta, Georgia 30320
Get access Rights & Permissions [Opens in a new window]

Abstract

We analyze the optimal preemptive sequencing of n jobs on two machines to minimize expected total flow time. The running times of the jobs are independent samples from the distribution Pr(X = 1) = p, Pr(X = κ + 1) = 1 − p. We verify that the shortest-expected-remaining-processing-time (SERPT) policy, which is optimal for independent and identically distributed (i.i.d.) running times with a monotone hazard-rate distribution, is not optimal for this distribution. However, we prove that if p ≥ 1/κ, then the number of decisions where SERPT and an optimal policy disagree is bounded by a constant independent of n. For p < 1/k, we prove that the expected number of such decisions has a similar bound. In addition, bounds on the expected increase in flow times under SERPT are derived; these bounds are also independent of n.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 1 , January 1989 , pp. 89 - 116
Copyright
Copyright © Cambridge University Press 1989

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.)

References

Agrawala, A., Coffman, E.G. JrGarey, M.R. & Tripathi, S. (1984). A stochastic optimiation algorithm minimizing expected flow times on uniform processors. IEEE Transactions on Computers C-33: 351–356.CrossRefGoogle Scholar
Bruno, J.L., Downey, P.J. & Frederickson, G.N. (1981). Sequencing tasks with exponential service times to minimize the expected flow time or makespan. Journal of the Association for Computing Machines 28: 100–113.Google Scholar
Chazan, D., Konheim, A.G. & Weiss, B. (1968). A note on time-sharing. Journal of Combinatorial Theory 5: 344–369.Google Scholar
Coffman, E.G. Jr, Flatto, L., Garey, M.R. & Weber, R.R. (1987). Minimizing expected makespans on uniform processor systems. Advances in Applied Probability 19: 177–201.Google Scholar
Feller, W. (1971). An introduction to probability theory and its applications, Vol. 11, 2nd Edidon, New York: John Wiley & Sons.Google Scholar
Gittins, J.C. (1979). Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society Series B 14: 148–177.Google Scholar
Glazebrook, K.D. (1979). Scheduling tasks with exponential service times on parallel processors. Journal of Applied Probability 16: 658–689.Google Scholar
Kämpke, T. (1987). On the optimality of static priority policies in stochastic scheduling on parallel machines. Journal of Applied Probability 24: 430–448.Google Scholar
Meilijson, I. & Weiss, G. (1977). Multiple feedback at a single server station. Stochastic Processes and Their Applications 5: 195–205.CrossRefGoogle Scholar
Papadimitriou, C. (1985). Games against nature. Journal of Computer and System Sciences 31: 288–301CrossRefGoogle Scholar
Ross, S. (1983). Introduction to stochastic dynamic programming. New York: Academic Press.Google Scholar
Sevcik, K.C. (1974). Scheduling for minimum total loss using service time distributions. Journal of the Association for Computing Machines 21: 66–75.CrossRefGoogle Scholar
Weber, R.R. (1982). Scheduling jobs with stochastic processing requirements on parallel machines to minimize makespan or flow time. Journal of Applied Probability 19: 167–182.CrossRefGoogle Scholar
Weber, R.R., Varaiya, P. & Walrand, J. (1986). Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flow time. Journal of Applied Probability 23: 841–847.CrossRefGoogle Scholar
Weiss, G. & Pinedo, M. (1980). Scheduling tasks with exponential service times on nonidentical processors to minimize various cost functions. Journal of Applied Probability 17: 187–202.Google Scholar