Semi-online Scheduling Problem With An Unexpected Breakdown

Scheduling is a very active branch of operations research.In general,we divide the scheduling problem into offline scheduling and online scheduling.The problem of semi-online scheduling with an unexpected breakdown in this paper is that the arrival time,the processing time,the delivery time and other information of jobs are known before the scheduling,but the information that when and how long the breakdown occurs are not known beforehand.The decision makers need to provide decisions only based on the jobs'information.In this paper,we study two scheduling problems,one is a semi-online scheduling problem on a single machine with breakdown and delivery time,and the other is a semi-online scheduling problem on a parallel batch machine with breakdown.Here parallel batch means that multiple jobs can be placed in the same batch,jobs in each batch are processed and completed at the same,and the processing time of each batch is the maximum processing time of jobs in the batch.The batch capacity(7 means that at most(7 jobs can be processed together,which is generally divided into two cases:bounded and unbounded.The online scheduling with the delivery time means that every job needs to be transported to the destination by a vehicle after the job has been processed.In general,we assume that there are enough vehicles,and once the job is processed,it can be transported immediately,so the delivery(transport completion)time is equal to the sum of the jobs'completion time and its delivery time.In this paper,we mainly studied two models.The first one is a semi-online scheduling on a single machine with breakdown and delivery time,and the objective is to minimize the maximum delivery(transport completion)time,expressed as a three-parameter method:(?).In the second chapter of this paper,we first prove that the lower bound of the problem is 3?2.For the problem(?),we give an online algorithm and prove that the competitive ratio is(?5+1)?2.Then we provide an online algorithm with competitive ratio(3?2+)for the problem (?) under the condition of (?),and when<1?2,the competitive ratio is less than 2.The second model we studied is a semi-online scheduling on a bounded parallel batch machine with breakdown,and the objective is to minimize the maximum completion time,which is expressed by the three-parameter method:(?).In the third chapter of this paper,we find that the lower bound of the problem is 3?2,and we give the best possible online algorithm,which has a competitive ratio 3?2.