Several Kinds Of Single Machine Serial Batch Scheduling Problems

In large-scale production lines,there is often one or more machines that work in batches.Therefore,the research of serial batch scheduling problem has great theoretical significance and practical application value.In the serial batch scheduling problem,the processing time of a batch is the sum of the processing time among all the jobs in the batch.The completion time of a batch is the completion time of the last job in the batch.The start processing time of the job in the batch is the same as the start processing time of the batch to which it belongs,and the completion time of the job in the batch is the same as the completion time of the batch.Each batch can not be interrupted during processing.Only after all the jobs in the same batch have arrived,the batch can be processed.The machine can process the next batch after this batch has been finished.According to the availability of machine,the actual processing time and characteristics of the job,and the fixed setup time before each batch of processing,we divide the study of some single batch scheduling problems into unavailability interval,rej ection and deteriorating and so on.We carry out theoretical research from different aspects.The specific research content is summarized as follows:1.The machine has an unavailable interval and an unlimited capacity.We studied the case where the jobs have two different arrival times,0 or r,in which the jobs'arrival times and due dates are assumed to be agreeable.Among them,before each batch is processed,an independent constant setup time is required.And the machine cannot process within the setup time or unavailable interval.The objective is to minimize the number of weighted tardy jobs.Firstly,we propose the optimal properties of the problem,and give a dynamic programming algorithm.In the optimal scheduling,the batch on time is scheduled by batch EDD order.The complexity of the algorithm is also analyzed to be quasi-polynomial time.Finally,we use an example to verify the correctness of the algorithm.2.For the job has rejection and deterioration,when the job is rej ected,we need to pay the corresponding rejection penalty.Before each batch is processed,an independent constant setup time is required.And the machine cannot process within the setup time.The objective function is the sum of the maximum completion time and the rejection penalty.We research two different deterioration effects respectively:(1)All the jobs arrive at time t0.The basic processing time of the jobs is different and the deterioration rate is the same.That is the actual processing time is pi=ai+bt,i=1,2,…,n.We analyze the properties of the optimal solution of this problem and give its dynamic programming algorithm.We also analyze that the time complexity of the algorithm is quasi-polynomial.(2)All the jobs arrive at zero time.The basic processing time of the jobs is the same and the deterioration rate is different.That is,the actual processing time is pj=a+bjSj,j=1,2,…,n.Firstly,we propose the optimal properties of the problem,and give a dynamic programming algorithm.We also analyze that the time complexity of the algorithm is quasi-polynomial.Finally,we use an example to verify the correctness of the algorithm.