Abstract
Motivated by certain situations in manufacturing systems and communication networks, we look into the problem of maximizing the profit in a queueing system with linear reward and cost structure and having a choice of selecting the streams of Poisson arrivals according to an independent Markov chain. We view the system as a MMPP/GI/1 queue and seek to maximize the profits by optimally choosing the stationary probabilities of the modulating Markov chain. We consider two formulations of the optimization problem. The first one (which we call the PUT problem) seeks to maximize the profit per unit time whereas the second one considers the maximization of the profit per accepted customer (the PAC problem). In each of these formulations, we explore three separate problems. In the first one, the constraints come from bounding the utilization of an infinite capacity server; in the second one the constraints arise from bounding the mean queue length of the same queue; and in the third one the finite capacity of the buffer reflect as a set of constraints. In the problems bounding the utilization factor of the queue, the solutions are given by essentially linear programs, while the problems with mean queue length constraints are linear programs if the service is exponentially distributed. The problems modeling the finite capacity queue are non-convex programs for which global maxima can be found. There is a rich relationship between the solutions of the PUT and PAC problems. In particular, the PUT solutions always make the server work at a utilization factor that is no less than that of the PAC solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Asmussen, Ladder heights and the Markov-modulated M / G/ 1 queue, Stochastic Process. Appl. 37 (1991) 313–326.
M.S. Bazaraa, H.D. Sherali and C.M. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd ed. (Wiley, New York, 1993).
E.A. van Doorn and G.J.K. Regterschot, Conditional PASTA, Oper. Res. Lett. 7(5) (October 1988) 229–232.
E.A. Fienberg, A generalization of 'Expectation equals reciprocal of intensity' to non-stationary exponential distributions, J. Appl. Probab. 31 (1994) 262–267.
W. Fischer and K. Meier-Hellstern, The Markov-modulated Poisson process (MMPP) cookbook, Performance Evaluation 18 (1993) 149–171.
P. Hansen and B. Jaumard, Lipschitz optimization, in: Handbook of Global Optimization, R. Horst and M. Pardalos, eds. (Kluwer Academic, Dordrecht, 1995) pp. 407–494.
R. Horst and M. Pardolas (eds.), Handbook of Global Optimization (Kluwer Academic, Dordrecht, 1995).
K.G. Murty, Linear Programming (Wiley, New York, 1983).
T. Rolski, Queues with non-stationary input stream: Ross's conjecture, Adv. in Appl. Probab. 13 (1981) 603–618.
T. Rolski, Upper bounds for single server queues with doubly stochastic Poisson arrivals, Math. Oper. Res. 11 (1986) 442–456.
E. Seneta, Non-negative Matrices and Markov Chains, 2nd ed. (Springer-Verlag, New York, 1981).
S. Stidham, Jr., Optimal control of admission to a queueing system, IEEE Trans. Automat. Control 30 (August 1985) 705–713.
S. Stidham, Jr., Scheduling, routing, and flow control in stochastic networks, in: Stochastic Differential Systems, Stochastic Control Theory and Applications, IMA, Vol. 10, W. Fleming and P.L. Lions, eds. (Springer-Verlag, Berlin, 1988) pp. 529–561.
S. Stidham, Jr. and R. Weber, A survey of Markov decision models for control of networks of queues, Queueing Systems Theory Appl. 13 (1993) 291–314.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hemachandra, N., Narahari, Y. A Mathematical Programming Approach to Optimal Markovian Switching of Poisson Arrival Streams to Queueing Systems. Queueing Systems 36, 443–461 (2000). https://doi.org/10.1023/A:1010983510051
Issue Date:
DOI: https://doi.org/10.1023/A:1010983510051