Anarchy in the UJ: Coordination mechanisms for minimizing the number of late jobs

We consider the distributed scheduling problem on parallel machines with the central objective of maximizing the number of on-time jobs. Jobs are self-interested utility-maximizers that can choose the machines they are processed on and are exclusively interested in reducing their own private objective function. Each machine processes the jobs according to a local policy. We discuss Nash equilibria in the resulting schedules and perform a thorough analysis of the resulting (absolute) prices of anarchy for various parallel machine environments, utilities of the agents, and local policies of the machines. We show that local policies that are based on simple sorting-based procedures like shortest processing time first (SPT) and earliest due date first (EDD) lead to big losses in welfare compared to the global optimum. However, when employing Moore-Hodgson's algorithm as a local policy, we can prove a price of anarchy of (2m−1)/m for identical machines and a price of anarchy of 2 for related and unrelated parallel machines. Moreover, we show how these results can be used to prove approximation ratios for greedy scheduling algorithms. This paper is the first to prove approximation ratios for two greedy scheduling procedures, turning them from simple heuristics into actual approximation ratios with a provable approximation ratio.