×

Diffusion approximations for double-ended queues with reneging in heavy traffic. (English) Zbl 1442.60094

The system under consideration consists of two classes of customers. Whenever there is a pair of customers from both classes, they are matched and leave the system immediately. The matching follows the first-come-first-match principle. If a customer from one class cannot be matched immediately, he/she will stay in a queue and wait for the upcoming arrivals from the other class. Thus the system is either empty or all customers present in it belong to the same class. Customers are impatient, and they can leave the system without being matched. The arrival processes are independent renewal processes, and the patience times for customers of each class are independent and identically distributed with a general distribution. The author imposes a suitable heavy traffic condition and a mild condition on patience time distributions, and establishes simple asymptotic linear relationships between the diffusion-scaled queue length process and the diffusion-scaled offered waiting time processes and shows that the diffusion-scaled queue length process converges weakly to a diffusion process. Finally, the unique stationary distribution of the diffusion limit is derived.

MSC:

60K25 Queueing theory (aspects of probability theory)
60F05 Central limit and other weak theorems
90B22 Queues and service in operations research
60K05 Renewal theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Afeche, P., Diamant, A., Milner, J.: Double-sided batch queues with abandonment: modeling crossing networks. Oper. Res. 62(5), 1179-1201 (2014) · Zbl 1327.90045
[2] Boxma, O.J., David, I., Perry, D., Stadje, W.: A new look at organ transplantation models and double matching queues. Probab. Eng. Inf. Sci. 25, 135-155 (2011) · Zbl 1213.90085
[3] Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34(1), 45-56 (2009) · Zbl 1214.60013
[4] Conolly, B.W., Parthasarathy, P.R., Selvaraju, N.: Double-ended queues with impatience. Comput. Oper. Res. 29(14), 2053-2072 (2002) · Zbl 1010.90011
[5] Dai, J.G., He, S.: Customer abandonment in many-server queues. Math. Oper. Res. 35(2), 347-362 (2010) · Zbl 1222.60071
[6] Dai, J.G., He, S., Tezcan, T.: Many-server diffusion limits for \[G/Ph/n+GI\] G/Ph/n+GI queues. Ann. Appl. Probab. 20(5), 1854-1890 (2010) · Zbl 1202.90085
[7] Dai, J.G., Williams, R.J.: Existence and uniqueness of semimartingale reflecting Brownian motions in convex polyhedrons. Theory Probab. Appl. 40(1), 1-40 (1996)
[8] Degirmenci, I.T.: Asymptotic analysis and performance-based design of large scale service and inventory systems. Ph.D., dissertation, Department of Business Administration, Duke University (2010)
[9] Dobbie, J.M.: A doubled-ended queuing problem of Kendall. Oper. Res. 9(5), 755-757 (1961) · Zbl 0107.13104
[10] Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, London (1986) · Zbl 0592.60049
[11] Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximations in generalized Jackson networks. Ann. Appl. Probab. 16(1), 56-90 (2006) · Zbl 1094.60052
[12] Garnet, O., Mandelbaum, A., Reiman, M.: Designing a call center with impatient customers. Manuf. Serv. Oper. Manag. 4(3), 208-227 (2002)
[13] Giveen, S.M.: A taxicab problem with time-dependent arrival rates. SIAM Rev. 5(2), 119-127 (1963) · Zbl 0117.13702
[14] Gurvich, I., Ward, A.: On the dynamic control of matching queues. Stoch. Syst. 4(2), 479-523 (2014) · Zbl 1327.60177
[15] Iglehart, D.L., Whitt, W.: Multiple channel queues in heavy traffic I. Adv. Appl. Probab. 2(1), 150-177 (1970) · Zbl 0218.60098
[16] Iglehart, D.L., Whitt, W.: The equivalence of functional central limit theorems for counting processes and associated partial sums. Ann. Math. Stat. 42(4), 1372-1378 (1971) · Zbl 0226.60028
[17] Jacod, J., Shiryaev, A.N.: Limit Theorem for Stochastic Processes, 2nd edn. Springer, Berlin (2003) · Zbl 1018.60002
[18] Kang, W., Ramanan, K.: Fluid limits of many-server queues with reneging. Ann. Appl. Probab. 20(6), 2204-2260 (2010) · Zbl 1208.60094
[19] Kashyap, B.R.K.: The double-ended queue with bulk service and limited waiting space. Oper. Res. 14(5), 822-834 (1966) · Zbl 0147.16602
[20] Kendall, D.G.: Some problems in the theory of queues. J. R. Stat. Soc. Ser. B 13(2), 151-185 (1951) · Zbl 0045.07801
[21] Khademi, A., Liu, X.: Asymptotically Optimal Allocation Policies for Transplant Queueing Systems, Working Paper (2018) · Zbl 1482.90068
[22] Kim, W.K., Yoon, K.P., Mendoza, G., Sedaghat, M.: Simulation model for extended double-ended queueing. Comput. Ind. Eng. 59(2), 209-219 (2010)
[23] Lee, C., Weerasinghe, A.: Convergence of a queueing system in heavy traffic with general patience-time distributions. Stoch. Process. Appl. 121(11), 2507-2552 (2011) · Zbl 1230.60098
[24] Liu, X., Gong, Q., Kulkarni, V.G.: Diffusion models for double-ended queues with renewal arrival processes. Stoch. Syst. 5(1), 1-61 (2015) · Zbl 1331.60177
[25] Mandelbaum, A., Momcilovic, P.: Queues with many servers and impatient customers. Math. Oper. Res. 37(1), 41-65 (2012) · Zbl 1239.60086
[26] Ozkan, E., Ward, A.: Dynamic Matching for Real-Time Ridesharing. https://ssrn.com/abstract=2844451 (2017)
[27] Pang, G., Talreja, R., Whitt, W.: Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surv. 4, 193-267 (2007) · Zbl 1189.60067
[28] Perry, D., Stadje, W.: Perishable inventory systems with impatient demands. Math. Methods Oper. Res. 50(1), 77-90 (1999) · Zbl 0972.90001
[29] Prabhakar, B., Bambos, N., Mountford, T.S.: The synchronization of Poisson processes and queueing networks with service and synchronization nodes. Adv. Appl. Probab. 32(3), 824-843 (2000) · Zbl 0968.60041
[30] Reed, J., Tezcan, T.: Hazard rate scaling of the abandonment distribution for the \[GI/M/n + GI\] GI/M/n+GI queue in heavy traffic. Oper. Res. 60(4), 981-995 (2012) · Zbl 1260.90072
[31] Reed, J.E., Ward, A.R.: Approximating the GI/GI/1+GI queue with a nonlinear drift diffusion: hazard rate scaling in heavy traffic. Math. Oper. Res. 33(3), 606-644 (2008) · Zbl 1231.90142
[32] Ward, A.R., Glynn, P.W.: A diffusion approximation for a Markovian queue with reneging. Queueing Syst. 43(1/2), 103-128 (2003) · Zbl 1054.60100
[33] Ward, A.R., Glynn, P.W.: A diffusion approximation for a \[GI/GI/1\] GI/GI/1 queue with balking or reneging. Queueing Syst. 50(4), 371-400 (2005) · Zbl 1094.60064
[34] Weerasinghe, A.: Diffusion approximations for G/M/n + GI queues with state-dependent service rates. Math. Oper. Res. 39(1), 207-228 (2013) · Zbl 1302.60127
[35] Zeltyn, S., Mandelbaum, A.: Call centers with impatient customers: many-server asymptotics of the \[M/M/n + G\] M/M/n+G queue. Queueing Syst. 51(3-4), 361-402 (2005) · Zbl 1085.60072
[36] Zenios, S.A.: Modeling the transplant waiting list: a queueing model with reneging. Queueing Syst. 31, 239-251 (1999) · Zbl 0934.90026
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.