×

On the instability of matching queues. (English) Zbl 1382.60119

Summary: A matching queue is described via a graph, an arrival process and a matching policy. Specifically, to each node in the graph there is a corresponding arrival process of items, which can either be queued or matched with queued items in neighboring nodes. The matching policy specifies how items are matched whenever more than one matching is possible. Given the matching graph and the matching policy, the stability region of the system is the set of intensities of the arrival processes rendering the underlying Markov process positive recurrent. In a recent paper, a condition on the arrival intensities, which was named NCOND, was shown to be necessary for the stability of a matching queue. That condition can be thought of as an analogue to the usual traffic condition for traditional queueing networks, and it is thus natural to study whether it is also sufficient. In this paper, we show that this is not the case in general. Specifically, we prove that, except for a particular class of graphs, there always exists a matching policy rendering the stability region strictly smaller than the set of arrival intensities satisfying NCOND. Our proof combines graph- and queueing-theoretic techniques: After showing explicitly, via fluid-limit arguments that the stability regions of two basic models is strictly included in NCOND, we generalize this result to any graph inducing either one of those two basic graphs.

MSC:

60K25 Queueing theory (aspects of probability theory)
60F17 Functional limit theorems; invariance principles
90B22 Queues and service in operations research

References:

[1] Adan, I. and Weiss, G. (2012). Exact FCFS matching rates for two infinite multitype sequences.Oper. Res.60475-489. · Zbl 1298.60089 · doi:10.1287/opre.1110.1027
[2] Adan, I. and Weiss, G. (2014). A skill based parallel service system under FCFS-ALIS—Steady state, overloads, and abandonments.Stoch. Syst.4250-299. · Zbl 1305.60091 · doi:10.1287/13-SSY117
[3] Baccelli, F. and Brémaud, P. (2003).Elements of Queueing Theory:Palm Martingale Calculus and Stochastic Recurrences, 2nd ed.Applications of Mathematics(New York)26. Springer, Berlin. · Zbl 1021.60001
[4] Billingsley, P. (1999).Convergence of Probability Measures, 2nd ed. Wiley, New York. · Zbl 0944.60003
[5] Bollobás, B. (2001).Random Graphs, 2nd ed.Cambridge Studies in Advanced Mathematics73. Cambridge Univ. Press, Cambridge.
[6] Bramson, M. (1994). Instability of FIFO queueing networks.Ann. Appl. Probab.4414-431. · Zbl 0804.60079 · doi:10.1214/aoap/1177005066
[7] Bramson, M. (2008).Stability of Queueing Networks. Lecture Notes in Math.1950. Springer, Berlin. · Zbl 1189.60005 · doi:10.1214/08-PS137
[8] Bušić, A., Gupta, V. and Mairesse, J. (2013). Stability of the bipartite matching model.Adv. in Appl. Probab.45351-378. · Zbl 1274.60228 · doi:10.1017/S0001867800006364
[9] Caldentey, R., Kaplan, E. H. and Weiss, G. (2009). FCFS infinite bipartite matching of servers and customers.Adv. in Appl. Probab.41695-730. · Zbl 1247.90099 · doi:10.1017/S0001867800003530
[10] Dai, J. G. (1995). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models.Ann. Appl. Probab.549-77. · Zbl 0822.60083 · doi:10.1214/aoap/1177004828
[11] Dai, J. G. (1996). A fluid limit model criterion for instability of multiclass queueing networks.Ann. Appl. Probab.6751-757. · Zbl 0860.60075 · doi:10.1214/aoap/1034968225
[12] Davis, A. E., Mehrotra, S., Kilambi, V., Perry, O., Friedewald, J. J. and Ladner, D. P. (2015). Addressing US national geographic disparity in kidney transplantation by creating sharing partnerships. Working paper.
[13] Durrett, R. (1991).Probability:Theory and Examples. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA. · Zbl 0709.60002
[14] Gamarnik, D. and Goldberg, D. A. (2010). Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections.Combin. Probab. Comput.1961-85. · Zbl 1213.90252 · doi:10.1017/S0963548309990186
[15] Gamarnik, D. and Hasenbein, J. J. (2005). Instability in stochastic and fluid queueing networks.Ann. Appl. Probab.151652-1690. · Zbl 1135.90006 · doi:10.1214/105051605000000179
[16] Gurvich, I., Lariviere, M. and Moreno, A. (2016). Operations in the on-demand economy: Staffing services with self-scheduling capacity. Available at SSRN 2336514.
[17] Gurvich, I. and Ward, A. (2014). On the dynamic control of matching queues.Stoch. Syst.4479-523. · Zbl 1327.60177 · doi:10.1287/13-SSY097
[18] Ibrahim, R. (2016). Staffing a service system where capacity is random. Working paper.
[19] Kurtz, T. G. (1992). Averaging for martingale problems and stochastic approximation. InApplied Stochastic Analysis(New Brunswick,NJ, 1991).Lect. Notes Control Inf. Sci.177186-209. Springer, Berlin.
[20] Lovász, L., Pelikán, J. and Vesztergombi, K. (2003).Discrete Mathematics:Elementary and Beyond. Springer, New York. · Zbl 1059.00001
[21] Lu, S. H. and Kumar, P. R. (1991). Distributed scheduling based on due dates and buffer priorities.IEEE Trans. Automat. Control361406-1416. · Zbl 0674.90041 · doi:10.1109/9.21085
[22] Luo, J. and Zhang, J. (2013). Staffing and control of instant messaging contact centers.Oper. Res.61328-343. · Zbl 1276.60101 · doi:10.1287/opre.1120.1151
[23] Mairesse, J. and Moyal, P. (2016). Stability of the stochastic matching model.J. Appl. Probab.531064-1077. · Zbl 1356.60147 · doi:10.1017/jpr.2016.65
[24] Meyn, S. P. (1995). Transience of multiclass queueing networks via fluid limit models.Ann. Appl. Probab.5946-957. · Zbl 0865.60079 · doi:10.1214/aoap/1177004601
[25] Pang, G., Talreja, R. and Whitt, W. (2007). Martingale proofs of many-server heavy-traffic limits for Markovian queues.Probab. Surv.4193-267. · Zbl 1189.60067 · doi:10.1214/06-PS091
[26] Perry, O. and Whitt, W. (2011). An ODE for an overloaded \(X\) model involving a stochastic averaging principle.Stoch. Syst.159-108. · Zbl 1291.60191 · doi:10.1287/10-SSY009
[27] Perry, O. and Whitt, W. (2013). A fluid limit for an overloaded \(X\) model via a stochastic averaging principle.Math. Oper. Res.38294-349. · Zbl 1305.60024 · doi:10.1287/moor.1120.0572
[28] Robert, P. (2003).Stochastic Networks and Queues, French ed.Applications of Mathematics(New York)52. Springer, Berlin. · Zbl 1038.60091
[29] Rybko, A. N. and Stolyar, A. L. (1992). On the ergodicity of random processes that describe the functioning of open queueing networks.Problemy Peredachi Informatsii283-26. · Zbl 0768.60089
[30] Siddhartha, B., Riquelme, C. and Johari, R. (2015). Pricing in ride-share platforms: A queueing-theoretic approach. Available at SSRN 2568258.
[31] Talreja, R. and Whitt, W. (2008). Fluid models for overloaded multiclass many-server queueing systems with first-come, first-served routing.Manage. Sci.541513-1527. · Zbl 1232.90156 · doi:10.1287/mnsc.1080.0868
[32] Van der Hofstad, R. (2013).Random Graphs and Complex Networks. Lecture notes. · Zbl 1269.05101 · doi:10.1002/rsa.20450
[33] Whitt, W. (1991). The pointwise stationary approximation for \(M_t/M_t/s\) queues is asymptotically correct as the rates increase.Manage. Sci.37207-314. · Zbl 0734.60094 · doi:10.1287/mnsc.37.3.307
[34] Whitt, W. (2002).Stochastic-Process Limits:An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer, New York. · Zbl 0993.60001
[35] Wormald, N. C. (1995). Differential equations for random processes and random graphs.Ann. Appl. Probab.51217-1235. · Zbl 0847.05084 · doi:10.1214/aoap/1177004612
[36] Wu, S.
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.