×

Properties of the Gittins index with application to optimal scheduling. (English) Zbl 1233.90104

Summary: We consider the optimal scheduling problem for a single-server queue without arrivals. We allow preemptions, and our purpose is to minimize the expected flow time. The optimal nonanticipating discipline is known to be the Gittins index policy, which, however, is defined in an implicit way. Until now, its general behavior in this specific problem has been characterized only in a few special cases. In this article, we give as complete a characterization as possible. It turns out that the optimal policy always belongs to the family of multilevel processor sharing disciplines.

MSC:

90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.2307/3214660 · Zbl 0706.60086 · doi:10.2307/3214660
[2] DOI: 10.1017/S0269964800001194 · Zbl 1134.90413 · doi:10.1017/S0269964800001194
[3] Pinedo, Scheduling – theory, algorithms, and systems (1995)
[4] Kleinrock, Queueing systems, (1976) · Zbl 0361.60082
[5] Sevcik, Journal of the Association for Computing Machinery 21 pp 66– (1974) · Zbl 0271.68047 · doi:10.1145/321796.321803
[6] Gelenbe, Analysis and synthesis of computer systems (1980) · Zbl 0484.68026
[7] DOI: 10.1007/s11134-009-9141-x · Zbl 1209.90100 · doi:10.1007/s11134-009-9141-x
[8] DOI: 10.1145/1243401.1243409 · Zbl 05443459 · doi:10.1145/1243401.1243409
[9] DOI: 10.1007/BF01182931 · Zbl 0648.68050 · doi:10.1007/BF01182931
[10] Gittins, Multi-armed bandit allocation indices (1989) · Zbl 0699.90068
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.