×

Optimal control and performance analysis of an \(M^X/M/1\) queue with batches of negative customers. (English) Zbl 1092.90013

Summary: 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.

MSC:

90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
90C40 Markov and semi-Markov decision processes

Software:

MCQueue
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[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 · Zbl 0971.90007 · doi:10.1016/S0377-2217(99)00476-2
[2] D. Bertsekas , Dynamic Programming , Deterministic and Stochastic Models. Prentice-Hall, Englewood Cliffs, New Jersey ( 1987 ). MR 896902 | Zbl 0649.93001 · 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 · 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 · Zbl 0264.60066 · doi:10.2307/1426040
[5] X. Chao , M. Miyazawa and M. Pinedo , Queueing Networks: Customers , Signals and Product Form Solutions. Wiley, Chichester ( 1999 ). Zbl 0936.90010 · 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 · Zbl 1026.90091 · doi:10.1016/S0377-2217(02)00355-7
[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 · Zbl 0428.60093 · doi:10.2307/3213040
[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 · Zbl 0741.60091 · doi:10.2307/3214499
[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 · Zbl 0744.60110 · doi:10.2307/3214756
[12] E. Gelenbe and R. Schassberger , Stability of product form G-networks . Probab. Eng. Inf. Sci. 6 ( 1992 ) 271 - 276 . Zbl 1134.60396 · Zbl 1134.60396 · doi:10.1017/S0269964800002539
[13] E. Gelenbe and G. Pujolle , Introduction to Queueing Networks . Wiley, Chichester ( 1998 ). MR 874339 | Zbl 0654.60079 · 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 · Zbl 0861.60088 · doi:10.2307/1428071
[15] O. Hernandez-Lerma and J. Lasserre , Discrete-time Markov Control Processes . Springer, New York ( 1996 ). MR 1363487 | Zbl 0840.93001 · 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 . Article | MR 1724812 | Zbl 0955.90147 · Zbl 0955.90147 · doi:10.1239/jap/1032374465
[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 · Zbl 0954.90063 · doi:10.1016/S0167-6377(99)00012-7
[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 · Zbl 1335.60173
[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 · Zbl 0947.90028 · doi:10.1016/S0377-2217(98)00085-X
[21] M. Puterman , Markov Decision Processes . Wiley, New York ( 1994 ). MR 1270015 | Zbl 0829.90134 · Zbl 0829.90134
[22] S.M. Ross , Applied Probability Models with Optimization Applications . Holden-Day Inc., San Francisco ( 1970 ). MR 264792 | Zbl 0213.19101 · Zbl 0213.19101
[23] S.M. Ross , Introduction to Stochastic Dynamic Programming . Academic Press, New York ( 1983 ). MR 749232 | Zbl 0567.90065 · 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 · 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 · Zbl 0525.60072 · doi:10.1287/opre.31.4.783
[26] R. Serfozo , An equivalence between continuous and discrete time Markov decision processes . Oper. Res. 27 ( 1979 ) 616 - 620 . MR 533923 | Zbl 0413.90079 · Zbl 0413.90079 · doi:10.1287/opre.27.3.616
[27] D. Stoyan , Comparison Methods for Queues and Other Stochastic Models . Wiley, Chichester ( 1983 ). MR 754339 | Zbl 0536.60085 · 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 · Zbl 0583.60092 · doi:10.1016/0377-2217(86)90234-1
[29] H.C. Tijms , A First Course in Stochastic Models . Wiley, Chichester ( 2003 ). MR 2190630 | Zbl 1088.60002 · 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 · Zbl 1019.60087 · doi:10.1081/SAP-120014554
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.