Abstract
We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.
Similar content being viewed by others
References
H. Heffes and D.M. Lucantoni, A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance, IEEE J. Selected Areas in Commun. SAC-4 (1986) 856–868.
D.P. Heyman and M.J. Sobel,Stochastic Models in Operations Research, vol. 2: Stochastic Optimization (McGraw-Hill, New York, 1984).
S.J. Johansen and S. Stidham, Jr., Control of arrivals to a stochastic input-output system, Adv. Appl. Prob. 12 (1980) 972–999.
H. Langen, Applying the method of phases in the optimization of queueing systems, Adv. Appl. Prob. 14 (1982) 122–142.
S.A. Lippman, Applying a new device in the optimization of exponential queueing systems, Oper. Res. 23 (1975) 687–710.
P. Naor and U. Yechiali, Queueing problems with heterogeneous arrivals and service, Oper. Res. 19 (1971) 722–734.
M.F. Neuts,Structured Stochastic Matrices of M/G/1 Type and their Applications (Marcel Dekker, New York, 1989).
M.L. Puterman and L.C. Thomas, A note on computing optimal control limits for GI/M/1 queueing systems, Manag. Sci. 33 (1987) 939–943.
S.N. Raju and U.N. Bhat, Recursive relations in the computation of the equilibrium results of finite queues, in: M.F. Neuts (ed.),Algorithmic Methods in Probability, TIMS Studies in the Management Sciences 7 (North-Holland, 1977) pp. 247–270.
S. Stidham, Jr., Socially and individually optimal control of arrivals, Manag. Sci. 24 (1978) 1598–1610.
S. Stidham, Jr., Optimal control of admission to a queueing system, IEEE Trans. Automatic Control AC-30 (1985) 705–713.
J.A.E.E. Van Nunen and M.L. Puterman, Computing optimal control limits forGI/M/s queueing systems with controlled arrivals, Manag. Sci. 29 (1983) 725–734.
U. Yechiali, Queueing type birth-and-death process defined on a continuous time Markov chain, Oper. Res. 21 (1973) 604–609.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.
Rights and permissions
About this article
Cite this article
Lamond, B.F. Optimal admission policies for a finite queue with bursty arrivals. Ann Oper Res 28, 243–260 (1991). https://doi.org/10.1007/BF02055584
Issue Date:
DOI: https://doi.org/10.1007/BF02055584