Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-06T10:37:53.444Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  01 July 2016

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.

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.

Type
General Applied Probability
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, 176202.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, 176194.CrossRefGoogle Scholar
Courcoubetis, C. and Weber, R. (1994). Stability of flexible manufacturing systems. Operat. Res. 42, 947957.CrossRefGoogle Scholar
de Haan, L. and Taconis-Haantjes, E. (1979). On Bahadur's representation of sample quantiles. Ann. Inst. Statist. Math. (Tokyo) A 31, 299308.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, 187197.CrossRefGoogle Scholar
Frenck, J. B. G. and Rinnooy Kan, A. H. G. (1987). The asymptotic optimality of the LPT rule. Math. Operat. Res. 12, 241254.CrossRefGoogle Scholar
Gans, N. F. and van Ryzin, G. J. (1997). Optimal control of a multi-class, flexible queueing system. Operat. Res. 45, 677693.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