Skip to main content
SpringerLink
Log in

Multiserver Stochastic Scheduling

  • Conference paper
Deterministic and Stochastic Scheduling

Part of the book series: NATO Advanced Study Institutes Series ((ASIC,volume 84))

Abstract

m Parallel machines are available for the processing of n jobs. The jobs require random amounts of processing. When processing times are exponentially distributed, SEPT (shortest expected processing time first) minimizes the flowtime, LEPT (longest expected processing time first) minimizes the makespan and maximizes the time to first machine idleness. For m = 2, various other problems can be optimized by different rules. Optimality of preemptive SEPT and LEPT also holds when processing times are drawn from a common MHR (monotone hazard rate) distribution.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. P.C. Bagga (1970) n-Job, 2-machine sequencing problem with stochastic service times. Opsearch 7,184–197.

    MathSciNet  Google Scholar 

  2. R.E. Barlow, F. Proschan (1975) Statistical Theory of Reliability and Life Testing: Probability Models, Holt, Rinehart and Winston, New York.

    Google Scholar 

  3. M. Brown, H. Solomon (1973) Optimal issuing policies under stochastic field lives. J. Appl. Probab. 10, 761–768.

    Article  MathSciNet  MATH  Google Scholar 

  4. J. Bruno (1976) Sequencing tasks with exponential service times on parallel machines. Technical Report, Department of Computer Science, Pennsylvania State University.

    Google Scholar 

  5. J. Bruno, P. Downey (1977) Sequencing tasks with exponential service times on two machines. Technical Report, Department of Electrical Engineering and Computer Science, University of California, Santa Barbara.

    Google Scholar 

  6. J. Bruno, P. Downey, G.N. Frederickson (1981) Sequencing tasks with exponential service times to minimize the expected flowtime or makespan. J. Assoc. Comput. Mach. 28, 100–113.

    MathSciNet  MATH  Google Scholar 

  7. V.YA. Burdyuk (1969) The stochastic problem of two machines. Cybernetics 5, 651–661 (translated from Russian).

    Article  Google Scholar 

  8. D.R. Cox (1959) A renewal problem with bulk ordering of components. J. Roy. Statist. Soc. Ser. B 21, 180–189.

    MathSciNet  MATH  Google Scholar 

  9. T.B. Crabill, D. Gross, M.J. Magazine (1977) A classified bibliography of research on optimal design and control of queues. Oper. Res. 25, 219–232.

    Article  MathSciNet  Google Scholar 

  10. A.A. Cunningham, S.K. Dutta (1973) Scheduling jobs with exponentially distributed processing times on two machines of a flow shop. Naval Res. Logist. Quart. 16, 69–81.

    Article  MathSciNet  Google Scholar 

  11. G.N. Frederickson (1978) Sequencing tasks with exponential service times to minimize the expected flow time or makespan. Technical Report, Department of Computer Science, Pennsylvania State University.

    Google Scholar 

  12. J.C. Gittins (1981) Multiserver scheduling of jobs with increasing completion rates. J. Appl. Probab. 18, 321–324.

    Article  MathSciNet  MATH  Google Scholar 

  13. K.D. Glazebrook (1979) Scheduling tasks with exponential service times on parallel processors. J. Appl. Probab. 16, 685–689.

    Article  MathSciNet  MATH  Google Scholar 

  14. K.D. Glazebrook, P. Nash (1976) On multiserver stochastic scheduling. J. Roy. Statist. Soc. Ser. B 38, 67–72.

    MathSciNet  MATH  Google Scholar 

  15. S.M. Johnson (1954) Optimal two-and three-stage production schedules with setup times included. Naval Res. Logist. Quart. 1, 61–68.

    Article  Google Scholar 

  16. E.L. Lehman (1959) Testing Statistical Hypotheses, Wiley, New York.

    Google Scholar 

  17. M. Pinedo (1980) Scheduling spares with exponential lifetimes in a two component parallel system. J. Appl. Probab. 17, 1025–1032.

    Article  MathSciNet  MATH  Google Scholar 

  18. M. Pinedo (1980) Minimizing the makespan in a stochastic flow-shop. Oper. Res., to appear.

    Google Scholar 

  19. M. Pinedo (1980) Minimizing makespan with bimodal processing time distributions. Management Sci., to appear.

    Google Scholar 

  20. M. Pinedo (1980) A note on the two machine job shop with exponential processing times. Naval Res. Logist. Quart., to appear.

    Google Scholar 

  21. M. Pinedo, S.M. Ross (1981) Minimizing expected makespan in stochastic open shops. J. Appl. Probab., to appear.

    Google Scholar 

  22. M. Pinedo, G. Weiss (1979) Scheduling of stochastic tasks on two parallel processors. Naval Res. Logist. Quart. 26, 527–535.

    Article  MathSciNet  MATH  Google Scholar 

  23. S.M. Ross (1970) Applied Probability Models with Optimization Applications, Holden Day, San Francisco.

    MATH  Google Scholar 

  24. M.H. Rothkopf (1966) Scheduling with random service times. Management Sci. 12, 707–713.

    Article  MathSciNet  Google Scholar 

  25. R. Strauch (1966) Negative dynamic programming. Ann. Math. Statist. 37, 871–890.

    Article  MathSciNet  MATH  Google Scholar 

  26. S.V. Tembe, R.W. Wolff (1974) The optimal order of service in tandem queues. Oper. Res. 22, 824-832.

    Google Scholar 

  27. L. Van Der Heyden (1979) A note on scheduling jobs with exponential processing times on identical processors so as to minimize makespan. Math. Oper. Res., to appear.

    Google Scholar 

  28. R.R. Weber (1978) On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15, 406–413.

    Article  MATH  Google Scholar 

  29. R.R. Weber (1979) Optimal organization of multiserver systems. Ph.D. thesis, University of Cambridge.

    Google Scholar 

  30. R.R. Weber, P. Nash (1979) An optimal strategy in multiserver stochastic scheduling. J. Roy. Statist. Soc. Ser. B 40, 322–327.

    MathSciNet  Google Scholar 

  31. G. Weiss (1977) A 2-machine n job scheduling problem. Technical Report, Department of Statistics, Tel-Aviv University.

    Google Scholar 

  32. G. Weiss (1981) Scheduling spares with exponential lifetimes in a two-component parallel system. Technical Report, Department of Statistics, Tel-Aviv University.

    Google Scholar 

  33. G. Weiss, M. Pinedo (1980) Scheduling tasks with exponential service times on non identical processors to minimize various cost functions. J. Appl. Probab. 17, 187–202.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Tel-Aviv University, Israel

    Gideon Weiss

Authors
  1. Gideon Weiss
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, Dalhousie University, Halifax, Nova Scotia, Canada

    M. A. H. Dempster

  2. Balliol College, Oxford, England

    M. A. H. Dempster

  3. Mathematisch Centrum, P.O. Box 4079, 1009 AB, Amsterdam, The Netherlands

    J. K. Lenstra

  4. Econometric Institute H2-11, Erasmus University, P.O. Box 1738, 3000 DR, Rotterdam, The Netherlands

    A. H. G. Rinnooy Kan

Rights and permissions

Reprints and permissions

Copyright information

© 1982 D. Reidel Publishing Company

About this paper

Cite this paper

Weiss, G. (1982). Multiserver Stochastic Scheduling. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series, vol 84. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-7801-0_8

Download citation

  • DOI: https://doi.org/10.1007/978-94-009-7801-0_8

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-009-7803-4

  • Online ISBN: 978-94-009-7801-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation