Machine Scheduling Problems With Rejection

Scheduling has been one of the most important and active branch in operation re-search and combinatorial optimization over the last six decades. In the classical scheduling literatures, job rejection is not allowed and all jobs must be processed on the machines. However, in real applications, this may not be true. Due to the limited resources, the scheduler can have the option to reject some jobs.Scheduling with rejection can be described as follows. There arc n jobs J1,…,Jn and m machines M1,….Mm. Each job Jj has a processing time pj and a rejection penalty ej. Jj is either rejected, in which case the rejection penalty ej has to be paid, or accepted and processed on the machine. In this paper, we study some typical scheduling problems with job rejection.In chapter 2, we consider the single-machine scheduling under the job rejection con-straint. A job is cither rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. However, the total rejection penalty of the rejected jobs cannot exceed a given upper bound. The objective is to find a schedule such that a given criterion f is minimized, where f is a non-decreasing function on the completion times of the accepted jobs. We analyze the computational complexities of the problems for distinct objective functions and present pseudo-polynomial-time algorithms. In addition, we provide a fully polynomial-time approximation scheme for the makespan problem with release dates. For other objective functions related to due dates, we point out that there is no approximation algorithm with a bounded approximation ratio.In chapter 3, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered:(1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs:(4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.In chapter 4, we consider the single-machine scheduling with arrival times and re-jection. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algo-rithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 1.618.In chapter 5, we consider the two-machine flow shop scheduling with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejec-tion penalty of rejected jobs. First, we show that this problem is binary NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we provide a pseudo-polynomial-time algorithm, a 2-approximation algorithm and a fully polynomial-time approximation scheme for the problem. Finally, we present two polynomial-time algorithms for two special cases of the problem.In chapter 6, we consider the parallel-machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is fixed, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. For arbitrary m, we present a 2-approximation algorithm for the problem.In chapter 7, we consider the scheduling problem with machine cost and rejection penalties on unrelated machines. A job is cither rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the unrelated machines. Each ma- chine has a machine cost to process each job. The objective is to minimize the sum of the machine costs, the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs. We show that this problem can be transformed into the assignment problem and thus can be solved in polynomial time.