# Two-Agent Single Machine Scheduling with Deteriorating Jobs and Rejection

Authors: Dawei Li; Ganggang Li; Fangzheng Cheng
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

We consider two two-agent scheduling problems with deteriorating jobs and rejection. Two agentsA and B compete for the usage of a single machine. The actual processing time of job JjX is pjX=bjXa+bt, X∈A,B, where bjX is the normal processing time of JjX, a≥0, b≥0 and t denotes the starting time of JjX. A job is either rejected by paying a rejection penalty, or accepted and processed on the machine. The objective is to minimize the sum of the completion time of the accepted A-jobs and total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function fB of the accepted B-jobs and total rejection penalty of the rejected B-jobs, where fB∈CmaxB,∑CjB. We give dynamic programming algorithms for them, respectively. When fB=CmaxB, we present a fully polynomial-time approximation scheme (FPTAS) for the case a=0 and b=1. When fB=∑CjB, a fully polynomial-time approximation scheme is also presented.


---

## Body

## 1. Introduction

In the real life, several departments may share an operating room in a hospital, some operations from these departments will be done in this operating room. For a patient, the later perform an operation for him, the harder to cure his disease, which can modeled as job deterioration. Besides, restricted by medical condition and medical level, a patient in serious condition may be transferred to more advanced hospitals for more systematic and professional treatment, which can be modeled as job rejection. If we regard the operating room as machine and each department as an agent. The goal is to minimize the objective function of one agent, subject to an upper bound on the objective functions of the other agents. Motivated by this background, we study the multiagent scheduling with deteriorating jobs and rejection.Scheduling with deteriorating jobs was first introduced by Gupta and Gupta [1] and Browne and Yechiali [2]. Since then, scheduling with deteriorating jobs has received extensive attention from researchers. The book [3] systematically studied the time-dependent scheduling from different perspectives. Liu et al. [4] considered problem Qmpj=aj+bjtCmax and gave a fully polynomial-time approximation scheme (FPTAS). Wang et al. [5] gave a branch-and-price algorithm for the single machine scheduling problem with deteriorating jobs and flexible periodic maintenance to minimize the make span. Gawiejnowicz [6] gave a comprehensive review of the research on time-dependent scheduling in the past decades. For more papers on scheduling with deteriorating jobs, the reader can refer to [7–10] and so on.In many practical cases, to obtain the maximum profits under the limited resources and increasing market competition, the manufacturer has to reject or outsource some jobs. The notion of scheduling with rejection was first introduced by Bartal et al. [11], they studied the problem PmrejCmax+∑Jj∈Rej. They proposed an FPTAS to fixed m and 2−1/m-approximation algorithm for arbitrary m. Since then, researchers have done a lot of research on the scheduling with rejection. Shabtay et al. [12] provided a comprehensive survey for most existing off-line scheduling problems with rejection. Recently published papers from the area include [13–16].In recent decades, multiagent scheduling has been widely concerned by scholars. Baker and Smith [17] and Agnetis et al. [18] are the pioneers of multiagent scheduling problem. Perez-Gonzalez and Framinan [19] and Agnetis et al. [20] provided reviews of this area, respectively. Other research in this field includes [21–24]. Although researchers conducted much research in the aspect of multiagent scheduling, few researchers consider multiagent scheduling and job rejection simultaneously, even with deteriorating jobs. Feng et al. [25] studied the two-agent single machine scheduling with rejection. They gave a 2-approximation algorithm and FPTASs. Li and Lu [26] extended the problem in [25] to the case of parallel machines. They presented dynamic programming algorithms and FPTASs. Oron [27] studied two single machine scheduling problems with two competing agents and rejection. Since multiagent scheduling, deterioration, and job rejection all can reflect many real-life situations, it is reasonable and meaningful to consider these cases simultaneously.The remainder of this paper is organized as follows: in Section2, we give the specific definition of our problem and the required notations. In Section 3, we consider the problem 1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA and give a dynamic programming algorithm and an FPTAS. In Section 4, we present a dynamic programming algorithm and an FPTAS for problem 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, respectively. Finally, we conclude the paper and put forward some future research issues.


## 2. Problem Formulation and Notation

The problem can be formally described as follows: there are two competing agentsA and B to be processed on a single machine, each of them has a set of nonpreemptive jobs JA=J1A,J2A,…,JnAA and JB=J1B,J2B,…,JnBB. The jobs belonging to JA and JB are referred to as A-jobs and B-jobs, respectively. All jobs are available at time t0, where t0>0. The actual processing time pjX of job JjX is a linear increasing function of its staring time, given by pjX=bjXa+bt, X∈A,B, where bjX is the normal processing time of job JjX,a≥0,b≥0, and t denotes the starting time of JjX. A job JjX is either rejected with a rejection penalty ejX has to be paid, or accepted and processed on the machine. For convenience, we define TP=t0∏i=1nA1+biA∏j=1nB1+bjb and TP=t0+a/b∏i=1nA1+biAb∏j=1nB1+bjBb−a/b.Under scheduleσ, CjXσ is the completion time of job JjX in schedule σ. When there is no ambiguity, we abbreviate CjXσ to CjX. Let AX and RX be the sets of accepted X-jobs and rejected X-jobs, respectively. The objective is to minimize the sum of completion time of the accepted A-jobs and the total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function fB of the accepted B-jobs and the total rejection penalty of the rejected B-jobs, where fB∈CmaxB,∑CjB. According to the three-field notation of Agnetis et al. [18], the problems can be defined as 1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA and 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA. If ∑j=1nBejB≤Q, it is optimal to reject all B-jobs. So, we only need to consider the case ∑j=1nBejB>Q.


## 3. Problem1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA

### 3.1. Dynamic Programming Algorithm

In this section, we will give a dynamic programming calgorithm for1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA. Feng et al. [25] proved 1rej,CmaxB≤Q∑JjA∈AACjA+∑JjA∈RAejA, a special case of our problem, is NP-hard. Hence, our problem is at least NP-hard.Lemma 1.
For1pj=bja+btCmax, the maximum completion time of the jobs is CmaxJ=t0+a/b∏j=1n1+bjb−a/b and is independent of the order of the job [3].Lemma 2.
Problem1pj=bja+bt∑Cj can be solved by scheduling jobs in nondecreasing order of bj/1+bbj ratios [3].
According to Lemma1 and 2, we can get the following lemma.Lemma 3.
For1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, there exists an optimal schedule such that the accepted A-jobs are processed in non-decreasing order of bjA/1+bbjA and the accepted B-jobs are processed consecutively in arbitrary order.
Based on Lemma3, we renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B≤b2B≤⋯≤bnBB.
Letfi,jt,tB,EB denote the optimal objective function value satisfying the following conditions: (1) the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB; (2) the completion time of the last job is t; (3) the completion time of the last B-job is no more than tB; (4) the total rejection penalty of the rejected B-jobs among J1B,J2B,…,JjB is EB.
The initial conditions are as follows:(1)f0,0t,tB,EB=0,ift=tB=t0,EB=0;+∞,otherwise.
Now we consider any optimal schedule for jobsJ1A, J2A,…,JiA, and J1B,J2B,…,JjB, in which meets the above conditions. In any such schedule, either JiA is rejected, or JjB is rejected, or the last scheduled job is one of JiA and JjB.Case 1. JobJiA is rejected. We have fi,jt,tB,EB=fi−1,jt,tB,EB+eiA.Case 2. The last scheduled job isJiA. In this case, for the accepted job among J1A,J2A,…,Ji−1A and J1B,J2B,…,JjB, the completion time of the last job must be t−abiA/1+bbiA, the completion time of the last B-job is no more than tB, and the total rejection penalty of the rejected B-jobs is EB. Then, we have fi,jt,tB,EB=fi−1,jt−abiA/1+bbiA,tB,EB+t.Case 3. JobJjB is rejected. At this point, in the corresponding optimal schedule for J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last job is t, the completion time of the last B-job is no more than tB, and the total rejection penalty of the rejected B-jobs among J1B,J2B,…,Jj−1B is EB−ejB. If tB+EB≤Q holds, we have fi,jt,tB,EB=fi,j−1t,tB,EB−ejB.Case 4. The last scheduled job isJjB. In this case, for the accepted job among J1A,J2A,…,JiA and J1B,J2B,⋯, Jj−1B, the completion time of the last job must be t−abjB/1+bbjB, the completion time of the last B-job is no more than tB−abjB/1+bbjB, and the total rejection penalty of the rejected B-jobs is EB. If tB+EB≤Q holds, we have fi,jt,tB,EB=fi,j−1t−abjB/1+bbjB,tB−abjB/1+bbjB,EB.Combining the above four cases, we get the following recursive function:(2)fi,jt,tB,EB=minfi−1,jt,tB,EB+eiA,fi−1,jt−abiA1+bbiA,tB,EB+t,fi,j−1t,tB,EB−ejB,iftB+EB≤Q;fi,j−1t−abjB1+bbjB,tB−abjB1+bbjB,EB,iftB+EB≤Q.The optimal value is given byminfnA,nBt,tB,EB:t0≤t≤TP,tB+EB≤Q, and the corresponding optimal schedule can be found by backtracking.Theorem 1.
The problem1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA can be solved in OnAnBQ2TP time.Proof.
The recursion function can have up toOnAnBQ2TP states, and each iteration costs a constant time. Hence, the total running time is bounded by OnAnBQ2TP.


### 3.2. Fully Polynomial-Time Approximation Scheme

In this subsection, we can give an FPTAS for problem1rej,pjX=bjXt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, such that for any ϵ>0, the algorithm can find a solution σ in polynomial time in the input size and 1/ϵ which satisfies the following:(1)
∑JjA∈AACjAσ+∑JjA∈RAejAσ≤1+ϵ∑JjA∈AACjAπ+∑JjA∈RAejAπ,(2)
CmaxBσ+∑JjB∈RBejBσ≤1+ϵQ,Hereπ is an optimal solution.Now, we will present an FPTAS by considering the modified deteriorating rates and the inflated rejection penalty witha=0andb=1. The definition of the modified deteriorating rates involves a geometric rounding technique developed by Sengupta [28]. And the rounding technique is stated as follows:For anyϵ′>0 and x≥1, if 1+ϵ′k−1<x<1+ϵ′k, then we define ⌈x⌉ϵ′=1+ϵ′k and ⌊x⌋ϵ′=1+ϵ′k−1. If x is an exact power of 1+ϵ′, then ⌈x⌉ϵ′=⌊x⌋ϵ′=x. Note that for any x≥1, we have ⌈x⌉ϵ′≤1+ϵ′x.For anyϵ>0, let ϵ′=ϵ/2n, the modified deteriorating rate is defined as b′jX=⌈1+bjX⌉ϵ′−1. Let LjX be the exponent of 1+b′jX, i.e., 1+b′jX=1+ϵ′LjX, then LjX=log⌈1+bjX⌉ϵ′/log1+ϵ′=Onlog1+bjX/ϵ.For anyϵ>0, let ϵ″=ϵ/2nB and RB=Ji1B,Ji2B,…,JiqB be the set of the rejected B-jobs, where i1<i2<⋯<iq. The inflated rejection penalty of RB is defined as follows:(3)fϵ″RB=ei1B+fϵ″RB−Ji1Bϵ″,q≥1;0,RB=∅.Lemma 4.
For any0<x≤1 and any integer n≥1,1+x/nn≤1+2x holds [29].Lemma 5.
For anyRB⊆JB and ϵ″>0,fϵ″RB≤1+ϵ″RB∑JjB∈RBejB [28].Lemma 6.
For any0<ϵ≤2, the optimal objective function value for 1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA with the modified deteriorating rates b′jX is at most of 1+ϵ times the optimal objective function value for 1rej,pjX=bjXt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA.Proof.
Assume that jobs in setAA are scheduled in the order of 1,2,…,AA, let ABi be the set of accepted B-jobs which precede JiA and AAB be the set of accepted A-jobs before the last B-job. The objective function with the modified deteriorating rates b′jXis as follows:(4)∑JiA∈AAC′iA+∑JjA∈RAejA=∑i=1AAt0∏j=1i1+b′jA∏JkB∈ABi1+b′kB+∑JjA∈RAejA≤∑i=1AAt01+ϵ′i+ABi∏j=1i1+bjA∏JkB∈ABi1+bkB+∑JjA∈RAejA≤1+ϵ′n∑i=1AAt0∏j=1i1+bjA∏JkB∈ABi1+bkB+∑JjA∈RAejA≤1+ϵ∑JiA∈AACiA+∑JjA∈RAejA,C′maxB+fϵ″RB≤t0∏JiA∈AAB1+b′iA∏JjB∈AB1+b′jB+1+ϵ∑JjB∈RBejB≤t01+ϵ′n∏JiA∈AAB1+biA∏JjB∈AB1+bjB+1+ϵ∑JjB∈RBejB≤1+ϵCmaxB+∑JjB∈RBejB≤1+ϵQ.
We then propose an exact dynamic programming algorithm for problem1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA with the modified deteriorating rates. Firstly, we renumber the jobs such that b′1A/1+bb′1A≤b′2A/1+bb′2A≤⋯≤b′nAA/1+bb′nAA and b′1B≤b′2B≤⋯≤b′nBB. We define(5)τl=1+ϵ′l,l≠−1,0,l=−1.νh=1+ϵ″h,h≠−1,0,h=−1.
Letfi,jl,lB,h denote the optimal objective function value satisfying the following conditions: (1) the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB; (2) the completion time of the last job is t0τl; (3) the completion time of the last B-job is no more than t0τlB; and (4) the total rejection penalty of the rejected B-jobs is νh.
The initial conditions are as follows:(6)f0,0l,lB,h=0,ifl=lB=h=−1;+∞,otherwise.
Now we consider any optimal schedule for jobsJ1A,J2A,…,JiA and J1B,J2B,…,JjB which meets the above conditions. In any such schedule, either JiA is rejected, JjB is rejected, or the last scheduled job is one of JiA and JjB.Case 1. JobJiA is rejected. Then, we have fi,jl,lB,h=fi−1,jl,lB,h+eiA.Case 2. The last scheduled job isJiA. In this case, for the accepted job among J1A,J2A,…,Ji−1A and J1B,J2B,…,JjB, the completion time of the last job must be t0τl−LiA, the completion time of the last B-job is no more than t0τlB, and the total rejection penalty of the rejected B-jobs is νh. Then, we have fi,jl,lB,h=fi−1,jl−LiA,lB,h+t0τl.Case 3. JobJjB is rejected. At this point, in the corresponding optimal schedule for J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last jobs is t0τl, the completion time of the last B-job is no more than t0τlB, and the total rejection penalty of the rejected B-jobs among J1B,J2B,…,Jj−1B is νh′ and −1≤h′≤h˜, where h˜ is given by 1+ϵ″h˜=fϵ″J1B,J2B,…,Jj−1B. If t0τlB+νh′≤1+ϵQ holds, we have fi,jl,lB,h=min−1≤h′≤h˜fi,j−1l,lB,h′.Case 4. The last scheduled job isJjB. In this case, for the accepted job among J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last job must be t0τl−LjB, the completion time of the last B-job is no more than t0τlB−LjB, and the total rejection penalty of the rejected B-jobs is νh. If t0τlB+νh≤1+ϵQ holds, we have fi,jl,lB,h=fi,j−1l−LjB,lB−LjB,h.
Combining the above four cases, we get the following recursive function:(7)fi,jl,lB,h=minfi−1,jl,lB,h+eiA,fi−1,jl−LiA,lB,h+t0τl,min−1≤h′≤h˜fi,j−1l,lB,h′,ift0τlB+νh≤1+ϵQ;fi,j−1l−LjB,lB−LjB,h,ift0τlB+νh≤1+ϵQ,where h˜ is given by 1+ϵ″h˜=fϵ″J1B,J2B,…,Jj−1B.
The optimal value is given byminfnA,nBl,lB,h:−1≤l≤∑i=1nALiA+∑j=1nBLjB,−1≤lB≤L,−1≤h≤H, where L and H are the smallest integer such that 1+ϵ′L≥1+ϵQ and 1+ϵ″H≥1+ϵQ, respectively, hence L=OnlogQ/ϵ and H=OnBlogQ/ϵ. The corresponding optimal schedule can be found by backtracking.Theorem 2.
Problem1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA can be solved in OnAnB3n2/ϵ4log3QlogTP time.Proof.
The recursive function has at mostOnAnB2n2/ϵ3log2QlogTP states, if the B-jobs is rejected, each iteration costs OH time; for the other three cases, each iteration cost a constant time. Hence, the total running time is bounded by OnAnB3n2/ϵ4log3QlogTP.


## 3.1. Dynamic Programming Algorithm

In this section, we will give a dynamic programming calgorithm for1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA. Feng et al. [25] proved 1rej,CmaxB≤Q∑JjA∈AACjA+∑JjA∈RAejA, a special case of our problem, is NP-hard. Hence, our problem is at least NP-hard.Lemma 1.
For1pj=bja+btCmax, the maximum completion time of the jobs is CmaxJ=t0+a/b∏j=1n1+bjb−a/b and is independent of the order of the job [3].Lemma 2.
Problem1pj=bja+bt∑Cj can be solved by scheduling jobs in nondecreasing order of bj/1+bbj ratios [3].
According to Lemma1 and 2, we can get the following lemma.Lemma 3.
For1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, there exists an optimal schedule such that the accepted A-jobs are processed in non-decreasing order of bjA/1+bbjA and the accepted B-jobs are processed consecutively in arbitrary order.
Based on Lemma3, we renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B≤b2B≤⋯≤bnBB.
Letfi,jt,tB,EB denote the optimal objective function value satisfying the following conditions: (1) the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB; (2) the completion time of the last job is t; (3) the completion time of the last B-job is no more than tB; (4) the total rejection penalty of the rejected B-jobs among J1B,J2B,…,JjB is EB.
The initial conditions are as follows:(1)f0,0t,tB,EB=0,ift=tB=t0,EB=0;+∞,otherwise.
Now we consider any optimal schedule for jobsJ1A, J2A,…,JiA, and J1B,J2B,…,JjB, in which meets the above conditions. In any such schedule, either JiA is rejected, or JjB is rejected, or the last scheduled job is one of JiA and JjB.Case 1. JobJiA is rejected. We have fi,jt,tB,EB=fi−1,jt,tB,EB+eiA.Case 2. The last scheduled job isJiA. In this case, for the accepted job among J1A,J2A,…,Ji−1A and J1B,J2B,…,JjB, the completion time of the last job must be t−abiA/1+bbiA, the completion time of the last B-job is no more than tB, and the total rejection penalty of the rejected B-jobs is EB. Then, we have fi,jt,tB,EB=fi−1,jt−abiA/1+bbiA,tB,EB+t.Case 3. JobJjB is rejected. At this point, in the corresponding optimal schedule for J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last job is t, the completion time of the last B-job is no more than tB, and the total rejection penalty of the rejected B-jobs among J1B,J2B,…,Jj−1B is EB−ejB. If tB+EB≤Q holds, we have fi,jt,tB,EB=fi,j−1t,tB,EB−ejB.Case 4. The last scheduled job isJjB. In this case, for the accepted job among J1A,J2A,…,JiA and J1B,J2B,⋯, Jj−1B, the completion time of the last job must be t−abjB/1+bbjB, the completion time of the last B-job is no more than tB−abjB/1+bbjB, and the total rejection penalty of the rejected B-jobs is EB. If tB+EB≤Q holds, we have fi,jt,tB,EB=fi,j−1t−abjB/1+bbjB,tB−abjB/1+bbjB,EB.Combining the above four cases, we get the following recursive function:(2)fi,jt,tB,EB=minfi−1,jt,tB,EB+eiA,fi−1,jt−abiA1+bbiA,tB,EB+t,fi,j−1t,tB,EB−ejB,iftB+EB≤Q;fi,j−1t−abjB1+bbjB,tB−abjB1+bbjB,EB,iftB+EB≤Q.The optimal value is given byminfnA,nBt,tB,EB:t0≤t≤TP,tB+EB≤Q, and the corresponding optimal schedule can be found by backtracking.Theorem 1.
The problem1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA can be solved in OnAnBQ2TP time.Proof.
The recursion function can have up toOnAnBQ2TP states, and each iteration costs a constant time. Hence, the total running time is bounded by OnAnBQ2TP.


## 3.2. Fully Polynomial-Time Approximation Scheme

In this subsection, we can give an FPTAS for problem1rej,pjX=bjXt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, such that for any ϵ>0, the algorithm can find a solution σ in polynomial time in the input size and 1/ϵ which satisfies the following:(1)
∑JjA∈AACjAσ+∑JjA∈RAejAσ≤1+ϵ∑JjA∈AACjAπ+∑JjA∈RAejAπ,(2)
CmaxBσ+∑JjB∈RBejBσ≤1+ϵQ,Hereπ is an optimal solution.Now, we will present an FPTAS by considering the modified deteriorating rates and the inflated rejection penalty witha=0andb=1. The definition of the modified deteriorating rates involves a geometric rounding technique developed by Sengupta [28]. And the rounding technique is stated as follows:For anyϵ′>0 and x≥1, if 1+ϵ′k−1<x<1+ϵ′k, then we define ⌈x⌉ϵ′=1+ϵ′k and ⌊x⌋ϵ′=1+ϵ′k−1. If x is an exact power of 1+ϵ′, then ⌈x⌉ϵ′=⌊x⌋ϵ′=x. Note that for any x≥1, we have ⌈x⌉ϵ′≤1+ϵ′x.For anyϵ>0, let ϵ′=ϵ/2n, the modified deteriorating rate is defined as b′jX=⌈1+bjX⌉ϵ′−1. Let LjX be the exponent of 1+b′jX, i.e., 1+b′jX=1+ϵ′LjX, then LjX=log⌈1+bjX⌉ϵ′/log1+ϵ′=Onlog1+bjX/ϵ.For anyϵ>0, let ϵ″=ϵ/2nB and RB=Ji1B,Ji2B,…,JiqB be the set of the rejected B-jobs, where i1<i2<⋯<iq. The inflated rejection penalty of RB is defined as follows:(3)fϵ″RB=ei1B+fϵ″RB−Ji1Bϵ″,q≥1;0,RB=∅.Lemma 4.
For any0<x≤1 and any integer n≥1,1+x/nn≤1+2x holds [29].Lemma 5.
For anyRB⊆JB and ϵ″>0,fϵ″RB≤1+ϵ″RB∑JjB∈RBejB [28].Lemma 6.
For any0<ϵ≤2, the optimal objective function value for 1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA with the modified deteriorating rates b′jX is at most of 1+ϵ times the optimal objective function value for 1rej,pjX=bjXt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA.Proof.
Assume that jobs in setAA are scheduled in the order of 1,2,…,AA, let ABi be the set of accepted B-jobs which precede JiA and AAB be the set of accepted A-jobs before the last B-job. The objective function with the modified deteriorating rates b′jXis as follows:(4)∑JiA∈AAC′iA+∑JjA∈RAejA=∑i=1AAt0∏j=1i1+b′jA∏JkB∈ABi1+b′kB+∑JjA∈RAejA≤∑i=1AAt01+ϵ′i+ABi∏j=1i1+bjA∏JkB∈ABi1+bkB+∑JjA∈RAejA≤1+ϵ′n∑i=1AAt0∏j=1i1+bjA∏JkB∈ABi1+bkB+∑JjA∈RAejA≤1+ϵ∑JiA∈AACiA+∑JjA∈RAejA,C′maxB+fϵ″RB≤t0∏JiA∈AAB1+b′iA∏JjB∈AB1+b′jB+1+ϵ∑JjB∈RBejB≤t01+ϵ′n∏JiA∈AAB1+biA∏JjB∈AB1+bjB+1+ϵ∑JjB∈RBejB≤1+ϵCmaxB+∑JjB∈RBejB≤1+ϵQ.
We then propose an exact dynamic programming algorithm for problem1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA with the modified deteriorating rates. Firstly, we renumber the jobs such that b′1A/1+bb′1A≤b′2A/1+bb′2A≤⋯≤b′nAA/1+bb′nAA and b′1B≤b′2B≤⋯≤b′nBB. We define(5)τl=1+ϵ′l,l≠−1,0,l=−1.νh=1+ϵ″h,h≠−1,0,h=−1.
Letfi,jl,lB,h denote the optimal objective function value satisfying the following conditions: (1) the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB; (2) the completion time of the last job is t0τl; (3) the completion time of the last B-job is no more than t0τlB; and (4) the total rejection penalty of the rejected B-jobs is νh.
The initial conditions are as follows:(6)f0,0l,lB,h=0,ifl=lB=h=−1;+∞,otherwise.
Now we consider any optimal schedule for jobsJ1A,J2A,…,JiA and J1B,J2B,…,JjB which meets the above conditions. In any such schedule, either JiA is rejected, JjB is rejected, or the last scheduled job is one of JiA and JjB.Case 1. JobJiA is rejected. Then, we have fi,jl,lB,h=fi−1,jl,lB,h+eiA.Case 2. The last scheduled job isJiA. In this case, for the accepted job among J1A,J2A,…,Ji−1A and J1B,J2B,…,JjB, the completion time of the last job must be t0τl−LiA, the completion time of the last B-job is no more than t0τlB, and the total rejection penalty of the rejected B-jobs is νh. Then, we have fi,jl,lB,h=fi−1,jl−LiA,lB,h+t0τl.Case 3. JobJjB is rejected. At this point, in the corresponding optimal schedule for J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last jobs is t0τl, the completion time of the last B-job is no more than t0τlB, and the total rejection penalty of the rejected B-jobs among J1B,J2B,…,Jj−1B is νh′ and −1≤h′≤h˜, where h˜ is given by 1+ϵ″h˜=fϵ″J1B,J2B,…,Jj−1B. If t0τlB+νh′≤1+ϵQ holds, we have fi,jl,lB,h=min−1≤h′≤h˜fi,j−1l,lB,h′.Case 4. The last scheduled job isJjB. In this case, for the accepted job among J1A,J2A,…,JiA and J1B,J2B,…,Jj−1B, the completion time of the last job must be t0τl−LjB, the completion time of the last B-job is no more than t0τlB−LjB, and the total rejection penalty of the rejected B-jobs is νh. If t0τlB+νh≤1+ϵQ holds, we have fi,jl,lB,h=fi,j−1l−LjB,lB−LjB,h.
Combining the above four cases, we get the following recursive function:(7)fi,jl,lB,h=minfi−1,jl,lB,h+eiA,fi−1,jl−LiA,lB,h+t0τl,min−1≤h′≤h˜fi,j−1l,lB,h′,ift0τlB+νh≤1+ϵQ;fi,j−1l−LjB,lB−LjB,h,ift0τlB+νh≤1+ϵQ,where h˜ is given by 1+ϵ″h˜=fϵ″J1B,J2B,…,Jj−1B.
The optimal value is given byminfnA,nBl,lB,h:−1≤l≤∑i=1nALiA+∑j=1nBLjB,−1≤lB≤L,−1≤h≤H, where L and H are the smallest integer such that 1+ϵ′L≥1+ϵQ and 1+ϵ″H≥1+ϵQ, respectively, hence L=OnlogQ/ϵ and H=OnBlogQ/ϵ. The corresponding optimal schedule can be found by backtracking.Theorem 2.
Problem1rej,pjX=bjXt,CmaxB+fϵ″RB≤1+ϵQ∑JjA∈AACjA+∑JjA∈RAejA can be solved in OnAnB3n2/ϵ4log3QlogTP time.Proof.
The recursive function has at mostOnAnB2n2/ϵ3log2QlogTP states, if the B-jobs is rejected, each iteration costs OH time; for the other three cases, each iteration cost a constant time. Hence, the total running time is bounded by OnAnB3n2/ϵ4log3QlogTP.


## 4. Problem1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA

### 4.1. Dynamic Programming Algorithm

Agnetis et al. [18] showed that problem 1∑CjB≤Q∑CjA, a special case of our problem when a=1,b=0 and the rejection penalty is large enough, i.e., it is optimal to accept all the jobs, is NP-hard. Hence, our problem 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA is at least NP-hard.Lemma 7.
There exists an optimal schedule for1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA such that the accepted A-jobs and accepted B-jobs are processed in nondecreasing order of bjX/1+bbjX, X∈A,B, respectively.Based on Lemma7, we renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Letfi,j,t,CB,EB be the optimal objective function value when the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB, where t is the completion time of the last job, CB is the total completion time of the accepted B-jobs and EB is the total rejection penalty of the rejected B-jobs. Let list Γij include all the possible quadruplets solutions fi,j,t,CB,EB,t,CB,EB. Then, we can give the following forward dynamic programming algorithm. First, we initialize Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0. For each quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, we construct either two quadruplets in Γi+1j by adding job Ji+1A to this state or two quadruplets in Γij+1 by adding job Jj+1B to this state. More specifically, for any quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij we do the following:Case 1: JobJi+1A is rejected. At this point, we have gi+1,j,t,CB,EB,t,CB,EB in Γi+1j, where gi+1,j,t,CB,EB=fi,j,t,CB,EB+ei+1A.Case 2: The last scheduled job isJi+1A. At this point, we have gi+1,j,t′,CB,EB,t,CB,EB in Γi+1j, where gi+1,j,t′,CB,EB=fi,j,t,CB,EB+t′ and t′=t+a/b1+bi+1Ab−a/b, where t′ is the completion time of Ji+1A.Case 3: JobJj+1B is rejected. If CB+EB+ej+1B≤Q, we include the quadruplet gi,j+1,t,CB, EB+ej+1B,t,CB,EB+ej+1B in Γij+1, where gi,j+1,t,CB,EB+ej+1B=fi,j,t,CB,EB.Case 4: The last scheduled job isJj+1B. At this point, the completion time of Jj+1B is t′=t+a/b1+bj+1Bb−a/b and CB′=CB+t′. If CB+t+a/b1+bj+1Bb−a/b+EB≤Q holds, we include the quadruplet gi,j+1,t′,CB′,EB′,t′,CB′,EB′ in Γij+1, where gi,j+1,t′,CB′,EB′=fi,j,t,CB,EB, and EB′=EB.Naturally, the construction of listΓi+1j or Γij+1 may generate more than one quadruplet with same t,CB, and EB values. To find the optimal value, among all quadruplets with same t,CB, and EB values, we can keep in Γi+1j or Γij+1 only the one with the minimum fi+1,j,t,CB,EB or fi,j+1,t,CB,EB value, respectively, that is, if there are qi+1,j,t,CB,EB quadruplets in Γi+1j, i.e., g1i+1,j,t,CB,EB,t,CB,EB,g2i+1,j,t,CB,EB,t,CB,EB,…, gqi+1,j,t,CB,EBi+1,j,t,CB,EB,t,CB,EB with the same t, CB, and EB values, we keep in Γi+1j only the quadruplet fi+1,j,t,CB,EB,t,CB,EB, where fi+1,j,t,CB,EB=minr=1,2,…,qi+1,j,t,CB,EBgri+1,j,t,CB,EB.At the end, the optimal solution is given by thefnA,nB,t,CB,EB value that corresponds to the quadruplet fnA,nB,t,CB,EB,t,CB,EB with the minimum fnA,nB,t,CB,EB value among all the quadruplets in ΓnAnB. Next, we propose an exact algorithm for 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA.Theorem 3.
Algorithm 1 solves problem1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejAinOnAnBQ2TP.Algorithm 1:Dynamic programming algorithm.
Step 1:Preprocessing: Renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Step 2:Initialization: Set Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0.Step 3:Generation:Fori=0 to nA doForj=0 to nB do.Out of each quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij doConstruct inΓi+1j the quadruplet gi+1,j,t,CB,EB,t,CB,EB, where gi+1,j,t,CB,EB=fi,j,t,CB,EB+ei+1A and the quadruplet gi+1,j,t′,CB,EB,t′,CB,EB, where gi+1,j,t′,CB,EB=fi,j,t,CB,EB+t′, and t′=t+a/b1+bi+1Ab−a/b.IfCB+EB+ej+1B≤Q;Construct inΓij+1 the quadruplet gi,j+1,t,CB,EB+ej+1B,t,CB,EB+ej+1B, where gi,j+1,t,CB,EB+ej+1B=fi,j,t,CB,EB;EndifIfCB+t+a/b1+bj+1Bb−a/b+EB≤Q;Construct inΓij+1 the quadruplet gi,j+1,t′,CB′,EB,t′,CB′,EB, where gi,j+1,t′,CB′,EB′=fi,j,t,CB,EB, t′=t+a/b1+bj+1Bb−a/b, CB′=CB+t′ and EB′=EB;EndifElimination:(1)
Among theqi+1,j,t,CB,EB quadruplets g1i+1,j,t,CB,EB,t,CB,EB,g2i+1,j,t,CB,EB,t,CB,EB, ⋯, gqi+1,j,t,CB,EBi+1,j,t,CB,EB,t,CB,EB in Γi+1j with the same t, CB, and EB values, we keep in Γi+1j only the quadruplet fi+1,j,t,CB,EB,t,CB,EB, wherefi+1,j,t,CB,EB=minr=1,2,…,qi+1,j,t,CB,EBgri+1,j,t,CB,EB;(2)
Among theqi,j+1,t,CB,EB quadruplets g1i,j+1,t,CB,EB,t,CB,EB,g2i,j+1,t,CB,EB,t,CB,EB, ⋯, gqi,j+1,t,CB,EBi,j+1,t,CB,EB,t,CB,EB in Γij+1 with the same t, CB, and EB values, we keep in Γij+1 only the quadruplet fi,j+1,t,CB,EB,t,CB,EB, wherefi,j+1,t,CB,EB=minr=1,2,…,qi,j+1,t,CB,EBgri,j+1,t,CB,EB;EndforEndforStep 4:Result: The optimal solution value is given by fnA,nB,t,CB,EB with the minimum fnA,nB,t,CB,EB value among all quadruplets in ΓnAnB, the optimal solution can be found by backtracking.Proof.
The optimality of Algorithm 1 follows from the above analysis. Step 1 requires a sorting procedure, which takesOnAlognA+nBlognB time. Step 2 requires O1 time. In Step 3, out of each quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, we construct at most two quadruplets in Γi+1j or two quadruplets in Γij+1. Since we have OQ2TP quadruplets in each list, the construction of Γi+1j or Γij+1 requires OQ2TP time, this is also the time of elimination process. After nAnB iterations, Step 3 can be executed in OnAnBQ2TP time. Step 4 takes OQ2TP time. Hence, the total running time of Algorithm 1 is indeed OnAnBQ2TP.


### 4.2. Fully Polynomial-Time Approximation Scheme

In this subsection, we mainly describe how to convert Algorithm 1 into an FPTAS by partitioning the state space into boxes [30], which originates from the interval partitioning technique proposed by Sahni [31]. To do this, we divided the state space Γij, i=1,2,…,nA,j=1,2,…,nB, into three-dimensional boxes and approximate the solution by retaining only one state within any box. The detailed algorithm (Algorithm 2) is described as follows:Algorithm 2:Fully polynomial-time approximation scheme.
Step 1:Preprocessing: Renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Step 2:Initialization: Set Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0.Step 3:Generation:Fori=0 to nA doForj=0 to nB do[State Generation]:GenerateΓi+1j or Γij+1 from Γij the same as that in Algorithm 1 except for replacing Q by Q¯=1+ϵQ.[Labeling]:For each quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij, attach the label Δfi,j,t,CB,EB,Δt,ΔCB to it, where the function Δ is defined as Δx=k in which x satisfies δk≤x≤δk+1 and δ=1+ϵ/21+ϵn;[Elimination]:(1)
For any two quadrupletsfi+1,j,t,CB,EB,t,CB,EB and fi+1,j,t′,CB′,EB′′,t′,CB′,EB′ in Γi+1j with the same label and EB≤EB′, eliminate the latter quadruplet from Γi+1j;(2)
For any two quadrupletsfi,j+1,t,CB,EB,t,CB,EB and fi,j+1,t′,CB′,EB′′,t′,CB′,EB′ in Γij+1 with the same label and EB≤EB′, eliminate the latter quadruplet from Γij+1;EndforEndforStep 4:Result: The approximate solution value is given by fnA,nB,t˜,CB˜,EB˜ with the minimum fnA,nB,t˜,CB˜,EB˜ value among all the quadruplets in ΓnAnB.Lemma 8.
For any eliminated quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij, there exists a quadruplet fi,j,t′,CB′,EB′′,t′,CB′,EB′ such that fi,j,t′,CB′,EB′′≤δi+jfi,j,t,CB,EB,t′≤δi+jt,CB′≤δi+jCB and EB′≤EB.Proof.
We prove the lemma by induction oni+j. Obviously, lemma holds for i+j=1. Now let’s assume that the lemma holds for i+j−1, i.e.,(1)
For any eliminated quadrupletfi−1,j,t,CB,EB,t,CB,EB∈Γi−1j, there exists a quadruplet fi−1,j,t′,CB′,EB′′,t′,CB′,EB′ such that fi−1,j,t′,CB′,EB′′≤δi+j−1fi−1,j,t,CB,EB, t′≤δi+j−1t,CB′≤δi+j−1CB,and EB′≤EB;(2)
For any eliminated quadrupletfi,j−1,t,CB,EB,t,CB,EB∈Γij−1, there exists a quadruplet fi,j−1,t˜,CB˜,EB˜,t˜,CB˜,EB˜ such that fi,j−1,t˜,CB˜,EB˜≤δi+j−1fi,j−1,t,CB, EB,t˜≤δi+j−1t,CB˜≤δi+j−1CB, and EB˜≤EB.
We need to show that the lemma holds also fori+j. That is to say, for any eliminated quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, there is a quadruplet fi,j,t¯,C¯B,E¯B,t¯,C¯B,E¯B such that fi,j,t¯,C¯B,E¯B≤δi+jfi,j,t,CB,EB,t¯≤δi+jt,C¯B≤δi+jCB and E¯B≤EB
Consider an arbitrary quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij. We first consider Case 1 that JiA is rejected. While implementing Algorithm 2, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^∈Γi−1j, where gi−1,j,t^,CB^,EB^=fi,j,t,CB,EB−eiA, t^=t, CB^=CB and EB^=EB. According to the induction hypothesis, there exists a quadruplet gi−1,j,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^) with gi−1,j,t′,CB′,EB′≤δi+j−1gi−1,j,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij, there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi−1,j,t′,CB′,EB′+eiA, t″=t′,CB″=CB′ and EB″=EB′. Thus after the elimination in Γij, there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi−1,j,t′,CB′,EB′+δeiA≤δi+jgi−1,j,t^,CB^,EB^+δeiA=δi+jfi,j,t,CB,EB+δ−δi+jeiA≤δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δt′≤δi+jt^=δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Let us now consider Case 2, where the last scheduled job isJiA, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^∈Γi−1j, where gi−1,j,t^,CB^,EB^=fi,j,t,CB,EB−t,t^=t−abiA/1+bbiA,CB^=CB and EB^=EB. According to the induction hypothesis, there exists a quadruplet gi−1,j,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^)with gi−1,j,t′,CB′,EB′≤δi+j−1gi−1,j,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij, there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi−1,j,t′,CB′,EB′+abiA+1+bbiAt′,t″=abiA+1+bbiAt′,CB″=CB′ and EB″=EB′. Thus after the elimination in Γij, there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi−1,j,t′,CB′,EB′+δabiA+δ1+bbiAt′≤δi+jgi−1,j,t^,CB^,EB^+δabiA+δi+j1+bbiAt^=δi+jfi,j,t,CB,EB+δ−δi+jabiA≤δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δabiA+δ1+bbiAt′≤δabiA+δi+j1+bbiAt^=δi+jt+δ−δi+jabiA≤δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Let’s then consider Case 3 thatJjB is rejected, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^∈Γij−1, where gi,j−1,t^,CB^,EB^=fi,j,t,CB,EB,t^=t,CB^=CB and EB^=EB−ejB. This implies that CB^+EB^+ejB≤1+ϵQ. According to the induction hypothesis, there exists a quadruplet gi,j−1,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^) with gi,j−1,t′,CB′,EB′≤δi+j−1gi,j−1,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij there exists a quadruplet gi,j,t″,CB″,EB″, t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi,j−1,t′,CB′,EB′,t″=t′,CB″=CB′ and EB″=EB′+ejB. Thus after the elimination in Γij there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi,j−1,t′,CB′,EB′≤δi+jgi,j−1,t^,CB^,EB^=δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δt′≤δi+jt^=δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′+ejB≤EB^+ejB=EB.
Last we consider Case 4 that the last scheduled job isJjB. In this case, this state fi,j,t,CB,EB, t,CB,EB is constructed from the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^∈Γij−1 where gi,j−1,t^,CB^,EB^=fi,j,t,CB,EB,t^=t−abjB/1+bbjB, CB^=CB−t and EB^=EB. This implies that CB^+abjB+1+bbjBt^+EB^≤1+ϵQ. According to the induction hypothesis, there exists a quadruplet gi,j−1,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^) with gi,j−1,t′,CB′,EB′≤δi+j−1gi,j−1,t^,CB^,EB^, t′≤δi+j−1t^, CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi,j−1,t′,CB′,EB′,t″=abjB+1+bbjBt′,CB″=CB′+abjB+1+bbjBt′ and EB″=EB′. Thus, after the elimination in Γij there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi,j−1,t′,CB′,EB′≤δi+jgi,j−1,t^,CB^,EB^=δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δabjB+δ1+bbjBt′≤δabjB+δi+j1+bbjBt^=δi+jt+δ−δi+jabjB≤δi+jt,(c)
CB‴≤δCB″=δCB′+δabjB+δ1+bbjBt′≤δi+jCB^+δabjB+δi+j1+bbjBt^=δi+jCB+δ−δi+jabjB≤δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Combining the above four cases, the induction hypothesis holds fori+j in each case.Theorem 4.
For anyϵ>0 and an optimal quadruplet f∗nA,nB,t∗,CB∗,EB∗,t∗,CB∗,EB∗, Algorithm 2 finds in OnAnBn3log2TPlogQ/ϵ3 time a quadruplet fnA,nB,t,CB˜,EB˜,t˜,CB˜,EB˜ such that fnA,nB,t˜,CB˜,EB˜≤1+ϵf∗nA,nB,t∗,CB∗,EB∗ and CB˜+EB˜≤1+ϵQ.Proof.
Based on Lemma8, if f∗nA,nB,t∗,CB∗,EB∗,t∗,CB∗,EB∗ is the corresponding quadruplet of the optimal solution, and if we can eliminate it in Algorithm 2, there will be a noneliminated quadruplet fnA,nB,t˜,CB˜,EB˜,t˜,CB˜,EB˜ with the following:(1)
fnA,nB,t˜,CB˜,EB˜≤δnf∗nA,nB,t∗,CB∗,EB∗=1+ϵ/21+ϵnnf∗nA,nB,t∗,CB∗,EB∗≤1+ϵ/1+ϵf∗nA,nB,t∗,CB∗,EB∗≤1+ϵf∗nA,nB,t∗,CB∗,EB∗,(2)
CB˜+EB˜≤δnCB∗+EB∗=1+ϵ/21+ϵnnCB∗+EB∗≤1+ϵCB+EB≤1+ϵQ.
Then, we discuss the time complexity of Algorithm 2. Step 1 takesOnAlognA+nBlognB time. Step 2 takes O1 time. Note that there are at most TP possible value for t, 1+ϵQ possible value for CB and nTP possible value for fi,j,t,CB,EB. Therefore, the number of possible values of Δt is ⌈logδTP⌉=⌈logTP/logδ⌉≤⌈1+2n1+ϵ/ϵlogTP⌉=OnlogTP/ϵ. Similarly, the number of possible values ΔCB is ⌈logδ1+ϵQ⌉≤1+2n1+ϵ/ϵlog1+ϵQ=OnlogQ/ϵ, and the number of possible value fi,j,t,CB,EB is ⌈logδnTP⌉=OnlogTP/ϵ. Hence, the total number of different boxes at the beginning of each iteration which equals the number of different quadruplets at the beginning of each iteration is at most On3log2TPlogQ/ϵ3, because after the elimination process, each possible label can retain at most one quadruplet. In addition, for each quadruplet in Γij, we can construct at most two quadruplets in Γi+1j or two quadruplets in Γij+1. So, Step 3 takes On3log2TPlogQ/ϵ3 time to construct Γi+1j and Γij+1. At the same time, this is the time required for the elimination process. In Step 4, the quadruplet fnA,nB,t˜,CB˜,EB˜,t˜,CB˜,EB˜ with minimum fnA,nB,t˜,CB˜,EB˜ in ΓnAnB can be found in On3log2TPlogQ/ϵ3 time. Because Step 3 requires at most OnAnB iterations, the overall complexity of Algorithm 2 is OnAnBn3log2TPlogQ/ϵ3.


## 4.1. Dynamic Programming Algorithm

Agnetis et al. [18] showed that problem 1∑CjB≤Q∑CjA, a special case of our problem when a=1,b=0 and the rejection penalty is large enough, i.e., it is optimal to accept all the jobs, is NP-hard. Hence, our problem 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA is at least NP-hard.Lemma 7.
There exists an optimal schedule for1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA such that the accepted A-jobs and accepted B-jobs are processed in nondecreasing order of bjX/1+bbjX, X∈A,B, respectively.Based on Lemma7, we renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Letfi,j,t,CB,EB be the optimal objective function value when the jobs in consideration are J1A,J2A,…,JiA and J1B,J2B,…,JjB, where t is the completion time of the last job, CB is the total completion time of the accepted B-jobs and EB is the total rejection penalty of the rejected B-jobs. Let list Γij include all the possible quadruplets solutions fi,j,t,CB,EB,t,CB,EB. Then, we can give the following forward dynamic programming algorithm. First, we initialize Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0. For each quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, we construct either two quadruplets in Γi+1j by adding job Ji+1A to this state or two quadruplets in Γij+1 by adding job Jj+1B to this state. More specifically, for any quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij we do the following:Case 1: JobJi+1A is rejected. At this point, we have gi+1,j,t,CB,EB,t,CB,EB in Γi+1j, where gi+1,j,t,CB,EB=fi,j,t,CB,EB+ei+1A.Case 2: The last scheduled job isJi+1A. At this point, we have gi+1,j,t′,CB,EB,t,CB,EB in Γi+1j, where gi+1,j,t′,CB,EB=fi,j,t,CB,EB+t′ and t′=t+a/b1+bi+1Ab−a/b, where t′ is the completion time of Ji+1A.Case 3: JobJj+1B is rejected. If CB+EB+ej+1B≤Q, we include the quadruplet gi,j+1,t,CB, EB+ej+1B,t,CB,EB+ej+1B in Γij+1, where gi,j+1,t,CB,EB+ej+1B=fi,j,t,CB,EB.Case 4: The last scheduled job isJj+1B. At this point, the completion time of Jj+1B is t′=t+a/b1+bj+1Bb−a/b and CB′=CB+t′. If CB+t+a/b1+bj+1Bb−a/b+EB≤Q holds, we include the quadruplet gi,j+1,t′,CB′,EB′,t′,CB′,EB′ in Γij+1, where gi,j+1,t′,CB′,EB′=fi,j,t,CB,EB, and EB′=EB.Naturally, the construction of listΓi+1j or Γij+1 may generate more than one quadruplet with same t,CB, and EB values. To find the optimal value, among all quadruplets with same t,CB, and EB values, we can keep in Γi+1j or Γij+1 only the one with the minimum fi+1,j,t,CB,EB or fi,j+1,t,CB,EB value, respectively, that is, if there are qi+1,j,t,CB,EB quadruplets in Γi+1j, i.e., g1i+1,j,t,CB,EB,t,CB,EB,g2i+1,j,t,CB,EB,t,CB,EB,…, gqi+1,j,t,CB,EBi+1,j,t,CB,EB,t,CB,EB with the same t, CB, and EB values, we keep in Γi+1j only the quadruplet fi+1,j,t,CB,EB,t,CB,EB, where fi+1,j,t,CB,EB=minr=1,2,…,qi+1,j,t,CB,EBgri+1,j,t,CB,EB.At the end, the optimal solution is given by thefnA,nB,t,CB,EB value that corresponds to the quadruplet fnA,nB,t,CB,EB,t,CB,EB with the minimum fnA,nB,t,CB,EB value among all the quadruplets in ΓnAnB. Next, we propose an exact algorithm for 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA.Theorem 3.
Algorithm 1 solves problem1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejAinOnAnBQ2TP.Algorithm 1:Dynamic programming algorithm.
Step 1:Preprocessing: Renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Step 2:Initialization: Set Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0.Step 3:Generation:Fori=0 to nA doForj=0 to nB do.Out of each quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij doConstruct inΓi+1j the quadruplet gi+1,j,t,CB,EB,t,CB,EB, where gi+1,j,t,CB,EB=fi,j,t,CB,EB+ei+1A and the quadruplet gi+1,j,t′,CB,EB,t′,CB,EB, where gi+1,j,t′,CB,EB=fi,j,t,CB,EB+t′, and t′=t+a/b1+bi+1Ab−a/b.IfCB+EB+ej+1B≤Q;Construct inΓij+1 the quadruplet gi,j+1,t,CB,EB+ej+1B,t,CB,EB+ej+1B, where gi,j+1,t,CB,EB+ej+1B=fi,j,t,CB,EB;EndifIfCB+t+a/b1+bj+1Bb−a/b+EB≤Q;Construct inΓij+1 the quadruplet gi,j+1,t′,CB′,EB,t′,CB′,EB, where gi,j+1,t′,CB′,EB′=fi,j,t,CB,EB, t′=t+a/b1+bj+1Bb−a/b, CB′=CB+t′ and EB′=EB;EndifElimination:(1)
Among theqi+1,j,t,CB,EB quadruplets g1i+1,j,t,CB,EB,t,CB,EB,g2i+1,j,t,CB,EB,t,CB,EB, ⋯, gqi+1,j,t,CB,EBi+1,j,t,CB,EB,t,CB,EB in Γi+1j with the same t, CB, and EB values, we keep in Γi+1j only the quadruplet fi+1,j,t,CB,EB,t,CB,EB, wherefi+1,j,t,CB,EB=minr=1,2,…,qi+1,j,t,CB,EBgri+1,j,t,CB,EB;(2)
Among theqi,j+1,t,CB,EB quadruplets g1i,j+1,t,CB,EB,t,CB,EB,g2i,j+1,t,CB,EB,t,CB,EB, ⋯, gqi,j+1,t,CB,EBi,j+1,t,CB,EB,t,CB,EB in Γij+1 with the same t, CB, and EB values, we keep in Γij+1 only the quadruplet fi,j+1,t,CB,EB,t,CB,EB, wherefi,j+1,t,CB,EB=minr=1,2,…,qi,j+1,t,CB,EBgri,j+1,t,CB,EB;EndforEndforStep 4:Result: The optimal solution value is given by fnA,nB,t,CB,EB with the minimum fnA,nB,t,CB,EB value among all quadruplets in ΓnAnB, the optimal solution can be found by backtracking.Proof.
The optimality of Algorithm 1 follows from the above analysis. Step 1 requires a sorting procedure, which takesOnAlognA+nBlognB time. Step 2 requires O1 time. In Step 3, out of each quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, we construct at most two quadruplets in Γi+1j or two quadruplets in Γij+1. Since we have OQ2TP quadruplets in each list, the construction of Γi+1j or Γij+1 requires OQ2TP time, this is also the time of elimination process. After nAnB iterations, Step 3 can be executed in OnAnBQ2TP time. Step 4 takes OQ2TP time. Hence, the total running time of Algorithm 1 is indeed OnAnBQ2TP.


## 4.2. Fully Polynomial-Time Approximation Scheme

In this subsection, we mainly describe how to convert Algorithm 1 into an FPTAS by partitioning the state space into boxes [30], which originates from the interval partitioning technique proposed by Sahni [31]. To do this, we divided the state space Γij, i=1,2,…,nA,j=1,2,…,nB, into three-dimensional boxes and approximate the solution by retaining only one state within any box. The detailed algorithm (Algorithm 2) is described as follows:Algorithm 2:Fully polynomial-time approximation scheme.
Step 1:Preprocessing: Renumber the jobs such that b1A/1+bb1A≤b2A/1+bb2A≤⋯≤bnAA/1+bbnAA and b1B/1+bb1B≤b2B/1+bb2B≤⋯≤bnBB/1+bbnBB.Step 2:Initialization: Set Γ00=f0,0,t0,0,0,t0,0,0=0,t0,0,0.Step 3:Generation:Fori=0 to nA doForj=0 to nB do[State Generation]:GenerateΓi+1j or Γij+1 from Γij the same as that in Algorithm 1 except for replacing Q by Q¯=1+ϵQ.[Labeling]:For each quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij, attach the label Δfi,j,t,CB,EB,Δt,ΔCB to it, where the function Δ is defined as Δx=k in which x satisfies δk≤x≤δk+1 and δ=1+ϵ/21+ϵn;[Elimination]:(1)
For any two quadrupletsfi+1,j,t,CB,EB,t,CB,EB and fi+1,j,t′,CB′,EB′′,t′,CB′,EB′ in Γi+1j with the same label and EB≤EB′, eliminate the latter quadruplet from Γi+1j;(2)
For any two quadrupletsfi,j+1,t,CB,EB,t,CB,EB and fi,j+1,t′,CB′,EB′′,t′,CB′,EB′ in Γij+1 with the same label and EB≤EB′, eliminate the latter quadruplet from Γij+1;EndforEndforStep 4:Result: The approximate solution value is given by fnA,nB,t˜,CB˜,EB˜ with the minimum fnA,nB,t˜,CB˜,EB˜ value among all the quadruplets in ΓnAnB.Lemma 8.
For any eliminated quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij, there exists a quadruplet fi,j,t′,CB′,EB′′,t′,CB′,EB′ such that fi,j,t′,CB′,EB′′≤δi+jfi,j,t,CB,EB,t′≤δi+jt,CB′≤δi+jCB and EB′≤EB.Proof.
We prove the lemma by induction oni+j. Obviously, lemma holds for i+j=1. Now let’s assume that the lemma holds for i+j−1, i.e.,(1)
For any eliminated quadrupletfi−1,j,t,CB,EB,t,CB,EB∈Γi−1j, there exists a quadruplet fi−1,j,t′,CB′,EB′′,t′,CB′,EB′ such that fi−1,j,t′,CB′,EB′′≤δi+j−1fi−1,j,t,CB,EB, t′≤δi+j−1t,CB′≤δi+j−1CB,and EB′≤EB;(2)
For any eliminated quadrupletfi,j−1,t,CB,EB,t,CB,EB∈Γij−1, there exists a quadruplet fi,j−1,t˜,CB˜,EB˜,t˜,CB˜,EB˜ such that fi,j−1,t˜,CB˜,EB˜≤δi+j−1fi,j−1,t,CB, EB,t˜≤δi+j−1t,CB˜≤δi+j−1CB, and EB˜≤EB.
We need to show that the lemma holds also fori+j. That is to say, for any eliminated quadruplet fi,j,t,CB,EB,t,CB,EB∈Γij, there is a quadruplet fi,j,t¯,C¯B,E¯B,t¯,C¯B,E¯B such that fi,j,t¯,C¯B,E¯B≤δi+jfi,j,t,CB,EB,t¯≤δi+jt,C¯B≤δi+jCB and E¯B≤EB
Consider an arbitrary quadrupletfi,j,t,CB,EB,t,CB,EB∈Γij. We first consider Case 1 that JiA is rejected. While implementing Algorithm 2, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^∈Γi−1j, where gi−1,j,t^,CB^,EB^=fi,j,t,CB,EB−eiA, t^=t, CB^=CB and EB^=EB. According to the induction hypothesis, there exists a quadruplet gi−1,j,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^) with gi−1,j,t′,CB′,EB′≤δi+j−1gi−1,j,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij, there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi−1,j,t′,CB′,EB′+eiA, t″=t′,CB″=CB′ and EB″=EB′. Thus after the elimination in Γij, there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi−1,j,t′,CB′,EB′+δeiA≤δi+jgi−1,j,t^,CB^,EB^+δeiA=δi+jfi,j,t,CB,EB+δ−δi+jeiA≤δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δt′≤δi+jt^=δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Let us now consider Case 2, where the last scheduled job isJiA, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^∈Γi−1j, where gi−1,j,t^,CB^,EB^=fi,j,t,CB,EB−t,t^=t−abiA/1+bbiA,CB^=CB and EB^=EB. According to the induction hypothesis, there exists a quadruplet gi−1,j,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi−1,j,t^,CB^,EB^,t^,CB^,EB^)with gi−1,j,t′,CB′,EB′≤δi+j−1gi−1,j,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij, there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi−1,j,t′,CB′,EB′+abiA+1+bbiAt′,t″=abiA+1+bbiAt′,CB″=CB′ and EB″=EB′. Thus after the elimination in Γij, there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi−1,j,t′,CB′,EB′+δabiA+δ1+bbiAt′≤δi+jgi−1,j,t^,CB^,EB^+δabiA+δi+j1+bbiAt^=δi+jfi,j,t,CB,EB+δ−δi+jabiA≤δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δabiA+δ1+bbiAt′≤δabiA+δi+j1+bbiAt^=δi+jt+δ−δi+jabiA≤δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Let’s then consider Case 3 thatJjB is rejected, the quadruplet fi,j,t,CB,EB,t,CB,EB is constructed from the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^∈Γij−1, where gi,j−1,t^,CB^,EB^=fi,j,t,CB,EB,t^=t,CB^=CB and EB^=EB−ejB. This implies that CB^+EB^+ejB≤1+ϵQ. According to the induction hypothesis, there exists a quadruplet gi,j−1,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^) with gi,j−1,t′,CB′,EB′≤δi+j−1gi,j−1,t^,CB^,EB^,t′≤δi+j−1t^,CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij there exists a quadruplet gi,j,t″,CB″,EB″, t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi,j−1,t′,CB′,EB′,t″=t′,CB″=CB′ and EB″=EB′+ejB. Thus after the elimination in Γij there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi,j−1,t′,CB′,EB′≤δi+jgi,j−1,t^,CB^,EB^=δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δt′≤δi+jt^=δi+jt,(c)
CB‴≤δCB″=δCB′≤δi+jCB^=δi+jCB, and(d)
EB‴≤EB″=EB′+ejB≤EB^+ejB=EB.
Last we consider Case 4 that the last scheduled job isJjB. In this case, this state fi,j,t,CB,EB, t,CB,EB is constructed from the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^∈Γij−1 where gi,j−1,t^,CB^,EB^=fi,j,t,CB,EB,t^=t−abjB/1+bbjB, CB^=CB−t and EB^=EB. This implies that CB^+abjB+1+bbjBt^+EB^≤1+ϵQ. According to the induction hypothesis, there exists a quadruplet gi,j−1,t′,CB′,EB′,t′,CB′,EB′ (which might also be the quadruplet gi,j−1,t^,CB^,EB^,t^,CB^,EB^) with gi,j−1,t′,CB′,EB′≤δi+j−1gi,j−1,t^,CB^,EB^, t′≤δi+j−1t^, CB′≤δi+j−1CB^ and EB′≤EB^. It directly follows that before the elimination in Γij there exists a quadruplet gi,j,t″,CB″,EB″,t″,CB″,EB″∈Γij with gi,j,t″,CB″,EB″=gi,j−1,t′,CB′,EB′,t″=abjB+1+bbjBt′,CB″=CB′+abjB+1+bbjBt′ and EB″=EB′. Thus, after the elimination in Γij there exists a quadruplet gi,j,t‴,CB‴,EB‴,t‴,CB‴,EB‴∈Γij with the following:(a)
gi,j,t‴,CB‴,EB‴≤δgi,j,t″,CB″,EB″=δgi,j−1,t′,CB′,EB′≤δi+jgi,j−1,t^,CB^,EB^=δi+jfi,j,t,CB,EB,(b)
t‴≤δt″=δabjB+δ1+bbjBt′≤δabjB+δi+j1+bbjBt^=δi+jt+δ−δi+jabjB≤δi+jt,(c)
CB‴≤δCB″=δCB′+δabjB+δ1+bbjBt′≤δi+jCB^+δabjB+δi+j1+bbjBt^=δi+jCB+δ−δi+jabjB≤δi+jCB, and(d)
EB‴≤EB″=EB′≤EB^=EB.
Combining the above four cases, the induction hypothesis holds fori+j in each case.Theorem 4.
For anyϵ>0 and an optimal quadruplet f∗nA,nB,t∗,CB∗,EB∗,t∗,CB∗,EB∗, Algorithm 2 finds in OnAnBn3log2TPlogQ/ϵ3 time a quadruplet fnA,nB,t,CB˜,EB˜,t˜,CB˜,EB˜ such that fnA,nB,t˜,CB˜,EB˜≤1+ϵf∗nA,nB,t∗,CB∗,EB∗ and CB˜+EB˜≤1+ϵQ.Proof.
Based on Lemma8, if f∗nA,nB,t∗,CB∗,EB∗,t∗,CB∗,EB∗ is the corresponding quadruplet of the optimal solution, and if we can eliminate it in Algorithm 2, there will be a noneliminated quadruplet fnA,nB,t˜,CB˜,EB˜,t˜,CB˜,EB˜ with the following:(1)
fnA,nB,t˜,CB˜,EB˜≤δnf∗nA,nB,t∗,CB∗,EB∗=1+ϵ/21+ϵnnf∗nA,nB,t∗,CB∗,EB∗≤1+ϵ/1+ϵf∗nA,nB,t∗,CB∗,EB∗≤1+ϵf∗nA,nB,t∗,CB∗,EB∗,(2)
CB˜+EB˜≤δnCB∗+EB∗=1+ϵ/21+ϵnnCB∗+EB∗≤1+ϵCB+EB≤1+ϵQ.
Then, we discuss the time complexity of Algorithm 2. Step 1 takesOnAlognA+nBlognB time. Step 2 takes O1 time. Note that there are at most TP possible value for t, 1+ϵQ possible value for CB and nTP possible value for fi,j,t,CB,EB. Therefore, the number of possible values of Δt is ⌈logδTP⌉=⌈logTP/logδ⌉≤⌈1+2n1+ϵ/ϵlogTP⌉=OnlogTP/ϵ. Similarly, the number of possible values ΔCB is ⌈logδ1+ϵQ⌉≤1+2n1+ϵ/ϵlog1+ϵQ=OnlogQ/ϵ, and the number of possible value fi,j,t,CB,EB is ⌈logδnTP⌉=OnlogTP/ϵ. Hence, the total number of different boxes at the beginning of each iteration which equals the number of different quadruplets at the beginning of each iteration is at most On3log2TPlogQ/ϵ3, because after the elimination process, each possible label can retain at most one quadruplet. In addition, for each quadruplet in Γij, we can construct at most two quadruplets in Γi+1j or two quadruplets in Γij+1. So, Step 3 takes On3log2TPlogQ/ϵ3 time to construct Γi+1j and Γij+1. At the same time, this is the time required for the elimination process. In Step 4, the quadruplet fnA,nB,t˜,CB˜,EB˜,t˜,CB˜,EB˜ with minimum fnA,nB,t˜,CB˜,EB˜ in ΓnAnB can be found in On3log2TPlogQ/ϵ3 time. Because Step 3 requires at most OnAnB iterations, the overall complexity of Algorithm 2 is OnAnBn3log2TPlogQ/ϵ3.


## 5. Conclusions

This paper investigated several two-agent scheduling problems with deteriorating jobs and rejection. Two agents share a single machine, and each agent has its own optimization criteria. We proposed a dynamic programming algorithm for1rej,pjX=bjXa+bt,CmaxB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA and 1rej,pjX=bjXa+bt,∑JjB∈ABCjB+∑JjB∈RBejB≤Q∑JjA∈AACjA+∑JjA∈RAejA, respectively. For the former problem, we give an FPTAS when a=0,b=1. For the latter problem, we also give an FPTAS.For future research, we can analyze scheduling problems with more than two agents. In addition, other machine environments, such as parallel machines or flow shop settings, are also worth studying.



---

*Source: 3565133-2022-11-28.xml*