Whittle index approach to the multi-class queueing systems with convex holding costs and IHR service times
Loading...
Access rights
openAccess
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)
Other link related to publication (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)
Other link related to publication (opens in new window)
Authors
Date
2024-09-20
Major/Subject
Mcode
Degree programme
Language
en
Pages
32
Series
Mathematical Methods of Operations Research
Abstract
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 [18]. He launched the so-called generalized cμ 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 [18] 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 discretetime 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 cμ rule. Thus, while the generalized cμ rule is asymptotically optimal in the heavy traffic limit, it can still be improved in normal traffic conditions.Description
Keywords
Whittle index, Single-server, Generalized cμ rule, Multi-class queueing systems, Optimal scheduling, Convex holding costs
Other note
Citation
Aalto, S 2024, ' Whittle index approach to the multi-class queueing systems with convex holding costs and IHR service times ', Mathematical Methods of Operations Research . https://doi.org/10.1007/s00186-024-00877-w