×

Reversibility and further properties of FCFS infinite bipartite matching. (English) Zbl 1433.60080

Summary: The model of FCFS infinite bipartite matching was introduced in [R. Caldentey et al., Adv. Appl. Probab. 41, No. 3, 695–730 (2009; Zbl 1247.90099)]. In this model, there is a sequence of items that are chosen i.i.d. from a finite set \(\mathcal{C}\) and an independent sequence of items that are chosen i.i.d. from a finite set \(\mathcal{S} \), and a bipartite compatibility graph \(G\) between \(\mathcal{C}\) and \(\mathcal{S} \). Items of the two sequences are matched according to the compatibility graph, and the matching is FCFS, meaning that each item in the one sequence is matched to the earliest compatible unmatched item in the other sequence. In [I. Adan and G. Weiss, Oper. Res. 60, No. 2, 475–489 (2012; Zbl 1298.60089)], a Markov chain associated with the matching was analyzed, a condition for stability was derived, and a product form stationary distribution was obtained. In the current paper, we present several new results that unveil the fundamental structure of the model. First, we provide a pathwise Loynes’ type construction which enables to prove the existence of a unique matching for the model defined over all the integers. Second, we prove that the model is dynamically reversible: we define an exchange transformation in which we interchange the positions of each matched pair, and show that the items in the resulting permuted sequences are again independent and i.i.d., and the matching between them is FCFS in reversed time. Third, we obtain product form stationary distributions of several new Markov chains associated with the model. As a by-product, we compute useful performance measures, for instance the link lengths between matched items.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adan I, Boon M, Weiss G (2013) Design and evaluation of call centers with skill based routing, under FCFS policies. Performance Evaluation 70(10):873-888.Crossref, Google Scholar · doi:10.1016/j.peva.2013.08.007
[2] Adan I, Boon M, Weiss G (2014) Design heuristic for parallel many server systems under FCFS-ALIS. Preprint arXiv:1603.01404.Google Scholar
[3] Adan I, Hurkens CAJ, Weiss G (2010) A reversible multi-class multi-server loss system. Probab. Engrg. Informational Sci. 24(4):535-548.Crossref, Google Scholar · Zbl 1235.60124 · doi:10.1017/S0269964810000161
[4] Adan I, Weiss G (2012) Exact FCFS matching rates for two infinite multi-type sequences. Oper. Res. 60(2):475-489.Link, Google Scholar · Zbl 1298.60089
[5] Adan I, Weiss G (2012) A loss system with skill based servers under assign to longest idle server policy. Probab. Engrg. Informational Sci. 26(3):307-321.Crossref, Google Scholar · Zbl 1277.60149 · doi:10.1017/S0269964812000034
[6] Adan I, Weiss G (2014) A skill based parallel service system under FCFS-ALIS—Steady state, overloads, and abandonments. Stochastic Systems 4(1):1-50.Link, Google Scholar · Zbl 1305.60091
[7] Baccelli F, Brémaud P (2003) Elements of Queueing Theory (Springer, Berlin).Crossref, Google Scholar · Zbl 1021.60001 · doi:10.1007/978-3-662-11657-9
[8] Bušić A, Gupta V, Mairesse J (2013) Stability of the bipartite matching model. Adv. Appl. Probab. 45(2):351-378.Crossref, Google Scholar · Zbl 1274.60228 · doi:10.1239/aap/1370870122
[9] Caldentey R, Kaplan EH, Weiss G (2009) FCFS infinite bipartite matching of servers and customers. Adv. Appl. Probab. 41(3):695-730.Crossref, Google Scholar · Zbl 1247.90099 · doi:10.1239/aap/1253281061
[10] Foss S, Chernova N (1998) On the stability of a partially accessible multistation queue with state-dependent routing. Queueing Systems 29(1):55-73.Crossref, Google Scholar · Zbl 0915.60089 · doi:10.1023/A:1019175812444
[11] Kaplan EH (1984) Managing the demand for public housing. ORC technical report # 183, MIT, Cambridge, MA.Google Scholar
[12] Kaplan EH (1988) A public housing queue with reneging and task-specific servers. Decision Sci. 19(2):383-391.Crossref, Google Scholar · doi:10.1111/j.1540-5915.1988.tb00274.x
[13] Kelly FP (1979) Reversibility and Stochastic Networks (John Wiley & Sons, New York).Google Scholar · Zbl 0422.60001
[14] Loynes RM (1962) The stability of a queue with non-independent inter-arrival and service times. Math. Proc. Cambridge Philos. Soc. 58(3):497-520.Crossref, Google Scholar · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[15] Mairesse J, Moyal P (2014) Stability of the stochastic matching model. Preprint arXiv:1404.6677.Google Scholar
[16] Øksendal B (2003) Stochastic Differential Equations (Springer, Berlin).Crossref, Google Scholar · Zbl 1025.60026 · doi:10.1007/978-3-642-14394-6
[17] Talreja R, Whitt W (2008) Fluid Models for overloaded multi-class many-service queueing systems with FCFS routing. Management Sci. 54(8):1513-1527.Link, Google Scholar · Zbl 1232.90156
[18] Visschers J, Adan I, Weiss G (2012) A product form solution to a system with multi-type jobs and multi-type servers. Queueing Systems 70(3):269-298.Crossref, Google Scholar · Zbl 1275.60091 · doi:10.1007/s11134-011-9274-6
[19] Visschers J (2000) Random walks with geometric jumps. PhD Thesis, · Zbl 0974.60080
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.