Optimal control and performance analysis of an M X /M/1 queue with batches of negative customers
RAIRO - Operations Research - Recherche Opérationnelle, Volume 38 (2004) no. 2, pp. 121-151.

We consider a Markov decision process for an M X /M/1 queue that is controlled by batches of negative customers. More specifically, we derive conditions that imply threshold-type optimal policies, under either the total discounted cost criterion or the average cost criterion. The performance analysis of the model when it operates under a given threshold-type policy is also studied. We prove a stability condition and a complete stochastic comparison characterization for models operating under different thresholds. Exact and asymptotic results concerning the computation of the stationary distribution of the model are also derived.

DOI: 10.1051/ro:2004016
Keywords: queueing, Markov decision processes, negative customers, stationary distribution, stochastic comparison
@article{RO_2004__38_2_121_0,
     author = {Artalejo, Jesus R. and Economou, Antonis},
     title = {Optimal control and performance analysis of an $M^{X}/M/1$ queue with batches of negative customers},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {121--151},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {2},
     year = {2004},
     doi = {10.1051/ro:2004016},
     mrnumber = {2081834},
     zbl = {1092.90013},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2004016/}
}
TY  - JOUR
AU  - Artalejo, Jesus R.
AU  - Economou, Antonis
TI  - Optimal control and performance analysis of an $M^{X}/M/1$ queue with batches of negative customers
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2004
SP  - 121
EP  - 151
VL  - 38
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2004016/
DO  - 10.1051/ro:2004016
LA  - en
ID  - RO_2004__38_2_121_0
ER  - 
%0 Journal Article
%A Artalejo, Jesus R.
%A Economou, Antonis
%T Optimal control and performance analysis of an $M^{X}/M/1$ queue with batches of negative customers
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2004
%P 121-151
%V 38
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2004016/
%R 10.1051/ro:2004016
%G en
%F RO_2004__38_2_121_0
Artalejo, Jesus R.; Economou, Antonis. Optimal control and performance analysis of an $M^{X}/M/1$ queue with batches of negative customers. RAIRO - Operations Research - Recherche Opérationnelle, Volume 38 (2004) no. 2, pp. 121-151. doi : 10.1051/ro:2004016. http://archive.numdam.org/articles/10.1051/ro:2004016/

[1] J.R. Artalejo, G-networks: A versatile approach for work removal in queueing networks. Eur. J. Oper. Res. 126 (2000) 233-249. | MR | Zbl

[2] D. Bertsekas, Dynamic Programming, Deterministic and Stochastic Models. Prentice-Hall, Englewood Cliffs, New Jersey (1987). | MR | Zbl

[3] R.K. Deb, Optimal control of bulk queues with compound Poisson arrivals and batch service. Opsearch 21 (1984) 227-245. | MR | Zbl

[4] R.K. Deb and R.F. Serfozo, Optimal control of batch service queues. Adv. Appl. Prob. 5 (1973) 340-361. | MR | Zbl

[5] X. Chao, M. Miyazawa and M. Pinedo, Queueing Networks: Customers, Signals and Product Form Solutions. Wiley, Chichester (1999). | Zbl

[6] A. Economou, On the control of a compound immigration process through total catastrophes. Eur. J. Oper. Res. 147 (2003) 522-529. | MR | Zbl

[7] A. Federgruen and H.C. Tijms, Computation of the stationary distribution of the queue size in an M/G/1 queueing system with variable service rate. J. Appl. Prob. 17 (1980) 515-522. | MR | Zbl

[8] E. Gelenbe, Random neural networks with negative and positive signals and product-form solutions. Neural Comput. 1 (1989) 502-510.

[9] E. Gelenbe, Product-form queueing networks with negative and positive customers. J. Appl. Prob. 28 (1991) 656-663. | MR | Zbl

[10] E. Gelenbe, G-networks with signals and batch removal. Probab. Eng. Inf. Sci. 7 (1993) 335-342.

[11] E. Gelenbe, P. Glynn and K. Sigman, Queues with negative arrivals. J. Appl. Prob. 28 (1991) 245-250. | MR | Zbl

[12] E. Gelenbe and R. Schassberger, Stability of product form G-networks. Probab. Eng. Inf. Sci. 6 (1992) 271-276. | Zbl

[13] E. Gelenbe and G. Pujolle, Introduction to Queueing Networks. Wiley, Chichester (1998). | MR | Zbl

[14] P.G. Harrison and E. Pitel, The M/G/1 queue with negative customers. Adv. Appl. Prob. 28 (1996) 540-566. | MR | Zbl

[15] O. Hernandez-Lerma and J. Lasserre, Discrete-time Markov Control Processes. Springer, New York (1996). | MR | Zbl

[16] E.G. Kyriakidis, Optimal control of a truncated general immigration process through total catastrophes. J. Appl. Prob. 36 (1999) 461-472. | MR | Zbl

[17] E.G. Kyriakidis, Characterization of the optimal policy for the control of a simple immigration process through total catastrophes. Oper. Res. Letters 24 (1999) 245-248. | MR | Zbl

[18] T. Nishigaya, K. Mukumoto and A. Fukuda, An M/G/1 system with set-up time for server replacement. Transactions of the Institute of Electronics, Information and Communication Engineers J74-A-10 (1991) 1586-1593.

[19] S. Nishimura and Y. Jiang, An M/G/1 vacation model with two service modes. Prob. Eng. Inform. Sci. 9 (1994) 355-374. | MR

[20] R.D. Nobel and H.C. Tijms, Optimal control of an M X /G/1 queue with two service modes. Eur. J. Oper. Res. 113 (1999) 610-619. | Zbl

[21] M. Puterman, Markov Decision Processes. Wiley, New York (1994). | MR | Zbl

[22] S.M. Ross, Applied Probability Models with Optimization Applications. Holden-Day Inc., San Francisco (1970). | MR | Zbl

[23] S.M. Ross, Introduction to Stochastic Dynamic Programming. Academic Press, New York (1983). | MR | Zbl

[24] L.I. Sennott, Stochastic Dynamic Programming and the Control of Queueing Systems. Wiley, New York (1999). | MR | Zbl

[25] L.I. Sennott, P.A. Humblet and R.L. Tweedie, Mean drifts and the non-ergodicity of Markov chains. Oper. Res. 31 (1983) 783-789. | MR | Zbl

[26] R. Serfozo, An equivalence between continuous and discrete time Markov decision processes. Oper. Res. 27 (1979) 616-620. | MR | Zbl

[27] D. Stoyan, Comparison Methods for Queues and Other Stochastic Models. Wiley, Chichester (1983). | MR | Zbl

[28] J. Teghem, Control of the service process in a queueing system. Eur. J. Oper. Res. 23 (1986) 141-158. | MR | Zbl

[29] H.C. Tijms, A First Course in Stochastic Models. Wiley, Chichester (2003). | MR | Zbl

[30] W.S. Yang, J.D. Kim and K.C. Chae, Analysis of M/G/1 stochastic clearing systems. Stochastic Anal. Appl. 20 (2002) 1083-1100. | MR | Zbl

Cited by Sources: