Abstract
Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of γ each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters.
Similar content being viewed by others
References
Altman E, Nain P (1991) Optimality of a threshold policy in the M/M/1 queue with repeated vacations. INRIA Report, RR-1419
Altman E, Nain P (1993) Optimal control of an M/G/1 queue with repeated vacations. IEEE Trans Aut Cont 38/12:1766–1755
Bertsekas DP (1987) Dynamic programming. Deterministic and Stochastic Models. Prentice Hall, Inc Englewoods Cliff
Brémaud P (1981) Point processes and queues. Springer Verlag, New York
Blanc JPC, de Waal P, Nain P, and Towsley D (1992) Optimal control of admission to a multi-server queue with two arrival streams. IEEE Trans Aut Cont 37/6:785–797
Chung KL (1967) Markov chains with stationary transition probabilities, 2nd. Ed. Springer Verlag, New York
Doshi B (1986) Queueing systems with vacations — a survey. Queueing Syst 1:29–66
Doshi B (1986) Conditional and unconditional distributions for M/G/1 type queues with server vacations. Queueing Syst 7:229–252
Federgruen A, So KC (1991) Optimality of threshold policies in single-server queueing systems with server vacations. Adv Appl Prob 23:388–405
Gelenbe E, Mitrani I (1980) Analysis and synthesis of computer systems. Academic Press, London
Gelenbe E, Lasnogorodski R (1980) A queue with server of walking type (autonomous service). Ann Inst Henry Poincaré XVI:63–73
Heyman DP, Sobel MJ (1984) Stochastic models in operations research, Volume II, Stochastic Optimization. McGraw-Hill Book Company, New York
Kella O (1989) The threshold policy in the M/G/1 queue with server vacations. Naval Res Quat 33:111–123
Kella O (1990) Optimal control of the vacation scheme in an M/G/1 queue. Opns Res 38:724–728
Lee H-S, Srinivasan MM (1989) Control policies for the Mx/G/1 queueing system. Mgmt Sci 35:708–721
Levy H, Yechiali U (1975) Utilization of idle time in an M/G/1 queueing system. Mgmt Sci 22:202–211
Lippman SA (1975) On dynamic programming with unbounded rewards. Mgmt Sci 21:1225–1233
Ross SM (1970) Applied probability models with optimization applications. Holden-Day, San Francisco
Schäl M (1975) Conditions for optimality in dynamic programming and for the limit of the n-stage optimal policies to be optimal. Z Wahrscheinlichkeitsth 32:179–196
Sennott LI (1989) Average cost semi-Markov decision processes and the control of queueing system. Prob in the Engineering and the Information Sci 3:247–272
Talman AJJ (1979) A simple proof of the optimality of the best n-policy in the M/G/1 queueing control problem with removable server. Statistica Neerlandica 33:143–150
Takagi H (1986) Analysis of polling systems. MIT Press, Cambridge (Mass)
Teghem J Jr (1986) Control of the service process in a queueing system. European J of Opns Res 23:141–158
Widder DV (1941) The Laplace transform. Princeton University Press, Princeton
Yadin M, Naor P (1963) Queueing systems with a removable service station. Opns Res Quat 14:393–405
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Altman, E., Nain, P. Optimality of a Threshold Policy in theM/M/ queue with repeated vacations. Mathematical Methods of Operations Research 44, 75–96 (1996). https://doi.org/10.1007/BF01246330
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01246330