{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:37:13Z","timestamp":1780591033675,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Order-independent (OI) queues, introduced by Berezner et al. (Queueing Syst 19(4):345\u2013359, 1995), expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&amp;S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be <jats:italic>swapped<\/jats:italic> with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&amp;S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&amp;S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&amp;S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&amp;S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints.<\/jats:p>","DOI":"10.1007\/s11134-021-09700-3","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T05:02:40Z","timestamp":1618203760000},"page":"275-331","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Pass-and-swap queues"],"prefix":"10.1007","volume":"98","author":[{"given":"C\u00e9line","family":"Comte","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6403-6377","authenticated-orcid":false,"given":"Jan-Pieter","family":"Dorsman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"9700_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/j.peva.2018.10.005","volume":"127\u2013128","author":"IJBF Adan","year":"2018","unstructured":"Adan, I.J.B.F., Kleiner, I., Righter, R., Weiss, G.: FCFS parallel service systems and matching models. Perform. Eval. 127\u2013128, 253\u2013272 (2018)","journal-title":"Perform. Eval."},{"issue":"3","key":"9700_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1017\/S0269964812000034","volume":"26","author":"IJBF Adan","year":"2012","unstructured":"Adan, I.J.B.F., Weiss, G.: A loss system with skill-based servers under assign to longest idle server policy. Probab. Eng. Inf. Sci. 26(3), 307\u2013321 (2012)","journal-title":"Probab. Eng. Inf. Sci."},{"issue":"1","key":"9700_CR3","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/13-SSY117","volume":"4","author":"IJBF Adan","year":"2014","unstructured":"Adan, I.J.B.F., Weiss, G.: A skill based parallel service system under FCFS-ALIS\u2014steady state, overloads, and abandonments. Stoch. Syst. 4(1), 250\u2013299 (2014)","journal-title":"Stoch. Syst."},{"key":"9700_CR4","doi-asserted-by":"crossref","unstructured":"Ayesta, U., Bodas, T., Dorsman, J.L., Verloop, I.M.: A token-based central queue with order-independent service rates. Oper. Res. (2021) To appear","DOI":"10.1287\/opre.2020.2088"},{"key":"9700_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.peva.2018.09.008","volume":"127\u2013128","author":"U Ayesta","year":"2018","unstructured":"Ayesta, U., Bodas, T., Verloop, I.M.: On a unifying product form framework for redundancy models. Perform. Eval. 127\u2013128, 93\u2013119 (2018)","journal-title":"Perform. Eval."},{"issue":"2","key":"9700_CR6","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321879.321887","volume":"22","author":"F Baskett","year":"1975","unstructured":"Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2), 248\u2013260 (1975)","journal-title":"J. ACM"},{"issue":"4","key":"9700_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BF01151928","volume":"19","author":"SA Berezner","year":"1995","unstructured":"Berezner, S.A., Kriel, C.F., Krzesinski, A.E.: Quasi-reversible multiclass queues with order independent departure rates. Queueing Syst. 19(4), 345\u2013359 (1995)","journal-title":"Queueing Syst."},{"issue":"1\u20134","key":"9700_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/BF01206565","volume":"23","author":"SA Berezner","year":"1996","unstructured":"Berezner, S.A., Krzesinski, A.E.: Order independent loss queues. Queueing Syst. 23(1\u20134), 331\u2013335 (1996)","journal-title":"Queueing Syst."},{"key":"9700_CR9","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.peva.2017.08.006","volume":"116","author":"T Bonald","year":"2017","unstructured":"Bonald, T., Comte, C.: Balanced fair resource sharing in computer clusters. Perform. Eval. 116, 70\u201383 (2017)","journal-title":"Perform. Eval."},{"key":"9700_CR10","doi-asserted-by":"crossref","unstructured":"Boucherie, R.J., van Dijk, N.M. (eds.): Queueing networks: A fundamental approach. International Series in Operations Research & Management Science. Springer, US (2011)","DOI":"10.1007\/978-1-4419-6472-4"},{"key":"9700_CR11","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-1-4419-6472-4_5","volume-title":"Queueing Networks: A Fundamental Approach. International Series in Operations Research & Management Science","author":"X Chao","year":"2011","unstructured":"Chao, X.: Networks with customers, signals, and product form solution. Queueing Networks: A Fundamental Approach. International Series in Operations Research & Management Science, pp. 217\u2013267. Springer, Boston (2011)"},{"key":"9700_CR12","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.comcom.2019.05.007","volume":"144","author":"C Comte","year":"2019","unstructured":"Comte, C.: Dynamic load balancing with tokens. Comput. Commun. 144, 76\u201388 (2019)","journal-title":"Comput. Commun."},{"key":"9700_CR13","unstructured":"Comte, C.: Resource management in computer clusters: algorithm design and performance analysis. PhD Thesis, Institut Polytechnique de Paris (2019)"},{"issue":"1","key":"9700_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11134-020-09668-6","volume":"96","author":"KS Gardner","year":"2020","unstructured":"Gardner, K.S., Righter, R.: Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview. Queueing Syst. 96(1), 3\u201351 (2020)","journal-title":"Queueing Syst."},{"issue":"3\u20134","key":"9700_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s11134-016-9485-y","volume":"83","author":"KS Gardner","year":"2016","unstructured":"Gardner, K.S., Zbarsky, S., Doroudi, S., Harchol-Balter, M., Hyyti\u00e4, E., Scheller-Wolf, A.: Queueing with redundant requests: exact analysis. Queueing Syst. 83(3\u20134), 227\u2013259 (2016)","journal-title":"Queueing Syst."},{"issue":"4","key":"9700_CR16","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1287\/opre.5.4.518","volume":"5","author":"JR Jackson","year":"1957","unstructured":"Jackson, J.R.: Networks of waiting lines. Oper. Res. 5(4), 518\u2013521 (1957)","journal-title":"Oper. Res."},{"key":"9700_CR17","volume-title":"Reversibility and Stochastic Networks","author":"FP Kelly","year":"2011","unstructured":"Kelly, F.P.: Reversibility and Stochastic Networks. Cambridge University Press, Cambridge (2011)"},{"key":"9700_CR18","doi-asserted-by":"crossref","unstructured":"Kelly, F.P., Walrand, J.: Networks of quasi-reversible nodes. In: Applied Probability-Computer Science: The Interface Volume 1, Progress in Computer Science, pp. 3\u201329. Birkh\u00e4user, Boston (1982)","DOI":"10.1007\/978-1-4612-5791-2_1"},{"key":"9700_CR19","doi-asserted-by":"crossref","unstructured":"Krzesinski, A.E.: Order independent queues. In: Boucherie, R.J., van Dijk, N.M. (eds.) Queueing networks: A fundamental approach. number 154 in International Series in Operations Research & Management Science, pp. 85\u2013120. Springer, US (2011)","DOI":"10.1007\/978-1-4419-6472-4_2"},{"issue":"2","key":"9700_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1017\/S0269964800002412","volume":"6","author":"AE Krzesinski","year":"1992","unstructured":"Krzesinski, A.E., Schassberger, R.: Product form solutions for multiserver centers with hierarchical concurrency constraints. Probab. Eng. Inf. Sci. 6(2), 147\u2013156 (1992)","journal-title":"Probab. Eng. Inf. Sci."},{"issue":"1","key":"9700_CR21","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/317531.317541","volume":"14","author":"J-Y Le Boudec","year":"1986","unstructured":"Le Boudec, J.-Y.: A BCMP extension to multiserver stations with concurrent classes of customers. SIGMETRICS Perform. Eval. Rev. 14(1), 78\u201391 (1986)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"9700_CR22","unstructured":"Moyal, P., Busic, A., Mairesse, J.: A product form for the general stochastic matching model. arXiv:1711.02620 [math] (2020)"},{"key":"9700_CR23","volume-title":"Poisson Departure Processes and Queueing Networks","author":"RR Muntz","year":"1972","unstructured":"Muntz, R.R.: Poisson Departure Processes and Queueing Networks. IBM Thomas J. Watson Research Centre, Yorktown Heights (1972)"},{"key":"9700_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1482-3","volume-title":"Introduction to Stochastic Networks. Stochastic Modelling and Applied Probability","author":"R Serfozo","year":"1999","unstructured":"Serfozo, R.: Introduction to Stochastic Networks. Stochastic Modelling and Applied Probability. Springer, Cham (1999)"},{"key":"9700_CR25","doi-asserted-by":"crossref","unstructured":"Van Dijk, N.M.: On practical product form characterizations. In: Boucherie, R.J., van Dijk, N.M. (eds.) Queueing networks: a fundamental approach. International Series in Operations Research & Management Science, pp. 1\u201383. Springer, Boston (2011)","DOI":"10.1007\/978-1-4419-6472-4_1"}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-021-09700-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-021-09700-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-021-09700-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,24]],"date-time":"2021-08-24T06:17:36Z","timestamp":1629785856000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-021-09700-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":25,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["9700"],"URL":"https:\/\/doi.org\/10.1007\/s11134-021-09700-3","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"value":"0257-0130","type":"print"},{"value":"1572-9443","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,12]]},"assertion":[{"value":"24 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}