{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:49:04Z","timestamp":1761324544545,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T00:00:00Z","timestamp":1693785600000},"content-version":"vor","delay-in-days":34,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2023528","DMS-2022448"],"award-info":[{"award-number":["DMS-2023528","DMS-2022448"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the optimal scheduling problem in the M\/G\/1 queue. While this is a thoroughly studied problem when the target is to minimize the mean delay, there are still open questions related to some other objective functions. In this paper, we focus on minimizing mean slowdown among non-anticipating polices, which may utilize the attained service of the jobs but not their remaining service time when making scheduling decisions. By applying the Gittins index approach, we give necessary and sufficient conditions for the jobs\u2019 service time distribution under which the well-known scheduling policies first come first served and foreground background are optimal with respect to the mean slowdown. Furthermore, we characterize the optimal non-anticipating policy in the multi-class case for certain types of service time distributions. In fact, our results cover a more general objective function than just the mean slowdown, since we allow the holding costs for a job to depend on its own service time <jats:italic>S<\/jats:italic> via a generic function <jats:italic>c<\/jats:italic>(<jats:italic>S<\/jats:italic>). When minimizing the mean slowdown, this function reads as <jats:inline-formula><jats:alternatives><jats:tex-math>$$c(x) = 1\/x$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>x<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s11134-023-09888-6","type":"journal-article","created":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T12:44:11Z","timestamp":1693831451000},"page":"187-210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimizing the mean slowdown in the M\/G\/1 queue"],"prefix":"10.1007","volume":"104","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1040-4095","authenticated-orcid":false,"given":"Samuli","family":"Aalto","sequence":"first","affiliation":[]},{"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,4]]},"reference":[{"key":"9888_CR1","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s11134-022-09777-4","volume":"100","author":"S Aalto","year":"2022","unstructured":"Aalto, S.: Minimizing the mean slowdown in a single-server queue. Queueing Syst. 100, 373\u2013375 (2022)","journal-title":"Queueing Syst."},{"key":"9888_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s11134-009-9141-x","volume":"63","author":"S Aalto","year":"2009","unstructured":"Aalto, S., Ayesta, U., Righter, R.: On the Gittins index in the M\/G\/1 queue. Queueing Syst. 63, 437\u2013458 (2009)","journal-title":"Queueing Syst."},{"key":"9888_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0269964811000015","volume":"25","author":"S Aalto","year":"2011","unstructured":"Aalto, S., Ayesta, U., Righter, R.: Properties of the Gittins index with application to optimal scheduling. Probab. Eng. Inf. Sci. 25, 269\u2013288 (2011)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9888_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s001860200257","volume":"57","author":"PS Ansell","year":"2003","unstructured":"Ansell, P.S., Glazebrook, K.D., Ni\u00f1o-Mora, J., O\u2019Keeffe, M.: Whittle\u2019s index policy for a multi-class queueing system with convex holding costs. Math. Methods Oper. Res. 57, 21\u201339 (2003)","journal-title":"Math. Methods Oper. Res."},{"key":"9888_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00453-004-1115-0","volume":"40","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Dhamdhere, K., K\u00f6nemann, J., Sinha, A.: Non-clairvoyant scheduling for minimizing mean slowdown. Algorithmica 40, 305\u2013318 (2004)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Becchetti, L., Leonardi, S.: Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. In: Proceedings of ACM STOC, pp. 94\u2013103 (2001)","key":"9888_CR6","DOI":"10.1145\/380752.380782"},{"issue":"2","key":"9888_CR7","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/959143.959165","volume":"31","author":"H Feng","year":"2003","unstructured":"Feng, H., Misra, V.: Mixed scheduling disciplines for network flows. ACM Sigmetrics Perform. Evaluat. Rev. 31(2), 36\u201339 (2003)","journal-title":"ACM Sigmetrics Perform. Evaluat. Rev."},{"key":"9888_CR8","volume-title":"Multi-armed Bandit Allocation Indices","author":"J Gittins","year":"1989","unstructured":"Gittins, J.: Multi-armed Bandit Allocation Indices. Wiley, New York (1989)"},{"key":"9888_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1023\/A:1026060405346","volume":"45","author":"KD Glazebrook","year":"2003","unstructured":"Glazebrook, K.D., Lumley, R.R., Ansell, P.S.: Index heuristics for multiclass M\/G\/1 systems with nonpreemptive service and convex holding costs. Queueing Syst. 45, 81\u2013111 (2003)","journal-title":"Queueing Syst."},{"doi-asserted-by":"crossref","unstructured":"Grosof, I., Scully, Z., Harchol-Balter, M., Scheller-Wolf, A.: Optimal scheduling in the multiserver-job model under heavy traffic. In: Proceedings of the ACM on Measurement and Analysis of Computing Systems 6, article 51 (2022)","key":"9888_CR10","DOI":"10.1145\/3570612"},{"key":"9888_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11134-020-09684-6","volume":"97","author":"M Harchol-Balter","year":"2021","unstructured":"Harchol-Balter, M.: Open problems in queueing theory inspired by datacenter computing. Queueing Syst. 97, 3\u201337 (2021)","journal-title":"Queueing Syst."},{"doi-asserted-by":"crossref","unstructured":"Hyyti\u00e4, E., Aalto, S., Penttinen, A.: Minimizing slowdown in heterogeneous size-aware dispatching systems. In: Proceedings of ACM Sigmetrics\/Performance, pp. 29\u201340 (2012)","key":"9888_CR12","DOI":"10.1145\/2318857.2254763"},{"issue":"6","key":"9888_CR13","doi-asserted-by":"publisher","first-page":"2637","DOI":"10.1109\/TNET.2018.2873606","volume":"26","author":"I Kadota","year":"2018","unstructured":"Kadota, I., Sinha, A., Uysal-Biyikoglu, E., Singh, R., Modiano, E.: Scheduling policies for minimizing age of information in broadcast wireless networks. IEEE\/ACM Trans. Netw. 26(6), 2637\u20132650 (2018)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9888_CR14","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1109\/TWC.2020.3032237","volume":"20","author":"A Maatouk","year":"2021","unstructured":"Maatouk, A., Kriouile, S., Assad, M., Ephremides, A.: On the optimality of the Whittle\u2019s index policy for minimizing the age of information. IEEE Trans. Wirel. Commun. 20, 1263\u20131277 (2021)","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"9888_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s11750-007-0025-0","volume":"15","author":"J Ni\u00f1o-Mora","year":"2007","unstructured":"Ni\u00f1o-Mora, J.: Dynamic priority allocation via restless bandit marginal productivity indices. TOP 15, 161\u2013198 (2007)","journal-title":"TOP"},{"key":"9888_CR16","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1016\/j.peva.2007.06.028","volume":"65","author":"M Nuyens","year":"2004","unstructured":"Nuyens, M., Wierman, A.: The foreground-background queue: A survey. Perform. Eval. 65, 286\u2013307 (2004)","journal-title":"Perform. Eval."},{"key":"9888_CR17","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1287\/opre.1070.0504","volume":"56","author":"M Nuyens","year":"2008","unstructured":"Nuyens, M., Wierman, A., Zwart, B.: Preventing large sojourn times using SMART scheduling. Oper. Res. 56, 88\u2013101 (2008)","journal-title":"Oper. Res."},{"key":"9888_CR18","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"L Schrage","year":"1968","unstructured":"Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 687\u2013690 (1968)","journal-title":"Oper. Res."},{"unstructured":"Scully, Z.: A new toolbox for scheduling theory. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA (2022)","key":"9888_CR19"},{"doi-asserted-by":"crossref","unstructured":"Scully, Z., Grosof, I., Harchol-Balter, M.: The Gittins policy is nearly optimal in the M\/G\/k under extremely general conditions. In: Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, article 43 (2020)","key":"9888_CR20","DOI":"10.1145\/3428328"},{"doi-asserted-by":"crossref","unstructured":"Scully, Z., Harchol-Balter, M.: The Gittins policy in the M\/G\/1 queue. In: Proceedings of WiOpt (2021)","key":"9888_CR21","DOI":"10.23919\/WiOpt52861.2021.9589051"},{"doi-asserted-by":"crossref","unstructured":"Scully, Z., Harchol-Balter, M., Scheller-Wolf, A.: Simple near-optimal scheduling for the M\/G\/1. In: Proceedings of the ACM on Measurement and Analysis of Computing Systems 4, article 11 (2020)","key":"9888_CR22","DOI":"10.1145\/3379477"},{"key":"9888_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/opre.26.1.197","volume":"26","author":"D Smith","year":"1978","unstructured":"Smith, D.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26, 197\u2013199 (1978)","journal-title":"Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Tripathi, V., Modiano, E.: A Whittle index approach to minimizing functions of age of information. In: Proceedings of Allerton Conference on Communication, Control, and Computing, pp. 1160\u20131167 (2019)","key":"9888_CR24","DOI":"10.1109\/ALLERTON.2019.8919842"},{"key":"9888_CR25","first-page":"262","volume":"14","author":"G von Olivier","year":"1972","unstructured":"von Olivier, G.: Kostenminimale Priorit\u00e4ten in Wartesystemen vom Typ M\/G\/1 [Cost-minimum priorities in queueing systems of type M\/G\/1]. Elektronische Rechenanlagen 14, 262\u2013271 (1972)","journal-title":"Elektronische Rechenanlagen"},{"doi-asserted-by":"crossref","unstructured":"Wierman, A., Harchol-Balter, M., Osogami, T.: Nearly insensitive bounds for SMART scheduling. In: Proceedings of ACM Sigmetrics, pp. 205\u2013216 (2005)","key":"9888_CR26","DOI":"10.1145\/1071690.1064236"},{"unstructured":"Yang, S., de Veciana, G.: Size-based adaptive bandwidth allocation: optimizing the average QoS for elastic flows. In: Proceedings of IEEE Infocom, pp. 657\u2013666 (2002)","key":"9888_CR27"},{"key":"9888_CR28","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1109\/TNET.2004.826280","volume":"12","author":"SJ Yang","year":"2004","unstructured":"Yang, S.J., de Veciana, G.: Enhancing both network and user performance for networks supporting Best Effort traffic. IEEE\/ACM Trans. Netw. 12, 349\u2013360 (2004)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"9888_CR29","doi-asserted-by":"publisher","first-page":"2343","DOI":"10.1109\/TAC.2018.2807924","volume":"63","author":"Z Yu","year":"2018","unstructured":"Yu, Z., Xu, Y., Tong, L.: Deadline scheduling as restless bandits. IEEE Trans. Autom. Control 63, 2343\u20132358 (2018)","journal-title":"IEEE Trans. Autom. Control"}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-023-09888-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-023-09888-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-023-09888-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T11:20:41Z","timestamp":1694604041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-023-09888-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":29,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["9888"],"URL":"https:\/\/doi.org\/10.1007\/s11134-023-09888-6","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"type":"print","value":"0257-0130"},{"type":"electronic","value":"1572-9443"}],"subject":[],"published":{"date-parts":[[2023,8]]},"assertion":[{"value":"18 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}