Research On Some Online Scheduling Problems With Machine Eligibility Constraints

In this thesis we study the online scheduling problem on parallel machines with eligibility constraints.Every job is associated with a release time rj,a processing time pj,and a processing set Mj,which mean the job can only be processed at or after time rj and on the machines in Mj,and its processing takes pj time units.We study this scheduling problem in the online setting.Then,the information of any job is available only after its being released,even about its existence.But when a job appears,we have the option of scheduling it immediately or postponing its scheduling till some later time.Our goal is to find a schedule that minimizes the makespan.We consider four special cases:nested processing set case,inclusive processing set case,tree-like processing set case and interval processing set case.In Chapter two,we consider the nested processing set case.In our problem,the number of machines is arbitrary and jobs have equal processing times.We present algo-rithm H1 for this problem,in which we schedule the jobs at times ?p + kp(? =(?)/2,k=0,1,2,...)and at each time,the jobs with the smallest |Mj|,have the highest priority.The competitive ratio of vi is(?)/2 and it is optimal for this problem.In Chapter three,we consider the inclusive processing set case.First,we consider the problem in which the number of machines is arbitrary and jobs have equal processing times.We present algorithm H2 for this problem.H2 is similar with H1 except we schedule the jobs not only at times ap + kp but also at times 2?p + kp,where ? =(?)-1 and k = 0,1,2,....We show the competitive ratio of algorithm H2 is(?)and it is optimal.Then,we consider the problem with two machines and arbitrary job size,and present an optimal algorithm for this problem.In Chapter four,we consider the tree-like processing set case.First,we consider the problem in which the number of machines is three and jobs have equal processing time.We show that the lower bound of this problem is 3/2,and present an optimal algorithm for this problem.Then,we consider a special case of tree-like processing set case:star-like processing set case.In this problem,the number of machines is arbitrary and jobs have equal processing time.We show that the lower bound of this problem is(?)/2 and present an optimal online algorithm for this problem.In Chapter five,we consider the interval processing set case.In our problem,the number of machines is arbitrary and jobs have equal processing time,further,there are only two different processing sets.We show that the lower bound of this problem is 3/2,and present an optimal algorithm.