# Parallel-Batch Scheduling with Two Models of Deterioration to Minimize the Makespan

Authors: Cuixia Miao
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We consider the bounded parallel-batch scheduling with two models of deterioration, in which the processing time of the first model ispj=aj+αt and of the second model is pj=a+αjt. The objective is to minimize the makespan. We present O(nlogn) time algorithms for the single-machine problems, respectively. And we propose fully polynomial time approximation schemes to solve the identical-parallel-machine problem and uniform-parallel-machine problem, respectively.


---

## Body

## 1. Introduction

Consider the following problem of parallel-batch scheduling with linear processing times. There aren independent deteriorating jobs J={J1,…,Jn} to be processed on a single or m (identical or uniform) parallel batching machines. The actual processing time of the first model is pj=aj+αt and of the second model is pj=a+αjt, where aj and a are the basic processing times, α and αj are the deteriorating rates, and t is the starting time of Jj in a given schedule. All jobs are available from time zero onwards. The batching machines can process up to b jobs simultaneously as a batch, and the processing time of the batch B is equal to the longest time of any job in the batch; that is, P(B)=max⁡{pj∣Jj∈B}=max⁡Jj∈B{aj}+αt or P(B)=max⁡{pj∣Jj∈B}=a+max⁡Jj∈B{αj}t. Let Mi(i=1,…,m) and si denote the ith machine and its proceeding speed, respectively. The speeds are identical in the identical parallel machines environment, while they are different from each other in the uniform parallel machines environment. Our objective is to minimize the makespan. Following Gawiejnowicz [1], we denote our problems as 1(Pm,Qm)∣p-batch,  pj=aj+αt, b<n∣Cmax⁡, and 1(Pm,Qm)∣p-batch,pj=a+αjt,  b<n∣Cmax⁡, where “p-batch” means parallel-batch.The model described above falls into two categories: parallel-batch scheduling and scheduling with deteriorating jobs. The parallel-batch scheduling is motivated by burn-in operations in semiconductor manufacturing. Brucker et al. [2] said that a parallel-batch machine is a machine that can process up to b jobs simultaneously as a batch, and the processing time of the batch is equal to the longest time of any job in the batch. All jobs contained in the same batch start and complete at the same time. Once processing of a batch is initiated, it cannot be interrupted and other jobs cannot be introduced into the batch until processing is completed. For the parallel-batch scheduling, there are two models: thebounded model, in which the bound b for each batch size is effective, that is, b<n, and theunbounded model, in which there is effectively no limit on the size of batch, that is, b≥n. This processing system has been extensively studied in the last two decades. The extensive survey of different models and results was provided both by Potts and Kovalyov [3] and Zhang and Cao [4]. Afterwards, Yuan et al. [5] gave some new results for the parallel-batch scheduling.Traditional scheduling problems all assume that the processing times of jobs are constant. However, the processing times may change in the real world. Examples can be found in steel production and firefighting, where any delay in processing a task may increase its completion time. Scheduling with deteriorating job was first considered by J. N. D. Gupta and S. K. Gupta [6] and Browne and Yechiali [7]. From then on, this scheduling model has been extensively studied. Cheng et al. [8] gave a survey and the monograph by Gawiejnowicz [1] presented this scheduling from different perspectives and covers results and examples. Ji and Cheng [9, 10] and Liu et al. [11] gave some new results for this scheduling.The parallel-batch scheduling with deteriorating jobs was initiated by Qi et al. [12]; Li et al. [13] and Miao et al. [14] also considered this scheduling; they gave some results for the minimizing makespan of the parallel-batch scheduling with the simple linear deterioration (i.e., pj=αjt). In this paper, we consider the parallel-batch scheduling with pj=aj+αt and pj=a+αjt. We not only consider the single-machine problem but also the parallel-machine problems.The remainder of the paper is organized as follows. In Section2, we give some preliminaries to be used in this paper. In Section 3, we present an O(nlog⁡n) time algorithm for the single-machine problem 1∣p-batch,pj=aj+αt,  b<n∣Cmax⁡, and propose two fully polynomial time approximation schemes for problems Pm∣p-batch,pj=aj+αt,  b<n∣Cmax⁡ and Qm∣p-batch,pj=aj+αt,  b<n∣Cmax⁡, respectively. In Section 4, we present an O(nlog⁡n) time algorithm for the single-machine problem 1∣p-batch,pj=a+αjt,  b<n∣Cmax⁡, and propose two fully polynomial time approximation schemes for problems Pm∣p-batch,pj=a+αjt,  b<n∣Cmax⁡ and Qm∣p-batch,pj=a+αjt,  b<n∣Cmax⁡, respectively. We conclude the paper and suggest some interesting topics for future research in the last section.


## 2. Preliminaries

In this section, we give some preliminaries to be used in the following sections.J. N. D. Gupta and S. K. Gupta [6] considered the general model pj=aj+αjt, where aj and αj denote the basic processing time and deteriorating rate of job Jj, respectively. Lemma 1 presented in [6] is useful for our problems.Lemma 1 (see [6]).
The problem1∣pj=aj+αjt∣Cmax⁡ is solvable in O(nlog⁡n) time by scheduling jobs in the nonincreasing order of αj/aj ratios.It leads to Lemmas2 and 3.Lemma 2.
The problem1∣pj=aj+αt∣Cmax⁡ is solvable in O(nlog⁡n) time by scheduling jobs in the increasing order of their basic processing times, and the makespan is Cmax⁡(π)=∑i=1n‍a[i](1+α)n-i for the given schedule π={J[1],J[2],…,J[n]} with a[1]≤a[2]≤⋯≤a[n].Lemma 3.
The problem1∣pj=a+αjt∣Cmax⁡ is solvable in O(nlog⁡n) time by scheduling jobs in the nonincreasing order of their deteriorating rates, and the makespan is Cmax⁡(π)=a[1+∑i=2n‍∏l=in‍(1+α[l])] for the given schedule π={J[1],J[2],…,J[n]} with α[1]≥α[2]≥⋯≥α[n].In the uniform parallel machines environment, letni(i=1,…,m) and J[i,j] denote the number of jobs scheduled on machine Mi and the jth job on this machine. Then ∑i=1m‍ni=n. Without loss of generality, let J[i,1],J[i,2],…,J[i,ni] be the jobs scheduled on machine Mi. Then, there exists g(g=1,…,n) such that J[i,j]=Jg with p[i,j]=a[i,j]+αt=ag+αt or p[i,j]=a+α[i,j]t=a+αgt.From Lemma2, we get the following lemma for problem Qm∣p-batch,pj=aj+αt,b<n∣Cmax⁡.Lemma 4.
The completion time of jobJ[i,j] is C[i,j]=∑h=1j‍(1+(α/si))j-h(a[i,h]/si).And from Lemma3, we get the following lemma for problem Qm∣p-batch,pj=a+αjt,b<n∣Cmax⁡.Lemma 5.
The completion time of jobJ[i,j] is C[i,j]=(a/si)[1+∑i=2j‍∏h=ij‍(1+(α[i,h]/si))].An algorithmA is called a (1+ε)-approximation algorithm for a minimization problem if it produces a solution that is at most (1+ε) times as big as the optimal value, running in time that is polynomial in the input size. A family approximation algorithm {Aε} is a fully polynomial-time approximation scheme (FPTAS) if, for each ε>0, the algorithm Aε is a (1+ε)-approximation algorithm that is polynomial in the input size and in 1/ε. Without loss of generality, we assume that 0<ε≤1.


## 3. Modelpj=aj+αt

In this section, we discuss the modelpj=aj+αt. First, we present polynomial time algorithm for problem 1∣p-batch,pj=aj+αt,  b<n∣Cmax⁡. Then we propose fully polynomial time approximation schemes for problems Pm∣p-batch,pj=aj+αt,  b<n∣Cmax⁡ and Qm∣p-batch,pj=aj+αt,  b<n∣Cmax⁡, respectively.


### 3.1. Single-Machine Problem1∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

In this subsection, we present anO(nlog⁡n) time algorithm for the single-machine problem.Algorithm
A. Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Let k=⌈n/b⌉ and j=n-b(k-1).Step
3. Form batches B1,…,Bk such that B1={J1,…,Jj}, B2={Jj+1,…,Jj+b},…, Bk={Jn-b+1,…,Jn}.Step
4. Schedule these batches in the increasing order of their basic processing times from time zero.Theorem 6.
The problem1∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is solvable in O(nlog⁡n) time by Algorithm A.Proof.
Suppose that we reindex the jobs in increasing order of their basic processing times. Now, we only need to prove that there exists an optimal schedule satisfying the following properties. (i) The indices of jobs in each batch are consecutive. (ii) All batches are full except possibly the one which contains jobJ1. (iii) Batches are scheduled in the increasing order of their basic processing times.
We consider an optimal scheduleπ in the following proof.
To show (i), suppose that there are two batchesBf and Bh and three jobs Ji, Jj, and Jl with ai≥aj≥al such that Ji,Jl∈Bf and Jj∈Bh in schedule π. We obtain a new schedule π′ by shifting job Jj with job Jl; that is, Bf′=Bf∖{Jl}∪{Jj} and Bh′=Bh∖{Jj}∪{Jl}. And then P(Bf′)=P(Bf) and P(Bh′)≤P(Bh) since ai≥aj≥al and the starting time is not changed. Thus, C(Bf′)≤C(Bf) and C(Bh′)≤C(Bh), and the completion times of other jobs do not increase. Thus, π′ remains optimal. A finite number of repetitions of this procedure yields an optimal schedule of the required form.
To show (ii), suppose that there is a batchBx in π such that Bx is not full. We know that the indices of jobs in Bx are consecutive from (i). Without loss of generality, let Bx={Jnx,Jnx+1,…,Jnx+e} with |Bx|=e+1<b. If we move the remaining consecutive b-(e+1) jobs {Jnx+e+1-b,…,Jnx-2,Jnx-1} from other batches to Bx, this procedure cannot increase the objective value since aj≤anx for all j=nx+e+1-b,…,nx-1. A finite number of repetitions of this procedure yields an optimal schedule with that all batches are full except possibly the one which contains the first job J1.
If we view each batchB as single aggregate job with P(B)=max⁡j∈B{aj}+αt in schedule π, property (iii) holds from Lemma 2.
This completes the proof of Theorem6.


### 3.2. ProblemPm∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

In this subsection, we assume thatm (≥2), aj(j=1,…,n) and α are all integral. We drive some properties of the optimal schedule and propose an FPTAS.We reindex jobs in increasing order of their basic processing times such thata1≤⋯≤an.Theorem 7.
For problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJ1.(iii)
Batches are scheduled in the increasing order of their basic processing times on every machine.The proof of this theorem is similar to the proof of Theorem6.For problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, the properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm A, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=max⁡Ji∈Bj{ai}+αt=an+b(j-k)+αt.Similar to the establishment of FPTAS in Kovalyov and Kubiak [15], we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on machine Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(1)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)+(1+α)Fj-1l(x)forxj=l,Fji(x)=Fj-1i(x)forxj=li≠l.
Then problem Pm∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is reduced to the following problem:
(2)Minimize⁡Q(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.
We introduce the procedure Partition (A,F,ρ) proposed by Kovalyov and Kubiak [15], where A⊆X, F is a nonnegative integer function on X, and 0<ρ≤1. This procedure partitions A into disjoint subsets A1F,A2F,…,AkFF such that |F(x)-F(x′)|≤ρmin⁡{F(x),F(x′)} for any x,x′∈AjF, j=1,2,…,kF. The following description provides the details of Partition (A,F,ρ).Procedure Partition
(
A
,
F
,
ρ
). Arrange the vectors x∈A in the order x(1),x(2),…,x(|A|), where 0≤F(x(1))≤F(x(2))≤⋯≤F(x(|A|)). Assign the vectors x(1),x(2),…,x(i1) to set A1F until i1 is found such that F(x(i1))≤(1+ρ)F(x(1)) and F(x(i1+1))>(1+ρ)F(x(1)). If such i1 does not exist, then take A1F=A and stop.Assignx(i1+1),x(i1+2),…,x(i2) to set A2F until i2 is found such that F(x(i2))≤(1+ρ)F(x(i1+1)) and F(x(i2+1))>(1+ρ)F(x(i1+1)). If such i2 does not exist, then take A2F=A-A1F and stop.Continue the above process untilx(|A|) is included in AkFF for some kF.The main properties of Partition were given by Kovalyov and Kubiak [15] as follows.Proposition 8.
Consider|F(x)-F(x′)|≤ρmin⁡{F(x),F(x′)} for any x,x′∈AjF, j=1,2,…,kF.Proposition 9.
ConsiderkF≤((log⁡F(x(|A|)))/ρ)+2 for 0<ρ≤1 and 1≤F(x(|A|)).Now, we give a fully polynomial time approximation scheme for problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡.Algorithm
A
ε
P
.
Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Form batches B1,…,Bk by using Algorithm A, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=an+b(j-k)+αt(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…,m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l:(3)Fjl(x)=an+b(j-k)+(1+α)Fj-1l(x),Fji(x)=Fj-1i(x)fori≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/2(k+1)), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(4)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that Q(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetT=log⁡(max⁡{k,1/ε,1+α,amax⁡}), where k=⌈n/b⌉, amax⁡=max⁡j=1,…,n{aj}.We get the following theorem.Theorem 10.
Algorithm
A
ε
P
finds
x
0
∈
X
for
P
m
∣
p
-
b
a
t
c
h
,
p
j
=
a
j
+
α
t
,
b
<
n
∣
C
max
⁡ such that Q(x0)≤(1+ε)Q(x*) in O((⌈n/b⌉)(2m+1)Tm+1/εm), where x* is an optimal solution.Proof.
Suppose thatx*[j]=(x1*,…,xj*,0,…,0)∈Yb1⋯bm⊆Yj′ for some j and b1,…,bm. Algorithm AεP may not choose x*[j] for further construction; however, for a vector x(b1⋯bm) chosen instead of it, we have
(5)|Fji(x*[j])-Fji(x(b1⋯bm))|≤ρFji(x*[j]),i=1,…,m.
Set ρ1=ρ. Consider the vector x*[j+1]=(x1*,…,xj*,xj+1*,0,…,0) and x~(b1⋯bm)=(x1(b1⋯bm),…,xj(b1⋯bm),xj+1*,0,…,0). We assume xj+1*=l. It follows that
(6)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|(an+b(j+1-k)+(1+α)Fjl(x*[j]))-(an+b(j+1-k)+(1+α)Fjl(x(b1⋯bm)))|=|(1+α)(Fjl(x*[j])-Fjl(x(b1⋯bm)))|≤(1+α)ρFjl(x*[j])≤ρ1(an+b(j+1-k)+(1+α)Fjl(x*[j]))=ρ1Fj+1l(x*[j+1]).
Consequently,(7)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).
Similarly, fori≠l, we have
(8)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).
Assume thatx~(b1⋯am)∈Yc1⋯cm⊆Yj+1′ and Algorithm AεP chooses x(c1⋯cm)∈Yc1⋯cm instead of x~(b1⋯bm) in the (j+1)th iteration; then we have
(9)|Fj+1i(x~(b1⋯bm))-Fj+1i(x(c1⋯cm))|≤ρFj+1i(x~(b1⋯bm))≤ρ(1+ρ1)Fj+1i(x*[j+1]),i=1,…,m.
Then we have
(10)|Fj+1i(x*[j+1])-Fj+1i(x(c1⋯cm))|≤|Fj+1i(x*[j+1])-Fj+1i(x~(b1⋯bm))|+|Fj+1i(x~(b1⋯bm))-Fj+1i(x(c1⋯cm))|≤(ρ1+ρ(1+ρ1))Fj+1i(x*[j+1])=(ρ+ρ1(1+ρ))Fj+1i(x*[j+1]),i=1,2,…,m.
Set ρh=ρ+(1+ρ)ρh-1, h=2,…,k-j.
Then,(11)|Fj+1i(x*[j+1])-Fj+1i(x(b1⋯bm))|≤ρ2Fj+1i(x*[j+1]),i=1,…,m.
By repeating the above argument for j+2,…,k, we show that ∃x′∈Yk such that
(12)|Fki(x′)-Fki(x*)|≤ρk-j+1Fki(x*),i=1,…,m.
Since,
(13)ρk-j+1≤ρ∑j=0k‍(1+ρ)j=(1+ρ)k+1-1=∑j=1k+1‍(k+1)k⋯(k-j+2)j!(k+1)!(ε2)j≤∑j=1k+1‍1j!ε2≤ε.
Then,(14)|Fki(x′)-Fki(x*)|≤εFki(x*),i=1,…,m.
Now, we have
(15)|max⁡i=1,…,m{Fki(x′)}-max⁡i=1,…,m{Fki(x*)}|≤εmax⁡i=1,…,m{Fki(x*)}.
From Step 6 in Algorithm AεP, we know that the vector x0 will be chosen such that
(16)|max⁡i=1,…,m{Fki(x0)}-max⁡i=1,…,m{Fki(x*)}|≤|max⁡i=1,…,m{Fki(x′)}-max⁡i=1,…,m{Fki(x*)}|≤εmax⁡i=1,…,m{Fki(x*)}.
Then,
(17)max⁡i=1,…,m{Fki(x0)}≤(1+ε)max⁡i=1,…,m{Fki(x*)}.
So,
(18)Q(x0)≤(1+ε)Q(x*).
To establish the computation of Algorithm AεP, we know that Step 5 requires the time of O(|Yj′|log⁡|Yj′|) to complete. We have |Yj+1′|≤2|Yj|≤2kF1⋯kFm.
By Proposition9, for i=1,…,m,
(19)kFi≤2(⌈n/b⌉+1)log⁡(⌈n/b⌉amax⁡(1+α)⌈n/b⌉)ε+2≤2(⌈n/b⌉+1)2Tε+2.
So |Yj′|=O((⌈n/b⌉)2mTm/εm) and |Yj′|log⁡|Yj′|=O((⌈n/b⌉)2mTm+1/εm). Now, we have that the time complexity of Algorithm AεP is O((⌈n/b⌉)2m+1Tm+1/εm).
This completes the proof of Theorem10.


### 3.3. ProblemQm∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

Motivated by Liu et al. [11], we propose an FPTAS for our uniform-parallel-machine problem Qm∣p-batch,pj=aj+αt,b<n∣Cmax⁡.We reindex jobs in increasing order of their basic processing times such thata1≤⋯≤an.We can obtain the following similar theorem to Theorem7.Theorem 11.
For problemQm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJ1.(iii)
Batches are scheduled in the increasing order of their basic processing times on every machine.For problemQm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, these properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm A, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=max⁡i∈Bj{ai}+αt=an+b(j-k)+αt.We design the FPTAS by using the procedurePartition proposed in Kovalyov and Kubiak [15] which requires that the function used must be a nonnegative integer function. Similar to Liu et al. [11], we first modify the objective function to a nonnegative integer function, and this operation does not affect the schedule. For any i∈{1,…,m} and j∈{1,…,n}, define Δ1=min⁡{aj/si}, Δ2=min⁡{1+(α/si)}. For simplicity, we suppose that Δ1 and Δ2 are finite decimals. Arbitrarily find integers {l1,l2}∈N+ such that 10l1Δ1∈N+ and 10l2Δ2∈N+. The parameter 10l1+jl2C[i,j] can be verified as an integer since C[i,j]=∑h=1j‍(1+(α/si))j-h(a[i,h]/si). Define L=10l1+kl2; the transformed objective function can be expressed as LCmax⁡. And we have that LCmax⁡ is a nonnegative integer. Meanwhile, the above scale operation only increases the absolute value of the Cmax⁡ and does not change the schedule. We use the new objective function instead of the original one in the remainder. Now our problem is equivalent to Qm∣p-batch,pj=aj+αt,b<n∣LCmax⁡.Similar to the FPTAS in Section3.2, we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(20)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)sl10l1+jl2+(1+αsl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l,
where Fji(x) is the magnified workload of machine Mi for the jobs among J1,J2,…,Jj.Then problemQm∣p-batch,pj=aj+αt,b<n∣LCmax⁡ is reduced to the following problem:
(21)Minimize⁡G(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Now, we propose the fully polynomial time approximation scheme.Algorithm
A
ε
Q. Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Form batches B1,…,Bk by using Algorithm A, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=an+b(j-k)+αt(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1 and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l. Set
(22)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)sl10l1+jl2+(1+αsl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=ε/(2(k+1)), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…; bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(23)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…; bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that G(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetK=log⁡(max⁡{⌈n/b⌉,(1/ε),Amax⁡,1+Bmax⁡,10l1,10l2}), where Amax⁡=max⁡j=1,…,n;i=1,…,m{aj/si} and Bmax⁡=max⁡i=1,…,m{α/si}.We get the following theorem.Theorem 12.
AlgorithmAεQ finds x0∈X for Qm∣p-batch,pj=aj+αt,b<n∣LCmax⁡ such that G(x0)≤(1+ε)G(x*) in O((⌈n/b⌉)(2m+1)Km+1/εm), where x* is an optimal solution.Analysis. The proof is similar to the proof of Theorem 10 except the following:
(24)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|an+b(j+1-k)sl10l1+jl2+(1+αsl)Fjl(x*[j])·10l2iiiiiiiiii1av)-an+b(j+1-k)sl10l1+jl2-(1+αsl)Fjl(x(b1⋯bm))·10l2|=(1+αsl)·10l2|Fjl(x*[j])-Fjl(x(b1⋯bm))|≤(1+αsl)·10l2ρFjl(x*[j])≤ρ1(an+b(j+1-k)sl10l1+jl2+(1+αsl)Fjl(x*[j])10l2)=ρ1Fj+1l(x*[j+1]).
Consequently,
(25)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).Similarly, fori≠l, we have
(26)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).To establish the computation of AlgorithmAεQ, we know that Step 5 requires the time of O(|Yj′|log⁡|Yj′|) to complete. We have |Yj+1′|≤2|Yj|≤2kF1⋯kFm.By Proposition9, for i=1,…,m,
(27)kFi≤2(⌈n/b⌉+1)log⁡(10l1+⌈n/b⌉l2⌈n/b⌉Amax⁡(1+Bmax⁡)⌈n/b⌉)ε+2≤2(⌈n/b⌉+1)2Kε+2.
So |Yj′|=O((⌈n/b⌉)2mKm/εm) and |Yj′|log⁡|Yj′|=O((⌈n/b⌉)2mKm+1/εm). Now, we have that the time complexity of Algorithm AεQ is O((⌈n/b⌉)2m+1Km+1/εm).


## 3.1. Single-Machine Problem1∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

In this subsection, we present anO(nlog⁡n) time algorithm for the single-machine problem.Algorithm
A. Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Let k=⌈n/b⌉ and j=n-b(k-1).Step
3. Form batches B1,…,Bk such that B1={J1,…,Jj}, B2={Jj+1,…,Jj+b},…, Bk={Jn-b+1,…,Jn}.Step
4. Schedule these batches in the increasing order of their basic processing times from time zero.Theorem 6.
The problem1∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is solvable in O(nlog⁡n) time by Algorithm A.Proof.
Suppose that we reindex the jobs in increasing order of their basic processing times. Now, we only need to prove that there exists an optimal schedule satisfying the following properties. (i) The indices of jobs in each batch are consecutive. (ii) All batches are full except possibly the one which contains jobJ1. (iii) Batches are scheduled in the increasing order of their basic processing times.
We consider an optimal scheduleπ in the following proof.
To show (i), suppose that there are two batchesBf and Bh and three jobs Ji, Jj, and Jl with ai≥aj≥al such that Ji,Jl∈Bf and Jj∈Bh in schedule π. We obtain a new schedule π′ by shifting job Jj with job Jl; that is, Bf′=Bf∖{Jl}∪{Jj} and Bh′=Bh∖{Jj}∪{Jl}. And then P(Bf′)=P(Bf) and P(Bh′)≤P(Bh) since ai≥aj≥al and the starting time is not changed. Thus, C(Bf′)≤C(Bf) and C(Bh′)≤C(Bh), and the completion times of other jobs do not increase. Thus, π′ remains optimal. A finite number of repetitions of this procedure yields an optimal schedule of the required form.
To show (ii), suppose that there is a batchBx in π such that Bx is not full. We know that the indices of jobs in Bx are consecutive from (i). Without loss of generality, let Bx={Jnx,Jnx+1,…,Jnx+e} with |Bx|=e+1<b. If we move the remaining consecutive b-(e+1) jobs {Jnx+e+1-b,…,Jnx-2,Jnx-1} from other batches to Bx, this procedure cannot increase the objective value since aj≤anx for all j=nx+e+1-b,…,nx-1. A finite number of repetitions of this procedure yields an optimal schedule with that all batches are full except possibly the one which contains the first job J1.
If we view each batchB as single aggregate job with P(B)=max⁡j∈B{aj}+αt in schedule π, property (iii) holds from Lemma 2.
This completes the proof of Theorem6.


## 3.2. ProblemPm∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

In this subsection, we assume thatm (≥2), aj(j=1,…,n) and α are all integral. We drive some properties of the optimal schedule and propose an FPTAS.We reindex jobs in increasing order of their basic processing times such thata1≤⋯≤an.Theorem 7.
For problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJ1.(iii)
Batches are scheduled in the increasing order of their basic processing times on every machine.The proof of this theorem is similar to the proof of Theorem6.For problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, the properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm A, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=max⁡Ji∈Bj{ai}+αt=an+b(j-k)+αt.Similar to the establishment of FPTAS in Kovalyov and Kubiak [15], we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on machine Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(1)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)+(1+α)Fj-1l(x)forxj=l,Fji(x)=Fj-1i(x)forxj=li≠l.
Then problem Pm∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is reduced to the following problem:
(2)Minimize⁡Q(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.
We introduce the procedure Partition (A,F,ρ) proposed by Kovalyov and Kubiak [15], where A⊆X, F is a nonnegative integer function on X, and 0<ρ≤1. This procedure partitions A into disjoint subsets A1F,A2F,…,AkFF such that |F(x)-F(x′)|≤ρmin⁡{F(x),F(x′)} for any x,x′∈AjF, j=1,2,…,kF. The following description provides the details of Partition (A,F,ρ).Procedure Partition
(
A
,
F
,
ρ
). Arrange the vectors x∈A in the order x(1),x(2),…,x(|A|), where 0≤F(x(1))≤F(x(2))≤⋯≤F(x(|A|)). Assign the vectors x(1),x(2),…,x(i1) to set A1F until i1 is found such that F(x(i1))≤(1+ρ)F(x(1)) and F(x(i1+1))>(1+ρ)F(x(1)). If such i1 does not exist, then take A1F=A and stop.Assignx(i1+1),x(i1+2),…,x(i2) to set A2F until i2 is found such that F(x(i2))≤(1+ρ)F(x(i1+1)) and F(x(i2+1))>(1+ρ)F(x(i1+1)). If such i2 does not exist, then take A2F=A-A1F and stop.Continue the above process untilx(|A|) is included in AkFF for some kF.The main properties of Partition were given by Kovalyov and Kubiak [15] as follows.Proposition 8.
Consider|F(x)-F(x′)|≤ρmin⁡{F(x),F(x′)} for any x,x′∈AjF, j=1,2,…,kF.Proposition 9.
ConsiderkF≤((log⁡F(x(|A|)))/ρ)+2 for 0<ρ≤1 and 1≤F(x(|A|)).Now, we give a fully polynomial time approximation scheme for problemPm∣p-batch,pj=aj+αt,b<n∣Cmax⁡.Algorithm
A
ε
P
.
Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Form batches B1,…,Bk by using Algorithm A, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=an+b(j-k)+αt(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…,m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l:(3)Fjl(x)=an+b(j-k)+(1+α)Fj-1l(x),Fji(x)=Fj-1i(x)fori≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/2(k+1)), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(4)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that Q(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetT=log⁡(max⁡{k,1/ε,1+α,amax⁡}), where k=⌈n/b⌉, amax⁡=max⁡j=1,…,n{aj}.We get the following theorem.Theorem 10.
Algorithm
A
ε
P
finds
x
0
∈
X
for
P
m
∣
p
-
b
a
t
c
h
,
p
j
=
a
j
+
α
t
,
b
<
n
∣
C
max
⁡ such that Q(x0)≤(1+ε)Q(x*) in O((⌈n/b⌉)(2m+1)Tm+1/εm), where x* is an optimal solution.Proof.
Suppose thatx*[j]=(x1*,…,xj*,0,…,0)∈Yb1⋯bm⊆Yj′ for some j and b1,…,bm. Algorithm AεP may not choose x*[j] for further construction; however, for a vector x(b1⋯bm) chosen instead of it, we have
(5)|Fji(x*[j])-Fji(x(b1⋯bm))|≤ρFji(x*[j]),i=1,…,m.
Set ρ1=ρ. Consider the vector x*[j+1]=(x1*,…,xj*,xj+1*,0,…,0) and x~(b1⋯bm)=(x1(b1⋯bm),…,xj(b1⋯bm),xj+1*,0,…,0). We assume xj+1*=l. It follows that
(6)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|(an+b(j+1-k)+(1+α)Fjl(x*[j]))-(an+b(j+1-k)+(1+α)Fjl(x(b1⋯bm)))|=|(1+α)(Fjl(x*[j])-Fjl(x(b1⋯bm)))|≤(1+α)ρFjl(x*[j])≤ρ1(an+b(j+1-k)+(1+α)Fjl(x*[j]))=ρ1Fj+1l(x*[j+1]).
Consequently,(7)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).
Similarly, fori≠l, we have
(8)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).
Assume thatx~(b1⋯am)∈Yc1⋯cm⊆Yj+1′ and Algorithm AεP chooses x(c1⋯cm)∈Yc1⋯cm instead of x~(b1⋯bm) in the (j+1)th iteration; then we have
(9)|Fj+1i(x~(b1⋯bm))-Fj+1i(x(c1⋯cm))|≤ρFj+1i(x~(b1⋯bm))≤ρ(1+ρ1)Fj+1i(x*[j+1]),i=1,…,m.
Then we have
(10)|Fj+1i(x*[j+1])-Fj+1i(x(c1⋯cm))|≤|Fj+1i(x*[j+1])-Fj+1i(x~(b1⋯bm))|+|Fj+1i(x~(b1⋯bm))-Fj+1i(x(c1⋯cm))|≤(ρ1+ρ(1+ρ1))Fj+1i(x*[j+1])=(ρ+ρ1(1+ρ))Fj+1i(x*[j+1]),i=1,2,…,m.
Set ρh=ρ+(1+ρ)ρh-1, h=2,…,k-j.
Then,(11)|Fj+1i(x*[j+1])-Fj+1i(x(b1⋯bm))|≤ρ2Fj+1i(x*[j+1]),i=1,…,m.
By repeating the above argument for j+2,…,k, we show that ∃x′∈Yk such that
(12)|Fki(x′)-Fki(x*)|≤ρk-j+1Fki(x*),i=1,…,m.
Since,
(13)ρk-j+1≤ρ∑j=0k‍(1+ρ)j=(1+ρ)k+1-1=∑j=1k+1‍(k+1)k⋯(k-j+2)j!(k+1)!(ε2)j≤∑j=1k+1‍1j!ε2≤ε.
Then,(14)|Fki(x′)-Fki(x*)|≤εFki(x*),i=1,…,m.
Now, we have
(15)|max⁡i=1,…,m{Fki(x′)}-max⁡i=1,…,m{Fki(x*)}|≤εmax⁡i=1,…,m{Fki(x*)}.
From Step 6 in Algorithm AεP, we know that the vector x0 will be chosen such that
(16)|max⁡i=1,…,m{Fki(x0)}-max⁡i=1,…,m{Fki(x*)}|≤|max⁡i=1,…,m{Fki(x′)}-max⁡i=1,…,m{Fki(x*)}|≤εmax⁡i=1,…,m{Fki(x*)}.
Then,
(17)max⁡i=1,…,m{Fki(x0)}≤(1+ε)max⁡i=1,…,m{Fki(x*)}.
So,
(18)Q(x0)≤(1+ε)Q(x*).
To establish the computation of Algorithm AεP, we know that Step 5 requires the time of O(|Yj′|log⁡|Yj′|) to complete. We have |Yj+1′|≤2|Yj|≤2kF1⋯kFm.
By Proposition9, for i=1,…,m,
(19)kFi≤2(⌈n/b⌉+1)log⁡(⌈n/b⌉amax⁡(1+α)⌈n/b⌉)ε+2≤2(⌈n/b⌉+1)2Tε+2.
So |Yj′|=O((⌈n/b⌉)2mTm/εm) and |Yj′|log⁡|Yj′|=O((⌈n/b⌉)2mTm+1/εm). Now, we have that the time complexity of Algorithm AεP is O((⌈n/b⌉)2m+1Tm+1/εm).
This completes the proof of Theorem10.


## 3.3. ProblemQm∣p-batch,  pj=aj+αt,  b<n∣Cmax⁡

Motivated by Liu et al. [11], we propose an FPTAS for our uniform-parallel-machine problem Qm∣p-batch,pj=aj+αt,b<n∣Cmax⁡.We reindex jobs in increasing order of their basic processing times such thata1≤⋯≤an.We can obtain the following similar theorem to Theorem7.Theorem 11.
For problemQm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJ1.(iii)
Batches are scheduled in the increasing order of their basic processing times on every machine.For problemQm∣p-batch,pj=aj+αt,b<n∣Cmax⁡, these properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm A, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=max⁡i∈Bj{ai}+αt=an+b(j-k)+αt.We design the FPTAS by using the procedurePartition proposed in Kovalyov and Kubiak [15] which requires that the function used must be a nonnegative integer function. Similar to Liu et al. [11], we first modify the objective function to a nonnegative integer function, and this operation does not affect the schedule. For any i∈{1,…,m} and j∈{1,…,n}, define Δ1=min⁡{aj/si}, Δ2=min⁡{1+(α/si)}. For simplicity, we suppose that Δ1 and Δ2 are finite decimals. Arbitrarily find integers {l1,l2}∈N+ such that 10l1Δ1∈N+ and 10l2Δ2∈N+. The parameter 10l1+jl2C[i,j] can be verified as an integer since C[i,j]=∑h=1j‍(1+(α/si))j-h(a[i,h]/si). Define L=10l1+kl2; the transformed objective function can be expressed as LCmax⁡. And we have that LCmax⁡ is a nonnegative integer. Meanwhile, the above scale operation only increases the absolute value of the Cmax⁡ and does not change the schedule. We use the new objective function instead of the original one in the remainder. Now our problem is equivalent to Qm∣p-batch,pj=aj+αt,b<n∣LCmax⁡.Similar to the FPTAS in Section3.2, we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(20)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)sl10l1+jl2+(1+αsl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l,
where Fji(x) is the magnified workload of machine Mi for the jobs among J1,J2,…,Jj.Then problemQm∣p-batch,pj=aj+αt,b<n∣LCmax⁡ is reduced to the following problem:
(21)Minimize⁡G(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Now, we propose the fully polynomial time approximation scheme.Algorithm
A
ε
Q. Consider the following steps.Step
1. Reindex the jobs in increasing order of their basic processing times such that a1≤a2≤⋯≤an.Step
2. Form batches B1,…,Bk by using Algorithm A, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=an+b(j-k)+αt(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1 and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l. Set
(22)F0i(x)=0i=1,2,…,m,Fjl(x)=an+b(j-k)sl10l1+jl2+(1+αsl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=ε/(2(k+1)), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…; bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(23)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…; bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that G(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetK=log⁡(max⁡{⌈n/b⌉,(1/ε),Amax⁡,1+Bmax⁡,10l1,10l2}), where Amax⁡=max⁡j=1,…,n;i=1,…,m{aj/si} and Bmax⁡=max⁡i=1,…,m{α/si}.We get the following theorem.Theorem 12.
AlgorithmAεQ finds x0∈X for Qm∣p-batch,pj=aj+αt,b<n∣LCmax⁡ such that G(x0)≤(1+ε)G(x*) in O((⌈n/b⌉)(2m+1)Km+1/εm), where x* is an optimal solution.Analysis. The proof is similar to the proof of Theorem 10 except the following:
(24)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|an+b(j+1-k)sl10l1+jl2+(1+αsl)Fjl(x*[j])·10l2iiiiiiiiii1av)-an+b(j+1-k)sl10l1+jl2-(1+αsl)Fjl(x(b1⋯bm))·10l2|=(1+αsl)·10l2|Fjl(x*[j])-Fjl(x(b1⋯bm))|≤(1+αsl)·10l2ρFjl(x*[j])≤ρ1(an+b(j+1-k)sl10l1+jl2+(1+αsl)Fjl(x*[j])10l2)=ρ1Fj+1l(x*[j+1]).
Consequently,
(25)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).Similarly, fori≠l, we have
(26)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).To establish the computation of AlgorithmAεQ, we know that Step 5 requires the time of O(|Yj′|log⁡|Yj′|) to complete. We have |Yj+1′|≤2|Yj|≤2kF1⋯kFm.By Proposition9, for i=1,…,m,
(27)kFi≤2(⌈n/b⌉+1)log⁡(10l1+⌈n/b⌉l2⌈n/b⌉Amax⁡(1+Bmax⁡)⌈n/b⌉)ε+2≤2(⌈n/b⌉+1)2Kε+2.
So |Yj′|=O((⌈n/b⌉)2mKm/εm) and |Yj′|log⁡|Yj′|=O((⌈n/b⌉)2mKm+1/εm). Now, we have that the time complexity of Algorithm AεQ is O((⌈n/b⌉)2m+1Km+1/εm).


## 4. Modelpj=a+αjt

In this section, we discuss the modelpj=a+αjt. First, we present polynomial time algorithm for problem 1∣p-batch,pj=a+αjt,b<n∣Cmax⁡. Then we propose fully polynomial time approximation schemes for problems Pm∣p-batch,pj=a+αjt,b<n∣Cmax⁡ and Qm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, respectively.


### 4.1. Single-Machine Problem1∣p-batch,  pj=a+αjt,  b<n∣Cmax⁡

In this subsection, we present anO(nlog⁡n) time algorithm for the single-machine problem.Algorithm FBLDR (fully batching longest deteriorating rate). Consider the following stepsStep
1. Reindex jobs in nonincreasing order of their deteriorating rates such that α1≥⋯≥αn.Step
2. Form batches by placing jobs Jjb+1 through J(j+1)b together in the same batch, for j=0,1,…,⌊n/b⌋Step
3. Schedule the batches in the increasing order of their indices.The schedule contains at most⌊n/b⌋+1 batches and all batches are full except possibly the last one, where ⌊n/b⌋ denotes the largest integer less than or equal to n/b.Theorem 13.
Algorithm FBLDR solves problem1∣p-batch,pj=a+αjt,b<n∣Cmax⁡ optimally, and the optimal objective value is Cmax⁡*=a[1+∑i=2n‍∏l=in‍(1+α(l-1)b+1)].We omit the proof as it is simple.


### 4.2. ProblemPm∣p-batch, pj=a+αjt, b<n∣Cmax⁡

In this subsection, we assume thatm(≥2), αj(j=1,…,n) and a are all integral. We drive some properties of the optimal schedule and propose an FPTAS.We reindex jobs in nonincreasing order of their deteriorating rates such thatα1≥⋯≥αn.Theorem 14.
For problemPm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJn.(iii)
Batches are scheduled in the increasing order of their indices on every machine.For problemPm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, the properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm FBLDR, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=a+max⁡Ji∈Bj{αi}t=a+α(j-1)b+1t.Similar to the establishment of FPTAS in Kovalyov and Kubiak [15], we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on machine Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(28)F0i(x)=0i=1,2,…,m,Fjl(x)=a+(1+α(j-1)b+1)Fj-1l(x)forxj=l,Fji(x)=Fj-1i(x)forxj=li≠l.
Then problem Pm∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is reduced to the following problem:
(29)MinimizeQ(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Using theProcedure Partition(A,F,ρ), we design a fully polynomial time approximation scheme for problem Pm∣p-batch,pj=a+αjt,b<n∣Cmax⁡ as follows.Algorithm
H
ε
P. Consider the following steps.Step
1. Reindex the jobs in nonincreasing order of their deteriorating rates such that α1≥α2≥⋯≥αn.Step
2. Form batches B1,…,Bk by using Algorithm FBLDR, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=a+α(j-1)b+1(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l:
(30)Fjl(x)=a+(1+α(j-1)b+1)Fj-1l(x),Fji(x)=Fj-1i(x)fori≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/(2(k+1))), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(31)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;⋯;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that Q(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetT=log⁡(max⁡{k,(1/ε),1+αmax⁡,a}), where αmax⁡=max⁡j=1,…,n{αj}.We get the following theorem.Theorem 15.
AlgorithmHεP finds x0∈X for Pm∣p-batch,pj=a+αjt,b<n∣Cmax⁡ such that Q(x0)≤(1+ε)Q(x*) in O((⌈n/b⌉)(2m+1)Tm+1/εm), where x* is an optimal solution.Proof.
Suppose thatx*[j]=(x1*,…,xj*,0,…,0)∈Yb1⋯bm⊆Yj′ for some j and b1,…,bm. Algorithm HεP may not choose x*[j] for further construction; however, for a vector x(b1⋯bm) chosen instead of it, we have
(32)|Fji(x*[j])-Fji(x(b1⋯bm))|≤ρFji(x*[j]),i=1,…,m.
Set ρ1=ρ. Consider the vector x*[j+1]=(x1*,…,xj*,xj+1*,0,…,0) and x~(b1⋯bm)=(x1(b1⋯bm),…,xj(b1⋯bm),xj+1*,0,…,0). We assume xj+1*=l. It follows that
(33)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|(a+(1+αjb+1)Fjl(x*[j]))-(a+(1+αjb+1)Fjl(x(b1⋯bm)))|=|(1+αjb+1)(Fjl(x*[j])-Fjl(x(b1⋯bm)))|≤(1+αjb+1)ρFjl(x*[j])≤ρ1(a+(1+αjb+1)Fjl(x*[j]))=ρ1Fj+1l(x*[j+1]).
Consequently,(34)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).
Similarly, fori≠l, we have
(35)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).
The remained proof of this theorem is similar to that of Theorem10.


### 4.3. ProblemQm∣p-batch, pj=a+αjt, b<n∣Cmax⁡

We reindex jobs in nonincreasing order of their deteriorating rates such thatα1≥⋯≥αn.Theorem 16.
For problemQm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJn.(iii)
Batches are scheduled in the increasing order of their indices on every machine.For problemQm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, these properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm FBLDR, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=a+α(j-1)b+1t.Followed that in Section3.3, for any i∈{1,…,m} and j∈{1,…,n}, define Δ1=min⁡{a/si}, Δ2=min⁡{1+(αj/si)}. For simplicity, we suppose that Δ1 and Δ2 are finite decimals. Arbitrarily find integers {l1,l2}∈N+ such that 10l1Δ1∈N+ and 10l2Δ2∈N+. From Lemma 5, the parameter 10l1+jl2C[i,j] can be verified as an integer since C[i,j]=(a/si)[1+∑i=2j‍∏h=ij‍(1+(α[i,h]/si))]. Define L=10l1+kl2, the transformed objective function can be expressed as LCmax⁡. And we have that LCmax⁡ is a nonnegative integer. Meanwhile, the above scale operation only increases the absolute value of the Cmax⁡ and does not change the schedule. We use the new objective function instead of the original one in the remainder. Now our problem is equivalent to Qm∣p-batch,pj=a+αjt,b<n∣LCmax⁡.Similar to the FPTAS in Section3.3, now, we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(36)F0i(x)=0i=1,2,…,m,Fjl(x)=asl10l1+jl2+(1+α(j-1)b+1sl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l,
where Fji(x) is the magnified workload of machine Mi for the jobs among J1,J2,…,Jj.Then problemQm∣p-batch,pj=a+αjt,b<n∣LCmax⁡ is reduced to the following problem:
(37)MinimizeG(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Now, we propose the fully polynomial time approximation scheme.Algorithm
H
ε
Q. Consider the following steps.Step
1. Reindex the jobs in non-increasing order of their deteriorating rates such that α1≥α2≥⋯≥αn.Step
2. Form batches B1,…,Bk by using Algorithm FBLDR, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=a+α(j-1)b+1t(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l. Set
(38)F0i(x)=0i=1,2,…,m,Fjl(x)=asl10l1+jl2+(1+α(j-1)b+1sl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/(2(k+1))), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(39)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that G(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetK=log⁡(max⁡{⌈n/b⌉,(1/ε),Dmax⁡,1+Emax⁡,10l1,10l2}), where Dmax⁡=max⁡i=1,…,m{a/si} and Emax⁡=max⁡j=1,…,n;i=1,…,m{αj/si}.We get the following theorem.Theorem 17.
AlgorithmHεQ finds x0∈X for Qm∣p-batch,pj=a+αjt,b<n∣LCmax⁡ such that G(x0)≤(1+ε)G(x*) in O((⌈n/b⌉)(2m+1)Km+1/εm), where x* is an optimal solution.


## 4.1. Single-Machine Problem1∣p-batch,  pj=a+αjt,  b<n∣Cmax⁡

In this subsection, we present anO(nlog⁡n) time algorithm for the single-machine problem.Algorithm FBLDR (fully batching longest deteriorating rate). Consider the following stepsStep
1. Reindex jobs in nonincreasing order of their deteriorating rates such that α1≥⋯≥αn.Step
2. Form batches by placing jobs Jjb+1 through J(j+1)b together in the same batch, for j=0,1,…,⌊n/b⌋Step
3. Schedule the batches in the increasing order of their indices.The schedule contains at most⌊n/b⌋+1 batches and all batches are full except possibly the last one, where ⌊n/b⌋ denotes the largest integer less than or equal to n/b.Theorem 13.
Algorithm FBLDR solves problem1∣p-batch,pj=a+αjt,b<n∣Cmax⁡ optimally, and the optimal objective value is Cmax⁡*=a[1+∑i=2n‍∏l=in‍(1+α(l-1)b+1)].We omit the proof as it is simple.


## 4.2. ProblemPm∣p-batch, pj=a+αjt, b<n∣Cmax⁡

In this subsection, we assume thatm(≥2), αj(j=1,…,n) and a are all integral. We drive some properties of the optimal schedule and propose an FPTAS.We reindex jobs in nonincreasing order of their deteriorating rates such thatα1≥⋯≥αn.Theorem 14.
For problemPm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJn.(iii)
Batches are scheduled in the increasing order of their indices on every machine.For problemPm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, the properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm FBLDR, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=a+max⁡Ji∈Bj{αi}t=a+α(j-1)b+1t.Similar to the establishment of FPTAS in Kovalyov and Kubiak [15], we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on machine Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(28)F0i(x)=0i=1,2,…,m,Fjl(x)=a+(1+α(j-1)b+1)Fj-1l(x)forxj=l,Fji(x)=Fj-1i(x)forxj=li≠l.
Then problem Pm∣p-batch,pj=aj+αt,b<n∣Cmax⁡ is reduced to the following problem:
(29)MinimizeQ(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Using theProcedure Partition(A,F,ρ), we design a fully polynomial time approximation scheme for problem Pm∣p-batch,pj=a+αjt,b<n∣Cmax⁡ as follows.Algorithm
H
ε
P. Consider the following steps.Step
1. Reindex the jobs in nonincreasing order of their deteriorating rates such that α1≥α2≥⋯≥αn.Step
2. Form batches B1,…,Bk by using Algorithm FBLDR, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=a+α(j-1)b+1(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l:
(30)Fjl(x)=a+(1+α(j-1)b+1)Fj-1l(x),Fji(x)=Fj-1i(x)fori≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/(2(k+1))), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(31)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;⋯;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that Q(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetT=log⁡(max⁡{k,(1/ε),1+αmax⁡,a}), where αmax⁡=max⁡j=1,…,n{αj}.We get the following theorem.Theorem 15.
AlgorithmHεP finds x0∈X for Pm∣p-batch,pj=a+αjt,b<n∣Cmax⁡ such that Q(x0)≤(1+ε)Q(x*) in O((⌈n/b⌉)(2m+1)Tm+1/εm), where x* is an optimal solution.Proof.
Suppose thatx*[j]=(x1*,…,xj*,0,…,0)∈Yb1⋯bm⊆Yj′ for some j and b1,…,bm. Algorithm HεP may not choose x*[j] for further construction; however, for a vector x(b1⋯bm) chosen instead of it, we have
(32)|Fji(x*[j])-Fji(x(b1⋯bm))|≤ρFji(x*[j]),i=1,…,m.
Set ρ1=ρ. Consider the vector x*[j+1]=(x1*,…,xj*,xj+1*,0,…,0) and x~(b1⋯bm)=(x1(b1⋯bm),…,xj(b1⋯bm),xj+1*,0,…,0). We assume xj+1*=l. It follows that
(33)|Fj+1l(x*[j+1])-Fj+1l(x~(b1⋯bm))|=|(a+(1+αjb+1)Fjl(x*[j]))-(a+(1+αjb+1)Fjl(x(b1⋯bm)))|=|(1+αjb+1)(Fjl(x*[j])-Fjl(x(b1⋯bm)))|≤(1+αjb+1)ρFjl(x*[j])≤ρ1(a+(1+αjb+1)Fjl(x*[j]))=ρ1Fj+1l(x*[j+1]).
Consequently,(34)Fj+1l(x~(b1⋯bm))≤(1+ρ1)Fj+1l(x*[j+1]).
Similarly, fori≠l, we have
(35)Fj+1i(x~(b1⋯bm))≤(1+ρ1)Fj+1i(x*[j+1]).
The remained proof of this theorem is similar to that of Theorem10.


## 4.3. ProblemQm∣p-batch, pj=a+αjt, b<n∣Cmax⁡

We reindex jobs in nonincreasing order of their deteriorating rates such thatα1≥⋯≥αn.Theorem 16.
For problemQm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, there exists an optimal schedule satisfying the following properties.(i)
The indices of jobs in each batch on every machine are consecutive.(ii)
All batches are full except possibly the one which contains jobJn.(iii)
Batches are scheduled in the increasing order of their indices on every machine.For problemQm∣p-batch,pj=a+αjt,b<n∣Cmax⁡, these properties allow us to determine the batch structure of an optimal solution a priori. So we divide jobs into batches B1,B2,…,Bk according to Algorithm FBLDR, where k=⌈n/b⌉. It is possible to view the batch Bj(j=1,2,…,k) as single aggregate job with processing times P(Bj)=a+α(j-1)b+1t.Followed that in Section3.3, for any i∈{1,…,m} and j∈{1,…,n}, define Δ1=min⁡{a/si}, Δ2=min⁡{1+(αj/si)}. For simplicity, we suppose that Δ1 and Δ2 are finite decimals. Arbitrarily find integers {l1,l2}∈N+ such that 10l1Δ1∈N+ and 10l2Δ2∈N+. From Lemma 5, the parameter 10l1+jl2C[i,j] can be verified as an integer since C[i,j]=(a/si)[1+∑i=2j‍∏h=ij‍(1+(α[i,h]/si))]. Define L=10l1+kl2, the transformed objective function can be expressed as LCmax⁡. And we have that LCmax⁡ is a nonnegative integer. Meanwhile, the above scale operation only increases the absolute value of the Cmax⁡ and does not change the schedule. We use the new objective function instead of the original one in the remainder. Now our problem is equivalent to Qm∣p-batch,pj=a+αjt,b<n∣LCmax⁡.Similar to the FPTAS in Section3.3, now, we introduce the variables xj, xj∈{1,2,…,m}, j=1,2,…,k, where xj=l if batch Bj is scheduled on Ml(l∈{1,2,…,m}). Let X be the set of all vectors x=(x1,x2,…,xk) with xj=l, j=1,2,…,k,  l=1,2,…,m. Set
(36)F0i(x)=0i=1,2,…,m,Fjl(x)=asl10l1+jl2+(1+α(j-1)b+1sl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l,
where Fji(x) is the magnified workload of machine Mi for the jobs among J1,J2,…,Jj.Then problemQm∣p-batch,pj=a+αjt,b<n∣LCmax⁡ is reduced to the following problem:
(37)MinimizeG(x)=max⁡{Fki(x)∣i=1,2,…,m}forx∈X.Now, we propose the fully polynomial time approximation scheme.Algorithm
H
ε
Q. Consider the following steps.Step
1. Reindex the jobs in non-increasing order of their deteriorating rates such that α1≥α2≥⋯≥αn.Step
2. Form batches B1,…,Bk by using Algorithm FBLDR, where k=⌈n/b⌉.Step
3. Regard batch Bj as an aggregate job with P(Bj)=a+α(j-1)b+1t(j=1,…,k).Step
4. Set Y0={(0,0,…,0︷k)}, j=1, and F0i(x)=0 for i=1,2,…m.Step
5. For the set Yj-1, generate the set Yj′ by adding l(l=1,2,…,m) in position j of each vector from Yj-1. Calculate the following for any x∈Yj′, without loss of generality, assuming xj=l. Set
(38)F0i(x)=0i=1,2,…,m,Fjl(x)=asl10l1+jl2+(1+α(j-1)b+1sl)Fj-1l(x)·10l2forxj=l,Fji(x)=Fj-1i(x)·10l2forxj=li≠l.
If j=k, then set Yk=Yk′, and go to Step 6.Ifj<k, then set ρ=(ε/(2(k+1))), and perform the following computation.Call Partition(Yj′,Fji,ρ)(i=1,…,m) to partition the set Yj′ into disjoint subsets Y1Fi,Y2Fi,…,YkFiFi.Divide setYj′ into disjoint subsets Yb1⋯bm=Yb1F1⋂‍⋯⋂‍YbmFm, b1=1,…,kF1;…;bm=1,…,kFm. For each nonempty subset Yb1⋯bm, choose a vector x(b1⋯bm) such that
(39)Fjl(x(b1⋯bm))=min⁡{max⁡i=1,…,mFji(x)∣x∈Yb1⋯bm}.
Set Yj:={x(b1⋯bm)∣b1=1,…,kF1;…;bm=1,…,kFm, and Yb1F1⋂‍⋯⋂‍YbmFm≠ϕ}, and j=j+1. Repeat Step 5.Step
6. Select set x0∈Yk such that G(x0)=min⁡x∈Yk{max⁡i=1,…,mFki(x)}.LetK=log⁡(max⁡{⌈n/b⌉,(1/ε),Dmax⁡,1+Emax⁡,10l1,10l2}), where Dmax⁡=max⁡i=1,…,m{a/si} and Emax⁡=max⁡j=1,…,n;i=1,…,m{αj/si}.We get the following theorem.Theorem 17.
AlgorithmHεQ finds x0∈X for Qm∣p-batch,pj=a+αjt,b<n∣LCmax⁡ such that G(x0)≤(1+ε)G(x*) in O((⌈n/b⌉)(2m+1)Km+1/εm), where x* is an optimal solution.


## 5. Conclusion

In this paper, we consider the parallel-batch scheduling withpj=aj+αt and pj=a+αjt; the objective is to minimize the makespan. For these two models of deterioration, we present O(nlog⁡n) algorithms for the single-machine problem and propose fully polynomial time approximation schemes to solve the identical-parallel-machine problem and uniform-parallel-machine problem, respectively.For future research, it is worth considering other objectives.



---

*Source: 495187-2014-07-23.xml*