Scheduling for a flowshop of batch and discrete processing machines

Abstract

This thesis considers three scheduling problems concerned with systems incorporating batch processing machines. Each of the batch processing machines can process a number of jobs together in batch. These problems are individually described below in detail. First, a scheduling problem is considered for a multi-stage flowshop of batch processing machines where each batch processing machine can process a batch of jobs simultaneously so that all jobs contained in each batch are released together to the next machine after their processing. With respect to any regular measure of performance, several solution properties are characterized to exploit a problem reduction procedure for removing dominated machines. The reduction procedure is incorporated into two efficient heuristic solution algorithms for minimizing two corresponding regular measures of performance including "makespan" and "sum of completion times". Second, a scheduling problem is considered for a flowshop composed of two batch processing machines. The problem is investigated for three cases each being concerned with one of three due date related measures including "maximum tardiness", "the number of tardy jobs" and "total tardiness". In the analysis, several solution properties are characterized, based on which the efficient polynomial time algorithms are developed for minimizing the corresponding due date related measures. Finally, a scheduling problem is considered for a two-machine flowshop where a discrete processing machine is followed by a batch processing machine and a finite number of jobs arrive dynamically at the first machine. In the flowshop, the discrete processing machine processes one job at a time and the batch processing machine processes a batch of jobs simultaneously. The objective is to find the optimal schedule which minimizes the maximum completion time (makespan) of all jobs. In the situation where preemption is allowed on the discrete processing machine, it is shown that the optim...