A scheduling game on parallel batch machines with setup cost
摘要
We consider a scheduling game with parallel batch machines and independent jobs. Each batch has a constant setup cost. The objective of a job is to minimize its own cost, which is the weighted sum of its completion time and its share of the setup cost. A coordination mechanism consists of a rule for sharing the setup cost and a policy to schedule all jobs on the machines. The objective of the scheduling system is to minimize the maximum cost of all jobs. We propose a 0-1 sharing rule and prove that it guarantees the existence of a pure strategy Nash equilibrium under a greedy batch policy based on the longest processing time first rule. Furthermore, we demonstrate that such a guarantee does not exist for any other sharing rule under any greedy batch policy. Also, we design an algorithm based on the longest processing time first rule, and show that the set of schedules obtainable is precisely the set of pure strategy Nash equilibria of our scheduling game. Finally, we propose an efficient coordination mechanism with the 0-1 sharing rule and the greedy batch policy, and establish the upper and lower bounds of its price of anarchy, i.e., the ratio of the system objective value of the worst Nash equilibrium and the optimal system objective value. These bounds depend on the number of machines, the setup cost and the processing times of jobs.