Optimal control and performance analysis of an M X /M/1 queue with batches of negative customers
RAIRO - Operations Research - Recherche Opérationnelle, Tome 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 : https://doi.org/10.1051/ro:2004016
Mots clés : 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},
     zbl = {1092.90013},
     mrnumber = {2081834},
     language = {en},
     url = {http://www.numdam.org/item/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, Tome 38 (2004) no. 2, pp. 121-151. doi : 10.1051/ro:2004016. http://www.numdam.org/item/RO_2004__38_2_121_0/

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

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

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

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

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

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

[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 568961 | Zbl 0428.60093

[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 1123837 | Zbl 0741.60091

[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 1090463 | Zbl 0744.60110

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

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

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

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

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

[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 1719920 | Zbl 0954.90063

[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 1365266

[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 0947.90028

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

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

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

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

[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 720515 | Zbl 0525.60072

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

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

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

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

[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 1938256 | Zbl 1019.60087