Machine Scheduling With Job Incompatibilities

Batch scheduling is a very common feature in semiconductor manufacturing, metal smelting industry, aviation industry, footwear industry and other large-scale production flow process lines and industries. As a generalization of the classical scheduling, it has a strong application background and practical significance. According to the differences in the way of the batch processing, batch scheduling models can be divided into two categories:parallel-batching scheduling and serial-batching scheduling. In the parallel-batching scheduling problem, several jobs can be processed as a batch simultaneously on a machine at one time, and the processing time of a batch is equal to the largest processing time among all the jobs in the batch. In the serial-batching scheduling problem, the jobs in a batch are processed one by one in a serial order, and the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. The main concern is to make batching and sequencing decisions simultaneously, which specify a partition of the jobs into batches and a processing order of the batches on the machines.Due to the differences of jobs' physical characteristics, chemical features and the processing requirements, these jobs are often classified into different job families (groups) in advance. And the jobs in different job families often require different methods of op-eration in the production and transportation process. In this dissertation, we study the scheduling problems with multiple incompatible job families. The job's incompatibility may take different forms in different scheduling problems:(1) In the batch scheduling problem, we require that jobs from different families cannot be placed in the same pro-cessing/delivery batch; (2) Under the Group Technology assumption, all jobs of the same group are required to be processed contiguously on the machine; (3) Due to the limited resources or limited available machine capacity, the scheduler may need to reject some jobs and outsource them to other manufacturers for processing, hence those outsourced jobs and the remaining jobs also form two different job families; (4) In the multi-agent scheduling problem, the jobs in each agent can also be regarded as a job family, and each agent has its own objective function to be optimized.In Chapter 2, we consider the scheduling of incompatible job families in which both processing and delivery are coordinated together. We assume that jobs from different families cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an O(n log n)-time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we first show that the problem is NP-hard and then provide a heuristic algorithm with a worst-case performance ratio of 3/2. Also, we present an optimal algorithm for the case where the number of families is a constant.In Chapter 3, we address the scheduling problem that integrates parallel-batch pro-duction with family jobs and job delivery at the same time. The jobs are first processed in an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. When the number of job families F is 1, Lu and Yuan [101] present an optimal O(n2)-time algorithm. When the number of job families is arbitrary, we first show that the problem is NP-hard, and then by ex-ploring the algorithm developed by Lu and Yuan, we propose for it a heuristic algorithm with a worst-case performance ratio of 3/2. Finally, when the number of job families F is a constant, we give a pseudo-polynomial time algorithm and a fully polynomial-time approximation scheme which runs in O(nF+3/∈) time.In Chapter 4, we study a single-machine scheduling problem involving both the due-date assignment and job scheduling under a group technology environment. All jobs of the same group are required to be processed contiguously on the machine. The due-dates are assignable according to one of the following three due-date assignment methods:FML-CON, FML-SLK and DIF, where FML-CON means that all jobs within the same group are assigned a common due-date, FML-SLK means that all jobs within the same group are assigned an equal flow allowance, and DIF means that each job can be assigned a different due-date with no restrictions. The goal is to determine an optimal combination of the due-date assignment strategy and job sequence so as to minimize an objective function that includes earliness, tardiness, due-date assignment and How time costs. An O(n log n)-time optimization algorithm is provided for all of the above three due-date assignment methods.In Chapter 5, we consider the problem of scheduling deteriorating jobs with release dates on a single parallel-batch machine. Each job's processing time is a simple linear increasing function of its starting time. The objective is to minimize the maximum com-pletion time, i.e., makespan. For the unbounded model, we obtain an O(nlogn)-time dynamic programming algorithm. For the bounded model, we first show that the prob-lem is NP-hard even if there are only two distinct release dates. Then we present optimal algorithms for the case where the job processing order is predetermined in advance and for the case where the number of distinct deteriorating rates is a constant, respectively. Furthermore, we provide a fully polynomial-time approximation scheme for the case where the number of distinct release dates is a constant.In Chapter 6, we consider several parallel-machine scheduling problems in which the processing time of a job is a (simple) linear increasing function of its starting time and jobs can be rejected by paying penalties. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. When the job processing time is a linear increasing function of its starting time and the scheduling cost is the makespan (i.e., maximum completion of all jobs), we propose for it a fully polynomial-time approximation scheme. When the job processing time is a simple linear increasing function of its starting time and the scheduling cost is the total weighted completion time, we also provide for it a fully polynomial-time approximation scheme. When all jobs have the same deteriorating rate and the scheduling cost is the total completion time, we present an optimal O(n2)-time dynamic programming algorithm.In Chapter 7, we study a scheduling problem in which two agents, each with its own set of jobs, compete to perform their respective jobs on a common unbounded parallel-batch machine. Two main categories of batch processing based on the compatibility of job families are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. When the objective is to find a schedule that minimizes the maximum completion cost or the number of tardy jobs of one agent while keeping the maximum completion cost or the number of tardy jobs of the other agent not exceeding a fixed value, we present for them polynomial-time algorithms, respectively. When the objective is to find a schedule that minimizes the maximum completion cost or the total completion costs of one agent while keeping the maximum completion cost or the total completion costs of the other agent not exceeding a fixed value, we present for them pseudo-polynomial-time algorithms, respectively. When the goal is to find a schedule that minimizes the total weighted completion time of one agent while keeping the makespan or total completion time of the other agent not exceeding a fixed value, we show that both of them are NP-hard in the ordinary sense.In Chapter 8, we consider a scheduling problem in which two agents, each with its own set of jobs, compete to perform their respective jobs on a common serial-batch ma-chine. When the goal is to find a schedule that minimizes the maximum completion cost, the total completion time, or the number of tardy jobs of one agent while keeping the maximum completion cost of the other agent not exceeding a fixed value, we present for them polynomial-time algorithms, respectively. When the objective is to find a schedule that minimizes the total completion time of one agent while keeping the total completion time or the number of tardy jobs of the other agent not exceeding a fixed value, we first show that they are NP-hard and then propose for them pseudo-polynomial-time algo-rithms, respectively. When both agents wants to minimize their weighted number of tardy jobs, we present for it a pseudo-polynomial-time algorithm. The algorithm also implies that the un-weighted problem is polynomially solvable.