Research On Game Sorting And Controllable Sorting With Variable Working Hour

In this thesis,we consider the game scheduling problem and controllable scheduling problem with varying processing times.We study the game scheduling problem of parallel-batch machines with deterioration efect,the game scheduling problem of uniform-batch machines with deterioration effect,and the unrelated machine controllable scheduling problems with deterioration effect and truncated learning effect.This thesis contains five chapters:In Chapter 1,we mainly introduce some concepts in the scheduling problem,and summarize the research status of game scheduling and controllable scheduling.In Chapter 2,we consider a game scheduling problem of parallel-batch machines with deterioration effect.For the game scheduling problem Pm|B<n,pj=ajt|Cmax,we design a FBLDRPT coordination mechanism and show that the FBLDRPT coordination mechanism has an LPoA at most 2-1/3max{m,B}-2/3B.When m ≤B,we show that the FBLDRPT coordination mechanism has an LPoA at least 2-1/m.When m>B,we show that the FBLDRPT coordination mechanism has an LPoA at least 2-(m+B-R)/mB.In Chapter 3,we consider a game scheduling problem of uniform-batch machines with deterioration effect.For the game scheduling problem Qm|B<n,lj=ajt|Cmax,we design a FBLDRL coordination mechanism and show that the FBLDRL coordination mechanism has an LPoA at most 1+1/B ln(1+amin/smin)/(ln(1+amin/smax)+δ)+(1-1/B)ln(1+amax/smin)/(ln(1+amin/smax)+δ)-1/mΔ.When m=2,we show that the FBLDRL coordination mechanism has an LPoA at most 1+2/B ln(1+amin/smin)/(ln((1+a11/s1)(1+a21/s2))+δ’)+(22/B)ln(1+amax/smin)/(ln((1+a11/s1)(1+a21/s2))+δ’)-1/2Δ.In Chapter 4,we consider the unrelated machine controllable scheduling problems with deterioration effect and truncated learning effect.We study the linear resource allocation model pij=(aij+ct-φijuij)max{f(r),b} and the convex resource allocation mode pij=((aij/uij)k+ct)max{f(r),b},respectively,and the minimization of objective functions (?) and (?) are discussed respectively.When m is a given constant,we show that these problems are solvable in time O(nm+2).In Chapter 5,we summarize the main results in this thesis and look forward to some future research directions.