Research On Game And Supply Chain Management Based On Scheduling Theory

In this thesis,we mainly investigate the two topic areas in the modern scheduling,including supply chain scheduling and game scheduling.Our studies are supply chain scheduling with an assignable common due window and holding time,game scheduling of jobs in two kinds of limited number of uniform machines with activation cost,and game scheduling of jobs on uniformly related machines with coordination mechanism in detail.The thesis consists of five Chapters:In Chapter 1,we introduce some preliminary concepts,definitions,and necessary knowledge of scheduling problems.We then give reviews for the achievements of supply chain scheduling and game scheduling,and give the main results in this thesis.In Chapter 2,we consider three supply chain scheduling problems with an assignable common due window and holding time.A job which is processed completely by the machine need to dispatch with batch to customer by many vehicles,and a job will incur a holding cost if its completion time is earlier than its dispatch date.Each job will incur an early(tardy)penalty if it is early(tardy)with respect to the common due window under a given schedule.The objective is to find the optimal size and location of the window,the optimal dispatch date for each job,as well as an optimal job sequence to minimize a cost function based on earliness,tardiness,holding time,window location,window size,and batch delivery.For the first problem,we consider the case where the unit cost of holding time is not more than the unit cost of tardiness.We provide the proof of -hard and give a dynamic programming algorithm for the problem.For the second problem,we consider weighted number of tardy jobs,rather than tardiness.We also provide the proof of -hard and give a dynamic programming algorithm for the problem.For the third problem,we consider the special case of the second problem,where all jobs have same processing time.We provide a polynomial-time algorithm for the special case.In Chapter 3,we consider supply chain scheduling problems with an assignable common due window and holding time once more.The problem is the case of the second problem in Chapter 2,where the unit cost of earliness is not more than the unit cost of holding time.We present a(1 + )-approximation algorithm for the problem.In Chapter 4,we consider game scheduling of jobs in two kinds of limited number of uniform machines with activation cost.The number of machines with speed 1 and activation cost in the first category is limited.Similarly,the number of machines with speed (6(> 1)and activation cost (6 in the second category is also limited.Each job,as an agent,selects a machine for processing to minimize his individual cost composed of its machine's load and its share in the machine's activation cost,which is proportionally shared with respect to its size.We design different algorithms for different cases.Then,every assignment obtained by each different algorithm is proved to be a Nash Equilibrium.In Chapter 5,we consider three game scheduling problems of jobs on uniformly related machines with coordination mechanism.First,we give an improved upper bound of the PoA for the scheduling game studied by Hoeksma and Uetz(2011)[WAOA,9(2011),pp.261-273].Then,we present a better lower bound of the PoA for the scheduling game studied by Lee et al.(2012)[Eur J Oper Res,220(2012),pp.305-313].Finally,we provide improved upper bounds of the PoA in terms of the number of machines,for another scheduling game proposed by Chen and Gürel(2012)[J Scheduling,15(2012),pp.157-164].