Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-27T08:13:44.794Z Has data issue: false hasContentIssue false
  • English
  • Français

Scheduling Two-Point Stochastic Jobs to Minimize the Makespan on Two Parallel Machines

Published online by Cambridge University Press:  27 July 2009

Sem Borst ,
John Bruno ,
E. G. Coffman Jr  and
Steven Phillips
Sem Borst
Affiliation:
Bell Labs, Lucent Technologies Murray Hill, New Jersey 07974
John Bruno
Affiliation:
Department of Computer Science, University of California, Santa Barbara, California 93106
E. G. Coffman Jr
Affiliation:
Bell Labs, Lucent Technologies Murray Hill, New Jersey 07974
Steven Phillips
Affiliation:
AT&T Research Murray Hill, New Jersey 07974
Get access Rights & Permissions [Opens in a new window]

Abstract

Simple optimal policies are known for the problem of scheduling jobs to minimize expected makespan on two parallel machines when the job running-time distribution has a monotone hazard rate. But no such policy appears to be known in general. We investigate the general problem by adopting two-point running-time distributions, the simplest discrete distributions not having monotone hazard rates. We derive a policy that gives an explicit, compact solution to this problem and prove its optimality. We also comment briefly on first-order extensions of the model, but each of these seems to be markedly more difficult to analyze.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 11 , Issue 1 , January 1997 , pp. 95 - 105
Copyright
Copyright © Cambridge University Press 1997

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

1.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 Machinery 28: 100–113.Google Scholar
2.Coffman, E.G. Jr (ed.). (1976). Computer and Job-Shop Scheduling Theory. New York: John Wiley and Sons.Google Scholar
3.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.CrossRefGoogle Scholar
4.Coffman, E.G. Jr, Hofri, M., & Weiss, G. (1989). Scheduling stochastic jobs with a two-point distribution on two parallel machines. Probability in the Engineering and Informational Sciences 3: 89–116.CrossRefGoogle Scholar
5.Glazebrook, K.D. (1979). Scheduling tasks with exponential service times on parallel processors. Journal of Applied Probability 16: 658–689.CrossRefGoogle Scholar
6.McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science 6: 1–12.CrossRefGoogle Scholar
7.Papadimitriou, C. (1985). Games against nature. Journal of Computer and System Sciences 31: 288–301.Google Scholar
8.Rothkopf, M.H. (1966). Scheduling independent tasks on parallel processors. Management Science 12: 437–447.Google Scholar
9.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
10.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.Google Scholar
11.Weiss, G. & Pinedo, M. (1980). Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions. Journal of Applied Probability 17: 187–202.CrossRefGoogle Scholar