On the Gittins index for multistage jobs

Loading...
Thumbnail Image

Access rights

openAccess

URL

Journal Title

Journal ISSN

Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Date

2022-12

Major/Subject

Mcode

Degree programme

Language

en

Pages

19
353-371

Series

QUEUEING SYSTEMS, Volume 102, issue 3-4

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.

Description

Keywords

Other note

Citation

Aalto, S & Scully, Z 2022, ' On the Gittins index for multistage jobs ', QUEUEING SYSTEMS, vol. 102, no. 3-4, pp. 353-371 . https://doi.org/10.1007/s11134-022-09760-z