{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:55:26Z","timestamp":1777517726755,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T00:00:00Z","timestamp":1642377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T00:00:00Z","timestamp":1642377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2016\/23\/B\/ST1\/00492"],"award-info":[{"award-number":["2016\/23\/B\/ST1\/00492"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide two examples of strictly subcritical multiclass queueing networks which are unstable under the shortest remaining processing time (SRPT) service protocol. Both of them are reentrant lines with two servers and eight customer classes. The customer service times in our first system are deterministic, yielding an example of an unstable shortest remaining expected processing time (SERPT) network. In the second one, the service times in one customer class are randomized. Both our examples show also system instability under the shortest job first (SJF) discipline. A simulation study of robustness of our results with respect to changes in the customer interarrival and service times is also provided. Our results indicate that size-based service policies may not use the available resources efficiently in a multiserver network setting and in fact cause instability effects. This is in sharp contrast with their satisfactory performance for single-server queues.<\/jats:p>","DOI":"10.1007\/s11134-021-09733-8","type":"journal-article","created":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T14:05:08Z","timestamp":1642428308000},"page":"57-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Instability of SRPT, SERPT and SJF multiclass queueing networks"],"prefix":"10.1007","volume":"101","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3073-959X","authenticated-orcid":false,"given":"\u0141ukasz","family":"Kruk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3294-2794","authenticated-orcid":false,"given":"Tymoteusz","family":"Chojecki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,17]]},"reference":[{"key":"9733_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10479-008-0427-x","volume":"170","author":"S Aalto","year":"2009","unstructured":"Aalto, S., Ayesta, U.: SRPT applied to bandwidth sharing networks. Ann. Oper. Res. 170, 3\u201319 (2009)","journal-title":"Ann. Oper. Res."},{"key":"9733_CR2","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1214\/17-AAP1309","volume":"28","author":"R Atar","year":"2018","unstructured":"Atar, R., Biswas, A., Kaspi, H., Ramanan, K.: A Skorokhod map on measure-valued paths with applications to priority queues. Ann. Appl. Probab. 28, 418\u2013481 (2018)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR3","unstructured":"Atar, R., Shadmi, Y.: Fluid limits for earliest-deadline-first networks. arXiv:2009.07169v1 (2020)"},{"key":"9733_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1023\/A:1019191105117","volume":"32","author":"F Bacelli","year":"1999","unstructured":"Bacelli, F., Bonald, T.: Window flow control of FIFO networks with cross traffic. Queueing Syst. 32, 195\u2013231 (1999)","journal-title":"Queueing Syst."},{"key":"9733_CR5","first-page":"213","volume":"29","author":"J Banks","year":"1997","unstructured":"Banks, J., Dai, J.G.: Simulation studies of multiclass queueing networks. IIE Trans. 29, 213\u2013219 (1997)","journal-title":"IIE Trans."},{"key":"9733_CR6","unstructured":"Banerjee, S., Budhiraja, A., Puha, A.L.: Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions. arXiv: 2003.03655v1 (2020)"},{"key":"9733_CR7","unstructured":"Bender, M., Chakrabarti, S., Muthukrishnan, S.: Flow and stretch metrics for scheduling continuous job streams. In: Proceedings of the 9th annual ACM-SIAM symposium on discrete algorithms (1998)"},{"key":"9733_CR8","unstructured":"Botvich, D.D., Zamyatin, A.A.: Ergodicity of conservative communication networks. Rapport de Recherche 1772, INRIA (1992)"},{"key":"9733_CR9","first-page":"414","volume":"4","author":"M Bramson","year":"1994","unstructured":"Bramson, M.: Instability of FIFO queueing networks. Ann. Appl. Probab. 4, 414\u2013431 (1994)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR10","first-page":"693","volume":"4","author":"M Bramson","year":"1994","unstructured":"Bramson, M.: Instability of FIFO queueing networks with quick service times. Ann. Appl. Probab. 4, 693\u2013718 (1994)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01159391","volume":"22","author":"M Bramson","year":"1996","unstructured":"Bramson, M.: Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Syst. 22, 5\u201345 (1996)","journal-title":"Queueing Syst."},{"key":"9733_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01206549","volume":"23","author":"M Bramson","year":"1996","unstructured":"Bramson, M.: Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks. Queueing Syst. 23, 1\u201326 (1996)","journal-title":"Queueing Syst."},{"key":"9733_CR13","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1023\/A:1019182619288","volume":"28","author":"M Bramson","year":"1998","unstructured":"Bramson, M.: Stability of two families of queueing networks and a discussion of fluid limits. Queueing Syst. 28, 7\u201331 (1998)","journal-title":"Queueing Syst."},{"key":"9733_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1023\/A:1017987600517","volume":"39","author":"M Bramson","year":"2001","unstructured":"Bramson, M.: Stability of earliest-due-date, first-served queueing networks. Queueing Syst. 39, 79\u2013102 (2001)","journal-title":"Queueing Syst."},{"key":"9733_CR15","unstructured":"Bramson, M.: Stability of Queueing Networks. Lecture Notes in Mathematics, vol. 1950. Springer-Verlag, New York (2008)"},{"key":"9733_CR16","doi-asserted-by":"crossref","unstructured":"Brown, P.: Stability of networks with age-based scheduling. In: IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications, Barcelona, pp. 901-909 (2007)","DOI":"10.1109\/INFCOM.2007.110"},{"key":"9733_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-5301-1","volume-title":"Fundamentals of Queueing Networks","author":"H Chen","year":"2001","unstructured":"Chen, H., Yao, D.D.: Fundamentals of Queueing Networks. Springer, New York (2001)"},{"key":"9733_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1214\/aoap\/1177004828","volume":"5","author":"JG Dai","year":"1995","unstructured":"Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49\u201377 (1995)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1023\/A:1019184331042","volume":"22","author":"JG Dai","year":"1999","unstructured":"Dai, J.G., Hasenbein, J.J., Vande Vate, J.H.: Stability of a three-station fluid network. Queueing Syst. 22, 293\u2013325 (1999)","journal-title":"Queueing Syst."},{"key":"9733_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1214\/aoap\/1075828055","volume":"14","author":"JG Dai","year":"2004","unstructured":"Dai, J.G., Hasenbein, J.J., Vande Vate, J.H.: Stability and instability of a two-station queueing network. Ann. Appl. Probab. 14, 326\u2013377 (2004)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR21","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1287\/moor.21.1.115","volume":"21","author":"JG Dai","year":"1996","unstructured":"Dai, J.G., Weiss, G.: Stability and instability for fluid models of reentrant lines. Math. Oper. Res. 21, 115\u2013134 (1996)","journal-title":"Math. Oper. Res."},{"key":"9733_CR22","doi-asserted-by":"publisher","unstructured":"Dong, J., Ibrahim, R.: On the SRPT scheduling discipline in many-server queues with impatient customers. Manag. Sci. https:\/\/doi.org\/10.1287\/mnsc.2021.4110 (2021)","DOI":"10.1287\/mnsc.2021.4110"},{"key":"9733_CR23","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1287\/moor.1090.0409","volume":"34","author":"DG Down","year":"2009","unstructured":"Down, D.G., Gromoll, H.C., Puha, A.L.: Fluid limits for shortest remaining processing time queues. Math. Oper. Res. 34, 880\u2013911 (2009)","journal-title":"Math. Oper. Res."},{"key":"9733_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1019122115228","volume":"25","author":"V Dumas","year":"1997","unstructured":"Dumas, V.: A multiclass network with non-linear, non-convex, non-monotonic stability conditions. Queueing Syst. 25, 1\u201343 (1997)","journal-title":"Queueing Syst."},{"key":"9733_CR25","doi-asserted-by":"publisher","first-page":"74","DOI":"10.37394\/23206.2021.20.8","volume":"20","author":"R Gieroba","year":"2021","unstructured":"Gieroba, R., Kruk, \u0141: Minimality of SRPT networks with resource sharing. WSEAS Trans. Math. 20, 74\u201383 (2021)","journal-title":"WSEAS Trans. Math."},{"issue":"1","key":"9733_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/10-SSY016","volume":"1","author":"HC Gromoll","year":"2011","unstructured":"Gromoll, H.C., Kruk, \u0141, Puha, A.L.: Diffusion limits for shortest remaining processing time queues. Stochast. Syst. 1(1), 1\u201316 (2011)","journal-title":"Stochast. Syst."},{"key":"9733_CR27","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.peva.2018.10.001","volume":"127\u2013128","author":"I Grosof","year":"2018","unstructured":"Grosof, I., Scully, Z., Harchol-Balter, M.: SRPT for multiserver systems. Perform. Eval. 127\u2013128, 154\u2013175 (2018)","journal-title":"Perform. Eval."},{"key":"9733_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139226424","volume-title":"Performance Modeling and Design of Computer Systems: Queueing Theory in Action","author":"M Harchol-Balter","year":"2013","unstructured":"Harchol-Balter, M.: Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, Cambridge (2013)"},{"key":"9733_CR29","first-page":"179","volume":"28","author":"\u0141 Kruk","year":"2008","unstructured":"Kruk, \u0141: Stability of two families of real-time queueing networks. Probab. Math. Stat. 28, 179\u2013202 (2008)","journal-title":"Probab. Math. Stat."},{"key":"9733_CR30","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s11134-017-9553-y","volume":"88","author":"\u0141 Kruk","year":"2018","unstructured":"Kruk, \u0141: Stability of linear EDF networks with resource sharing. Queueing Syst. 88, 167\u2013203 (2018)","journal-title":"Queueing Syst."},{"key":"9733_CR31","first-page":"105","volume":"73","author":"\u0141 Kruk","year":"2019","unstructured":"Kruk, \u0141: Stability of preemptive EDF queueing networks. Ann. Univ. Mariae Curie-Sk\u0142odowska Math. A. 73, 105\u2013134 (2019)","journal-title":"Ann. Univ. Mariae Curie-Sk\u0142odowska Math. A."},{"key":"9733_CR32","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.orl.2020.11.009","volume":"49","author":"\u0141 Kruk","year":"2021","unstructured":"Kruk, \u0141: Instability of LAS multiclass queueing networks. Oper. Res. Lett. 49, 76\u201380 (2021)","journal-title":"Oper. Res. Lett."},{"key":"9733_CR33","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1109\/9.50339","volume":"35","author":"PR Kumar","year":"1990","unstructured":"Kumar, P.R., Seidman, T.I.: Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Trans. Automat. Control 35, 289\u2013298 (1990)","journal-title":"IEEE Trans. Automat. Control"},{"key":"9733_CR34","doi-asserted-by":"publisher","first-page":"1406","DOI":"10.1109\/9.106156","volume":"36","author":"SH Lu","year":"1991","unstructured":"Lu, S.H., Kumar, P.R.: Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Automat. Control 36, 1406\u20131416 (1991)","journal-title":"IEEE Trans. Automat. Control"},{"key":"9733_CR35","first-page":"124","volume":"4","author":"SP Meyn","year":"1994","unstructured":"Meyn, S.P., Down, D.: Stability of generalized Jackson networks. Ann. Appl. Probab. 4, 124\u2013148 (1994)","journal-title":"Ann. Appl. Probab."},{"issue":"6","key":"9733_CR36","doi-asserted-by":"publisher","first-page":"3381","DOI":"10.1214\/14-AAP1076","volume":"25","author":"AL Puha","year":"2015","unstructured":"Puha, A.L.: Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Ann. Appl. Probab. 25(6), 3381\u20133404 (2015)","journal-title":"Ann. Appl. Probab."},{"key":"9733_CR37","first-page":"199","volume":"28","author":"AN Rybko","year":"1992","unstructured":"Rybko, A.N., Stolyar, A.L.: Ergodicity of stochastic processes describing the operations of open queueing networks. Probl. Inf. Transm. 28, 199\u2013220 (1992)","journal-title":"Probl. Inf. Transm."},{"key":"9733_CR38","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"LE Schrage","year":"1968","unstructured":"Schrage, L.E.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 687\u2013690 (1968)","journal-title":"Oper. Res."},{"key":"9733_CR39","doi-asserted-by":"crossref","unstructured":"Seidman, T.I.: \u201cFirst come, first served\u201d can be unstable! IEEE Trans. Automat. Control 39, 2166\u20132171 (1994)","DOI":"10.1109\/9.328805"},{"key":"9733_CR40","volume-title":"Fundamentals of Queueing Networks","author":"R Serfozo","year":"1999","unstructured":"Serfozo, R.: Fundamentals of Queueing Networks. Springer, New York (1999)"},{"key":"9733_CR41","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.peva.2005.07.008","volume":"62","author":"M Verloop","year":"2005","unstructured":"Verloop, M., Borst, S., N\u00fa\u00f1ez-Queija, R.: Stability of size-based scheduling disciplines in resource-sharing networks. Perform. Eval. 62, 247\u2013262 (2005)","journal-title":"Perform. Eval."}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-021-09733-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-021-09733-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-021-09733-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,17]],"date-time":"2022-06-17T09:29:12Z","timestamp":1655458152000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-021-09733-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,17]]},"references-count":41,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9733"],"URL":"https:\/\/doi.org\/10.1007\/s11134-021-09733-8","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"value":"0257-0130","type":"print"},{"value":"1572-9443","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,17]]},"assertion":[{"value":"29 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}