Parallel-batch Scheduling Problems With Forbidden Intervals And Deteriorating Effect

In manufacture industry, the processing machine has some forbidden intervalswhich are occupied by machine breakdowns or maintenance durations in which themachine is not available. Moreover, the actual processing time is related to its startingtime.This paper considers an unbounded parallel-batch scheduling problem withforbidden intervals and deteriorating effect. In the parallel-batch scheduling, all jobsin the same batch start processing and finish simultaneously and once processingstarted of a batch, it cannot be interrupted; The processing time of a batch is given bythe largest processing time of the jobs in the batch; the completion time of all jobs in abatch is equal to the completion time of the batch. We analyze the unbounded model,in which there is effectively no upper bound on the number of jobs that can beprocessed in the same batch. We gave the pseudo-polynomial time optimal algorithmfor minimizing the maximum cost and minimizing the total cost, respectively.Especially when k is fixed, we prove that the problem for minimizing the number oftardy jobs can be solved in polynomial time. When the jobs have different releasedates, we analyze the problem that the objective is to minimize the makespan. Whenthe job’s processing time isp j a j btorp j b jt, we give a polynomial dynamicprogramming algorithm. The content of the dissertation is summarized as follows:1. When the job’s processing time isp j a j bt, this paper considers anunbounded parallel-batch scheduling problem with forbidden intervals.(1) For the scheduling problem that the objective is to minimize the maximumcost, we provided a pseudo-polynomial time optimal algorithm.(2) For the scheduling problem that the objective is to minimize the total cost, weprovide a pseudo-polynomial dynamic programming algorithm. Especially when k isfixed, we prove that the problem for minimizing the number of tardy jobs can besolved in polynomial time.(3) We discuss the scheduling problem that the jobs have different release datesand the objective is to minimize the makespan. We provided a polynomial dynamicprogramming algorithm.2. When the job’s processing time isp j b jt, this paper considers an unbounded parallel-batch scheduling problem with forbidden intervals. We discuss the problemthat the jobs have different release dates and the objective is to minimize themakespan. We provided a polynomial dynamic programming algorithm.