Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-29T07:54:43.169Z Has data issue: false hasContentIssue false

Applying the method of phases in the optimization of queuing systems

Published online by Cambridge University Press:  01 July 2016

Hans-Joachim Langen*
Affiliation:
Universität Bonn
*
Present address: Graf-Haeseler-Str. 11, 4600 Dortmund 1, W. Germany

Abstract

A new device in the optimization of queuing systems is introduced by using the method of phases. Non-exponential queues under control are considered with respect to the expected discounted reward criterion. For models with hyper-Erlang distributions equivalent phase-type systems are established. Approximation results for Markov decision models allow the extension to the case of general distribution functions. The approach is demonstrated by finding the form of an optimal policy for the GI/M/c queue with customer admission and batch arrival as well as for the GI/M/1 queue with interarrival time control.

Type
Research Article
Copyright
Copyright © Applied Probability Trust 1982 

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 by the SFB 72 of the Deutsche Forschungsgemeinschaft.

References

1. Cinlar, E. (1974) Periodicity in Markov renewal theory. Adv. Appl. Prob. 6, 6178.Google Scholar
2. Harrison, J. M. (1975) Dynamic scheduling of a multiclass queue: discount optimality. Operat. Res. 23, 270282.CrossRefGoogle Scholar
3. Johansen, S. G. and Stidham, S. (1980) Optimal control of arrivals to a stochastic input–output system. Adv. Appl. Prob. 12, 972999.CrossRefGoogle Scholar
4. Langen, H. J. (1981) Convergence of dynamic programming models. Math. Operat. Res. 6.CrossRefGoogle Scholar
5. Lippman, S. A. (1975) Applying a new device in the optimization of queuing systems. Operat. Res. 23, 687710.Google Scholar
6. Lippman, S. A. and Stidham, S. (1977) Individual versus social optimization in exponential congestion systems. Operat. Res. 25, 233247.Google Scholar
7. Neuts, M. F. (1975) Computational uses of the method of phases in the theory of queues. Computers Math. Appl. 1, 151166.Google Scholar
8. Schäl, M. (1970) Markov renewal processes with auxiliary paths. Ann. Math. Statist. 41, 16041623.CrossRefGoogle Scholar
9. Schäl, M. (1975) Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal. Z. Wahrscheinlichkeitsth. 32, 179196.Google Scholar
10. Schassberger, R. (1973) Warteschlangen. Springer-Verlag, New York.Google Scholar
11. Schellhaas, H. (1979) Semi-Regenerative processes with unbounded rewards. Math. Operat. Res. 4, 7078.Google Scholar
12. Serfozo, K. L. (1979) An equivalence between continuous and discrete time Markov decision processes. Operat. Res. 27, 616620.CrossRefGoogle Scholar
13. Stidham, S. (1978) Socially and individually optimal control of arrivals to a GI/M/1 queue. Management Sci. 24, 15981610.CrossRefGoogle Scholar
14. Tijms, H. C. (1978) An algorithm for average cost denumerable state semi-Markov decision problems with applications to controlled production and inventory systems. In Recent Developments in Markov Decision Theory, ed. White, D. J. Google Scholar
15. Topkis, D. M. (1978) Minimizing a submodular function on a lattice. Operat. Res. 26, 305321.Google Scholar