Control and optimization of single-server queues: the Gittins index approach revisited

Abstract : We consider the optimal scheduling problem for a single-server queue. We allow preemptions, and our purpose is to minimize the mean sojourn time. The optimal non-anticipating discipline is known to be the Gittins index policy, which, however, is de ned in an implicit way. Until now, its general behaviour in this speci c problem has been characterized only in a few special cases. In this presentation, we shed light on the properties of the Gittins index. Then we apply the properties to give as complete a characterization as possible for the Gittins index policy. It turns out that, in the static case without arrivals, the optimal policy always belongs to the family of Multi-Level-Processor-Sharing (MLPS) disciplines. For the dynamic case with Poisson arrivals (i.e. for the M/G/1 queue), the optimal policy is generally more complicated. However, we give new results that characterize the optimal policy even in this dynamic case.
Type de document :
Communication dans un congrès
NET-COOP 2010 - 4th Workshop on Network Control and Optimization, Nov 2010, Ghent, Belgium. 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00597565
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 1 juin 2011 - 13:41:52
Dernière modification le : mercredi 13 juin 2018 - 18:36:02

Identifiants

  • HAL Id : inria-00597565, version 1

Collections

Citation

Samuli Aalto. Control and optimization of single-server queues: the Gittins index approach revisited. NET-COOP 2010 - 4th Workshop on Network Control and Optimization, Nov 2010, Ghent, Belgium. 2010. 〈inria-00597565〉

Partager

Métriques

Consultations de la notice

18