A duality approach to queues with service restrictions and storage systems with state-dependent rates. (English) Zbl 1282.60092

The authors develop the duality techniques for M/G/1 and G/M/1 type queueing processes. Specifically, they study two different queueing models, for which the duality techniques are developed. These are the queueing model 1 (specifically defined in the paper) with truncated service policy and the queueing model 2 (specifically defined in the paper) with the bounded waiting time policy. The first type model suggests that any service requirement that would increase the total workload beyond some constant capacity threshold is reduced such that this threshold can be reached but not exceeded. The second type model suggests that new arrivals whose waiting time in the queue would exceed some fixed constant are not admitted to the system. For these systems the authors derive the steady state distributions of the workload and the numbers of customers present in the systems as well as distributions of the length of busy and idle periods. The duality approach is used to study finite capacity storage systems with general state-dependent outflow rates. A connection is also derived between the steady state densities of the non-Markovian continuous time content level process of the G/M/1 finite storage system with state-dependent outflow rule and the corresponding embedded sequences of local maximum points.


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI Euclid


[1] Asmussen, S. (2003). Applied Probability and Queues , 2nd edn. Springer, New York. · Zbl 1029.60001
[2] Bekker, R. (2005). Finite-buffer queues with workload-dependent service and arrival rates. Queueing Systems 50, 231-253. · Zbl 1085.60066
[3] Bekker, R. and Zwart, B. (2005). On an equivalence between loss rates and cycle maxima in queues and dams. Prob. Eng. Inf. Sci. 19, 241-255. · Zbl 1097.90017
[4] Bekker, R., Borst, S. C., Boxma, O. J. and Kella, O. (2004). Queues with workload-dependent arrival and service rates. Queueing Systems 46, 537-556. · Zbl 1056.90026
[5] Boxma, O., Perry, D., Stadje, W. and Zacks, S. (2009). The \({\mathrm M}/{\mathrm G}/1\) queue with quasi-restricted accessibility. Stoch. Models 25, 151-196. · Zbl 1178.60062
[6] Brandt, A. and Brandt, M. (2002). Asymptotic results and a Markovian approximation for the \(M(n)/\break M(n)/s + GI\) system. Queueing Systems 41, 73-94. · Zbl 1010.90014
[7] Brill, P. H. (2008). Level Crossing Methods in Stochastic Models . Springer, New York. · Zbl 1157.60003
[8] Chen, H. and Yao, D. D. (1992). A fluid model for systems with random disruptions. Operat. Res. S40, S239-S247. · Zbl 0754.60107
[9] Cohen, J. W. (1969). Single server queues with restricted accessibility. J. Eng. Math. 3, 265-285. · Zbl 0186.24503
[10] Cohen, J. W. (1982). The Single Server Queue , 2nd edn. North Holland, Amsterdam. · Zbl 0481.60003
[11] Conolly, B. W., Parthasarathy, P. R. and Selvaraju, N. (2002). Double-ended queues with impatience. Comput. Operat. Res. 29, 2053-2072. · Zbl 1010.90011
[12] Daley, D. J. (1964). Single-server queueing systems with uniformly limited queueing times. J. Austral. Math. Soc. 4, 489-505. · Zbl 0131.16802
[13] De Kok, A. G. and Tijms, H. C. (1985). A queueing system with impatient customers. J. Appl. Prob. 22, 688-696. · Zbl 0573.60086
[14] Gavish, B. and Schweitzer, P. J. (1977). The Markovian queue with bounded waiting time. Manag. Sci. 23, 1349-1357. · Zbl 0372.60134
[15] Harrison, J. M. and Resnick, S. I. (1976). The stationary distribution and first exit probabilities of a storage process with general release rule. Math. Operat. Res. 1, 347-358. · Zbl 0381.60092
[16] Kaspi, H. and Perry, D. (1989). On a duality between a non-Markov storage/production process and a Markovian dam process with state dependent input and output. J. Appl. Prob. 26, 835-844. · Zbl 0758.60106
[17] Kaspi, H., Kella, O. and Perry, D. (1996). Dam processes with state dependent batch sizes and intermittent production processes with state dependent rates. Queueing Systems 24, 37-57. · Zbl 0874.90075
[18] Kella, O. and Whitt, W. (1992). Useful martingales for stochastic storage processes with Lévy input. J. Appl. Prob. 29, 396-403. · Zbl 0761.60065
[19] Liu, L. and Kulkarni, V. G. (2006). Explicit solutions for the steady state distributions in M/PH/\(1\) queues with workload dependent balking. Queueing Systems 52, 251-260. · Zbl 1098.90023
[20] Liu, L. and Kulkarni, V. G. (2008). Busy period analysis for M/PH/\(1\) queues with workload dependent balking. Queueing Systems 59 , 37-51. · Zbl 1147.60328
[21] Löpker, A. and Perry, D. (2010). The idle period of the finite \({\mathrm G}/{\mathrm M}/1\) queue with an interpretation in risk theory. Queueing Systems 64, 395-407. · Zbl 1201.60087
[22] Nahmias, S., Perry, D. and Stadje, W. (2004). Actuarial valuation of perishable inventory systems. Prob. Eng. Inf. Sci. 18, 219-232. · Zbl 1051.60093
[23] Perry, D. and Asmussen, S. (1995). Rejection rules in the \({\mathrm M}/{\mathrm G}/1\) type queue. Queueing Systems 19, 105-130. · Zbl 0835.60080
[24] Perry, D. and Stadje, W. (2003). Duality of dams via mountain processes. Operat. Res. Lett. 31, 451-458. · Zbl 1052.90021
[25] Perry, D., Stadje, W. and Zacks, S. (2000). Busy period analysis for \({\mathrm M}/{\mathrm G}/1\) and \({\mathrm G}/{\mathrm M}/1\) type queues with restricted accessibility. Operat. Res. Lett. 27, 163-174. · Zbl 1096.90517
[26] Stanford, R. E. (1990). On queues with impatience. Adv. Appl. Prob. 22, 768-769. · Zbl 04580107
[27] Zwart, A. P. (2006). A fluid queue with a finite buffer and subexponential input. Adv. Appl. Prob. 32, 221-243. · Zbl 0964.60081
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.