Coordination mechanisms from (almost) all scheduling policies

Abstract

We study the price of anarchy of coordination mechanisms for a scheduling problem where each job j has a weight wj, processing time pij, assignment cost hij, and communication delay (or release date) rij, on machine i. Each machine is free to declare its own scheduling policy. Each job is a selfish agent and selects a machine that minimizes its own disutility, which is equal to its weighted completion time plus its assignment cost. The goal is to minimize the total disutility incurred by all the jobs. Our model is general enough to capture scheduling jobs in a distributed environment with heterogeneous machines (or data centers) that are situated across different locations.