On the Gittins index for multistage jobs

Samuli Aalto, Ziv Scully

Research output: Contribution to journalArticleScientificpeer-review

54 Downloads (Pure)

Abstract

Optimal scheduling in single-server queueing systems is a classic problem in queueing theory. The Gittins index policy is known to be the optimal nonanticipating policy minimizing the mean delay in the M/G/1 queue. While the Gittins index is thoroughly characterized for ordinary jobs whose state is described by the attained service, it is not at all the case with jobs that have more complex structure. Recently, a class of such jobs, multistage jobs, were introduced, and it was shown that the computation of Gittins index of a multistage job decomposes into separable computations for the individual stages. The characterization is, however, indirect in the sense that it relies on the recursion for an auxiliary function (the so-called SJP—single-job profit—function) and not for the Gittins index itself. In this paper, we focus on sequential multistage jobs, which have a fixed sequence of stages, and prove that, for them, it is possible to compute the Gittins index directly by recursively combining the Gittins indices of its individual stages. In addition, we give sufficient conditions for the optimality of the FCFS and SERPT disciplines for scheduling sequential multistage jobs. On the other hand, we demonstrate that, for nonsequential multistage jobs, it is better to compute the Gittins index by utilizing the SJP functions.
Original languageEnglish
Pages (from-to)353-371
Number of pages19
JournalQUEUEING SYSTEMS
Volume102
Issue number3-4
Early online date7 Apr 2022
DOIs
Publication statusPublished - Dec 2022
MoE publication typeA1 Journal article-refereed

Fingerprint

Dive into the research topics of 'On the Gittins index for multistage jobs'. Together they form a unique fingerprint.

Cite this