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

Optimal Scheduling of Multiclass Stochastic Systems

Published online by Cambridge University Press:  27 July 2009

Rhonda Righter
Rhonda Righter
Affiliation:
Department of Decision and Information Sciences, Santa Clara University, Santa Clara, California 95053
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the problem of scheduling multiclass parallel server queues where the cost for each job is a general class-dependent function of the job's completion time and a second random variable. We characterize the structure of the optimal policy under fairly general conditions on the random variables.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 2 , April 1996 , pp. 229 - 241
Copyright
Copyright © Cambridge University Press 1996

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.Baccelli, F., Liu, Z., & Towsley, D. (1993). Extremal scheduling of parallel processing with and without real-time constraints. Journal of the Association of Computing Machinery 40: 1209–1237.CrossRefGoogle Scholar
2.Chang, C.-S. & Yao, D.D. (1993). Rearrangement, majorization and stochastic scheduling. Mathematics of Operations Research 18: 658–684.CrossRefGoogle Scholar
3.Daley, D.J. (1987). Certain optimality properties of the first come first served discipline for G/G/s queues. Stochastic Processes and Their Applications 25: 301–308.CrossRefGoogle Scholar
4.Forst, F.G. (1993). Stochastic sequencing on one machine with earliness and tardiness penalties. Probability in the Engineering and Informational Sciences 7: 291–300.CrossRefGoogle Scholar
5.Foss, S.G. (1980). Approximation of multichannel queueing systems. Siberian Mathematics Journal 21: 851–857.CrossRefGoogle Scholar
6.Foss, S.G. (1981). Comparison of servicing strategies in multichannel queueing systems. Siberian Mathematics Journal 22: 142–147.CrossRefGoogle Scholar
7.Hirayama, T. & Kijima, M. (1989). An extremal property of FIFO discipline in G/IFR/I queues. Advances in Applied Probability 21: 481–484.CrossRefGoogle Scholar
8.Huang, C.-C. & Weiss, G. (1992). Scheduling jobs with stochastic processing times and due dates to minimize total tardiness. Preprint.Google Scholar
9.Kingman, J.F.C. (1970). Inequalities in the theory of queues. Journal of the Royal Statistical Society B 32: 102–110.Google Scholar
10.Liu, Z. & Righter, R. (1995). Optimal scheduling on parallel processors with precedence constraints. Preprint.Google Scholar
11.Liu, Z. & Towsley, D. (1994). Effects of service disciplines in G/G/s queueing systems. Annals of Operations Research 48 (Special Issue on Queueing Networks) (to appear).CrossRefGoogle Scholar
12.Liu, Z. & Towsley, D. (1994). Stochastic scheduling in in-forest networks. Advances in Applied Probability 26: 222–241.CrossRefGoogle Scholar
13.Marshall, A.W. & Olkin, I. (1979). Inequalities: Theory of majorization and its application. New York: Academic Press.Google Scholar
14.Pandelis, D.G. & Teneketzis, D. (1994). Optimal stochastic dynamic scheduling in multi-class queues with tardiness and/or earliness penalties. Probability in the Engineering and Informational Sciences 8: 491–509.CrossRefGoogle Scholar
15.Ross, S.M. (1983). Stochastic processes. New York: J. Wiley & Sons.Google Scholar
16.Shanthikumar, J.G. & Sumita, U. (1987). Convex ordering of sojourn times in single-server queues: Extremal properties of FIFO and LIFO service disciplines. Journal of Applied Probability 24: 737–748.CrossRefGoogle Scholar
17.Towsley, D. & Baccelli, F. (1991). Comparisons of service disciplines in a tandem queueing network with real time constraints. Operations Research Letters 10: 49–55.CrossRefGoogle Scholar
18.Towsley, D. & Panwar, S.S. (1991). Optimality of the stochastic earliest deadline policy for the G/M/c queue serving customers with deadlines. COINS Technical Report 91–61.Google Scholar
19.Vasicek, O.A. (1997). An inequality for the variance of waiting time under a general queueing discipline. Operations Research 25: 879–884.CrossRefGoogle Scholar
20.Wolff, R.W. (1977). An upper bound for multi-channel queues. Journal of Applied Probability 14: 884–888.CrossRefGoogle Scholar
21.Wolff, R.W. (1987). Upper bounds on work in system for multichannel queues. Journal of Applied Probability 24: 547–551.CrossRefGoogle Scholar