Online Scheduling On Parallel Batch Machines With Incompatible Job Families

Scheduling is for each job to allocate one or more time intervals to one or more machines.Scheduling problem is that the decision maker finds a scheduling algorithm that satisfies specific restrictions and makes the objective function optimal.Generally,the scheduling problem is divided into the off-line scheduling problem and the online scheduling problem.We consider the online scheduling problem.In the online scheduling problem,only when one job arrives,the decision maker knows all the information about it.Batch scheduling problem is to group the arrived and unprocessed jobs into batches and arrange the processing sequence and corresponding parallel batch machines of these batches.Parallel batch means that the parallel batch machine can process all jobs of a batch at the same time,i.e.,the jobs of the same batch have the same starting time.The processing time of a batch is the maximum processing time of all jobs in this batch.Then all jobs of the same batch have the same starting time,processing time and completing time.Since the jobs of different families are incompatible,the jobs of different families cannot be processed in the same batch.Batch capacity refers to the maximum number of jobs processed simultaneously in a single batch,which is denoted by b.According to the value of b,batch scheduling model can be divided into bounded batch model(b<?)and unbounded batch model(b = ?).In this paper,we investigate the online scheduling problem on parallel batch machines with incompatible job families,where once one machine starts,the decision maker cannot regret and interrupt the processing of a job.The goal is to find an online algorithm to make the makespan as small as possible in the schedule generated by the online algorithm,i.e.,make the maximum completion time of all jobs as small as possible.The online scheduling problem on parallel batch machines is always difficult,so we have the following limitation:jobs belonging to the same family have the same processing time.In this paper,we mainly consider several problems in the two environments of the online scheduling model:(1)KRT setting(online environment under KRT restriction)and(2)general setting(online environment with general release time constraints).The English expression of KRT is kind release time,which means that no new jobs will arrive when all machines are busy,i.e.,new jobs can arrive only when one machine is idle or when one batch is finished.We firstly investigate online scheduling about f incompatible job families on a bound-ed parallel batch machine in this environment,where the jobs from the same family have equal processing time.For this model,in Chapter 2 we prove the lower bound of its com-petitive ratio is 1+?f when b?f,where satisfies f?f2+2?f +1-f = 0.Then we provide a best possible online algorithm.In general setting,the jobs can arrive at any time,that is,there is no requirementfor the arrival time of the jobs.We also study online scheduling about f incompatible job families in this environment,where the jobs from the same family have equal processing time.For the model,in Chapter 3 we firstly prove its lower bound of competitive ratio is 1+?f' when b?f+1,where satisfies f·?f'2+?f'-f=0.Then we also provide an online algorithm whose lower bound of competitive ratio is,so that it is best possible when b?f+1.We also study online scheduling about f incompatible job families on f unboundedparallel batch machines in general situation,where the jobs from the same family have equal processing time.For this model,in Chapter 4 we prove the lower bound of its com-petitive ratio is 1+?,where satisfies ?2 +?-1=0.Then we also provide a best possible online algorithm.