A Coordination Mechanism for a Scheduling Game with Uniform-Batching Machines

In this paper, we consider a scheduling problem with m uniform parallel-batching machines {M-1, M-2,..., M-m} under game situation. There are n jobs, each of which is associated with a load. Each machine M-i(1 <= i <= m) has a speed si and can handle up to b jobs simultaneously as a batch. The load of a batch is the load of the longest job in the batch. All the jobs in a batch start and complete at the same time. Each job is owned by an agent and its individual cost is the completion time of the job. The social cost is the largest completion time over all jobs, i.e., the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of Nash Equilibrium and offer an upper bound on the price of anarchy (POA) of the coordination mechanism. We present a greedy algorithm and show that: (i) under the coordination mechanism, any instance of the scheduling game problem has a unique Nash Equilibrium and it is precisely the schedule returned by the greedy algorithm; (ii) the mechanism has a POA no more than 1+ s(max)/(s) over bar (1-1/max{m, b}) + delta, where s(max) = max{s(1), s(2),..., s(m)}, (s) over bar = (s(1) + s(2) + ... + s(m))/m, and delta is a small positive number that tends to 0.