Online Batch Scheduling With Linear Deteriorating Jobs

In many realistic scenarios of job processing,one job consumes a longer time to be satisfied with a later start time of processing.This phenomenon is known as job's deterioration effect.In this paper we study online batch scheduling of jobs or job families with linear deterioration effect.The actual processing time pj of Job Jj is assumed to be a linear function of its starting time t,i.e.,pj =?jt,where aj>0 is the deterioration ratio,which is unknown until it arrives.Batch means that one batch processing machine can process b jobs at the same time.The processing time of a batch is the maximum processing time of all jobs in this batch.All jobs in a batch have the same starting time,processing time and completing time.According to the number of jobs contained in a batch,it can be divided into two cases:the unbounded model(b>?)and the bounded model(b<?).Job families mean that one job must belong to some job family,and jobs of different families cannot be processed in the same batch.In chapter 2,we consider the online scheduling problem with deteriorating jobs on a batch machine.The goal is to find an online algorithm to minimize the makespan.For the unbounded model,we prove the lower bound and give an online algorithm that matches the lower bound.Then the algorithm is the best possible and its competitive ratio is 1+?max,where ?max,is the maximum deterioration ratio of all jobs.For the bounded model where jobs have two distinct arrival times,we also give an online algorithm which is the best possible,and its competitive ratio is 1+?max.In chapter 3,we consider the online scheduling on an unbounded batch ma-chine and the jobs belong to incompatible deteriorating job families.The goal is to find an online algorithm to minimize the makespan.The number of job families,f,is known in advance.We prove the lower bound and give an online algorithm that matches the lower bound.Then the algorithm is the best possible and its competitive ratio is(1+?max)f,where ?max is the maximum deterioration ratio of all jobs.In chapter 4,we consider the online scheduling problem on m identical batch machines and all jobs have the same deterioration ratio,?,where ?>0.The goal is to find an online algorithm to minimize the makespan.We consider two cases:the unbounded model and the bounded model.For the unbounded model,we prove the lower bound and give an online algorithm that matches the lower bound.Then the algorithm is the best possible and its competitive ratio is 1+?,where ??is determined by(1+?)m = 1+?;For the bounded model,we give an online algorithm which is the best possible and its competitive ratio is 1+?.In chapter 5,we consider the online scheduling on m parallel batch machines where the batch capacity is unbounded and the jobs belong to m incompatible deteriorating job families.The goal is to find an online algorithm to minimize the makespan.We prove the lower bound and give an online algorithm that matches the lower bound.Then the algorithm is the best possible and its competitive ratio is 1+?max,where ?max is the maximum deterioration ratio of all jobs.