Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-09T14:50:58.609Z Has data issue: false hasContentIssue false
  • English
  • Français

Two competing queues with linear costs and geometric service requirements: the μc-rule is often optimal

Published online by Cambridge University Press:  01 July 2016

J. S. Baras ,
A. J. Dorsey  and
A. M. Makowski
J. S. Baras*
Affiliation:
University of Maryland
A. J. Dorsey*
Affiliation:
IBM—Federal Systems Division
A. M. Makowski*
Affiliation:
University of Maryland
*
∗Postal address: Electrical Engineering Department, University of Maryland, College Park, MD 20742, USA.
∗∗ Postal address: IBM—Federal Systems Division, 21 Firstfield Road, Gaithersburg, MD 20748, USA.
∗Postal address: Electrical Engineering Department, University of Maryland, College Park, MD 20742, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

A discrete-time model is presented for a system of two queues competing for the service attention of a single server with infinite buffer capacity. The service requirements are geometrically distributed and independent from customer to customer as well as from the arrivals. The allocation of service attention is governed by feedback policies which are based on past decisions and buffer content histories. The cost of operation per unit time is a linear function of the queue sizes. Under the model assumptions, a fixed prioritization scheme, known as the μc-rule, is shown to be optimal for the expected long-run average criterion and for the expected discounted criterion, over both finite and infinite horizons. Two different approaches are proposed for solving these problems. One is based on the dynamic programming methodology for Markov decision processes, and assumes the arrivals to be i.i.d. The other is valid under no additional assumption on the arrival stream and uses direct comparison arguments. In both cases, the sample path properties of the adopted state-space model are exploited.

Keywords

DISCRETE-TIME MODELSINGLE SERVERINFINITE BUFFERFEEDBACKSAMPLE PATHS
Type
Research Article
Information
Advances in Applied Probability , Volume 17 , Issue 1 , March 1985 , pp. 186 - 209
Copyright
Copyright © Applied Probability Trust 1985 

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 work was supported in part by the Department of Energy under Grant DOE-AC01-78ET 29244, A5 and the National Science Foundation under Grant ECS-82-04451.

References

1. Baras, J. S. and Dorsey, A. J. (1981) Stochastic control of two partially observed competing queues. IEEE Trans. Automatic Control AC-26, 1095–1106.Google Scholar
2. Baras, J. S. and Dorsey, A. J. (1983) Adaptive control of two competing queues. In Proc. 2nd IEEE Annual Joint Conf. Infocom, April 1983, San Diego, CA, 427–435.Google Scholar
3. Baras, J. S., Dorsey, A. J. and Makowski, A. M. (1983) Two competing queues with linear costs: the µc-rule is often optimal. Technical Research Report SRR-83-1, Electrical Engineering Department, University of Maryland, College Park.Google Scholar
4. Baras, J. S., Ma, D.-J. and Makowski, A. M. (1983) Competing queues with geometric service requirements and linear costs: the µc-rule is always optimal. Technical Research Report SRR-83-9, Electrical Engineering Department, University of Maryland, College Park.Google Scholar
5. Bertsekas, D. P. (1976) Dynamic Programming and Stochastic Control. Academic Press, New York.Google Scholar
6. Buyukkoc, C., Varaiya, P. and Walrand, J. (1985) The cµ-rule revisited. Adv. Appl. Prob. 17, 234–235.Google Scholar
7. Cox, D. R. and Smith, W. L. (1961) Queues. Chapman and Hall, London.Google Scholar
8. Dorsey, A. J. (1983) Adaptive Control of a Simple Queueing System. Ph.D. Thesis, Electrical Engineering Department, University of Maryland, College Park.Google Scholar
9. Ephremides, A., Varaiya, P. and Walrand, J. (1980) A simple dynamic routing problem. IEEE Trans. Automatic Control AC-25, 690–693.Google Scholar
10. Hajek, ?. (1982) Optimal control of two interactive service stations. In Proc. 21st IEEE Conf. Decision and Control , December 1982, Orlando, FL, 840–845.Google Scholar
11. Harrison, J.M. (1975) A priority queue with discounted linear costs. Operat. Res. 23, 260–269.Google Scholar
12. Harrison, J. M. (1975) Dynamic scheduling of a multiclass queue: discount optimality. Operat. Res. 23, 270–282.CrossRefGoogle Scholar
13. Jaiswal, N. K. (1968) Priority Queues. Academic Press, New York.Google Scholar
14. Kakalik, J. S. (1969) Optimal dynamic operating policies for a service facility. Technical Report No. 47, Operations Research Center, MIT.Google Scholar
15. Kleinrock, L. (1976) Queueing Systems, Vol. 2: Computer Applications. Wiley, New York.Google Scholar
16. Kushner, H. (1971) Introduction to Stochastic Control. Holt, Rinehart and Winston, New York.Google Scholar
17. Lippman, S. A. (1973) Semi-Markov decision processes with unbounded rewards. Management Sci. 19, 717–731.Google Scholar
18. Meilijson, I. and Yechiali, U. (1977) On optimal right-of-way policies at a single server station when insertion of idle time is permitted. Stoch. Proc. Appl. 5, 25–32.Google Scholar
19. Pinedo, M. (1983) Stochastic scheduling with release dates and due dates. Operat. Res. 31, 559–572.CrossRefGoogle Scholar
20. Reiser, M. (1982) Performance evaluation of data communication systems. Proc. IEEE 70 (12), 171–196.Google Scholar
21. Rosberg, Z., Varaiya, P. and Walrand, J. (1982) Optimal control of service in tandem queues. IEEE Trans. Automatic Control AC-27, 600–610.Google Scholar
22. Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
23. Rykov, V. V. and Lembert, E. Ye. (1967) Optimal dynamic priorities in single-line queueing systems. Engineering Cybernetics 5(1), 21–30.Google Scholar
24. Scholl, M. (1976) Multiplexing Techniques for Data Transmission over Packet-Switched Radio Systems. Ph.D. Thesis, Computer Science Department, UCLA.Google Scholar
25. Shacham, N. (1983) A protocol for preferred access in packet-switching radio networks. IEEE Trans. Communications COM-31, 253–264.Google Scholar
26. Sidi, M. and Segall, A. (1983) Structured priority queueing systems with applications to packet-radio networks. Performance Evaluation 3, 265–275.Google Scholar
27. Varaiya, P., Walrand, J. and Buyukkoc, C. (1985) Extensions of the multi-armed bandit problem. IEEE Trans. Automatic Control. To appear.CrossRefGoogle Scholar