# Scheduling Simple Linear Deteriorating Jobs with Rejection

Authors: Juan Zou; Yuzhong Zhang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We consider the problems of scheduling deteriorating jobs with release dates on a single machine (parallel machines) and jobs can be rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. For a single machine model, the objective is to minimize the maximum lateness of the accepted jobs plus the total penalty of the rejected jobs. We show that the problem is NP-hard in the strong sense and presents a fully polynomial time approximation scheme to solve it when all jobs have agreeable release dates and due dates. For parallel-machine model, the objective is to minimize the maximum delivery completion time of the accepted jobs plus the total penalty of the rejected jobs. When the jobs have identical release dates, we first propose a fully polynomial time approximation scheme to solve it. Then, we present a heuristic algorithm for the case where all jobs have to be accepted and evaluate its efficiency by computational experiments.


---

## Body

## 1. Introduction

For most classical scheduling problems, the processing times of jobs are considered to be constant and independent of their starting time. However, this assumption is not appropriate for the modelling of many modern industrial processes; we often encounter situations in which processing time increases over time, when the machines gradually lose efficiency. Such problems are generally known as scheduling with deterioration effects. Scheduling with linear deterioration was first considered by Browne and Yechiali [1] who assumed that the processing times of jobs are nondecreasing and start time dependent linear functions. They derived optimal scheduling policies that minimize the expected makespan. Mosheiov [2] considered simple linear deterioration where jobs have a fixed job-dependent growth rate but no basic processing time. He showed that most commonly applied performance criteria, such as the makespan, the total flow time, the total lateness, the sum of weighted completion time, the maximum lateness, the maximum tardiness, and the number of tardy jobs, remain polynomially solvable. Since then, machine scheduling problems with deteriorating jobs have received increasing attention. An extensive survey of different models and problems was provided by Alidaee and Womer [3]. Cheng et al. [4] presented an updated survey of the results on scheduling problems with time-dependent processing times. Other new results of scheduling with deterioration effect can be found in [5–7].At the same time, it is always assumed in traditional research that all the jobs have to be processed. In the real world, however, things may be more complicated. For example, due to limited resources or limited available capacity, the decider of a factory can choose only a subset of these tasks to be scheduled, while perhaps incurring some penalty for the rejected jobs. The machine scheduling problem with rejection was first introduced by Bartal et al. [8]. They studied both the offline and online versions of scheduling problem with rejection on 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. After that, the machine scheduling problem with rejection received more and more attention. Hoogeveen et al. [9] considered the offline multiprocessor scheduling problem with rejection where preemption is allowed. Zhang et al. [10] studied the single machine scheduling with release dates and rejection to minimize the sum of the maximum completion times of the scheduled jobs and the total penalty of the rejected jobs. Sengupta [11] considered algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Shabtay et al. [12] recently presented an updated survey on offline scheduling with rejection. In addition, there has been some work on scheduling deteriorating jobs with rejection. For example, Cheng and Sun [13] considered the single machine scheduling problem with deterioration and rejection, in which the processing time of a job is a linear function of its starting time. Li and Yuan [14] studied several parallel-machine scheduling problems in which the processing time of a job is a linear increasing function of its starting time and jobs can be rejected by paying penalties. The objectives are to minimize the makespan and the total weighted completion time plus the total penalty of the rejected jobs. Hsua and Chang [15] considered the unrelated parallel-machine scheduling with deteriorating jobs and rejection. To the best of our knowledge, the problems of scheduling deteriorating jobs with release dates and rejection have not been discussed.In this paper, we study the single machine (parallel-machine) scheduling of deteriorating jobs with release dates and rejection. The paper is organized as follows. In Section2, we formulate the problems under consideration and introduce some notations. In Section 3, we first discuss single machine model and show that the problem is strongly NP-hard. Then we propose a fully polynomial time approximation scheme for the case where all jobs have agreeable release dates and due dates. In Section 4, we consider parallel-machine scheduling problem with deterioration and rejection. In Section 5, we conclude the paper and suggest some topics for future research.


## 2. Problem Description and Notation

The problems considered in this paper can be formally described as follows. There are an independent job setJ={J1,…,Jn} and a single machine (m≥2 identical parallel machines {M1,…,Mm}). Each job Jj(j=1,…,n) has a release date rj, a due date dj (a delivery time qj), a deteriorating rate bj>0, and a rejection penalty ej. Each job Jj(j=1,…,n) is either rejected with a rejection penalty ej having to be paid or accepted and processed on the single machine (one of parallel machines). The actual processing time of job Jj is given by pj=bjt, where t≥rj is the starting time of Jj. Denote by R and R¯=J∖R the set of rejected jobs and the set of accepted jobs, respectively. Denote by Cj the completion time of the accepted job Jj. In the single machine model, assume min⁡{rj∣j=1,…,n}≥t0>0; the lateness of job Jj is defined as Lj=Cj-dj. The objective is to minimize the maximum lateness (i.e., Lmax⁡=max⁡{Lj:Jj∈R-}) plus the total penalty of the rejected jobs. In parallel-machine model, assume min⁡{rj∣j=1,…,n}=t0>0. We consider that each job Jj has a delivery time qj≥0 rather than a due date dj. The delivery of a job begins immediately after it completes processing, and job deliveries are allowed to overlap. We define the delivery completion time as Dj=Cj+qj; the objective is to minimize the maximum delivery completion time (i.e., Dmax⁡=max⁡{Dj:Jj∈R-}) plus the total penalty of the rejected jobs. Using the three-field notation of Graham et al. [16], the problems are denoted by 1∣rj,pj=bjt,rej∣Lmax⁡(R-)+∑Jj∈Rej and Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej.


## 3. The Single Machine Problem

### 3.1. NP-Hardness Proof

In this subsection, we first discuss the complexity of the problem1∣rj, pj=bjt∣Lmax⁡ where rejection is not considered.Theorem 1.
The problem1∣rj, pj=bjt∣Lmax⁡ is strongly NP-hard.Proof.
The decision version of the scheduling problem is clearly in NP. We use a reduction from the 4-product problem (4-P), which is strongly NP-hard (see [17]).
An instance of the 4-product problem is formulated as follows. GivenD∈Q+, a finite set N={1,2,…,4k} for some natural number k, a size yj∈Q+ and D1/5<yj<D1/3 for every j∈N, ∏j∈Nyj=Dk. Does there exist disjoint subsets N1,…,Nk such that ⋃i=1kNi=N and the product of sizes of the elements in Ni satisfies ∏j∈Niyj=D for 1≤i≤k ?
Given an arbitrary instanceI of 4-product problem, we construct an instance II of the scheduling problem as follows.(i)
There aren=5k-1 jobs.(ii)
For1≤j≤4k, rj=1, bj=yj-1, and dj=2k-1Dk.(iii)
For4k+1≤j≤5k-1, rj=2j-4k+1Dj-4k, bj=1, and dj=2j-4kDj-4k.(iv)
The threshold value is defined byY=0.
The decision version asks whether there is a scheduleπ for problem 1∣rj,pj=bjt∣Lmax⁡ such that Lmax⁡≤Y.
It is clear that the reduction can be done in polynomial time. Now we prove that instanceI has a solution if and only if instance II has a schedule π with Lmax⁡≤Y.
Assume that 4-product problem has a solution; that is, there exist disjoint subsetsN1,…,Nk such that ⋃i=1kNi=N and the product of sizes of the elements in Ni satisfies ∏j∈Niyj=D for 1≤i≤k. For convenience, we denote the set of jobs {Jj:j∈Nl}(1≤l≤k) by JNl. The jobs are scheduled without idle times as follows. First, the set of jobs JNl are scheduled in the interval [2l-1Dl-1,2l-1Dl] for l=1,…,k. Next, each job Jj is scheduled at time rj=2j-4k+1Dj-4k for j=4k+1,…,5k-1. Therefore, the maximum lateness of this schedule is Lmax⁡=max⁡{Cj-dj:1≤j≤5k-1}=0.
Conversely, assume that there is a scheduleπ with Lmax⁡≤0. We are ready to prove that instance I has a solution.
First, each jobJj(4k+1≤j≤5k-1) must start exactly at its release date rj and finish at its due date dj, since Lmax⁡≤Y=0. Second, the rest 4k jobs are scheduled as the k intervals from time t=1 to time t=2k-1Dk. Without loss of generality, let JNl(1≤l≤k) be the set of jobs scheduled in the interval [2l-1Dl-1,2l-1Dl].
Therefore, from the above discussion, we know that∏j∈Nlyj≤D for 1≤l≤k. Note that ∏l=1k∏j∈Nlyj=∏j=14kyj=Dk. Thus, we have ∏j∈Nlyj=D for 1≤l≤k. That is, instance I has a solution. This completes the proof.Corollary 2.
The problem1∣rj,pj=bjt,rej∣Lmax⁡(R-)+∑Jj∈Rej is strongly NP-hard, so it has no fully polynomial time approximation scheme unless P=NP.


### 3.2. An FPTAS for One Special Case

An algorithmA is a ρ-approximation (ρ≥1) algorithm for a minimization problem if it produces a solution that is at most ρ times than the optimal one (ρ is also referred to as the worst-case ratio). A family of algorithms {Aϵ:ϵ>0} is called a fully polynomial time approximation scheme (FPTAS), if for each ϵ>0, the algorithm Aϵ is a (1+ϵ) approximation algorithm running in polynomial time in the input size and 1/ϵ.In this subsection, we consider the special case where all jobs have agreeable release dates and due dates and assume that the jobs have been indexed such thatr1≤⋯≤rn and d1≤⋯≤dn. The problem can be denoted by 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej.We design an FPTAS for this problem by considering the modified deteriorating rates, the modified release dates, the modified due dates, and the inflated rejection penalty. The definition of the modified deteriorating rates and the modified release dates involves a geometric rounding technique developed by Afrati et al. [18]. The definition of the inflated rejection penalty is stated by Sengupta [11]. The rounding technique and the inflated rejection penalty are stated, respectively, as follows.For anyϵ′>0 and x≥1, if (1+ϵ′)k-1<x<(1+ϵ′)k, then we define ⌈x⌉ϵ′=(1+ϵ′)k,⌊x⌋ϵ′=(1+ϵ′)k-1. If x is an exact power of (1+ϵ′), then ⌈x⌉ϵ′=⌊x⌋ϵ′=x. Note that ⌈x⌉ϵ′≤(1+ϵ′)x for any x≥1.For anyϵ>0, we define the modified deteriorating rate of job Jj as bj′=⌈1+bj⌉ϵ′-1, the modified release date of job Jj as rj′=⌈rj⌉ϵ′ and the modified due date of job Jj as dj′=(1+ϵ)dj, where ϵ′=ϵ/2(n+1). Let Lj denote the exponent of 1+bj′; that is, 1+bj′=⌈1+bj⌉ϵ′=(1+ϵ′)Lj; then Lj=log⁡⌈1+bj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡(1+bj)/ϵ); let lj denote the exponent of rj′; that is, rj′=⌈rj⌉ϵ′=(1+ϵ′)lj; then lj=log⁡⌈rj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡rj/ϵ).For anyϵ>0, let ϵ′=ϵ/2(n+1) and R={Ji1,Ji2,…,Jim} be the set of the rejected jobs, where i1<i2<⋯<im. The inflated rejection penalty of the set R is defined as
(1)ϕϵ′(R)={⌈eim+ϕϵ′(R-Jim)⌉ϵ′,ifm≥1,0,ifR=⌀.Lemma 3 (see [11]).
For any setR of jobs and any ϵ′>0, ϕϵ′(R)≤(1+ϵ′)|R|∑Jj∈Rej.Lemma 4 (see [19]).
For any0<x≤1 and for any integer n≥1, (1+x/n)n≤1+2x holds.Theorem 5.
For any0<ϵ≤2, the optimal objective function value for 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates, the modified release dates, and the modified due dates is at most (1+ϵ) times the optimal objective function value for 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej.Proof.
Assume that jobs in the setR- are scheduled in the order of [1],…,[|R-|]. Let Cj′ denote the completion time of job Jj under the modified deteriorating rates and release dates; we have Cj′=max⁡1≤i≤j{r[i]′∏k=ij(1+b[k]′)}, then
(2)Lj′=Cj′-dj′=max⁡1≤i≤j{r[i]′∏k=ij(1+b[k]′)}-d[j]′≤(1+ϵ′)j+1max⁡1≤i≤j{r[i]∏k=ij(1+b[k])}-(1+ϵ)d[j]≤(1+ϵ′)n+1Cj-(1+ϵ)dj≤(1+ϵ)Lj.
The objective function is
(3)Lmax⁡′(R-)+ϕϵ′(R)≤max⁡{Lj′}+(1+ϵ′)|R|∑Jj∈Rej≤(1+ϵ)(Lmax⁡(R-)+∑Jj∈Rej).
Since the above inequality is valid for any R-⊆J, the results hold.
Assume that the jobs have been reindexed such thatd1≤⋯≤dn and define
(4)τk={(1+ϵ′)k,ifk≠-1,0,ifk=-1.
Letf(j,λ,k) denote the minimum value of the maximum lateness satisfying the following conditions.(i)
The jobs in consideration areJ1,…,Jj.(ii)
The maximum completion time of the accepted jobs is(1+ϵ′)λ.(iii)
The inflated rejection penalty of the rejected jobs isτk.
In any such schedule, there are two possible cases: either jobJj is rejected or Jj is accepted and processed on the machine.Case 1 (JobJj is rejected).
Let(1+ϵ′)k′ be the inflated rejection penalty of the rejected jobs among J1,…,Jj-1. From the definition of inflated rejection penalty, the largest value of k′ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′. Hence, the value of the maximum lateness for the optimal schedule is min⁡-1≤k′≤k~f(j-1,λ,k′).Case 2 (JobJj is accepted).
Consider the following.
Case
2
.1  (λ>lj+Lj). In this case, the maximum completion time of accepted jobs among J1,…,Jj-1 is (1+ϵ′)λ/(1+ϵ′)Lj. Therefore, f(j,λ,k)=max⁡{f(j-1,λ-Lj,k),(1+ϵ′)λ-dj′}.
Case
2.2  (λ=lj+Lj). In this case, let (1+ϵ′)λ′ be the maximum completion time of accepted jobs among J1,…,Jj-1. Since the starting time of job Jj is rj′, we have λ′≤lj. Hence, f(j,λ,k)=max⁡{min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′}.Combining the above two cases, the dynamic programming algorithm is stated as follows.Algorithm DP1Step 1 (initialization).
(5)
f
(
1
,
λ
,
k
)
=
{
r
1
′
⌈
1
+
b
1
⌉
ϵ
′
-
d
′
λ
=
l
1
+
L
1
,
k
=
-
1
,
-
∞
λ
=
0
,
τ
k
=
⌈
e
1
⌉
ϵ
′
,
+
∞
otherwise
.Step 2 (recursion).
Ifλ<lj+Lj, f(j,λ,k)=min⁡-1≤k′≤k~f(j-1,λ,k′),
Ifλ>lj+Lj,
(6)f(j,λ,k)=min⁡{min⁡-1≤k′≤k~max⁡{f(j-1,λ-Lj,k),(1+ϵ′)λ-dj′},&mmmmin⁡-1≤k′≤k~f(j-1,λ,k′)}.
Ifλ=lj+Lj,
(7)f(j,λ,k)=min⁡{max⁡{min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′},mmmmmmin⁡-1≤k′≤k~f(j-1,λ,k′){min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′}},
where k~ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′.Step 3 (output).
The optimal value is determined bymin⁡{f(n,λ,k)+τk:0≤λ≤max⁡1≤i≤n{li}+∑j=1nLj,-1≤k≤K}, where K is the smallest integer such that (1+ϵ′)K≥(1+ϵ′)n∑j=1nej.
LetL=log⁡max⁡{rmax⁡,1+bmax⁡,∑j=1nej}, where rmax⁡=max⁡1≤j≤nrj, bmax⁡=max⁡1≤j≤nbj. We have the following theorem.Theorem 6.
There exists an FPTAS for problem1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej which runs in O(n7L4/ϵ4) time.Proof.
We need to compute exactlyO(n(max⁡1≤i≤n{li}+∑j=1nLj+1)(K+2)) values f(j,λ,k) and computation of each value takes at most O((max⁡1≤i≤n{li}+∑j=1nLj)K) time, where K=O((n/ϵ)log⁡∑j=1nej). Hence, the running time of Algorithm DP1 is
(8)O(n(max⁡1≤i≤n{li}+∑j=1nLj)2K2)=O(n(nlog⁡rmax⁡ϵ+n2log⁡⁡(1+bmax⁡)ϵ)2mmmmm×(nlog⁡∑j=1nejϵ)2)=O(n7L4ϵ4).


## 3.1. NP-Hardness Proof

In this subsection, we first discuss the complexity of the problem1∣rj, pj=bjt∣Lmax⁡ where rejection is not considered.Theorem 1.
The problem1∣rj, pj=bjt∣Lmax⁡ is strongly NP-hard.Proof.
The decision version of the scheduling problem is clearly in NP. We use a reduction from the 4-product problem (4-P), which is strongly NP-hard (see [17]).
An instance of the 4-product problem is formulated as follows. GivenD∈Q+, a finite set N={1,2,…,4k} for some natural number k, a size yj∈Q+ and D1/5<yj<D1/3 for every j∈N, ∏j∈Nyj=Dk. Does there exist disjoint subsets N1,…,Nk such that ⋃i=1kNi=N and the product of sizes of the elements in Ni satisfies ∏j∈Niyj=D for 1≤i≤k ?
Given an arbitrary instanceI of 4-product problem, we construct an instance II of the scheduling problem as follows.(i)
There aren=5k-1 jobs.(ii)
For1≤j≤4k, rj=1, bj=yj-1, and dj=2k-1Dk.(iii)
For4k+1≤j≤5k-1, rj=2j-4k+1Dj-4k, bj=1, and dj=2j-4kDj-4k.(iv)
The threshold value is defined byY=0.
The decision version asks whether there is a scheduleπ for problem 1∣rj,pj=bjt∣Lmax⁡ such that Lmax⁡≤Y.
It is clear that the reduction can be done in polynomial time. Now we prove that instanceI has a solution if and only if instance II has a schedule π with Lmax⁡≤Y.
Assume that 4-product problem has a solution; that is, there exist disjoint subsetsN1,…,Nk such that ⋃i=1kNi=N and the product of sizes of the elements in Ni satisfies ∏j∈Niyj=D for 1≤i≤k. For convenience, we denote the set of jobs {Jj:j∈Nl}(1≤l≤k) by JNl. The jobs are scheduled without idle times as follows. First, the set of jobs JNl are scheduled in the interval [2l-1Dl-1,2l-1Dl] for l=1,…,k. Next, each job Jj is scheduled at time rj=2j-4k+1Dj-4k for j=4k+1,…,5k-1. Therefore, the maximum lateness of this schedule is Lmax⁡=max⁡{Cj-dj:1≤j≤5k-1}=0.
Conversely, assume that there is a scheduleπ with Lmax⁡≤0. We are ready to prove that instance I has a solution.
First, each jobJj(4k+1≤j≤5k-1) must start exactly at its release date rj and finish at its due date dj, since Lmax⁡≤Y=0. Second, the rest 4k jobs are scheduled as the k intervals from time t=1 to time t=2k-1Dk. Without loss of generality, let JNl(1≤l≤k) be the set of jobs scheduled in the interval [2l-1Dl-1,2l-1Dl].
Therefore, from the above discussion, we know that∏j∈Nlyj≤D for 1≤l≤k. Note that ∏l=1k∏j∈Nlyj=∏j=14kyj=Dk. Thus, we have ∏j∈Nlyj=D for 1≤l≤k. That is, instance I has a solution. This completes the proof.Corollary 2.
The problem1∣rj,pj=bjt,rej∣Lmax⁡(R-)+∑Jj∈Rej is strongly NP-hard, so it has no fully polynomial time approximation scheme unless P=NP.


## 3.2. An FPTAS for One Special Case

An algorithmA is a ρ-approximation (ρ≥1) algorithm for a minimization problem if it produces a solution that is at most ρ times than the optimal one (ρ is also referred to as the worst-case ratio). A family of algorithms {Aϵ:ϵ>0} is called a fully polynomial time approximation scheme (FPTAS), if for each ϵ>0, the algorithm Aϵ is a (1+ϵ) approximation algorithm running in polynomial time in the input size and 1/ϵ.In this subsection, we consider the special case where all jobs have agreeable release dates and due dates and assume that the jobs have been indexed such thatr1≤⋯≤rn and d1≤⋯≤dn. The problem can be denoted by 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej.We design an FPTAS for this problem by considering the modified deteriorating rates, the modified release dates, the modified due dates, and the inflated rejection penalty. The definition of the modified deteriorating rates and the modified release dates involves a geometric rounding technique developed by Afrati et al. [18]. The definition of the inflated rejection penalty is stated by Sengupta [11]. The rounding technique and the inflated rejection penalty are stated, respectively, as follows.For anyϵ′>0 and x≥1, if (1+ϵ′)k-1<x<(1+ϵ′)k, then we define ⌈x⌉ϵ′=(1+ϵ′)k,⌊x⌋ϵ′=(1+ϵ′)k-1. If x is an exact power of (1+ϵ′), then ⌈x⌉ϵ′=⌊x⌋ϵ′=x. Note that ⌈x⌉ϵ′≤(1+ϵ′)x for any x≥1.For anyϵ>0, we define the modified deteriorating rate of job Jj as bj′=⌈1+bj⌉ϵ′-1, the modified release date of job Jj as rj′=⌈rj⌉ϵ′ and the modified due date of job Jj as dj′=(1+ϵ)dj, where ϵ′=ϵ/2(n+1). Let Lj denote the exponent of 1+bj′; that is, 1+bj′=⌈1+bj⌉ϵ′=(1+ϵ′)Lj; then Lj=log⁡⌈1+bj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡(1+bj)/ϵ); let lj denote the exponent of rj′; that is, rj′=⌈rj⌉ϵ′=(1+ϵ′)lj; then lj=log⁡⌈rj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡rj/ϵ).For anyϵ>0, let ϵ′=ϵ/2(n+1) and R={Ji1,Ji2,…,Jim} be the set of the rejected jobs, where i1<i2<⋯<im. The inflated rejection penalty of the set R is defined as
(1)ϕϵ′(R)={⌈eim+ϕϵ′(R-Jim)⌉ϵ′,ifm≥1,0,ifR=⌀.Lemma 3 (see [11]).
For any setR of jobs and any ϵ′>0, ϕϵ′(R)≤(1+ϵ′)|R|∑Jj∈Rej.Lemma 4 (see [19]).
For any0<x≤1 and for any integer n≥1, (1+x/n)n≤1+2x holds.Theorem 5.
For any0<ϵ≤2, the optimal objective function value for 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates, the modified release dates, and the modified due dates is at most (1+ϵ) times the optimal objective function value for 1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej.Proof.
Assume that jobs in the setR- are scheduled in the order of [1],…,[|R-|]. Let Cj′ denote the completion time of job Jj under the modified deteriorating rates and release dates; we have Cj′=max⁡1≤i≤j{r[i]′∏k=ij(1+b[k]′)}, then
(2)Lj′=Cj′-dj′=max⁡1≤i≤j{r[i]′∏k=ij(1+b[k]′)}-d[j]′≤(1+ϵ′)j+1max⁡1≤i≤j{r[i]∏k=ij(1+b[k])}-(1+ϵ)d[j]≤(1+ϵ′)n+1Cj-(1+ϵ)dj≤(1+ϵ)Lj.
The objective function is
(3)Lmax⁡′(R-)+ϕϵ′(R)≤max⁡{Lj′}+(1+ϵ′)|R|∑Jj∈Rej≤(1+ϵ)(Lmax⁡(R-)+∑Jj∈Rej).
Since the above inequality is valid for any R-⊆J, the results hold.
Assume that the jobs have been reindexed such thatd1≤⋯≤dn and define
(4)τk={(1+ϵ′)k,ifk≠-1,0,ifk=-1.
Letf(j,λ,k) denote the minimum value of the maximum lateness satisfying the following conditions.(i)
The jobs in consideration areJ1,…,Jj.(ii)
The maximum completion time of the accepted jobs is(1+ϵ′)λ.(iii)
The inflated rejection penalty of the rejected jobs isτk.
In any such schedule, there are two possible cases: either jobJj is rejected or Jj is accepted and processed on the machine.Case 1 (JobJj is rejected).
Let(1+ϵ′)k′ be the inflated rejection penalty of the rejected jobs among J1,…,Jj-1. From the definition of inflated rejection penalty, the largest value of k′ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′. Hence, the value of the maximum lateness for the optimal schedule is min⁡-1≤k′≤k~f(j-1,λ,k′).Case 2 (JobJj is accepted).
Consider the following.
Case
2
.1  (λ>lj+Lj). In this case, the maximum completion time of accepted jobs among J1,…,Jj-1 is (1+ϵ′)λ/(1+ϵ′)Lj. Therefore, f(j,λ,k)=max⁡{f(j-1,λ-Lj,k),(1+ϵ′)λ-dj′}.
Case
2.2  (λ=lj+Lj). In this case, let (1+ϵ′)λ′ be the maximum completion time of accepted jobs among J1,…,Jj-1. Since the starting time of job Jj is rj′, we have λ′≤lj. Hence, f(j,λ,k)=max⁡{min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′}.Combining the above two cases, the dynamic programming algorithm is stated as follows.Algorithm DP1Step 1 (initialization).
(5)
f
(
1
,
λ
,
k
)
=
{
r
1
′
⌈
1
+
b
1
⌉
ϵ
′
-
d
′
λ
=
l
1
+
L
1
,
k
=
-
1
,
-
∞
λ
=
0
,
τ
k
=
⌈
e
1
⌉
ϵ
′
,
+
∞
otherwise
.Step 2 (recursion).
Ifλ<lj+Lj, f(j,λ,k)=min⁡-1≤k′≤k~f(j-1,λ,k′),
Ifλ>lj+Lj,
(6)f(j,λ,k)=min⁡{min⁡-1≤k′≤k~max⁡{f(j-1,λ-Lj,k),(1+ϵ′)λ-dj′},&mmmmin⁡-1≤k′≤k~f(j-1,λ,k′)}.
Ifλ=lj+Lj,
(7)f(j,λ,k)=min⁡{max⁡{min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′},mmmmmmin⁡-1≤k′≤k~f(j-1,λ,k′){min⁡0≤λ′≤ljf(j-1,λ′,k),(1+ϵ′)λ-dj′}},
where k~ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′.Step 3 (output).
The optimal value is determined bymin⁡{f(n,λ,k)+τk:0≤λ≤max⁡1≤i≤n{li}+∑j=1nLj,-1≤k≤K}, where K is the smallest integer such that (1+ϵ′)K≥(1+ϵ′)n∑j=1nej.
LetL=log⁡max⁡{rmax⁡,1+bmax⁡,∑j=1nej}, where rmax⁡=max⁡1≤j≤nrj, bmax⁡=max⁡1≤j≤nbj. We have the following theorem.Theorem 6.
There exists an FPTAS for problem1∣rj,pj=bjt,rej,agreeable∣Lmax⁡(R-)+∑Jj∈Rej which runs in O(n7L4/ϵ4) time.Proof.
We need to compute exactlyO(n(max⁡1≤i≤n{li}+∑j=1nLj+1)(K+2)) values f(j,λ,k) and computation of each value takes at most O((max⁡1≤i≤n{li}+∑j=1nLj)K) time, where K=O((n/ϵ)log⁡∑j=1nej). Hence, the running time of Algorithm DP1 is
(8)O(n(max⁡1≤i≤n{li}+∑j=1nLj)2K2)=O(n(nlog⁡rmax⁡ϵ+n2log⁡⁡(1+bmax⁡)ϵ)2mmmmm×(nlog⁡∑j=1nejϵ)2)=O(n7L4ϵ4).


## 4. Parallel-Machine Problem

### 4.1. An FPTAS

In this subsection, we focus our attention on identical parallel machines problem with deterioration and rejection. For convenience of discussion, we consider a scheduling model in which each jobJj has a delivery time qj≥0 rather than a due date dj. When all jobs have identical release dates, the problem Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej is at least ordinarily NP-hard according to Kononov [20]. We give a fully polynomial time approximation scheme to solve it by considering the modified deteriorating rates, the modified delivery times, and the inflated rejection penalty.For anyϵ>0, we define the modified deteriorating rate and delivery time of job Jj as bj′=⌈1+bj⌉ϵ′-1, qj′=(1+ϵ′)qj, where ϵ′=ϵ/2n. Let Lj denote the exponent of 1+bj′; that is, 1+bj′=⌈1+bj⌉ϵ′=(1+ϵ′)Lj; then Lj=log⁡⌈1+bj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡(1+bj)/ϵ).For anyϵ>0, let ϵ′=ϵ/2n and R={Ji1,Ji2,…,Jim} be the set of the rejected jobs, where i1<i2<⋯<im. The inflated rejection penalty of the set R is defined as
(9)ϕϵ′(R)={⌈eim+ϕϵ′(R-Jim)⌉ϵ′,ifm≥1,0,ifR=⌀.Lemma 7.
For any0<ϵ≤2, the optimal objective function value for Pm∣rj=t0, pj=bjt, rej∣Dmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates and the modified delivery times is at most (1+ϵ) times the optimal objective function value for
(10)Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej.Lemma 8.
There exists an optimal job sequence forPm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej such that on each machine the accepted jobs are sequenced in nonincreasing order of qj.Based on Lemmas7 and 8, we design a dynamic programming algorithm for Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates and delivery times. Let us index the jobs such that q1≥⋯≥qn and define
(11)τk={(1+ϵ′)k,ifk≠-1,0,ifk=-1.LetF(j,λ1,…,λm,k) denote the optimal value of the maximum delivery completion time satisfying the following conditions.(i)
The jobs in consideration areJ1,…,Jj.(ii)
The maximum completion time of the accepted jobs on machineMi is t0(1+ϵ′)λi for i=1,…,m.(iii)
The inflated rejection penalty of the rejected jobs isτk.The dynamic programming algorithm is stated as follows.Algorithm DP2Step 1 (initialization).
(12)
F
(
1
,
λ
1
,
…
,
λ
m
,
k
)
=
{
t
0
(
1
+
ϵ
′
)
L
1
+
q
1
′
,
(
λ
1
,
…
,
λ
i
,
…
,
λ
m
,
k
)
=
(
0
,
…
,
L
1
,
…
,
0
,
-
1
)
,
-
∞
,
(
λ
1
,
…
,
λ
i
,
…
,
λ
m
)
=
(
0
,
…
,
0
,
…
,
0
)
,
τ
k
=
⌈
e
1
⌉
ϵ
′
+
∞
,
otherwise
.Step 2 (recursion).
If jobJj is rejected,
(13)F(j,λ1,…,λm,k)=min⁡-1≤k′≤k~F(j-1,λ1,…,λm,k′).
If job Jj is accepted,
(14)F(j,λ1,…,λm,k)=min⁡1≤i≤m{max⁡{t0(1+ϵ′)λi+qj′}F(j-1,λ1,…,λi-Li,…,λm,k),mmmmmmmmmt0(1+ϵ′)λi+qj′}}.
Combining the two cases, we have
(15)F(j,λ1,…,λm,k)=min⁡{min⁡-1≤k′≤k~min⁡1≤i≤m{max⁡{t0(1+ϵ′)λi+qj′}F(j-1,λ1,…,λi-Li,…,λm,k),mmmmmmmmmmmt0(1+ϵ′)λi+qj′}},mmmmmmin⁡-1≤k′≤k~F(j-1,λ1,…,λm,k′)},
where k~ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′.Step 3 (output).
The optimal value is determined by(16)min⁡{F(n,λ1,…,λm,k)+τk:0≤λi≤∑j=1nLj,mmmm1≤i≤m,-1≤k≤K∑j=1nLj},
where K is the smallest integer such that (1+ϵ′)K≥(1+ϵ′)n∑j=1nej.Theorem 9.
There exists an FPTAS for problemPm∣rj=t0,pj=bjt, rej∣Dmax⁡(R-)+∑Jj∈Rej which runs in O((nm+3/ϵm+2)(∑j=1nlog⁡(1+bj))mlog⁡2(∑j=1nej)) time.Proof.
We need to computen(∑j=1nLj+1)m(K+2) values F(j,λ1,…,λm,k). Computation of each such value takes O(K) time, where K=O((n/ϵ)log⁡∑j=1nej). Therefore the overall time of the algorithm is O(n(∑j=1nLj)mK2)=O((nm+3/ϵm+2)(∑j=1nlog⁡(1+bj))mlog2(∑j=1nej)).


### 4.2. A Heuristic Algorithm for a Special Case

In this subsection, it is assumed that all jobs have to be processed; that is, rejection is not allowed. This problem can be denoted byPm∣rj=t0, pj=bjt∣Dmax⁡. We present a heuristic algorithm and give its worst case analysis.Heuristic
D
L
S. Consider the following steps.Step 1.
Place all jobs in a list ordered by nonincreasing delivery times. SetSi=t0 for 1≤i≤m, and Si denotes the total completion time of jobs assigned to machine Mi.Step 2.
Select a machineMi for which Si is as small as possible. Choose the first unscheduled job Jj of the list and assign it to machine Mi. Set Si=Si(1+bj).Step 3.
Repeat Step2 until all jobs are scheduled.Theorem 10.
The worst case performance ratio of heuristicDLS is (1+bmax⁡)1-1/mand this bound is tight.Proof.
LetDmax⁡DLS be the maximum delivery completion time according to heuristic DLS and let Dmax⁡* be the corresponding time in an optimal schedule. Assume that there exists a counterexample with Dmax⁡DLS/Dmax⁡*>(1+bmax⁡)1-1/m. Let Jk be the first job in the sorted list with Ck+qk>(1+bmax⁡)1-1/mDmax⁡*, remove all the following jobs from the list, and produce a minimum counterexample with Dmax⁡DLS=Ck+qk, where Jk is the job with smallest delivery time. Next, we transform the counterexample by subtracting qk from all delivery times. Obviously, this decreases both Dmax⁡DLS and Dmax⁡* by qk. Since
(17)Dmax⁡DLS-qkDmax⁡*-qk≥Dmax⁡DLSDmax⁡*>(1+bmax⁡)1-1/m
holds, the transformation yields another counterexample. Now the last job has delivery times zero and Dmax⁡DLS=Ck. At the time before job Jk is assigned to its machine Mi,
(18)Si≤(∏l=1k(1+b1))1/m(1+bk)1/m≤Dmax⁡*(1+bk)1/m.
This implies
(19)Dmax⁡DLS=Ck=Si(1+bk)≤(1+bk)1-1/mDmax⁡*≤(1+bmax⁡)1-1/mDmax⁡*.
To prove that the bound is tight, consider the following example withn=m(m-1)+1 jobs, all jobs have delivery time zero, the first m(m-1) of them has deteriorating rates bj=1, j=1,2,…,m(m-1), and the last job’s deteriorating rate is bn=2m-1. Then bmax⁡=bn and (1+bmax⁡)1-1/m=2m-1. By DLS, Dmax⁡DLS=t0(1+bj)m-1(1+bn)=t02m-12m=t022m-1. In an optimal schedule, Jn is assigned to one machine and all the previous m(m-1) jobs are equally assigned to the other m-1 machines. This yields to Dmax⁡*=t02m. Thus,
(20)Dmax⁡DLSDmax⁡*=(1+bmax⁡)1-1/m=2m-1.
This completes the proof.


### 4.3. Numerical Experiment

This section conducts some numerical experiments to evaluate the performance of heuristicDLS. Without loss of generality, we set t0=1. The delivery time qj,1≤j≤n and the deteriorating rate bj,1≤j≤n are generated from U[0,50] and U[1,10], respectively. The lower bound of optimal value is L(Dmax⁡*)=(∏l=1n(1+bl))1/m. The numerical results are summarized in Table 1. The program was coded in Matlab. The results of numerical experiments show that the algorithm has good performance. The proposed algorithm is acceptable for the NP-hard problem.Table 1
Summary of the computational results.
m
n
L
(
D
max
⁡
*
)
D
max
⁡
DLS
D
max
⁡
DLS
L
(
D
max
⁡
*
)
|
D
max
⁡
DLS
-
L
(
D
max
⁡
*
)
|
L
(
D
max
⁡
*
)
3
10
240
559
2.329
1.329
4
12
208
577
2.774
1.774
4
12
168
485
2.887
1.887
4
15
380
520
1.368
0.368
4
15
477
931
1.952
0.952
5
10
33
60
1.818
0.818
5
10
57
115
2.018
1.018
5
18
611
1688
2.762
1.763


## 4.1. An FPTAS

In this subsection, we focus our attention on identical parallel machines problem with deterioration and rejection. For convenience of discussion, we consider a scheduling model in which each jobJj has a delivery time qj≥0 rather than a due date dj. When all jobs have identical release dates, the problem Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej is at least ordinarily NP-hard according to Kononov [20]. We give a fully polynomial time approximation scheme to solve it by considering the modified deteriorating rates, the modified delivery times, and the inflated rejection penalty.For anyϵ>0, we define the modified deteriorating rate and delivery time of job Jj as bj′=⌈1+bj⌉ϵ′-1, qj′=(1+ϵ′)qj, where ϵ′=ϵ/2n. Let Lj denote the exponent of 1+bj′; that is, 1+bj′=⌈1+bj⌉ϵ′=(1+ϵ′)Lj; then Lj=log⁡⌈1+bj⌉ϵ′/log⁡(1+ϵ′)=O(nlog⁡(1+bj)/ϵ).For anyϵ>0, let ϵ′=ϵ/2n and R={Ji1,Ji2,…,Jim} be the set of the rejected jobs, where i1<i2<⋯<im. The inflated rejection penalty of the set R is defined as
(9)ϕϵ′(R)={⌈eim+ϕϵ′(R-Jim)⌉ϵ′,ifm≥1,0,ifR=⌀.Lemma 7.
For any0<ϵ≤2, the optimal objective function value for Pm∣rj=t0, pj=bjt, rej∣Dmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates and the modified delivery times is at most (1+ϵ) times the optimal objective function value for
(10)Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej.Lemma 8.
There exists an optimal job sequence forPm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej such that on each machine the accepted jobs are sequenced in nonincreasing order of qj.Based on Lemmas7 and 8, we design a dynamic programming algorithm for Pm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+ϕϵ′(R) with the modified deteriorating rates and delivery times. Let us index the jobs such that q1≥⋯≥qn and define
(11)τk={(1+ϵ′)k,ifk≠-1,0,ifk=-1.LetF(j,λ1,…,λm,k) denote the optimal value of the maximum delivery completion time satisfying the following conditions.(i)
The jobs in consideration areJ1,…,Jj.(ii)
The maximum completion time of the accepted jobs on machineMi is t0(1+ϵ′)λi for i=1,…,m.(iii)
The inflated rejection penalty of the rejected jobs isτk.The dynamic programming algorithm is stated as follows.Algorithm DP2Step 1 (initialization).
(12)
F
(
1
,
λ
1
,
…
,
λ
m
,
k
)
=
{
t
0
(
1
+
ϵ
′
)
L
1
+
q
1
′
,
(
λ
1
,
…
,
λ
i
,
…
,
λ
m
,
k
)
=
(
0
,
…
,
L
1
,
…
,
0
,
-
1
)
,
-
∞
,
(
λ
1
,
…
,
λ
i
,
…
,
λ
m
)
=
(
0
,
…
,
0
,
…
,
0
)
,
τ
k
=
⌈
e
1
⌉
ϵ
′
+
∞
,
otherwise
.Step 2 (recursion).
If jobJj is rejected,
(13)F(j,λ1,…,λm,k)=min⁡-1≤k′≤k~F(j-1,λ1,…,λm,k′).
If job Jj is accepted,
(14)F(j,λ1,…,λm,k)=min⁡1≤i≤m{max⁡{t0(1+ϵ′)λi+qj′}F(j-1,λ1,…,λi-Li,…,λm,k),mmmmmmmmmt0(1+ϵ′)λi+qj′}}.
Combining the two cases, we have
(15)F(j,λ1,…,λm,k)=min⁡{min⁡-1≤k′≤k~min⁡1≤i≤m{max⁡{t0(1+ϵ′)λi+qj′}F(j-1,λ1,…,λi-Li,…,λm,k),mmmmmmmmmmmt0(1+ϵ′)λi+qj′}},mmmmmmin⁡-1≤k′≤k~F(j-1,λ1,…,λm,k′)},
where k~ is given by (1+ϵ′)k~=⌊(1+ϵ′)k-ej⌋ϵ′.Step 3 (output).
The optimal value is determined by(16)min⁡{F(n,λ1,…,λm,k)+τk:0≤λi≤∑j=1nLj,mmmm1≤i≤m,-1≤k≤K∑j=1nLj},
where K is the smallest integer such that (1+ϵ′)K≥(1+ϵ′)n∑j=1nej.Theorem 9.
There exists an FPTAS for problemPm∣rj=t0,pj=bjt, rej∣Dmax⁡(R-)+∑Jj∈Rej which runs in O((nm+3/ϵm+2)(∑j=1nlog⁡(1+bj))mlog⁡2(∑j=1nej)) time.Proof.
We need to computen(∑j=1nLj+1)m(K+2) values F(j,λ1,…,λm,k). Computation of each such value takes O(K) time, where K=O((n/ϵ)log⁡∑j=1nej). Therefore the overall time of the algorithm is O(n(∑j=1nLj)mK2)=O((nm+3/ϵm+2)(∑j=1nlog⁡(1+bj))mlog2(∑j=1nej)).


## 4.2. A Heuristic Algorithm for a Special Case

In this subsection, it is assumed that all jobs have to be processed; that is, rejection is not allowed. This problem can be denoted byPm∣rj=t0, pj=bjt∣Dmax⁡. We present a heuristic algorithm and give its worst case analysis.Heuristic
D
L
S. Consider the following steps.Step 1.
Place all jobs in a list ordered by nonincreasing delivery times. SetSi=t0 for 1≤i≤m, and Si denotes the total completion time of jobs assigned to machine Mi.Step 2.
Select a machineMi for which Si is as small as possible. Choose the first unscheduled job Jj of the list and assign it to machine Mi. Set Si=Si(1+bj).Step 3.
Repeat Step2 until all jobs are scheduled.Theorem 10.
The worst case performance ratio of heuristicDLS is (1+bmax⁡)1-1/mand this bound is tight.Proof.
LetDmax⁡DLS be the maximum delivery completion time according to heuristic DLS and let Dmax⁡* be the corresponding time in an optimal schedule. Assume that there exists a counterexample with Dmax⁡DLS/Dmax⁡*>(1+bmax⁡)1-1/m. Let Jk be the first job in the sorted list with Ck+qk>(1+bmax⁡)1-1/mDmax⁡*, remove all the following jobs from the list, and produce a minimum counterexample with Dmax⁡DLS=Ck+qk, where Jk is the job with smallest delivery time. Next, we transform the counterexample by subtracting qk from all delivery times. Obviously, this decreases both Dmax⁡DLS and Dmax⁡* by qk. Since
(17)Dmax⁡DLS-qkDmax⁡*-qk≥Dmax⁡DLSDmax⁡*>(1+bmax⁡)1-1/m
holds, the transformation yields another counterexample. Now the last job has delivery times zero and Dmax⁡DLS=Ck. At the time before job Jk is assigned to its machine Mi,
(18)Si≤(∏l=1k(1+b1))1/m(1+bk)1/m≤Dmax⁡*(1+bk)1/m.
This implies
(19)Dmax⁡DLS=Ck=Si(1+bk)≤(1+bk)1-1/mDmax⁡*≤(1+bmax⁡)1-1/mDmax⁡*.
To prove that the bound is tight, consider the following example withn=m(m-1)+1 jobs, all jobs have delivery time zero, the first m(m-1) of them has deteriorating rates bj=1, j=1,2,…,m(m-1), and the last job’s deteriorating rate is bn=2m-1. Then bmax⁡=bn and (1+bmax⁡)1-1/m=2m-1. By DLS, Dmax⁡DLS=t0(1+bj)m-1(1+bn)=t02m-12m=t022m-1. In an optimal schedule, Jn is assigned to one machine and all the previous m(m-1) jobs are equally assigned to the other m-1 machines. This yields to Dmax⁡*=t02m. Thus,
(20)Dmax⁡DLSDmax⁡*=(1+bmax⁡)1-1/m=2m-1.
This completes the proof.


## 4.3. Numerical Experiment

This section conducts some numerical experiments to evaluate the performance of heuristicDLS. Without loss of generality, we set t0=1. The delivery time qj,1≤j≤n and the deteriorating rate bj,1≤j≤n are generated from U[0,50] and U[1,10], respectively. The lower bound of optimal value is L(Dmax⁡*)=(∏l=1n(1+bl))1/m. The numerical results are summarized in Table 1. The program was coded in Matlab. The results of numerical experiments show that the algorithm has good performance. The proposed algorithm is acceptable for the NP-hard problem.Table 1
Summary of the computational results.
m
n
L
(
D
max
⁡
*
)
D
max
⁡
DLS
D
max
⁡
DLS
L
(
D
max
⁡
*
)
|
D
max
⁡
DLS
-
L
(
D
max
⁡
*
)
|
L
(
D
max
⁡
*
)
3
10
240
559
2.329
1.329
4
12
208
577
2.774
1.774
4
12
168
485
2.887
1.887
4
15
380
520
1.368
0.368
4
15
477
931
1.952
0.952
5
10
33
60
1.818
0.818
5
10
57
115
2.018
1.018
5
18
611
1688
2.762
1.763


## 5. Conclusion

In this paper, we focus on several scheduling problems with deterioration, release date, and rejection. For the single machine model, we show that this problem is strongly NP-hard and provides a fully polynomial time approximation scheme when all jobs have agreeable release dates and due dates. For parallel machines model, we propose a fully polynomial time approximation scheme forPm∣rj=t0,pj=bjt,rej∣Dmax⁡(R-)+∑Jj∈Rej and a heuristic algorithm for a special case. The computational results show that the heuristics is efficient in obtaining near-optimal solutions. For future research, it would be interesting to focus on scheduling deteriorating jobs and rejection with other objectives. Furthermore, investigation of the online version of this scheduling model is also an interesting research direction.



---

*Source: 170475-2014-07-14.xml*