Inducing Optimal Scheduling with Selfish Users

It is well known that scheduling jobs according to the Shortest-Remaining-Processing-Time (SRPT) policy is optimal for minimizing mean response time in a single-server system with online arrivals. Unfortunately, SRPT scheduling requires users to reveal their job size (service requirement), which is not always realistic. This may be because some users are informed, but selsh (or rational): they know their job size but are willing to lie about it if that is to their advantage. Alternatively, users may be uninformed { they may genuinely not know their size. Complicating matters further, the system administrator may not be able to differentiate between users of these two types. This adds significant complications to the management of such systems, as threats that are credible to force informed users to reveal their size may be unfair to uninformed users. This situation is common in supercomputing environments, for example.To cope with such a situation we develop a novel approach for inducing the informed users into self- scheduling themselves according to (an approximation of) SRPT while not, unfairly, penalizing the uninformed users.We achieve this by defining a game that users play, applying priority-boosting tokens to portions of their job. For the informed users, we characterize the features of a unique equilibrium self-scheduling policy. We prove that the equilibrium policy is a dominant strategy, i.e. no user has any incentive to follow any other strategy, regardless of other users' behavior. We show that the optimal strategy of uninformed users is highly complex and may lead to multiple, potentially unstable, equilibria. Then, via queueing-theoretic analysis, we evaluate the effectiveness of our game as a function of job size variability, load, and other system parameters. We find that our game results in a near approximation of SRPT scheduling for informed users when the appropriate number of tokens (which we can determine) is distributed.