Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-27T23:13:41.773Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal dynamic scheduling of a general class of parallel-processing queueing systems

Part of: Operations research and management science Computer system organization Special processes Stochastic systems and control

Published online by Cambridge University Press:  01 July 2016

Noah Gans  and
Garrett van Ryzin
Noah Gans*
Affiliation:
University of Pennsylvania
Garrett van Ryzin*
Affiliation:
Columbia University
*
∗ Postal address: OPIM Department, The Wharton School, University of Pennsylvania, Philadelphia PA 19104-6366, USA.
∗∗ Postal address: Graduate School of Business, Columbia University, New York, NY 10027, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we develop policies for scheduling dynamically arriving jobs to a broad class of parallel-processing queueing systems. We show that in heavy traffic the policies asymptotically minimize a measure of the expected system backlog, which we call system work. Our results yield succinct, closed-form expressions for optimal system work in heavy traffic.

Keywords

Parallel processor queueing systemsdynamic nonpreemptive schedulingoptimal stochastic control

MSC classification

Primary: 60K25: Queueing theory
Secondary: 68M20: Performance evaluation; queueing; scheduling 90B22: Queues and service 90B35: Scheduling theory, deterministic 93E20: Optimal stochastic control
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 30 , Issue 4 , December 1998 , pp. 1130 - 1156
Copyright
Copyright © Applied Probability Trust 1998 

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

This is a revision of a working paper dated 17 November 1995.

References

Bambos, N. and Walrand, J. (1993). Scheduling and stability aspects of a general class of parallel processing systems. Adv. Appl. Prob. 25, 176–202.CrossRefGoogle Scholar
Bazaraa, M. S., Jarvis, J. and Sherali, H. D. (1990). Linear Programming and Network Flows. Wiley, New York.Google Scholar
Courcoubetis, C. and Rothblum, U. G. (1991). On optimal packing of randomly arriving objects. Math. Operat. Res. 16, 176–194.CrossRefGoogle Scholar
Courcoubetis, C. and Weber, R. (1994). Stability of flexible manufacturing systems. Operat. Res. 42, 947–957.CrossRefGoogle Scholar
de Haan, L. and Taconis-Haantjes, E. (1979). On Bahadur's representation of sample quantiles. Ann. Inst. Statist. Math. (Tokyo) A 31, 299–308.CrossRefGoogle Scholar
Feller, W. (1957). An Introduction to Probability Theory and Its Applications. Wiley, New York.Google Scholar
Frenck, J. B. G. and Rinnooy Kan, A. H. G. (1986). The rate of convergence to optimality of the LPT rule. Discrete Appl. Math. 14, 187–197.CrossRefGoogle Scholar
Frenck, J. B. G. and Rinnooy Kan, A. H. G. (1987). The asymptotic optimality of the LPT rule. Math. Operat. Res. 12, 241–254.CrossRefGoogle Scholar
Gans, N. F. and van Ryzin, G. J. (1997). Optimal control of a multi-class, flexible queueing system. Operat. Res. 45, 677–693.CrossRefGoogle Scholar
Karlin, S. and Taylor, H. T. (1981). A Second Course in Stochastic Processes. Academic Press, New York.Google Scholar
Karp, R. M. and Karmarker, N. (1982). The differencing method of set partitioning. UCB/CSD Report 82/113, Computer Science Division (EECS), Univeristy of California, Berkeley.Google Scholar
Pinedo, M. (1995). Scheduling: Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
Wolff, R. W. (1989). Stochastic Modeling and the Theory of Queues. Prentice Hall, Englewood Cliffs, NJ.Google Scholar