Online Batch Scheduling Problem With Varying Work Hour

In the classical scheduling problem,the processing time of a job is generally regarded as a constant.In practical applications,however,the processing time of the job often increases with the aging of the machine and other problems.This phenomenon is called deterioration effect of the job.Deterioration effect of a job means that its processing time is a function of its execution start time.In this paper,two classes of online batch scheduling problems with deteriorating jobs are studied:(1)In some service systems,customers’ orders usually arrive over time,and each customer wants their service cost to be as small as possible.Therefore,how to arrange the order of customers’ orders to minimize the maximum service cost of all customers is an important issue.(2)The classical scheduling model usually assumes that the job can be used after processing,so only the processing stage of the job is considered.In practical applications,however,the job should be distributed to corresponding customers after processing.Due to the limited resources of processing and distribution,how to arrange the processing sequence and how to transport to customers is an important problem.In chapter 1,the basic concept,research background and development status of scheduling are given,as well as the main research results of this paper.In chapter 2,the online batch scheduling on a single machine with deteriorating jobs is studied.The goal is to minimize the maximum weighted completion time,i.e.,WCmax=max {wjCj:j=1,...,n},where wj denotes the weight of the job Jj and Cj denotes the completion time of the job Jj.When the batch machine’s capacity is unbounded,we provide a best possible online algorithm and the competitive ratio of this online algorithm is 1+α,in which α is the degradation rate of the job.In chapter 3,the online batch scheduling problem on a single batch machine with deteriorating jobs is studied.The goal is to minimize the maximum delivery completion time,i.e.,Dmax=max{δ(Bi)+T:1 ≤i≤n},where δ(Bi)denotes the time when the vehicle batch Bi begins to be delivered and T denotes the time it takes the vehicle to deliver a round trip between the machine and the customer.The job with different deterioration rates is first processed on a single batch machine,then the finished job are transported to a customer by a transport vehicle.When the capacity of the batch machine is unbounded,the lower bound of the problem is given.For the case that the capacity of the transport vehicle is unbounded and bounded,an online algorithm is proposed respectively.Finally,the competitive ratio of the online algorithm is analyzed.In chapter 4,the difference from the previous chapter is that this chapter studies the processing of jobs on m parallel batch machines,in which the job has the same deterioration rate.When the capacity of batch machine is unbounded,for the case of unbounded and bounded capacity of transport vehicle,online algorithms are proposed and their competition ratio is analyzed.When the capacity of batch machine is bounded,for the case of unbounded and bounded capacity of transport vehicle,online algorithms are proposed and their competition ratio is analyzed.