Minimizing the mean slowdown in the M/G/1 queue

Samuli Aalto () and Ziv Scully
Additional contact information
Samuli Aalto: Aalto University
Ziv Scully: Cornell University

Queueing Systems: Theory and Applications, 2023, vol. 104, issue 3, No 4, 187-210

Abstract: 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$$ c ( x ) = 1 / x .

Keywords: Optimal scheduling; M/G/1; Slowdown; Gittins index; FCFS; FB; 60K25; 90B22; 90B36; 68M20 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-023-09888-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:104:y:2023:i:3:d:10.1007_s11134-023-09888-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-023-09888-6

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().