{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T08:17:37Z","timestamp":1775031457701,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T00:00:00Z","timestamp":1708300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T00:00:00Z","timestamp":1708300800000},"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":["Queueing Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the optimal scheduling problem in a multiserver queue with impatient customers belonging to multiple classes. We assume that each customer has a random abandonment time, after which the customer leaves the system if its service has not been completed before that. In addition, we assume that the scheduler is not able to anticipate the expiration of the abandonment times but only knows their distributions and how long each customer has been in the system. Many papers consider this scheduling problem under Poisson arrivals and linear holding costs assuming further that both the service times and the abandonment times have exponential distributions. Even with these additional assumptions, the exact solution is known only in very few special cases. To tackle this tricky problem, we apply the Whittle index approach. Unlike the earlier papers, which were restricted to exponential service times, we allow the service time distributions for which the hazard rate is decreasing. The Whittle index approach is applied to the discrete-time multiserver queueing problem with discounted costs. As our main theoretical result, we prove that the related relaxed optimization problem is indexable and derive the corresponding Whittle index explicitly. Based on this discrete-time result, we develop a reasonable heuristic for the original continuous-time multiserver scheduling problem. The performance of the resulting policy is evaluated in the M\/G\/<jats:italic>M<\/jats:italic> setup by numerical simulations, which demonstrate that it, indeed, gives better performance than the other policies included in the comparison.<\/jats:p>","DOI":"10.1007\/s11134-024-09902-5","type":"journal-article","created":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T16:03:12Z","timestamp":1708358592000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Whittle index approach to multiserver scheduling with impatient customers and DHR service times"],"prefix":"10.1007","volume":"107","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,2,19]]},"reference":[{"key":"9902_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.: On the Gittins index in the M\/G\/1 queue. Queueing Syst. 63, 437\u2013458 (2009)","journal-title":"Queueing Syst."},{"key":"9902_CR2","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1287\/opre.1100.0826","volume":"58","author":"R Atar","year":"2010","unstructured":"Atar, R., Giat, C., Shimkin, N.: The $$c\\mu \/\\theta $$ rule for many-server queues with abandonment. Oper. Res. 58, 1427\u20131439 (2010)","journal-title":"Oper. Res."},{"key":"9902_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s11134-010-9206-x","volume":"67","author":"R Atar","year":"2011","unstructured":"Atar, R., Giat, C., Shimkin, N.: On the asymptotic optimality of the $$c\\mu \/\\theta $$ rule under ergodic costs. Queueing Syst. 67, 127\u2013144 (2011)","journal-title":"Queueing Syst."},{"key":"9902_CR4","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1287\/moor.2013.0630","volume":"39","author":"R Atar","year":"2014","unstructured":"Atar, R., Kaspi, H., Shimkin, N.: Fluid limits for many-server systems with reneging under a priority policy. Math. Oper. Res. 39, 672\u2013696 (2014)","journal-title":"Math. Oper. Res."},{"key":"9902_CR5","doi-asserted-by":"crossref","unstructured":"Ayesta, U., Jacko, P., Novak, V.: A nearly-optimal index rule for scheduling of users with abandonment. In: Proc. of IEEE Infocom, pp. 2849\u20132857 (2011)","DOI":"10.1109\/INFCOM.2011.5935122"},{"key":"9902_CR6","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10951-015-0456-7","volume":"20","author":"U Ayesta","year":"2017","unstructured":"Ayesta, U., Jacko, P., Novak, V.: Scheduling of multi-class multi-server queueing systems with abandonments. J. Sched. 20, 129\u2013145 (2017)","journal-title":"J. Sched."},{"key":"9902_CR7","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10479-019-03131-3","volume":"317","author":"S Bhulai","year":"2022","unstructured":"Bhulai, S., Blok, H., Spieksma, F.: $$K$$ competing queues with customer abandonment: optimality of a generalised $$c\\mu $$-rule by the smoothed rate truncation method. Ann. Oper. Res. 317, 387\u2013416 (2022)","journal-title":"Ann. Oper. Res."},{"issue":"5","key":"9902_CR8","doi-asserted-by":"publisher","first-page":"1789","DOI":"10.1287\/opre.2022.2285","volume":"71","author":"G Chen","year":"2023","unstructured":"Chen, G., Gayon, J., Lemairec, P.: Stochastic scheduling with abandonment: necessary and sufficient conditions for the optimality of a strict priority policy. Oper. Res. 71(5), 1789\u20131793 (2023)","journal-title":"Oper. Res."},{"key":"9902_CR9","unstructured":"Cox, D., Smith, W.: Queues. Methuen (1961)"},{"key":"9902_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s11134-010-9201-2","volume":"67","author":"D Down","year":"2011","unstructured":"Down, D., Koole, G., Lewis, M.: Dynamic control of a single-server system with abandonments. Queueing Syst. 67, 63\u201390 (2011)","journal-title":"Queueing Syst."},{"key":"9902_CR11","volume-title":"Multi-armed Bandit Allocation Indices","author":"J Gittins","year":"1989","unstructured":"Gittins, J.: Multi-armed Bandit Allocation Indices. Wiley, Hoboken (1989)"},{"key":"9902_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1287\/msom.2017.0642","volume":"20","author":"J Kim","year":"2017","unstructured":"Kim, J., Randhawa, R., Ward, A.: Dynamic scheduling in a many-server, multiclass system: the role of customer impatience in large systems. Manuf. Serv. Oper. Manag. 20, 285\u2013301 (2017)","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"9902_CR13","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s11134-012-9325-7","volume":"75","author":"J Kim","year":"2013","unstructured":"Kim, J., Ward, A.: Dynamic scheduling of a GI\/GI\/1+GI queue with multiple customer classes. Queueing Syst. 75, 339\u2013384 (2013)","journal-title":"Queueing Syst."},{"key":"9902_CR14","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.peva.2013.08.009","volume":"70","author":"M Larra\u00f1aga","year":"2013","unstructured":"Larra\u00f1aga, M., Ayesta, U., Verloop, I.: Dynamic fluid-based scheduling in a multi-class abandonment queue. Perform. Eval. 70, 841\u2013858 (2013)","journal-title":"Perform. Eval."},{"key":"9902_CR15","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, I.: Asymptotically optimal index policies for an abandonment queue with convex holding cost. Queueing Syst. 81, 99\u2013169 (2015)","journal-title":"Queueing Syst."},{"key":"9902_CR16","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.: Dynamic scheduling of multiclass many-server queues with abandonment: the generalized $$c\\mu \/h$$ rule. Oper. Res. 68, 1218\u20131230 (2020)","journal-title":"Oper. Res."},{"key":"9902_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s11134-013-9342-1","volume":"75","author":"P Moyal","year":"2013","unstructured":"Moyal, P.: On queues with impatience: stability, and the optimality of earliest deadline first. Queueing Syst. 75, 211\u2013242 (2013)","journal-title":"Queueing Syst."},{"key":"9902_CR18","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\u2013background queue: a survey. Perform. Eval. 65, 286\u2013307 (2004)","journal-title":"Perform. Eval."},{"key":"9902_CR19","volume-title":"Applied Probability Models with Optimization Applications","author":"S Ross","year":"1970","unstructured":"Ross, S.: Applied Probability Models with Optimization Applications. Holden-Day, Toronto (1970)"},{"key":"9902_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3428328","volume":"4","author":"Z Scully","year":"2020","unstructured":"Scully, Z., Grosof, I., Harchol-Balter, M.: The Gittins policy is nearly optimal in the M\/G\/$$k$$ under extremely general conditions. Proc. ACM Meas. Anal. Comput. Syst. 4, 1\u201329 (2020)","journal-title":"Proc. ACM Meas. Anal. Comput. Syst."},{"key":"9902_CR21","doi-asserted-by":"crossref","unstructured":"Scully, Z., Harchol-Balter, M.: The Gittins policy in the M\/G\/1 queue. In: Proc. of WiOpt (2021)","DOI":"10.23919\/WiOpt52861.2021.9589051"},{"key":"9902_CR22","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.: Discrete hazard rate functions. Comput. Oper. Res. 22, 391\u2013402 (1995)","journal-title":"Comput. Oper. Res."},{"key":"9902_CR23","doi-asserted-by":"publisher","first-page":"1947","DOI":"10.1214\/15-AAP1137","volume":"26","author":"I Verloop","year":"2016","unstructured":"Verloop, I.: Asymptotically optimal priority policies for indexable and nonindexable restless bandits. Ann. Appl. Probab. 26, 1947\u20131995 (2016)","journal-title":"Ann. Appl. Probab."},{"key":"9902_CR24","doi-asserted-by":"publisher","first-page":"637","DOI":"10.2307\/3214547","volume":"27","author":"R Weber","year":"1990","unstructured":"Weber, R., Weiss, G.: On an index policy for restless bandits. J. Appl. Probab. 27, 637\u2013648 (1990)","journal-title":"J. Appl. Probab."},{"key":"9902_CR25","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1214\/aop\/1176994469","volume":"9","author":"P Whittle","year":"1981","unstructured":"Whittle, P.: Arm-acquiring bandits. Ann. Probab. 9, 284\u2013292 (1981)","journal-title":"Ann. Probab."},{"key":"9902_CR26","doi-asserted-by":"publisher","first-page":"287","DOI":"10.2307\/3214163","volume":"25A","author":"P Whittle","year":"1988","unstructured":"Whittle, P.: Restless bandits: activity allocation in a changing world. J. Appl. Probab. 25A, 287\u2013298 (1988)","journal-title":"J. Appl. Probab."}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-024-09902-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-024-09902-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-024-09902-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,7]],"date-time":"2024-06-07T10:09:08Z","timestamp":1717754948000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-024-09902-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,19]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9902"],"URL":"https:\/\/doi.org\/10.1007\/s11134-024-09902-5","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"value":"0257-0130","type":"print"},{"value":"1572-9443","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,19]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}