Production scheduling in a system with batch processing machines

Abstract

This thesis considers four scheduling problems concerned with systems having a batch processing machine. The batch processing machine processes a number of jobs together in a batch. These problems are individually described below in more detail. First, a scheduling problem is considered for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs, for which a dynamic case is analyzed using a branch-and-bound algorithm and several heuristics. The worst case error performance ratios of the heuristics are also derived. For an instance of the dynamic problem case where each job belongs to one of a fixed number of families, a dynamic programming algorithm is proposed in a polynomial time complexity for a situation where the number of job families is given(fixed). Second, a single burn-in oven scheduling problem is considered for all jobs available at time zero with a given common due date to find the optimal schedule which minimizes the sum of earliness-tardiness. In the analysis, some optimal dominance properties are characterized, based upon which two heuristic algorithms including just a simple heuristic and a tabu-search-incorporated heuristic are derived. Third, a scheduling problem for a two-machine flowshop system with a batch processing machine incorporated is considered to find the optimal schedule which minimizes the maximum completion time. In the analysis, some solution dominance properties are characterized, based upon which the dynamic programming procedure is derived for the solution finding. Another scheduling problem is also investigated for a single batch processing machine with dynamic job arrivals allowed. Finally, a stochastic batching problem is considered for a batch process...