Parallel Machine Game Scheduling Problem With Resource Constraints

Scheduling is an important branch of combinatorial optimization problems.Previously,all of jobs are arranged by a centralization agent,and now scheduling problem is mostly studied by an agent who manages one job,the agent arranges the job to the machine.It is of great significance to design algorithms and how to arrange jobs to reduce the waste of social resources.In this paper,we investigate resource allocation game.The inefficiency of pure Nash Equilibrium is assessed by the POA(Price of Anarchy).The structure of this paper is as follows.In the first chapter,the background of the problems,some related definitions are in-troduced.We also show the related developments of this problem.The main results and innovation points of this paper are briefly introduced.In the second chapter,we consider a system with m uniform parallel machines.Machine speeds are respectively S1 = s,s2 = s3 = ··· = sm = 1,this problem' s social objective is minimized the total completion time.First,when one machine speed is faster than the 1,and the others are 1,we demonstrated that the POA is at most 4m-3+1/2 and at least 3/4+1/4 m+1/m-1;When one machine speed is less than 1,the rest speed is 1,we demonstrated that the POA is at most 4m-3+1/2 and at least 3m-3+(m2-3m+2)2m-1/(m2-4m+2)2m-1+2m2-m,m is the number of machines.In the third chapter,we investigate resource allocation game on m parallel-batching machines,each machine can handle up b jobs as a batch.The processing of a batch of jobs is the processing time of the longest job in the batch and all the jobs in a batch complete at the same time.The problem's social objective is minimized the total completion time.First,we design a LPT-greedy algorithm.Then we prove that the POA is at most bn/m.