Coordination mechanisms for scheduling selfish jobs with favorite machines

This paper studies the favorite machine model, where each machine has different speed for different types of jobs. The model is a natural generalization of the two related machines model and captures the features of some real life problems, such as the CPU–GPU task scheduling, the two products scheduling and the cloud computing task scheduling. We are interested in the game-theoretic version of the scheduling problem in which jobs correspond to self-interested users and machines correspond to resources. The goal is to design coordination mechanisms (local policies) with a small price of anarchy (PoA) for the scheduling game of favorite machines. We first analyze the well known Makespan policy for our problem, and provide exact bounds on both the PoA and the strong PoA (SPoA). We also propose a new local policy, called FF-LPT, which outperforms several classical policies (e.g., LPT, SPT, FF-SPT and Makespan) in terms of the PoA, and guarantees fast convergence to a pure Nash equilibrium. Moreover, computational results show that the FF-LPT policy also dominates other policies for random instances, and reveal some insights for practical applications.