Batch scheduling problems

Abstract

Batch scheduling is motivated by the burn-in operation of the final testing stage in the manufacturing of very large-scale integrated circuits, in which a machine can process several jobs simultaneously. The processing time of a batch is equal to the longest processing time of the jobs in the batch. Some other practical applications of this model include heat treatment in the metalworking industry, diffusion or oxidation processing in wafer fabrication of semiconductor manufacturing, etc. This thesis examines several batch scheduling problems on a single batch processing machine and parallel batch processing machines. The organization of the thesis is as follows: Chapters 1 and 2 introduce the problem and present a literature review of the class of scheduling problems under study in this thesis. In Chapter 3 we consider bi-criterion scheduling on a single batch processing machine, in which two criteria are considered at the same time. Most of the bi-criterion scheduling problems on a single batch processing machine are strongly NP-hard. We mainly focus on the bi-criterion scheduling problem with makespan as the primary criterion. We propose an optimal algorithm for the problem with total completion time as the secondary criterion, which runs in polynomial time when the machine capacity is fixed. We then prove that the problem with number of tardy jobs as the secondary criterion is binary NP-hard, and the problem with total weighted number of tardy jobs as the secondary criterion is strongly NP-hard. Our results also shed light on the computational complexity issues of two open problems of scheduling incompatible families of jobs on a single batch processing machine. From the NP-hardness proof of the problem with number of tardy jobs as the secondary criterion, we deduce that the problem of minimizing number of tardy jobs with incompatible job families is binary NP-hard. From the strong NP-hardness proof of the problem with weighted number of tardy jobs as the secondary criterion, we deduce that the problem of minimizing the weighted number of tardy jobs with incompatible job families is strongly NP-hard. In Chapter 4 we study the problems of scheduling jobs with agreeable processing times and due dates on a single batch processing machine to minimize total tardiness and weighted number of tardy jobs, respectively. Polynomial time algorithms for the problems of minimizing maximum tardiness and number of tardy jobs have been presented in the literature. We prove that the problem of minimizing total tardiness is binary NP-hard even if the machine capacity is two, and we propose a pseudo-polynomial time algorithm for an NP-hard special case of this problem. We also develop a pseudo-polynomial time algorithm for the NP-hard problem of minimizing weighted number of tardy jobs, which indicates that this problem cannot be strongly NP-hard unless P=NP. Most of the results appearing in batch scheduling deal with scheduling problems on a single batch processing machine. In Chapter 5 we explore the scheduling problems with release dates on parallel unbounded batch processing machines. We prove that the problem of minimizing any due date related objective is strongly NP-hard. Since the maximum lateness could be zero or even negative, it is meaningless to develop an approximation algorithm for it. We obtain a polynomial time approximation scheme (PTAS) for the problem of minimizing maximum delivery completion time, which is equivalent to minimizing maximum lateness from an optimization perspective. We show that the problem of minimizing total weighted completion time is strongly NP-hard, too. We provide a PTAS for this problem. In Chapter 6, the last chapter, we conclude the major findings of the study and suggest some directions for future research.