{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T15:25:32Z","timestamp":1773156332946,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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":["Math Meth Oper Res"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the dynamic scheduling problem in a single-server multi-class queueing system, where the accumulated holding costs of a customer is a convexly increasing function of the time that the customer spends in the system. This problem was already addressed by van Mieghem in his seminal paper (Ann Appl Probab 5:808\u2013833, 1995). He launched the so-called generalized <jats:inline-formula><jats:alternatives><jats:tex-math>$$c\\mu $$<\/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:mi>\u03bc<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rule and proved its asymptotic optimality in the heavy traffic limit. The optimal scheduling problem with convex holding costs have also been studied in many other papers. However, the holding costs in these papers are typically count-convex, i.e., the aggregate holding cost rate related to a class of customers increases convexly as a function of the current number of customers in this class, which is clearly different from the time-convex holding costs introduced in van Mieghem (Ann Appl Probab 5:808\u2013833, 1995) and studied also in the present paper. We utilize the Whittle index approach to develop a novel heuristic policy for the dynamic scheduling problem with time-convex holding costs. Instead of the original open version of the continuous-time scheduling problem, we apply the Whittle index approach to the corresponding discrete-time closed version of the problem. As the main theoretical contribution, we prove that, for IHR service times, the discounted discrete-time problem is indexable and also give an explicit expression for the Whittle index itself. A special challenge in our model is the two-dimensional state space with an infinite number of possible states. By utilizing the discrete-time results, we develop a novel index policy for the original continuous-time problem and demonstrate, by numerical simulations, that this Whittle index policy outperforms the generalized <jats:inline-formula><jats:alternatives><jats:tex-math>$$c\\mu $$<\/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:mi>\u03bc<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rule. Thus, while the generalized <jats:inline-formula><jats:alternatives><jats:tex-math>$$c\\mu $$<\/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:mi>\u03bc<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rule is asymptotically optimal in the heavy traffic limit, it can still be improved in normal traffic conditions.<\/jats:p>","DOI":"10.1007\/s00186-024-00877-w","type":"journal-article","created":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T02:10:10Z","timestamp":1727230210000},"page":"603-634","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Whittle index approach to the multi-class queueing systems with convex holding costs and IHR service times"],"prefix":"10.1007","volume":"100","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1040-4095","authenticated-orcid":false,"given":"Samuli","family":"Aalto","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,20]]},"reference":[{"key":"877_CR1","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 (2009) On the Gittins index in the M\/G\/1 queue. Queue Syst 63:437\u2013458","journal-title":"Queue Syst"},{"key":"877_CR2","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/3179418","volume":"2","author":"A Anand","year":"2018","unstructured":"Anand A, de Veciana G (2018) A Whittle\u2019s index based approach for QoE optimization in wireless networks. Proc ACM Meas Anal Comput Syst 2:15","journal-title":"Proc ACM Meas Anal Comput Syst"},{"key":"877_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s001860200257","volume":"57","author":"PS Ansell","year":"2003","unstructured":"Ansell PS, Glazebrook KD, Ni\u00f1o-Mora J, O\u2019Keeffe M (2003) Whittle\u2019s index policy for a multi-class queueing system with convex holding costs. Math Methods Oper Res 57:21\u201339","journal-title":"Math Methods Oper Res"},{"key":"877_CR4","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00186-020-00731-9","volume":"93","author":"U Ayesta","year":"2021","unstructured":"Ayesta U, Gupta MK, Verloop IM (2021) On the computation of Whittle\u2019s index for Markovian restless bandits. Math Methods Oper Res 93:179\u2013208","journal-title":"Math Methods Oper Res"},{"key":"877_CR5","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s11134-012-9316-8","volume":"73","author":"CF Bispo","year":"2013","unstructured":"Bispo CF (2013) The single-server scheduling problem with convex costs. Queue Syst 73:261\u2013294","journal-title":"Queue Syst"},{"key":"877_CR6","volume-title":"Queues","author":"DR Cox","year":"1961","unstructured":"Cox DR, Smith WL (1961) Queues. Methuen, London"},{"key":"877_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00186-023-00821-4","volume":"97","author":"N Gast","year":"2023","unstructured":"Gast N, Gaujal B, Khun K (2023) Testing indexability and computing Whittle and Gittins index in subcubic time. Math Methods Oper Res 97:391\u2013436","journal-title":"Math Methods Oper Res"},{"key":"877_CR8","volume-title":"Multi-armed bandit allocation indices","author":"JC Gittins","year":"1989","unstructured":"Gittins JC (1989) Multi-armed bandit allocation indices. Wiley, New York"},{"key":"877_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1023\/A:1026060405346","volume":"45","author":"KD Glazebrook","year":"2003","unstructured":"Glazebrook KD, Lumley RR, Ansell PS (2003) Index heuristics for multiclass M\/G\/1 systems with nonpreemptive service and convex holding costs. Queue Syst 45:81\u2013111","journal-title":"Queue Syst"},{"key":"877_CR10","first-page":"191","volume":"28","author":"O Hern\u00e1ndez-Lerma","year":"1992","unstructured":"Hern\u00e1ndez-Lerma O, Mu\u00f1oz de Ozak M (1992) Discrete-time Markov control processes with discounted unbounded costs: optimality criteria. Kybernetica 28:191\u2013212","journal-title":"Kybernetica"},{"key":"877_CR11","doi-asserted-by":"crossref","unstructured":"Larra\u00f1aga M, Ayesta U, Verloop IM (2015) Stochastic and fluid index policies for resource allocation problems. In: Proceedings of IEEE Infocom, pp. 1230\u20131238","DOI":"10.1109\/INFOCOM.2015.7218498"},{"key":"877_CR12","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s11134-015-9445-y","volume":"81","author":"M Larra\u00f1aga","year":"2015","unstructured":"Larra\u00f1aga M, Ayesta U, Verloop IM (2015) Asymptotically optimal index policies for an abandonment queue with convex holding cost. Queue Syst 81:99\u2013169","journal-title":"Queue Syst"},{"key":"877_CR13","doi-asserted-by":"publisher","first-page":"3812","DOI":"10.1109\/TNET.2016.2562564","volume":"24","author":"M Larra\u00f1aga","year":"2016","unstructured":"Larra\u00f1aga M, Ayesta U, Verloop IM (2016) Dynamic control of birth-and-death restless bandits: application to resource-allocation problems. IEEE\/ACM Trans Netw 24:3812\u20133825","journal-title":"IEEE\/ACM Trans Netw"},{"key":"877_CR14","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1287\/opre.2019.1908","volume":"68","author":"Z Long","year":"2020","unstructured":"Long Z, Shimkin N, Zhang H, Zhang J (2020) Dynamic scheduling of multiclass many-server queues with abandonment: the generalized $$c\\mu \/h$$ rule. Oper Res 68:1218\u20131230","journal-title":"Oper Res"},{"key":"877_CR15","doi-asserted-by":"publisher","first-page":"836","DOI":"10.1287\/opre.1040.0152","volume":"52","author":"A Mandelbaum","year":"2004","unstructured":"Mandelbaum A, Stolyar S (2004) Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized $$c\\mu $$-rule. Oper Res 52:836\u2013855","journal-title":"Oper Res"},{"key":"877_CR16","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.3390\/math11071639","volume":"11","author":"J Ni\u00f1o-Mora","year":"2023","unstructured":"Ni\u00f1o-Mora J (2023) Markovian restless bandits and index policies: a review. Mathematics 11:1639","journal-title":"Mathematics"},{"key":"877_CR17","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0305-0548(94)00048-D","volume":"22","author":"M Shaked","year":"1995","unstructured":"Shaked M, Shanthikumar J, Valdez-Torres J (1995) Discrete hazard rate functions. Comput Oper Res 22:391\u2013402","journal-title":"Comput Oper Res"},{"key":"877_CR18","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1214\/aoap\/1177004706","volume":"5","author":"JA van Mieghem","year":"1995","unstructured":"van Mieghem JA (1995) Dynamic scheduling with convex delay costs: the generalized $$c\\mu $$ rule. Ann Appl Probab 5:808\u2013833","journal-title":"Ann Appl Probab"},{"key":"877_CR19","doi-asserted-by":"publisher","first-page":"1947","DOI":"10.1214\/15-AAP1137","volume":"26","author":"IM Verloop","year":"2016","unstructured":"Verloop IM (2016) Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Ann Appl Probab 26:1947\u20131995","journal-title":"Ann Appl Probab"},{"key":"877_CR20","doi-asserted-by":"publisher","first-page":"637","DOI":"10.2307\/3214547","volume":"27","author":"R Weber","year":"1990","unstructured":"Weber R, Weiss G (1990) On an index policy for restless bandits. J Appl Probab 27:637\u2013648","journal-title":"J Appl Probab"},{"key":"877_CR21","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1214\/aop\/1176994469","volume":"9","author":"P Whittle","year":"1981","unstructured":"Whittle P (1981) Arm-acquiring bandits. Ann Probab 9:284\u2013292","journal-title":"Ann Probab"},{"key":"877_CR22","doi-asserted-by":"publisher","first-page":"287","DOI":"10.2307\/3214163","volume":"25A","author":"P Whittle","year":"1988","unstructured":"Whittle P (1988) Restless bandits: activity allocation in a changing world. J Appl Probab 25A:287\u2013298","journal-title":"J Appl Probab"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-024-00877-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-024-00877-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-024-00877-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T11:02:42Z","timestamp":1733742162000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-024-00877-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,20]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["877"],"URL":"https:\/\/doi.org\/10.1007\/s00186-024-00877-w","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,20]]},"assertion":[{"value":"10 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declares that he has no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}