PROPERTIES OF THE GITTINS INDEX WITH APPLICATION TO OPTIMAL SCHEDULING

Abstract

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.