Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval

Abstract

In this paper, we study two scheduling problems on a single machine with rejection and an operator non-availability interval. In the operator non-availability interval, no job can be started or be completed. However, a crossover job is allowed such that it can be started before this interval and completed after this interval. Furthermore, we also assume that job rejection is allowed. That is, each job is either accepted and processed in-house, or is rejected by paying a rejection cost. Our task is to minimize the sum of the makespan (or the total weighted completion time) of accepted jobs and the total rejection cost of rejected jobs. For two scheduling problems with different objective functions, by borrowing the previous algorithms in the literature, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme (FPTAS), respectively.

1. Introduction

In this section, we introduce some models on scheduling with (machine or operator) non-availability intervals, scheduling with rejection, and scheduling with rejection and non-availability intervals, respectively.

1.1. Scheduling with Non-Availability Intervals

In most scheduling problems, it is assumed that the machines are available at all times. However, in some industrial settings, the assumption might not be true. Some machines or the operator might be unavailable in some time intervals. Recently, some researchers have studied some scheduling problems with the non-availability intervals. Two models of the non-availability interval were studied mainly: one is the machine non-availability (MNA) intervals due to the machine maintenances and the other is the operator non-availability (ONA) intervals because the operator is resting from work. The difference between MNA intervals and ONA intervals is that a crossover job can exist in the ONA interval. However, no job can be processed in the MNA interval.

To the best of our knowledge, the earliest scheduling problem with MNA intervals was studied by Schmidt [1]. He considered a parallel-machine scheduling problem in which each machine has different MNA intervals. The task is to find a feasible preemptive schedule if it exists. A polynomial-time algorithm is presented for the above problem. We first introduce some single-machine scheduling problems with an MNA interval $(a,b)$. The corresponding problem can be denoted by $1\left|\mathrm{MNA}\right(a,b\left)\right|f$, where “MNA$(a,b)$” means that there is an MNA interval $(a,b)$ and f is the objective function to be minimized. For problem $1\left|\mathrm{MNA}(a,b)\right|\sum C_j$, Adiri et al. [2] proved that the problem is NP-hard and then presented a $\frac{5}{4}$-approximation algorithm. For problem $1\left|\mathrm{MNA}(a,b)\right|C_{max}$, Lee [3] showed that this problem is binary NP-hard and then provided a $\frac{4}{3}$-approximation algorithm. For problem $1\left|\mathrm{MNA}(a,b)\right|L_{max}$, Kacem [4] designed a $\frac{3}{2}$-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS). If there are $k\ge 2$ MNA intervals $(a_1,b_1),(a_2,b_2),\cdots ,(a_k,b_k)$ on the machine, the corresponding problem $1|\mathrm{MNA}(a_i,b_i)|C_{max}$ is strongly NP-hard (see [3]) when k is arbitrary. Breit et al. [5] showed that, for any $\rho \ge 1$ and $k\ge 2$, there is no $\rho$-approximation algorithm for problem $1|\mathrm{MNA}(a_i,b_i)|C_{max}$ unless P = NP.

When there are $m\ge 2$ parallel machines $M_1,\cdots ,M_m$ and each machine $M_i$ has an MNA interval $(a_i,b_i)$, the corresponding problem is denoted by $Pm\left|\mathrm{MNA}\right(a_i,b_i\left)\right|f$. For problem $Pm|\mathrm{MNA}(0,b_i)|C_{max}$, i.e., each machine $M_i$ has a machine release time $b_j$, Lee [6] provided a modified LPT (MLPT) algorithm with a tight approximation ratio $\frac{4}{3}$. Kellerer [7] improved this bound $\frac{4}{3}$ to $\frac{5}{4}$ by a dual approximation algorithm using a bin packing approach. For problem $Pm|\mathrm{MNA}(0,b_i)|\sum C_j$, Schmidt [8] showed that the SPT rule is optimal. Lee [6] also studied the problem $Pm|\mathrm{MNA}(a_i,b_i)|C_{max}$ with the assumption that one machine is always available. He showed that the approximation ratios of LS (List Scheduling) and LPT are m and $\frac{m+1}{2}$, respectively. Furthermore, Liao et al. [9] considered the same problem with $m=2$ and developed exact algorithms based on the TMO algorithm for problem $P2\left|\right|C_{max}$. Aggoune [10] studied the flow-shop scheduling problem with several MNA intervals on each machine. A heuristic algorithm is provided to approximately solve this problem. Burdett and Kozan [11] also addressed some MNA intervals in railway scenarios. They introduced new fixed jobs for the MNA intervals. Some constructive heuristics and meta-heuristic algorithms were proposed in this paper. For more new models and results about this topic, the reader is referred to the survey by Ma et al. [12].

Brauner et al. [13] first studied the scheduling problems with an ONA interval. Similarly, this scheduling model can be denoted by $1\left|\mathrm{ONA}\right(a,b\left)\right|f$. For problem $1\left|\mathrm{ONA}(a,b)\right|C_{max}$, Brauner et al. [13] proved that it is binary NP-hard and provided an FPTAS. For problem $1\left|\mathrm{ONA}(a,b)\right|L_{max}$, Kacem et al. [14] proposed an FPTAS by borrowing the FPTAS for problem $1\left|\mathrm{MNA}(a,b)\right|L_{max}$. Chen et al. [15] considered the problem $1\left|\mathrm{ONA}(a,b)\right|\sum C_j$ and presented a $\frac{20}{17}$-approximation algorithm. Wan and Yuan [16] further considered the problem $1\left|\mathrm{ONA}(a,b)\right|\sum w_j{C}_j$. They designed a pseudo-polynomial-time dynamic programming (DP) algorithm and then converted the DP algorithm into an FPTAS. Burdett et al. [17] considered the flexible job shop scheduling with operators (FJSOP) for coal export terminals. A hybrid meta-heuristic and a lot of numerical testings were designed for the above problem.

1.2. Scheduling with Rejection

In many practical cases, processing all jobs may occur high inventory or tardiness costs. However, rejecting some jobs can save time and reduce costs. When a job is rejected, a corresponding rejection cost is required. The decision maker needs to determine which jobs should be accepted (and a feasible schedule for accepted jobs), and which jobs should be rejected, such that the production cost and the total rejection cost are minimized. Thus, both from the practical and theoretical point of view, scheduling models with rejection are very interesting. In addition, an important application also occurs in scheduling with outsourcing. If the outsourcing cost is treated as the rejection cost, scheduling with rejection and scheduling with outsourcing are in fact equivalent.

Scheduling models with rejection were first introduced by Bartal et al. [18]. They considered several off-line and on-line scheduling problems on m parallel machines. The task is to minimize the sum of the makespan of accepted jobs and the total rejection cost of rejected jobs. For the on-line version, they designed an on-line algorithm with the best-possible competitive ratio of 2.618. For the off-line version, they provided an FPTAS when m is fixed, and a PTAS when m is arbitrary.

Next, we only introduce some results on the single-machine scheduling with rejection. The corresponding problem can be denoted by $1\left|\mathrm{rej}\right|f+e\left(R\right)$, where f is the objective function on the set A of accepted jobs and $e\left(R\right)$ is the total rejection cost on the set R of rejected jobs. For problem $1|r_j,\mathrm{rej}|C_{max}+e\left(R\right)$, Cao and Zhang [19] proved that this problem is NP-hard and designed a PTAS. However, they also pointed out that it is open whether this problem is ordinary or strongly NP-hard. Zhang et al. [20] showed that this problem is binary NP-hard by providing two different pseudo-polynomial-time algorithms. Finally, they also provided a 2-approximation algorithm and an FPTAS for the above problem. For problem $1\left|\mathrm{rej}\right|L_{max}+e\left(R\right)$, Sengupta [21] proved that this problem is binary NP-hard. He also proposed two dynamic programming algorithms and converted one of the two algorithms into an FPTAS. Engels et al. [22] studied the problem $1\left|\mathrm{rej}\right|\sum w_j{C}_j+e\left(R\right)$. They showed that this problem is binary NP-hard and then provided an FPTAS. They also showed that, when $w_j=1$, the problem $1\left|\mathrm{rej}\right|\sum C_j+e\left(R\right)$ is polynomial-time solvable. Recently, Shabtay et al. [23] presented a comprehensive survey for the off-line scheduling problems with rejection. For other models and results on scheduling with rejection, the reader is referred to the survey by Shabtay et al. [23].

1.3. Scheduling with Rejection and Non-Availability Intervals

There are only two articles which considered “scheduling with rejection” and “machine non-availability intervals” together. Zhong et al. [24], and Zhao and Tang [25] considered the problems $1|\mathrm{MNA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{MNA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, respectively. Both of them presented a pseudo-polynomial dynamic programming algorithm and an FPTAS for the corresponding problem. In addition, Li and Chen [26] investigated several scheduling problems with rejection and a deteriorating maintenance activity on a single machine. In their model, the starting time of the maintenance activity (non-availability intervals) is not fixed and the duration is a linear increasing function of its starting time. Some (pseudo-)polynomial-time algorithms are presented for some different objective functions. However, to the best of our knowledge, no article considered “scheduling with rejection” and “operator non-availability intervals” simultaneously. In this paper, we are the first to consider scheduling with rejection and an operator non-availability interval.

2. Problem Formulation

The single-machine scheduling with rejection and an operator non-availability interval can be stated formally as follows. There are n jobs $J_1,J_2,\cdots ,J_n$ and a single machine. Each job $J_j$ is available at time 0 and has a processing time $p_j$, a weight $w_j$ and a rejection cost $e_j$. Each job $J_j$ is either rejected and the rejection cost $e_j$ has to be paid, or accepted and then processed non-preemptively on the machine. There is an operator non-availability interval $(a,b)$ on the machine, where we assume that $0<a<b$. This implies that, in any feasible schedule $\pi$, no accepted job $J_j$ can be started or be completed in the interval $(a,b)$. However, a crossover job is allowed such that it can start before this interval and complete after this interval. Without loss of generality, we assume that all the parameters a, b, $p_j$, $w_j$ and $e_j$ are non-negative integers. Let A and R be the sets of accepted jobs and rejected jobs, respectively. Denote by $C_{max}=max\{C_j:J_j\in A\}$, $\sum w_j{C}_j={\sum }_{J_j\in A}{w}_j{C}_j$ and $e\left(R\right)={\sum }_{J_j\in R}{e}_j$ the makespan of accepted jobs, the total weighted completion time of accepted jobs and the total rejection cost of rejected jobs, respectively. Our task is to find a feasible schedule such that $C_{max}+e\left(R\right)$ or $\sum w_j{C}_j+e\left(R\right)$ is minimized. By using the notation for scheduling problems, the corresponding problems are denoted by $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, respectively.

Two similar problems related to the above problems are $1|\mathrm{MNA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{MNA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$. Zhong et al. [24] and Zhao and Tang [25] presented a pseudo-polynomial dynamic programming algorithm and an FPTAS for the corresponding problem, respectively. In this paper, by borrowing the algorithms in [24,25], we also presented a pseudo-polynomial dynamic programming algorithm and an FPTAS for the problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, respectively.

3. Pseudo-Polynomial-Time Algorithms

Brauner et al. [13] and Chen et al. [15] showed that problems $1\left|\mathrm{ONA}(a,b)\right|C_{max}$ and $1\left|\mathrm{ONA}(a,b)\right|\sum C_j$ are NP-hard. Thus, two problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$ are also NP-hard. In this section, we show that the above problems can be solved in pseudo-polynomial time. That is, both of the problems, $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, are binary NP-hard.

For problems $1|\mathrm{MNA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{MNA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, Zhong et al. [24] and Zhao and Tang [25] presented a pseudo-polynomial dynamic programming algorithm, respectively. By enumerating the crossover job and its starting time, we show that problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$ can be decomposed into many subproblems of $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Consequently, by borrowing the algorithms in [24,25], we also presented a pseudo-polynomial algorithm for problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, respectively.

Lemma 1.

If algorithm $A^{\mathrm{MNA}}$ solves problem $1\left|MNA\right(a,b),rej|f+e\left(R\right)$ in $O\left(T\right)$ time, then Algorithm 1 yields an optimal schedule for problem $1\left|ONA\right(a,b),rej|f+e\left(R\right)$ in $O\left(naT\right)$ time.

Algorithm 1$A^{\mathrm{ONA}}$

Step 1: Let $A^{\mathrm{MNA}}$ be a dynamic programming algorithm for problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, where $f\in \{C_{max},\sum w_j{C}_j\}$

Step 2: Applying algorithm $A^{\mathrm{MNA}}$ to the problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, we can obtain a schedule ${\pi }_0$

Step 3: For each job $J_j$ with $j=1,\cdots ,n$ and each integer t with $0\le t\le a$ and $t+p_j\ge b$, we first schedule $J_j$ in time interval $[t,t+p_j]$. Set $a^{\prime }=t$, $b^{\prime }=t+p_j$ and instance $I^{\prime }=\{J_1,\cdots ,J_n\}\backslash J_j$. Applying  algorithm $A^{\mathrm{MNA}}$ to the instance $I^{\prime }$ of problem $1|\mathrm{MNA}(a^{\prime },b^{\prime }),\mathrm{rej}|f+e\left(R\right)$, we can obtain a schedule $\pi (j,t)$

Step 4: Choose the schedule among all schedules in $\left\{{\pi }_0\right\}\cup \{\pi (j,t):1\le j\le n,0\le t\le a \mathrm{and} t+p_j\ge b\}$ with the smallest objective value.

Proof. 

Firstly, we show that Algorithm 1 yields an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Let ${\pi }^{*}$ be an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. We distinguish two cases into our discussion.

Case 1: No crossover job exist in ${\pi }^{*}$.

In this case, interval $(a,b)$ is completely forbidden. That is, an ONA interval is equivalent to an MNA interval. Thus, in this case, ${\pi }_0$ is also an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|$$f+e\left(R\right)$.

Case 2: There is a crossover job in ${\pi }^{*}$.

Let $J_j$ be the crossover job in ${\pi }^{*}$ and let t be the starting time of $J_j$ in ${\pi }^{*}$. Clearly, we have $0\le t\le a$ and $t+p_j\ge b$. In this case, no job in $I^{\prime }=\{J_1,\cdots ,J_n\}\backslash J_j$ can be processed in the interval $(t,t+p_j)$. Set $a^{\prime }=t$ and $b^{\prime }=t+p_j$. The remaining problem is equivalent to the instance $I^{\prime }$ of the problem $1|\mathrm{MNA}(a^{\prime },b^{\prime }),\mathrm{rej}|f+e\left(R\right)$. Thus, in this case, $\pi (j,t)$ is also an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$.

From the above discussions, Algorithm 1 always yields an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Note that algorithm $A^{\mathrm{MNA}}$ is called at most $O\left(na\right)$ times. Thus, the time complexity of Algorithm 1 is exactly $O\left(naT\right)$. □

Note that Zhong et al. [24] presented an $O\left(n{\sum }_{j=1}^n{p}_j\right)$-time dynamic programming algorithm for problem $1|\mathrm{MNA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$. Zhao and Tang [25] presented an $O\left(na{\sum }_{j=1}^n{p}_j\right)$-time algorithm for problem $1|\mathrm{MNA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$. Thus, we have the following corollaries.

Corollary 1.

Algorithm 1 solves problem $1|ONA(a,b),rej|C_{max}+e\left(R\right)$ in $O\left(n^{2}a{\sum }_{j=1}^n{p}_j\right)$ time and solves problem $1|ONA(a,b),rej|\sum w_j{C}_j+e\left(R\right)$ in $O\left(n^2{a}^2{\sum }_{j=1}^n{p}_j\right)$ time.

Example 1.

A simple example for problem $1|ONA(a,b),rej|C_{max}+e\left(R\right)$ is constructed as follows: Given a positive number $k>0$, we have three jobs $J_1,J_2,J_3$ with $(p_1,e_1)=(2k,k)$, $(p_2,e_2)=(4k,2k)$ and $(p_3,e_3)=(7k,+\infty )$. We also assume that there is a single machine with an ONA interval $(a,b)$, where $a=4k$ and $b=9k$. Note that $p_1<p_2<b_k-a_k=5k<p_3$. Thus, $J_3$ is the unique candidate for the crossover job. Note further that $e_3=+\infty$. Thus, $J_3$ must be accepted in any optimal schedule. We distinguish two cases in our discussion.

Case 1:$J_3$ is not a crossover job.

In this case, since $p_3=7k>a=4k$, $J_3$ must be processed at or after time $b=9k$. Thus, the optimal schedule is to process $J_2$ and $J_3$ in $[0,4k]$ and $[9k,16k]$, respectively, and reject $J_1$. That is, the $C_{max}+e\left(R\right)$ value is $16k+k=17k$.

Case 2:$J_3$ is the crossover job and $J_3$ starts its processing at time t.

Since $t\in [0,4k]$ and $t+p_3\ge b=9k$, we have $2k\le t\le 4k$. When $t\in [2k,4k)$, only $J_1$ can be processed before $J_3$. Thus, the $C_{max}+e\left(R\right)$ value is at least $t+7k+2k\ge 11k$. The minimum value $C_{max}+e\left(R\right)=11k$ can be reached by processing $J_1$ and $J_3$ in $[0,9k]$ and reject $J_2$. When $t=4k$, only one job between $J_1$ and $J_2$ can be processed before $J_3$. Thus, the $C_{max}+e\left(R\right)$ value is at least $4k+7k+k\ge 12k$. The minimum value $C_{max}+e\left(R\right)=12k$ can be reached by processing $J_2$ and $J_3$ in $[0,11k]$ and reject $J_1$.

By combining all cases, the optimal $C_{max}+e\left(R\right)$ value is $11k$, which can be reached by processing $J_1$ and $J_3$ in $[0,9k]$ and reject $J_2$.

4. Approximation Schemes

In this section, by borrowing the FPTASs in [24,25], we also presented an FPTAS for problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, respectively. Given an $ϵ=\frac{1}{E}$ for some positive integer E, we set $t_i=iϵa$ for each $i=1,2,\cdots ,E$. To propose an FPTAS, we delay the starting of the crossover job slightly such that the crossover job starts its processing at some time $t_i$. Such a delay may increase the objective value by $1+ϵ$ times, we say that it produces a $(1+ϵ)$-loss.

Lemma 2.

If a crossover job exists in an optimal schedule, with a $(1+ϵ)$-loss, we can assume that the crossover job starts its processing at some time $t_i$.

Proof. 

Let ${\pi }^{*}$ be an an optimal schedule for problem $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ or problem $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$. Let $A^{*}$ and $R^{*}$ be the set of accepted jobs and the set of rejected jobs in ${\pi }^{*}$, respectively. In addition, we also assume that $J_j\in A^{*}$ is the jth processed job in ${\pi }^{*}$. Without loss of generality, we assume that $J_k\in A^{*}$ is the crossover job in ${\pi }^{*}$. Furthermore, we assume that the starting time of $J_k$ is t with $0\le t\le a$ and $t+p_k\ge b$. If $t\ne t_i$ for each $i=1,2,\cdots ,E$, then there is some i with $1\le i\le E$ such that $t_{i-1}<t<t_i$, where $t_0=0$. By delaying the processing of $J_k,J_{k+1},\cdots ,J_{|A^{*}|}$ by a length of $t_i-t$, we can obtain a schedule $\pi$. Note that $t_i\le a$ and $t_i+p_k\ge t+p_k\ge b$. Thus, $\pi$ is feasible for problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$. Note further that $t_i-t<t_i-t_{i-1}=ϵa$ and $C_j\left({\pi }^{*}\right)\ge b>a$ for each $j=k,\cdots ,|A^{*}|$. Thus, we have $C_j\left(\pi \right)=C_j\left({\pi }^{*}\right)$ for each $j=1,\cdots ,k-1$ and $C_j\left(\pi \right)=C_j\left({\pi }^{*}\right)+(t_i-t)\le C_j\left({\pi }^{*}\right)+ϵa\le C_j\left({\pi }^{*}\right)+ϵC_j\left({\pi }^{*}\right)=(1+ϵ)C_j\left({\pi }^{*}\right)$ for each $j=k,\cdots ,|A^{*}|$. It follows that

$$C_{max}\left(\pi \right)\le (1+ϵ)C_{max}\left({\pi }^{*}\right) \mathrm{and} \sum w_j{C}_{\pi }\le (1+ϵ)\sum w_j{C}_j\left({\pi }^{*}\right).$$

Notice that both of the total rejection cost in $\pi$ and ${\pi }^{*}$ are $e\left(R^{*}\right)$. Thus, we can conclude that the objective value is increased by at most $1+ϵ$ times. This completes the proof of Lemma 2. □

Next, based on Lemma 2, we propose an FPTAS for problems $1|\mathrm{ONA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$ and $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$.

Lemma 3.

If algorithm $A_{ϵ}^{\mathrm{MNA}}$ is an FPTAS for problem $1\left|MNA\right(a,b),rej|f+e\left(R\right)$ with the time complexity of $O\left(T\right)$, then Algorithm 2 is also an FPTAS for problem $1\left|ONA\right(a,b),rej|f+e\left(R\right)$ with the time complexity of $O\left(\frac{nT}{ϵ}\right)$.

Algorithm 2$A_{ϵ}^{\mathrm{ONA}}$

Step 1: Let $A_{ϵ}^{\mathrm{MNA}}$ be an FPTAS for problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, where $f\in \{C_{max},\sum w_j{C}_j\}$.

Step 2: Applying algorithm $A_{ϵ}^{\mathrm{MNA}}$ to the problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, we can obtain a schedule ${\pi }_0$.

Step 3: For each job $J_j$ with $j=1,\cdots ,n$ and each integer $t_i$ with $0\le t_i\le a$ and $t_i+p_j\ge b$, we first schedule $J_j$ in time interval $[t_i,t_i+p_j]$. Set $a^{\prime }=t_i$, $b^{\prime }=t_i+p_j$ and instance $I^{\prime }=\{J_1,\cdots ,J_n\}\backslash J_j$. Applying algorithm $A_{ϵ}^{\mathrm{MNA}}$ to the instance $I^{\prime }$ of problem $1|\mathrm{MNA}(a^{\prime },b^{\prime }),\mathrm{rej}|f+e\left(R\right)$, we can obtain a schedule $\pi (j,t_i)$.

Step 4: Choose the schedule among all schedules in $\left\{{\pi }_0\right\}\cup \{\pi (j,t_i):1\le j\le n,0\le t_i\le a \mathrm{and} t_i+p_j\ge b\}$ with the smallest objective value.

Proof. 

Firstly, we prove that Algorithm 2 is an FPTAS for $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Let ${\pi }^{*}$ be an optimal schedule for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Let Z and $Z^{*}$ be the objective values obtained from Algorithm 2 and the optimal schedule ${\pi }^{*}$, respectively. We also distinguish two cases in our discussion.

Case 1: No crossover job exists in ${\pi }^{*}$.

In this case, interval $(a,b)$ is completely forbidden. That is, an ONA interval is equivalent to an MNA interval. Thus, we have $Z\le Z\left({\pi }_0\right)\le (1+ϵ)Z\left({\pi }^{*}\right)=(1+ϵ)Z^{*}$.

Case 2: There is a crossover job in ${\pi }^{*}$.

Let $J_j$ be the crossover job in ${\pi }^{*}$ and let t be the starting time of $J_j$ in ${\pi }^{*}$. Clearly, we have $0\le t\le a$ and $t+p_j\ge b$. In this case, no job in $I^{\prime }=\{J_1,\cdots ,J_n\}\backslash J_j$ can be processed in the interval $(t,t+p_j)$. Set $a^{\prime }=t$ and $b^{\prime }=t+p_j$. Thus, the remaining problem is equivalent to the instance $I^{\prime }$ of the problem $1|\mathrm{MNA}(a^{\prime },b^{\prime }),\mathrm{rej}|f+e\left(R\right)$. Let $Z^{*}(j,t)$ be the optimal objective value for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$ under the constraint in which $J_j$ is the crossover job and $J_j$ starts its processing at time t. Note that algorithm $A_{ϵ}^{\mathrm{MNA}}$ is an FPTAS for problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Thus, we have $Z\left(\pi (j,t_i)\right)\le (1+ϵ)Z^{*}(j,t_i)$. Furthermore, by Lemma 2, we also have $Z^{*}(j,t_i)\le (1+ϵ)Z^{*}(j,t)=(1+ϵ)Z^{*}$. It follows that

$$Z\le Z\left(\pi (j,t_i)\right)\le (1+ϵ)Z^{*}(j,t_i)\le {(1+ϵ)}^2{Z}^{*}(j,t)={(1+ϵ)}^2{Z}^{*}.$$

From the above discussions, Algorithm 2 is an FPTAS for $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Note that algorithm $A_{ϵ}^{\mathrm{MNA}}$ is called at most $O\left(\frac{n}{ϵ}\right)$ times. Thus, the time complexity of Algorithm 2 is exactly $O\left(\frac{nT}{ϵ}\right)$. □

Note that Zhong et al. [24] presented an FPTAS with the time complexity of $O\left(\frac{n}{ϵ}\right)$ for problem $1|\mathrm{MNA}(a,b),\mathrm{rej}|C_{max}+e\left(R\right)$. Zhao and Tang [25] presented an FPTAS with the time complexity $O\left(\frac{n^4{L}^5}{{ϵ}^4}\right)$ for problem $1|\mathrm{MNA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, where $L=log(max\{n,\frac{1}{ϵ},b,max{e}_j,(max{w}_j)·(max{p}_j)\})$. Thus, we have the following corollaries.

Corollary 2.

Algorithm 1 is an FPTAS for problems $1|ONA(a,b),rej|C_{max}+e\left(R\right)$ and $1\left|ONA\right(a,b),rej|$$\sum w_j{C}_j+e\left(R\right)$ with the time complexities of $O\left(\frac{n^2}{{ϵ}^2}\right)$ and $O\left(\frac{n^5{L}^5}{{ϵ}^5}\right)$, respectively.

5. Conclusions and Future Work

In this paper, we are the first to consider scheduling with rejection and an operator non-availability interval simultaneously. The objective is to minimize the sum of the makespan (or the total weighted completion time) of the accepted jobs and the total rejection cost of the rejected jobs. Firstly, we build the relation between problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$ and problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, where $f\in \{C_{max},\sum w_j{C}_j\}$. That is, by enumerating the crossover job and its starting time, problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$ can be decomposed into many subproblems of $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$. Consequently, by borrowing the previous algorithms for problem $1\left|\mathrm{MNA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, we provide a pseudo-polynomial-time algorithm and an FPTAS for problem $1\left|\mathrm{ONA}\right(a,b),\mathrm{rej}|f+e\left(R\right)$, respectively.

When there are $k\ge 2$ MNA or ONA intervals $(a_1,b_1),(a_2,b_2),\cdots ,(a_k,b_k)$ on the machine, the corresponding problem is strongly NP-hard (see [3]) when k is arbitrary. However, when k is a fixed constant, it is possible to propose a pseudo-polynomial-time algorithm with a larger time complexity. Breit et al. [5] showed that, for any $\rho \ge 1$ and $k\ge 2$, there is no $\rho$-approximation algorithm for problem $1|\mathrm{MNA}(a_i,b_i)|C_{max}$ unless P = NP. It is easy to verify that the inapproximability result still holds when there are $k\ge 2$ MNA or ONA intervals on the machine and $b_k$ is sufficiently large.

Note that, for problem $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$, the time complexity of the proposed FPTAS is $O\left(\frac{n^5{L}^5}{{ϵ}^5}\right)$. That is, the running time is very large and it is not strongly polynomial. Thus, an interesting problem is to design a faster (strongly polynomial) FPTAS for problem $1|\mathrm{ONA}(a,b),\mathrm{rej}|\sum w_j{C}_j+e\left(R\right)$. Note further that, when there are $k\ge 2$ MNA or ONA intervals and each MNA or ONA interval has a bounded length, it is possible to design an effective approximation algorithm. Thus, another interesting problem is to propose some approximation algorithms for the problems with multiple MNA or ONA intervals. Finally, it is also interesting to consider other objective functions such as $L_{max}+e\left(R\right)$ and other machine setting such as parallel machines or shop machines.