| A batch processing machine is a single machine which can process multiple jobs (up to some capacity) simultaneously as a batch. All jobs in a batch begin and complete processing at the same time, and the processing time of a batch does not directly depend on the number of jobs in the batch. Despite the important role of batch processing in many industries including semiconductor and flat panel display manufacturing, the optimal control of these machines is largely unknown. The questions which arise when controlling a batch processing machine in the face of uncertain job arrivals include when to start a batch and which jobs to include in that batch. This thesis considers the control of a single batch processing machine with random arrivals and random processing times. Both the cases of incompatible job families and compatible job families are considered. Job families are said to be incompatible when jobs from different families cannot be processed together in the same batch. Job families are said to be compatible when jobs from different families can be processed together in the same batch, with the processing time distribution for that batch determined prior to service by the job in the batch having the greatest expected processing time. This thesis also considers the control of an entire manufacturing network of machines which contains a batch processing machine. The objective considered throughout is to minimize the long-run average time that jobs spend in the system (for the incompatible job families case, we also allow non-identical holding costs for each job family). For these problems, this thesis uses Markov decision theory to determine properties possessed by the optimal policies. Since these policies tend to be quite complex and computationally expensive, this thesis also develops simple heuristic policies to control the batch processing machine. Computational results are provided to demonstrate the effectiveness of these heuristics over a wide range of sample problems when compared to the optimal policies and to existing heuristics. |
