Batch Scheduling Problem With Deterioration Effects On Workpiece

Scheduling problem is a typical class of combinatorial optimization problems.With the development of society,scheduling problem has been applied to many fields such as transport scheduling,computer systems and management science.In the classical scheduling problem,the processing time of the job is fixed.However,in real-life industrial production,due to the effects of machine aging wear,processing environment and the characteristics of the job itself,the processing time of the job may increase as the start time is delayed.This phenomenon is called the deterioration effect of the job.Deteriorating effects may occur in steel production,relief resource allocation,etc.Therefore,the research of scheduling problem with deteriorating jobs is of great theoretical and applied significance.In this thesis,we consider the online parallel batch scheduling problem with deteriorating jobs and the serial batch scheduling problem with deteriorating jobs,where the processing time of the job is a linear increasing function of its start time.The objective functions involved in this thesis include minimizing the maximum completion time,minimizing the maximum flow time and minimizing the maximum processing time respectively.The thesis is divided into four chapters,as follows:In Chapter 1,we first introduce the background and knowledge of the scheduling problem,as well as a review of related fields.We then briefly summarize the main work of this thesis.In Chapter 2,we consider the online parallel batch scheduling problem with simple linear deteriorating jobs on a single machine.In this problem,the processing time of the job Jj is pj=αjSj,where αj is the deterioration rate of the job Jj and Sj is the start time of the job Jj.When the objective function of the problem is to minimize the maximum completion time,we assume that the jobs arrive in a non-increasing order of deterioration rate and that the batch capacity of the machine is bounded.We analyze the lower bound of this problem and give the best possible online algorithm with a competitive ratio of 1+αmax,where amax is the maximum deterioration rate of these jobs.When the objective function of the problem is to minimize the maximum flow time,we assume that the jobs have the same deterioration rate α and that the batch capacity of the machine is unbounded.We analyze the lower bound of the problem and propose the best possible online algorithm with a competitive ratio of 2+α.In Chapter 3,we consider the online parallel batch scheduling problem with proportionally linear deteriorating jobs on a single machine.In this problem,the processing time of the job Jj is pj=αj(A+BSj),where αj is the deterioration rate of the job Jj and Sj is the start time of the job Jj,A and B are nonnegative,A and B are not simultaneously zero.For the case where the objective function of the problem is to minimize the maximum completion time and the batch capacity of the machine is unbounded,we give a lower bound for this problem and an online algorithm with a competition ratio of 2+Bαmax.For the case where the objective function of the problem is to minimize the maximum processing time and the batch capacity of the machine is unbounded,we give a lower bound for this problem and the best possible online algorithm with a competitive ratio of 1+Bαmax.In Chapter 4,we consider the serial batch scheduling problem with proportionally linear deteriorating jobs on a single machine.The problem assumes that the jobs are of different types and that each batch has a sequence-dependent setup time,and that the objective function is to minimize the maximum completion time.We design an optimal algorithm for this problem and prove that the time complexity of this algorithm is O(nlogn).