The Game Has The Game Effect Sorting Problem

In this paper, we consider game scheduling problems with learning effect. Specifically, when the machines are m identical machines and m uniform machines, Two objective functions that we study in this paper are to minimize makespan and total completion time, and we find out the boundary of POA, respectively. In recent years, game scheduling problems have received considerable attention. Learning effect also has received many attentions for many years. It is surprising that the well known learning effect has never been considered in connection with game scheduling problems. It is shown in this paper that we link them together.Below, we explain the definition of learning effect. There are n jobs available at time zero. Each job has a normal processing time and the jobs are indexed according to the shortest (normal) processing time (SPT) rule, i.e. P1≤P2≤···≤Pn. The normal processing time of a job is incurred if the job is scheduled first in a sequence. The processing times of the following jobs are smaller than their normal processing times because of the learning effect.Game scheduling problem is an important part of scheduling problems. It is a new type of scheduling problem. It is very meaningful in application value. Meanwhile, Nash equilibrium (NE) is also an important concept in Game theory. A Nash equilibrium is a profile of the users’ strategies such that no user can decrease its cost by a unilateral deviation from its current strategy (given that the strategies of the remaining users do not change). In this paper, we use the commonly accepted notions of the price of anarchy (PoA) to analyze the quality of NE solutions.The structure of this article is as follows:The first chapter introduces some notions that we will use in this thesis. In the second chapter, we study the game scheduling problems whose objective functions are to minimize Cmax. We find out the boundary of POA are m ·T2/T1(T1 and T2 are the load of the machine which machinings all jobs according to SPT rule and LPT rule, respectively) and m·Sm/S1·T1/T2(s1 and sm are the slowest and the fastest processing speed of the uniform machine, respectively) in the machine environment of m identical machines and m uniform machines, respectively. In the third chapter, we study the game scheduling problems whose objective functions are to minimize-n∑j=1Cj. We find out the boundary of POA are (n is the number of jobs, P is the sum of the normal processing time of all jobs) and in the machine environment of m identical machines and m uniform machines, respectively. In the forth chapter, We analyze the problems in the thesis and propect for future research.