Dynamic scheduling with convex delay costs revisited

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\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> 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\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> 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\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>μ</mml:mi> </mml:mrow> </mml:math> 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.