Online Scheduling With Machine Eligibility Constraints

In identical parallel machines,every machine has the same speed,and we assume that the speed of all machines is 1.Then the processing times of jobs are independent of machines.Machine eligibility constraints are that the machines have different capabilities.This gives rise to a generalization that each job is only allowed to be processed on a specified ubset of machines.The set of the machines which can process the job is called the processing set of the job.In the online scheduling,the information of any job is available only after its being released,even about its existence.The arrival method of the job can be divided into two categories:over time and over list.In the second chapter,we discuss online batch scheduling problem on m identical parallel machines with machine eligibility constraints.Parallel-batch shows that one ma-chine can process B jobs at the same time.When B = ?,we call this batch unbounded parallel batch.When B<n,we call it bounded parallel batch.The jobs arrive over time and have equal processing times(When a job appears,we have the option of scheduling it immediately or postponing its scheduling till some later time.).The objective is to mini-mize the time by which all jobs have been delivered.We suppose that there are sufficient number of vhicles.Once a job finishes its processing,it should be delivered to its destina-tion by a vehicle.For the nested processing set case,we respectively discuss the bounded version and the unbounded version of the parallel batch.The nested processing set is defined as:For any two jobs Ji and Jj,their processing sets are Mi and Mj,then we have Mi(?)Mj or Mj(?)Mi or Mi ?(?)0.When = ?,by the well-known three-field representation,the model can be denoted by Pm|Mi(nested),pj =p,rj,qj,P-batch,B?n,onlin|Lmax.We give an optimal online algorithm of competitive ratio(?).When B<n,The delivery times we consider have the following restrictions:For any two jobs Ji and Jj,their processing sets are Mi and Mj,if Mi(?)Mj,then we have qi ? qj.For Pm|Mj|(nested),pj=p,rj,qj,P-batch,B<n,online|Lmax.we present a.n optimal online algorithm with a competitive ratio of(?).In addition,we consider the case that the job has inclusive processing set(the processing sets of any two jobs have a relationship that contains and is included),i.e.,Pm|Mj(GOS),pj =p,rj,qj,P-batch,B<n,online|Lmax.The restrictions of the delivery times are the same as the restrictions in the third quarter.When B ? 2,for this problem,the lower bound of an online algorithm with a competitive ratio is also(?).The algorithm for the nested processing set case is also best for this problem.When 6 = 1,we provide that,the lower bound of this problem is 3/2,we develop an optimal online algorithm with a competitive ratio of 3/2.In the third chapter,we study online scheduling problem on m identical parallel ma-chines with two hierarchical levels(p = 2),the processing times of jobs belong to fixed interval.All the processing times of jobs belong to[1,?](?? 1).The typical goal is to minimize the maximum load of all machines.By the well-known threo-field ropresentation,the model can be denoted by P|GOS(g = 2),pj ?[1,?],online,over-list|Cmin.The jobs arrive one by one over a list,and only the current job is scheduled for the next job to ar-rives.Once the job arrives,it will be immediately arranged.In this chapter,the machines are distinguished by two hierarchies.The first layer machines can process all jobs,but the second layer machines can only process some jobs.We provide a best online algorithm with a competitive ratio of 1 + k? =1 or k = m-1.Note that,k is the number of the first layer machines.