Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-20T18:29:08.587Z Has data issue: false hasContentIssue false
  • English
  • Français

Interchange arguments in stochastic scheduling

Published online by Cambridge University Press:  14 July 2016

Philippe Nain ,
Pantelis Tsoucas  and
Jean Walrand
Philippe Nain*
Affiliation:
INRIA
Pantelis Tsoucas
Affiliation:
University of Maryland
Jean Walrand*
Affiliation:
University of California, Berkeley
*
∗Postal address: INRIA-Sophia Antipolis, Av. E. Hugues, 06565 Valbonne, France.
∗∗∗Postal address: EECS and Electronics Research Laboratory, University of California, Berkeley, CA 94720, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Interchange arguments are applied to establish the optimality of priority list policies in three problems. First, we prove that in a multiclass tandem of two ·/M/1 queues it is always optimal in the second node to serve according to the cµ rule. The result holds more generally if the first node is replaced by a multiclass network consisting of ·/M/1 queues with Bernoulli routing. Next, for scheduling a single server in a multiclass node with feedback, a simplified proof of Klimov's result is given. From it follows the optimality of the index rule among idling policies for general service time distributions, and among pre-emptive policies when the service time distributions are exponential. Lastly, we consider the problem of minimizing the blocking in a communication link with lossy channels and exponential holding times.

Keywords

OPTIMAL POLICIESTANDEM QUEUESMULTICLASS NETWORKS
Type
Research Papers
Information
Journal of Applied Probability , Volume 26 , Issue 4 , December 1989 , pp. 815 - 826
Copyright
Copyright © Applied Probability Trust 1989 

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

Work performed while this author was visiting the Systems Research Center, University of Maryland, College Park, supported by the Office of Naval Research through grant number N00014–84-K-0614.

∗∗

Present address: Computer Science, IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA.

The work of this author was supported in part by the NSF Engineering Research Centers Program NSFD-CDR-88–03012.

References

[1] Anantharam, V., Gopinath, B. and Hajela, D. J. (1988) A generalization of the Erlang formula of traffic engineering. Queueing Systems. 3, 277–288.CrossRefGoogle Scholar
[2] Baras, J. S., Ma, D.-J. and Makowski, A. M. (1985) K competing queues with geometric requirements and linear costs: the µ c rule is always optimal. Syst. Control Lett. 6, 173–180.CrossRefGoogle Scholar
[3] Buyukkoc, C., Varaiya, P. and Walrand, J. (1985) The cµ rule revisited. Adv. Appl. Prob. 17, 237–238.CrossRefGoogle Scholar
[4] Feller, W. (1966) An Introduction to Probability Theory and its Applications II, 2nd edn. Wiley, New York.Google Scholar
[5] Foss, F. G. (1984) Queues with customers of several types. In Limit Theorems and Related Problems, ed. Borovkov, A. A., Optimization Software.Google Scholar
[6] Hirayama, T. (1989) Optimal service assignment in a finite-source queue. IEEE Trans. Autom. Control. 34, 67–75.CrossRefGoogle Scholar
[7] Klimov, G. F. (1974) Time sharing service systems I. Theory Prob. Appl. 19, 532–551.CrossRefGoogle Scholar
[8] Kuang, L. and Tsoucas, P. (1989) Scheduling a server in a network: discounted and average cost. Proc. 28th IEEE CDC, Tampa, Florida. Google Scholar
[9] Lai, T. L. and Ying, Z. (1988) Open bandit problems and optimal scheduling of queueing networks. Adv. Appl. Prob. 20, 447–472.CrossRefGoogle Scholar
[10] Nash, P. and Weber, R. R. (1982) Dominant strategies in dynamic allocation and scheduling problems. In Deterministic and Stochastic Scheduling, ed. Dempster, M. H. A., Reidel, Dordrecht.Google Scholar
[11] Ross, K. W. and Yao, D. D. (1987) Optimal dynamic scheduling in Jackson networks. IEEE Trans. Autom. Control. 34, 47–53.CrossRefGoogle Scholar
[12] Smith, D. R. (1968) Optimal repair of a series system. Operat. Res. 26, 653–662.CrossRefGoogle Scholar
[13] Tsoucas, P. and Walrand, J. (1986) Optimal adaptive server allocation in a network. Syst. Control Lett. 7, 323–327.CrossRefGoogle Scholar
[14] Varaiya, P., Walrand, J. and Buyukkoc, C. (1985) Extensions of the multi-armed bandit problem. IEEE Trans. Autom. Control 30, 426–439.CrossRefGoogle Scholar
[15] Walrand, J. (1988) An Introduction to Queueing Networks. Prentice Hall, Englewood Cliffs. NJ.Google Scholar
[16] Weiss, G. (1984) Branching bandit processes. Industrial and Systems Engineering Report Series No. J-84–17, Georgia Tech. Google Scholar