Dynamic scheduling with convex delay costs revisited
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
48
Series
Queueing Systems, Volume 110, issue 1
Abstract
We consider the dynamic scheduling problem in a multi-server queue with Poisson arrivals, independent service times, and multiple customer classes with convex delay costs. This problem was already studied by van Mieghem (Ann Appl Probab 5:808–833, 1995) in his seminal paper. He launched the generalized cμ rule and proved its asymptotic optimality in the heavy traffic limit for a single-server system. Mandelbaum and Stolyar (Oper Res 52:836–855, 2004) generalized this asymptotic result for multi-server systems. While the generalized cμ rule is a near-optimal scheduling policy under heavy traffic, it can still be improved in normal traffic conditions. This was demonstrated in Aalto (Math Methods Oper Res 100:603–634, 2024), where we applied the Whittle index approach to develop an index policy for the dynamic scheduling problem assuming IHR service times. In this paper, we continue applying the Whittle index approach, and our aim is to get rid of the restrictive IHR assumption mentioned above. As the main theoretical contribution, we prove that the corresponding discrete-time problem with discounted costs is indexable even for non-IHR service time distributions. In addition, we give an explicit characterization of the corresponding Whittle index. By utilizing the discrete-time results, we develop a novel index policy for the original continuous-time dynamic scheduling problem. The performance of the developed Whittle index policy for convex delay costs is studied by numerical simulations. In this numerical study, we demonstrate that the Whittle index policy performs systematically better than the generalized cμ rule and the other scheduling policies included in the comparison. The numerical results also hint that applying the developed Whittle index policy is most efficient in single-server systems with customers that have highly varying service times.Description
Other note
Citation
Aalto, S 2025, 'Dynamic scheduling with convex delay costs revisited', Queueing Systems, vol. 110, no. 1, 2. https://doi.org/10.1007/s11134-025-09961-2