Research On Nash Equilibrium (NE) Related To Unemployment Problem In Constant Speed

The scheduling problem is an important kind of combinatorial optimization problem, which takes advantage of some processors, machines and resource to complete some given tasks and jobs optimally. The game scheduling problem is an important part of scheduling problems. It is an interdiscipline composed of game theory and traditional scheduling problem.We consider taking n jobs on m uniform machines in game scheduling, every agent holds a job who selects a machine to process his/her job and makes his/her objective function optimal. A Nash equilibrium is a solution concept in a game involving two or more players, in which each player is assumed to know the strategies of the other players, and no player has anything to gain by changing his or her own strategy unilaterally. In general, Nash equilibrium in pure strategies may not exist while Nash equilibrium in mixed strategies always exist. Throughout the paper, we focus on pure Nash equilibrium only.In the sequencing model, each job has a completion timejC,and its utility is defined as j-C. Without a central coordination, each job assigned to a given machine would try to finish as early as possible, which may lead to chaos. To resolve this conflict, each machine will announce, in advance, the sequencing rule used by the machine to sequence the jobs assigned to it. For example, if the Shortest Processing Time first( SPT) rule is used, jobs assigned to the machine are sequenced in non-decreasing order of their processing times. The sequencing rule used by each machine is usually called the local policy of the machine. A local policy is called strongly local if the sequencing rule depends only on the processing requirements of the jobs assigned to that machine. In this article, we investigate the Nash equilibrium(NE)of maximum tardiness, total tardiness, number of tardy jobs on uniform machines in EDD local policy and weighted number of tardy jobs in LW local policy.The structure of this article is as follows:The first chapter is introduction, it mainly introduces the scheduling problem, coordination mechanism, game and NE, the background of game scheduling and research status.In the second chapter, we consider the game scheduling of maximum tardiness, total tardiness on uniform m machines and every machine has EDD as its policy. A Nash equilibrium(NE) is a strategy profile, in any NE assignment, no job can reduce its cost by unilaterally changing its machine. But in terms of a given social objective, such an Nash equilibrium is not necessarily, indeed can often be far from optimal. We use the notion of the price of anarchy( POA) to measure the quality of NE. Because the optimal value may be 0 in this article, we use another notion of the absolute price of anarchy( APOA). In this chapter, we find the upper bound of APOA for the problem of maximum tardiness and total tardiness.In the third chapter, we firstly consider the game scheduling of number of tardy jobs in EDD local policy and weighted number of tardy jobs in LW local policy on 2 uniform machines.Then, we consider the jobs onm uniform machines in its own local policy. we finally find the value of the APOAfor above problems.