Minimizing the mean slowdown in the M/G/1 queue
Loading...
Access rights
openAccess
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)
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
Major/Subject
Mcode
Degree programme
Language
en
Pages
24
Series
QUEUEING SYSTEMS, Volume 104, issue 3-4, pp. 187-210
Abstract
We consider the optimal scheduling problem in the M/G/1 queue. While this is a thoroughly studied problem when the target is to minimize the mean delay, there are still open questions related to some other objective functions. In this paper, we focus on minimizing mean slowdown among non-anticipating polices, which may utilize the attained service of the jobs but not their remaining service time when making scheduling decisions. By applying the Gittins index approach, we give necessary and sufficient conditions for the jobs’ service time distribution under which the well-known scheduling policies first come first served and foreground background are optimal with respect to the mean slowdown. Furthermore, we characterize the optimal non-anticipating policy in the multi-class case for certain types of service time distributions. In fact, our results cover a more general objective function than just the mean slowdown, since we allow the holding costs for a job to depend on its own service time S via a generic function c(S). When minimizing the mean slowdown, this function reads as c(x) = 1 / x .Description
Keywords
Other note
Citation
Aalto, S & Scully, Z 2023, 'Minimizing the mean slowdown in the M/G/1 queue', QUEUEING SYSTEMS, vol. 104, no. 3-4, pp. 187-210. https://doi.org/10.1007/s11134-023-09888-6