Game Scheduling Problem With Detachment Effect In Workpiece

Game scheduling problem is a cross problem of scheduling theory and game theory, which means to study the scheduling problem in terms of game theory. Each of the participants’ personal goal is to minimize personal cost, and we define this as the load of the machine which processes his jobs. Maximizing social value is the social goal we considered, this is defined as the minimum machine load. The total time in Nash equilibrium is always not the minimum, sometimes deviates significantly from the optimal value. Therefore, we often use the PoA to measure the gap between the optimal value and the objective function of Nash equilibrium. The PoA refers to the worst bound for the ratio of social value in NE scheduling and the social value in the optimal scheduling.In this paper, we mainly studies the game scheduling problem with deteriorating effect. The actual processing time of jobs with deteriorating effect will increase with the starting time. Namely, the actual processing time includes the product of starting time, deterioration ratio and the job’s processing time. In this paper, the machines we considered are m identical machines.In the first chapter, we mainly introduces the scheduling problem, the related concepts of game scheduling problem, and advancements in this fields. At the last, briefly summarizes the main work and innovation of the article.In the second chapter, we mainly consider several identical machines-scheduling problems in which the processing time of a job is a linear increasing function of its starting time. The objectives are to minimize the total completion time of all jobs and the total load on all machines, respectively. We present the PoA value of the objective function when the jobs have different basic processing time and same deterioration rate.In the third chapter, we study the jobs with deteriorating effect on several identical machines. The objectives are to minimize the total completion time of all jobs. We present the PoA value of the objective function when the jobs have same basic processing time and same deterioration rate.