Scheduling With Agreeable Arrival Times And Due Dates On A Serial Batch Processing Machine

In the wafer and other electronic products manufacturing system, we often putjobs finished processing from the former procedure on a pallet, and jobs on the samepallet as a batch are placed on the machine to process one by one. This equivalent tothe situation of dynamic job arrivals. A batch starts to process after all jobs in thisbatch arrived. For each new batch, a constant set-up time is needed before the first jobof the batch is processed. There isn’t a set-up time between jobs in the same batch.Moreover, the machine can’t process any jobs during a set-up time. Jobs in the samebatch have the same start processing time and completion time. The processing timeof a batch is equal to the sum of processing time among all jobs in this batch. And thecompletion time of each job in the batch coincides with the completion time of thelast job in this batch. All of the jobs on the pallet can be deliveried after they havebeen processed. In this paper, we consider different objective functions under theassumption that job arrival times and due dates are agreeable. The specific content ofthis paper is summarized as follows:1. All of the jobs have only two distinct arrival times, but job due dates,processing times and weights can have a number of different values. We show that theproblem of minimizing the weighted number of late jobs is NP-hard. Besides, westudy the characterizations of the optimal scheduling, present a pseudo-polynomialtime dynamic programming algorithm and analyze the complexity of algorithms.Finally, we show the efficiency of the proposed algorithm by a numeral example.2. When jobs have several different arrival times and processing times are equal,for the particular case above, we consider two distinct objective functions.(1) When job due dates are given, different schedulings make some jobscomplete on time and others delay. In this paper, we consider the makespan of thejobs completed on time and the total penalty of the late jobs. We aim to make the sumof both minimal. For this problem, we analyze the optimal solution properties,provide a pseudo-polynomial algorithm and analyze the complexity of algorithm. A numerical example is given to explain the algorithm.(2) The problem of minimizing the number of late jobs can be solved inpolynomial time. We analyze the properties of the optimal solution and propose adynamic programming algorithm, which the computational complexity isO (n3). Weshow the efficiency of the algorithm by corresponding numeral example.