A Study On Coordination Mechanisms Of Three Classes Of Parallel Machine Scheduling Game Problems

Scheduling theory is an important part of the theory of combinatorialoptimization. If there is a system administrator to arrange tasks in schedulingprocessing, it may get an ideal solution. However, with the development of theInternet, many scheduling process imposed by the system administrator to control isnot feasible. It is because the systems consist of many independence self-interestagents who "selfishly" pursue their own optimal and do not care about the waste ofsocial resources. If there is no reasonable mechanism for the use of resources, theself-interest may lead to large deviation between the results and the theoreticaloptimal value. Designing a reasonable mechanism to influence and guide theindependent and selfish agents such that the waste of social resources is decreasedwill be of great theoretical significance.A scheduling game can be described as follows. There is a set of njobs （J {1,2,,n}）, and they must be scheduled on a set of m parallelmachines （{M₁,M₂,,Mm}）. Each job j has a processing time ofp j. Each jobcorresponds to an independent and selfish agent whose goal is to minimize thecompletion time of his job. The global goal of the problem is to minimize somefunction about the completion times of the jobs. Each agent will choose a machine toprocess his job depending on the coordination mechanism. A strategy set of job j isXj M1,M₂,,Mm,（j1,2,,n）. A coordination mechanism is a set ofscheduling policies, one for each machine, that determines how to schedule the jobsthat have selected the machine. A combination of strategies selected by all jobs iscalled a strategy profile X （X X₁X₂X_n）. A Nash equilibrium is a strategyprofile in which no job has a unilateral incentive to go to another machine.In this paper we study coordination mechanisms of three classes of parallelmachine scheduling game problems.Firstly, the following scheduling game problem is considered. There are twoparallel machines. The global objective is to minimize the maximum completion time.SPT-LPT mechanism means that one of the machines schedules jobs in the order ofincreasing processing time, the other schedules jobs in the order of decreasingprocessing time. An algorithm is designed, and then the set of Nash equilibriumsolutions of the SPT-LPT mechanism is equal to the set of the solutions of thealgorithm and the price of anarchy of SPT-LPT mechanism is4/3when there is atleast4jobs is proved.Secondly, the following scheduling game problem is considered. There are mparallel machines. The global objective is to minimize the maximum weightedcompletion time. The maximum-weight-first mechanism means that each machineschedules jobs in the order of decreasing weight and machineM istarts itsprocessing at time （i1）. An algorithm is designed, and then the set of Nashequilibrium solutions of the maximum-weight-first mechanism is equal to the set ofthe solutions of the algorithm and the price of anarchy of maximum-weight-first mechanism is no less than3/2is proved.Lastly, the following scheduling game problem is considered. There are mparallel batching machines with unrestrictive batch size. The global objective is tominimize the maximum completion time. The same batch mechanism means thatgroup all the jobs that have selectedM ias a batch and start to process the batch attime （i1）. The Nash equilibrium solutions of the same batch mechanism isanalyzed and the price of anarchy of the same batch mechanism is1is proved.