A Study On Coordination Mechanisms Of Several Scheduling Game Problems

Scheduling theory is an important part of Operations Research. In the pastseveral decades, the main studies of researchers concentrate on the algorithms of thescheduling problems. In their models, jobs follow the arrangement of the algorithms.But there are a lot of problems in which the jobs are independent and selfish. The onlyinterest of these jobs is the profit of themselves, ignoring the waste of social resources.Thus, designing coordination mechanisms to balance the selfishness of jobs and thewaste of social resources will be of great significance.A scheduling problem generally consists of m machinesM1, M2,,Mmandn jobs1,2,, n. Giving a schedule, the starting time and the completion time of jobj are denoted byS jandC jrespectively. The type of machines, the characteristicof jobs and the objective function determines a scheduling problem. The schedulingproblems we consider in this paper can be formulated as the following:(1) There are m parallel machines. Each job j has a weight j. The globalobjective function of this problem is to minimize the maximum weighted completiontimes of all the jobs.(2) There are m uniform machines, eachM iof which has a speedsi. Theload of job j isl jand its processing time on machineM iisl j si. The globalobjective function of this problem is to minimize the maximum weighted completiontimes of all the jobs.(3) There are m parallel-batching machines. b jobs can be processed on amachine simultaneously as a batch and all the jobs in a batch start and complete at thesame time. The global objective function of this problem is to minimize the maximumcompletion times of all the jobs.(4) There are m parallel-batching uniform machines. Each machineM ihas aspeedsi. The load of job j isl jand its processing time on machineM iisl j si.The global objective function of this problem is to minimize the maximumcompletion times of all the jobs.In this paper we consider the scheduling problems under game situation as follow. Each job is owned by an independent and selfish agent whose strategy is to minimize the completion time of it. Each job selects a machine according to the policies of the machines. The strategy set Xi of job j is the set of machines, i.e., Xj={M1,M2,…,Mm}. A strategy profile X which describes the choices of all the jobs is a map from the set of jobs to the set of machines. A Nash Equilibrium is a strategy profile such that no job has a unilateral incentive to change its selection. Each machine has a scheduling policy that determines how to assign all the jobs that select it. The set of the scheduling policies of all the machines is named as a coordination mechanism. It is easy to see, given a coordination mechanism and a strategy profile, one can determine the completion time of each job. Price of anarchy, which measures the quality of a coordination mechanism, is defined as the ratio between the social cost of the worst Nash Equilibrium and the social cost of an optimal schedule.We obtain the following results.(i) For the scheduling game problem in which the machines are parallel machines and the global objective is to minimize the maximum weighted completion time of the jobs, we show that the price of anarchy of the Greatest-Weight-First Coordination Mechanism is2-1/m.(ii) We apply the Greatest-Weight-First Coordination Mechanism to the scheduling game problem with uniform machines to minimize the maximum weighted completion times of the jobs. We first prove that the existence and the uniqueness of the Nash Equilibrium of the coordination mechanism. Then we show that for the problem the price of anarchy of the Greatest-Weight-First Coordination Mechanism is not greater than1+(m-1)smax/(ms).(iii) Design the s-FBLPT coordination mechanism for the scheduling problem with parallel-batching machines to minimize the maximum completion times of all the jobs. We first show that the existence and the uniqueness of the Nash Equilibrium of the coordination mechanism. Then we show that for the problem the price of anarchy of the coordination mechanism is not greater than2-2/(3b)-1/(3max{m,b}). We also consider the lower bound of the coordination mechanism and show that the bound of price of anarchy is tight when m=b.(iv) Apply the ε-FBLPT coordination mechanism to the scheduling game problem with parallel-batching uniform machines to minimize the maximum completion times of all the jobs. We prove the existence and the uniqueness of the Nash Equilibrium of the coordination mechanism. We show that for the problem the upper bound of price of anarchy of the coordination mechanism is not greater than1+smax(1-1/max{m,b})/s. For the special case m=2, the price of anarchy of the coordination mechanism is not greater than2-1/max{2, b).(v) Prove that each scheduling game problem we considered above is potential game under corresponding coordination mechanism respectively.