# Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection

Authors: Juan Zou; Cuixia Miao
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection. Each job is either accepted and processed on a single batching machine, or rejected by paying penalties. The processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of
the rejected jobs. First, we show that the problem is NP-hard in the ordinary sense. Then, we present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem. Furthermore, we provide an optimalO
(
n
log
⁡
n
) time algorithm for the case where jobs have identical release dates.


---

## Body

## 1. Introduction

The parallel batch scheduling problem has been extensively studied in the literature over the last decade. The fundamental model of the parallel batch scheduling problem was first introduced by Lee et al. [1] with the restriction that the number of jobs in each batch is bounded by a number b. This bounded model is motivated by the burn-in operations in semiconductor manufacturing. Brucker et al. [2] provided an extensive discussion of the unbounded version of the parallel batch scheduling problem. This unbounded model can be applied, for example, to situations where the batch contents are heated in a sufficiently large kiln. Cheng et al. [3], Deng et al. [4, 5], and Liu et al. [6, 7] presented new complexity results and approximation algorithms for the parallel batch scheduling problem subject to release dates. In addition, more recent developments of this topic can be found in [8].In classical scheduling problems, it is assumed that the processing times of jobs are fixed parameters. In practice, however, we often encounter situations in which processing time increases over time. Examples can be found in financial management, steel production, firefighting, and so forth, where any delay in processing a job may increase its completion time. Such problems are generally known as scheduling with deterioration effects. Browne and Yechiali [9] first considered scheduling problem with linear deterioration. They provided the optimal solution for the single machine when the objective is to minimize makespan. In addition, they solved a special case when the objective function is to minimize the total weighted completion time. Mosheiov [10] considered single machine scheduling problems with simple linear deteriorating jobs. He showed that most commonly scheduling objectives, such as the makespan, the total flow time, the sum of weighted completion times, the maximum lateness, the total lateness, the maximum tardiness, and the number of tardy jobs, remain solvable in polynomial time. Alidaee and Womer [11] presented an extensive survey of different deteriorating models and scheduling problems. Cheng et al. [12] provided an updated survey of scheduling problems with time-dependent processing times. Li et al. [13] considered the problem of scheduling of deteriorating jobs with release dates on a single batching machine. Miao et al. [14] studied the scheduling problems with deteriorating jobs and release dates on a single (batching) machine to minimize the maximum lateness. Zou et al. [15] considered several uniform parallel machine scheduling problems with linear deteriorating jobs.On the other hand, it is always assumed in traditional scheduling research that all the jobs have to be processed on some machines. In real applications, however, things may be more complicated. For example, due to limited resources, the scheduler may reject some jobs and thereby incur job-dependent penalties for each rejected job. Bartal et al. [16] first introduced the notion of rejection. They considered both the offline and online versions of scheduling problem and studied the multiprocessor scheduling problem to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. Subsequently, the machine scheduling problem with rejection has received increasing research attention. Hoogeveen et al. [17] considered the offline multiprocessor scheduling problem with rejection where preemption is allowed. They provided a pseudopolynomial time algorithm for each problem. Lu et al. [18] considered the unbounded parallel batch machine scheduling problem with release dates and rejection. Engels et al. [19] studied the single machine scheduling with rejection to minimize the sum of the weighted completion times of the scheduled jobs and the total penalty of the rejected jobs. Shabtay et al. [20] 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 [21] considered the single machine scheduling problems with linear deteriorating jobs and rejection. Li and Yuan [22] 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. To the best of our knowledge, no work has been done on the problem of scheduling deteriorating jobs with rejection on a single batching machine. Literature [20] on scheduling with rejection focuses on the following four models:P
1: to minimize the total integrated cost F
1
+
F
2;
P
2: to minimize F
1 subject to F
2
≤
E
¯;
P
3: to minimize F
2 subject to F
1
≤
K;
P
4: to identify a Pareto-optimal solution for each Pareto-optimal point,where F
1 is the original scheduling objective function and F
2 is total rejection cost. We discuss the first model with deterioration and release dates.In this paper, we study parallel batch scheduling of deteriorating jobs with release dates and rejection. The paper is organized as follows. In Section2, we formulate the problem under consideration and introduce some notations. In Section 3, we first show that the problem is binary NP-hard and provide two pseudopolynomial time algorithms. We also propose a fully polynomial-time approximation scheme for the problem and discuss one special case. In Section 4, we conclude the paper and suggest some topics for future research.


## 2. Problem Description and Notation

The problem considered in this paper can be formally described as follows. There are an independent job setJ
=
{
J
1
,
…
,
J
n
} and a single batching machine. The machine can process up to b job simultaneously as a batch, where b
≥
n. The jobs processed in the same batch have the same starting time and completion time. The processing time of a batch is equal to the largest processing time of the jobs in the batch. Each job J
j
(
j
=
1
,
…
,
n
) has a release date r
j, a deteriorating rate b
j
>
0, and a rejection penalty e
j. Each job J
j
(
j
=
1
,
…
,
n
) is either rejected with a rejection penalty e
j having to be paid or accepted and processed on the parallel batch machine. Denote by R and R
¯
=
J
∖
R the set of rejected jobs and the set of accepted jobs, respectively. The actual processing time of job J
j is given by p
j
=
b
j
t, where t
≥
r
j is the starting time of J
j. We assume min
⁡
{
r
j
∣
j
=
1
,
…
,
n
}
≥
t
0
>
0. For a given batch B, we denote its deteriorating rate and release date by b
(
B
) and r
(
B
), respectively. Then, b
(
B
)
=
max
⁡
{
b
j
:
J
j
∈
B
} and r
(
B
)
=
max
⁡
{
r
j
:
J
j
∈
B
}. Denote by C
j the completion time of the accepted job J
j. We study the problem of minimizing the sum of the makespan of the accepted jobs (i.e., C
max
⁡
(
R
¯
)
=
max
⁡
{
C
j
:
J
j
∈
R
¯
}) and the total penalty of the rejected jobs. Using the three-field notation of Graham et al. [23], we denote the problem by 1
|
p
-batch
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j.


## 3.  Main Results

### 3.1. NP-Hardness Proof

We first give a lemma, which will be used in what follows.Lemma 1 (see [10]).
For the problem1
|
r
j
=
t
0
,
p
j
=
b
j
t
|
C
max
⁡, the maximum completion time of the jobs is equal to C
max
⁡
=
t
0
∏
J
j
∈
J
‍
(
1
+
b
j
) and it does not depend on the processing order of the jobs.Theorem 2.
The problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j is binary NP-hard.Proof.
The decision version of the scheduling problem is clearly in NP. We use a reduction from the Equal Products Problem, which is NP-hard (see [24]).
An instance I of the Equal Products Problem is formulated as follows. Given a setQ
=
{
1,2
,
…
,
m
} and positive integers a
i for each i
∈
Q such that ∏
i
∈
Q
a
i
=
A
2 for a certain positive integer A, does there exist a subset S
⊂
Q such that ∏
i
∈
S
a
i
=
A?
For any given instance I of the Equal Products Problem, we construct a corresponding instance II of our problem as follows.(i)
There aren
=
2
m
+
1 jobs.
(ii)
Fori
=
1, there exist job J
1 with (
r
1
,
b
1
,
e
1
)
=
(
1
,
A
2
m
-
1,2
A
m
2
+
m
+
1
+
A
) and job J
2 with (
r
2
,
b
2
,
e
2
)
=
(
1
,
A
2
m
a
1
-
1
,
ln
⁡
a
1
).
(iii)
For each2
≤
i
≤
m, there exist job J
2
i
-
1 with (
r
2
i
-
1
,
b
2
i
-
1
,
e
2
i
-
1
) = (
A
∑
k
=
0
i
-
2
(
2
m
-
2
k
)
,
A
2
m
-
2
(
i
-
1
)
-
1,2
A
m
2
+
m
+
1
+
A
) and job J
2
i with (
r
2
i
,
b
2
i
,
e
2
i
) = (
A
∑
k
=
0
i
-
2
(
2
m
-
2
k
)
,
A
2
m
-
2
(
i
-
1
)
a
i
-
1
,
ln
⁡
a
i
).
(iv)
Fori
=
2
m
+
1, there exists only a job J
2
m
+
1 with (
r
2
m
+
1
,
b
2
m
+
1
,
e
2
m
+
1
)
=
(
A
m
2
+
m
+
1
,
1,2
A
m
2
+
m
+
1
+
A
).
(v)
The threshold value is given byY
=
2
A
m
2
+
m
+
1
+
ln
⁡
A.
The decision asks whether there is a schedule such thatC
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y.It is clear that the reduction can be done in polynomial time, and it is easy to verify thatb
i
>
0 for i
=
1
,
…
,
m
+
1. Assume first that the Equal Products Problem has a solution S such that ∏
i
∈
S
a
i
=
A. Then, we construct a schedule in the following way. If i
∈
S, we assign the jobs J
2
i
-
1 and J
2
i as a batch B
i. If i
∉
S, we assign the job J
2
i
-
1 as a batch B
i. We assign the job J
2
m
+
1 as the last batch B
m
+
1. The jobs are processed on the batch machine in the order of B
1
,
…
,
B
m
+
1. All other jobs are rejected. It is easy to verify that
(1)
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
e
j
=
max
⁡
⁡
{
A
m
2
+
m
∏
i
∈
S
‍
a
i
,
r
m
+
1
}
(
1
+
b
m
+
1
)
+
∑
i
∉
S
‍
ln
⁡
a
i
=
2
A
m
2
+
m
+
1
+
ln
⁡
A
=
Y
.Conversely, suppose that there is a scheduleπ with C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y. We need to show that there is a subset S for the Equal Products Problem with ∏
i
∈
S
a
i
=
A. We have the following claims.Claim 1.
All jobsJ
2
i
-
1 for each 1
≤
i
≤
m
+
1 are accepted and C
max
⁡
(
R
¯
)
≥
2
A
m
2
+
m
+
1.Proof.
If there exists some jobJ
2
i
-
1
(
1
≤
i
≤
m
+
1
) being rejected, then we have C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≥
e
2
i
-
1 = 2
A
m
2
+
m
+
1
+
A
>
Y. It is a contradiction. Since job J
2
m
+
1 is accepted, we have C
max
⁡
(
R
¯
)
≥
r
2
m
+
1
(
1
+
b
2
m
+
1
)
≥
2
A
m
2
+
m
+
1.
From Claim1, we can obtain that only the jobs {
J
2
i
:
1
≤
i
≤
m
} can be rejected.Claim 2.
Only jobJ
2
m
+
1 is processed in the last batch.Proof.
If there exists a jobJ
i (1
≤
i
≤
2
m) with J
2
m
+
1 processed in the same batch B, then we have
(2)
C
max
⁡
=
r
2
m
+
1
(
1
+
b
(
B
)
)
=
r
2
m
+
1
(
1
+
b
i
)
≥
A
m
2
+
m
+
1
(
1
+
A
2
-
1
)
=
A
m
2
+
m
+
3
>
Y
.
Then, we denote byB
m
+
1 the last batch containing only job J
2
m
+
1.Claim 3.
Each batch contains either a single jobJ
2
i
-
1 or two jobs {
J
2
i
-
1
,
J
2
i
} for 1
≤
i
≤
m.Proof.
For jobJ
2
m
-
1, if there exists a job J
i (1
≤
i
≤
2
m
-
2) with J
2
m
-
1 which are processed in the same batch B, then we have C
max
⁡
=
r
2
m
-
1
(
1
+
b
(
B
)
)
=
r
2
m
-
1
(
1
+
b
i
)
≥
A
m
2
+
m
-
2
(
1
+
A
4
-
1
)
=
A
m
2
+
m
+
1
·
A
>
Y.
Thus, we denote byB
m the new batch containing job J
2
m
-
1.
For jobJ
2
m
-
3, if there exists a job J
i (1
≤
i
≤
2
m
-
4) with J
2
m
-
3 which are processed in the same batch B
m
-
1, then we have the completion time of the batch as
(3)
C
(
B
m
-
1
)
≥
r
2
m
-
3
(
1
+
b
(
B
m
-
1
)
)
=
r
2
m
-
3
(
1
+
b
i
)
≥
A
m
2
+
m
-
6
(
1
+
A
6
-
1
)
=
A
m
2
+
m
.
The completion time of batch B
m is
(4)
C
(
B
m
)
=
max
⁡
{
C
(
B
m
-
1
)
,
r
2
m
-
1
}
(
1
+
b
(
B
m
)
)
≥
A
m
2
+
m
+
2
>
Y
.
Therefore, batchB
m
-
1 can only contain either job J
2
m
-
3 or jobs {
J
2
m
-
3
,
J
2
m
-
4
}. Repeat this deduction, we have the correctness of Claim 3. Let B
i be the batch containing job J
2
i
-
1 for 1
≤
i
≤
m.
By Claims2 and 3, we have batch B
i
=
{
J
2
i
-
1
,
J
2
i
} if J
2
i is accepted and batch B
i
=
{
J
2
i
-
1
} if J
2
i is rejected. Let S
=
{
i
:
J
2
i is rejected for 1
≤
i
≤
m
}. Next, we are ready to show that S is a solution of the Equal Products Problem.
SinceC
max
⁡
(
R
¯
)
≥
2
A
m
2
+
m
+
1 and C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y
=
2
A
m
2
+
m
+
1
+
ln
⁡
A, we have ∑
j
∈
S
‍
ln
⁡
a
j = ∑
J
2
j
∈
R
‍
e
2
j
≤
ln
⁡
A. If ∏
j
∈
S
‍
a
j
=
X
<
A, we have
(5)
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
=
max
⁡
⁡
{
r
(
B
m
+
1
)
,
C
(
B
m
)
}
(
1
+
b
m
+
1
)
+
∑
j
∈
S
‍
ln
⁡
a
j
=
2
max
⁡
⁡
{
A
m
2
+
m
+
1
,
A
m
2
+
m
·
∏
i
∈
S
¯
‍
a
i
}
+
ln
⁡
X
>
2
A
m
2
+
m
+
1
·
A
X
+
ln
⁡
X
>
Y
.
It is a contradiction. Hence, we have∏
j
∈
S
‍
a
j
=
A and S is a solution of the Equal Products Problem. This completes the proof.


### 3.2.  Dynamic Programming Algorithms

Lemma 3.
For problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, there exists an optimal schedule such that the accepted jobs are processed in a nonincreasing order of deteriorating rates.Proof.
Otherwise, there exist two accepted jobsJ
i and J
j such that J
j is processed later than J
i, but b
i
<
b
j. Since b
≥
n, there is no limit on the number of jobs in a batch and we can put job J
i into the batch containing job J
j. This does not delay the completion time of any batch. A finite number of repetitions of this procedure yields an optimal schedule of the required form.Based on Lemma3, we only consider the schedules in which the accepted jobs are processed in a nonincreasing order of deterioration rates. Assume that jobs are indexed such that b
1
≥
⋯
≥
b
n.LetF
(
j
,
k
,
E
) denote the optimal objective function value of the following scheduling problem:(i)
the jobs in consideration areJ
1
,
…
,
J
j;
(ii)
J
k is the job with the minimum index in the last batch;
(iii)
the total penalty of rejected jobs isE.In any such schedule, there are two possible cases: eitherJ
j is rejected or J
j is accepted and processed on the batching machine. We distinguish two cases in the following discussion.Case 1.
JobJ
j is rejected. Since J
j is rejected, in the corresponding optimal schedule for J
1
,
…
,
J
j
-
1, J
k is still the job with the minimum index in the last batch and the total rejection penalty among J
1
,
…
,
J
j
-
1 is E
-
e
j. Therefore, we have F
(
j
,
k
,
E
)
=
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j.Case 2.
JobJ
j is accepted. In this case, we consider this problem in the following two cases.
Case
2
.1. If k
=
j, then job J
j starts a new batch. The starting time of job J
j is max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}. Therefore, we have F
(
j
,
k
,
E
)
=
min
⁡
0
≤
k
′
≤
j
-
1
⁡
{
max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}
(
1
+
b
j
)
+
E
}.
Case
2.2. If k
<
j, then job J
j can be assigned to the last batch containing job J
k. Therefore, F
(
j
,
k
,
E
)
=
max
⁡
{
(
F
(
j
-
1
,
k
,
E
)
-
E
)
/
(
1
+
b
k
)
,
r
j
}
(
1
+
b
k
)
+
E.
Combining the above two cases, we design the following dynamic programming algorithm.
Algorithm DP1. Consider the following steps.
Step
1 (initialization). Consider F
(
1,1
,
0
)
=
r
1
(
1
+
b
1
) and F
(
1
,
k
,
E
)
=
∞ for (
k
,
E
)
≠
(
1,0
).
ConsiderF
(
1,0
,
e
1
)
=
t
0
+
e
1 and F
(
1
,
k
,
E
)
=
∞ for (
k
,
E
)
≠
(
0
,
e
1
).
Step
2 (recursion). If k
=
j,
(6)
F
(
j
,
k
,
E
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}
×
(
1
+
b
j
)
+
E
}
,
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j
min
⁡
0
≤
k
′
≤
j
-
1
}
.
Ifk
<
j,
(7)
F
(
j
,
k
,
E
)
=
min
⁡
{
max
⁡
{
F
(
j
-
1
,
k
,
E
)
-
E
1
+
b
k
,
r
j
}
(
1
+
b
k
)
+
E
,
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j
{
F
(
j
-
1
,
k
,
E
)
-
E
1
+
b
k
,
r
j
}
}
.
Step
3 (optimal solution). The optimal value is given by min
⁡
{
F
(
n
,
k
,
E
)
:
0
≤
k
≤
n
,
0
≤
E
≤
∑
j
=
1
n
e
j
}.Theorem 4.
AlgorithmDP1 solves the problem 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j in O
(
n
2
∑
j
=
1
n
e
j
) time.Proof.
The correctness of Algorithm DP1 is guaranteed by the above discussion. The recursive function has at mostO
(
n
2
∑
j
=
1
n
e
j
) states; each iteration takes a constant time to execute. Hence, the running time of Algorithm DP
1 is O
(
n
2
∑
j
=
1
n
e
j
).Next, we give another dynamic programming AlgorithmDP
2. Let f
(
j
,
k
,
E
) denote the minimum value of the maximum completion time satisfying the following conditions.(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
J
k is the job with the minimum index in the last batch.
(iii)
The total penalty of rejected jobs isE.In any such schedule, there are two possible cases: eitherJ
j is rejected or J
j is accepted and processed on the batching machine.Case 1.
If jobJ
j is rejected, we have f
(
j
,
k
,
E
)
=
f
(
j
-
1
,
k
,
E
-
e
j
).Case 2.
JobJ
j is accepted.
Case
2.1. If k
=
j, then job J
j starts a new batch; the starting time of job J
j is max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}. Therefore, we have f
(
j
,
k
,
E
)
=
min
⁡
0
≤
k
′
≤
j
-
1
⁡
{
max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}
(
1
+
b
j
)
}.
Case
2.2. If k
<
j, then job J
j can be assigned to the last batch containing job J
k. Therefore, f
(
j
,
k
,
E
)
=
max
⁡
{
f
(
j
-
1
,
k
,
E
)
/
(
1
+
b
k
)
,
r
j
}
(
1
+
b
k
).Combining the above two cases, we design the dynamic programming algorithm as follows.Algorithm DP2. Consider the following steps.Step
1 (initialization). Consider f
(
1,1
,
0
)
=
r
1
(
1
+
b
1
) and f
(
1
,
k
,
E
)
=
∞ for any (
k
,
E
)
≠
(
1,0
).Considerf
(
1,0
,
e
1
)
=
t
0 and f
(
1
,
k
,
E
)
=
∞ for any (
k
,
E
)
≠
(
0
,
e
1
).Step
2 (recursion). If k
=
j,
(8)
f
(
j
,
k
,
E
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}
(
1
+
b
j
)
}
,
f
(
j
-
1
,
k
,
E
-
e
j
)
min
⁡
0
≤
k
′
≤
j
-
1
}
.Ifk
<
j,
(9)
f
(
j
,
k
,
E
)
=
min
⁡
⁡
{
max
⁡
⁡
{
f
(
j
-
1
,
k
,
E
)
1
+
b
k
,
r
j
}
(
1
+
b
k
)
,
f
(
j
-
1
,
k
,
E
-
e
j
)
{
f
(
j
-
1
,
k
,
E
)
1
+
b
k
,
r
j
}
}
.Step
3 (optimal solution). The optimal value is determined by min
⁡
{
f
(
n
,
k
,
E
)
+
E
:
0
≤
k
≤
n
,
0
≤
E
≤
∑
j
=
1
n
e
j
}.Theorem 5.
Algorithm DP2 solves the problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j in O
(
n
2
∑
j
=
1
n
e
j
) time.


### 3.3.  An FPTAS

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 the sequel, we assume 0
<
ϵ
≤
1.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, let ϵ
′
=
ϵ
/
2
n and let R
=
{
J
i
1
,
J
i
2
,
…
,
J
i
m
} be the set of the rejected jobs, where i
1
<
i
2
<
⋯
<
i
m. The inflated rejection penalty of the set R with respect to any ϵ
′
>
0 is defined as
(10)
ϕ
ϵ
′
(
R
)
=
{
⌈
e
i
m
+
ϕ
ϵ
′
(
R
-
J
i
m
)
⌉
ϵ
′
,
if
m
≥
1
,
0
,
if
R
=
∅
.Lemma 6 (see [25]).
For any setR of jobs and any ϵ
′
>
0, ϕ
ϵ
′
(
R
)
≤
(
1
+
ϵ
′
)
|
R
|
∑
J
j
∈
R
‍
e
j.Lemma 7 (see [19]).
For any0
<
x
≤
1 and for any integer n
≥
1, (
1
+
(
x
/
n
)
)
n
≤
1
+
2
x holds.Based on Lemmas6 and 7, we have the following theorem.Theorem 8.
For any0
<
ϵ
≤
2, the optimal objective function value for 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
ϕ
ϵ
′
(
R
) is at most (
1
+
ϵ
) times the optimal objective function value for 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j.Assume that the jobs have been indexed such thatb
1
≥
⋯
≥
b
n and define
(11)
τ
l
=
{
(
1
+
ϵ
′
)
l
,
if
l
≠
-
1
,
0
,
if
l
=
-
1
.Letf
(
j
,
k
,
l
) denote the minimum value of the maximum completion time satisfying the following conditions.(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
In the last batch,J
k is the job with the minimum index.
(iii)
The inflated rejection penalty of the rejected jobs isτ
l.We design a dynamic programming algorithm as follows.Algorithm
A
ϵ. Consider the following steps.Step
1 (initialization). Consider
(12)
f
(
1
,
k
,
l
)
=
{
t
0
,
if
τ
1
=
⌈
e
1
⌉
ϵ
′
,
r
1
(
1
+
b
1
)
,
if
l
=
-
1
,
+
∞
,
otherwise
.Step
2 (recursion). If k
=
j, then
(13)
f
(
j
,
k
,
l
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
f
(
j
-
1
,
k
′
,
l
)
,
r
j
}
(
1
+
b
j
)
}
,
min
⁡
-
1
≤
l
′
≤
l
~
f
(
j
-
1
,
k
,
l
′
)
min
⁡
0
≤
k
′
≤
j
-
1
}
.Ifk
<
j, then
(14)
f
(
j
,
k
,
l
)
=
min
⁡
{
max
⁡
{
f
(
j
-
1
,
k
,
l
)
1
+
b
k
,
r
j
}
(
1
+
b
k
)
,
min
⁡
-
1
≤
l
′
≤
l
~
f
(
j
-
1
,
k
,
l
′
)
{
f
(
j
-
1
,
k
,
l
)
1
+
b
k
,
r
j
}
}
,
where l
~ is given by (
1
+
ϵ
′
)
l
~
=
⌊
(
1
+
ϵ
′
)
l
-
e
j
⌋
ϵ
′.Step
3 (output). The optimal value is determined by min
⁡
{
f
(
n
,
k
,
l
)
+
τ
l
:
0
≤
k
≤
n
,
-
1
≤
l
≤
L
}, where L is the smallest integer such that (
1
+
ϵ
′
)
L
≥
(
1
+
ϵ
′
)
n
∑
j
=
1
n
e
j.Theorem 9.
There exists an FPTAS for problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
j
∈
R
‍
e
j which runs in O
(
(
n
4
/
ϵ
2
)
log
⁡
2
∑
j
=
1
n
e
j
) time.Proof.
The correctness of AlgorithmA
ϵ is guaranteed by the above discussion. We need to compute exactly O
(
n
2
(
L
+
2
)
) values f
(
j
,
k
,
l
) and computation of each value takes O
(
L
) time, where L
=
O
(
(
n
/
ϵ
)
log
⁡
∑
j
=
1
n
e
j
). Hence, the running time of Algorithm A
ϵ is O
(
n
2
L
2
)
=
O
(
(
n
4
/
ϵ
2
)
log
⁡
2
∑
j
=
1
n
e
j
).


### 3.4.  An Optimal Algorithm of One Special Case

The special case where all jobs have the same release dates is considered in this subsection, that is, the problem1
|
p
-batch
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j.We first reindex the jobs in nonincreasing order of their deteriorating rates such thatb
1
≥
⋯
≥
b
n.Lemma 10.
For problem1
|
p
-
b
a
t
c
h
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, in any optimal schedule, if job J
j
(
1
≤
j
≤
n
) is accepted, then the jobs set {
J
i
:
i
≥
j
} is accepted too.Proof.
If jobJ
j is accepted, since b
≥
n, there is no limit on the number of jobs in a batch; the jobs {
J
j
+
1
,
…
,
J
n
} can be accepted and assigned to the current last batch. Obviously, this does not increase the value of the objective function. This completes the proof.Theorem 11.
For problem1
|
p
-
b
a
t
c
h
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, the optimal function value is min
⁡
{
t
0
(
1
+
b
1
)
,
∑
j
=
1
n
e
j
,
min
⁡
2
≤
j
≤
n
⁡
{
t
0
(
1
+
b
j
)
+
∑
i
=
1
j
-
1
e
i
}
}; the optimal solution can be found in O
(
n
log
⁡
n
) time.


## 3.1. NP-Hardness Proof

We first give a lemma, which will be used in what follows.Lemma 1 (see [10]).
For the problem1
|
r
j
=
t
0
,
p
j
=
b
j
t
|
C
max
⁡, the maximum completion time of the jobs is equal to C
max
⁡
=
t
0
∏
J
j
∈
J
‍
(
1
+
b
j
) and it does not depend on the processing order of the jobs.Theorem 2.
The problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j is binary NP-hard.Proof.
The decision version of the scheduling problem is clearly in NP. We use a reduction from the Equal Products Problem, which is NP-hard (see [24]).
An instance I of the Equal Products Problem is formulated as follows. Given a setQ
=
{
1,2
,
…
,
m
} and positive integers a
i for each i
∈
Q such that ∏
i
∈
Q
a
i
=
A
2 for a certain positive integer A, does there exist a subset S
⊂
Q such that ∏
i
∈
S
a
i
=
A?
For any given instance I of the Equal Products Problem, we construct a corresponding instance II of our problem as follows.(i)
There aren
=
2
m
+
1 jobs.
(ii)
Fori
=
1, there exist job J
1 with (
r
1
,
b
1
,
e
1
)
=
(
1
,
A
2
m
-
1,2
A
m
2
+
m
+
1
+
A
) and job J
2 with (
r
2
,
b
2
,
e
2
)
=
(
1
,
A
2
m
a
1
-
1
,
ln
⁡
a
1
).
(iii)
For each2
≤
i
≤
m, there exist job J
2
i
-
1 with (
r
2
i
-
1
,
b
2
i
-
1
,
e
2
i
-
1
) = (
A
∑
k
=
0
i
-
2
(
2
m
-
2
k
)
,
A
2
m
-
2
(
i
-
1
)
-
1,2
A
m
2
+
m
+
1
+
A
) and job J
2
i with (
r
2
i
,
b
2
i
,
e
2
i
) = (
A
∑
k
=
0
i
-
2
(
2
m
-
2
k
)
,
A
2
m
-
2
(
i
-
1
)
a
i
-
1
,
ln
⁡
a
i
).
(iv)
Fori
=
2
m
+
1, there exists only a job J
2
m
+
1 with (
r
2
m
+
1
,
b
2
m
+
1
,
e
2
m
+
1
)
=
(
A
m
2
+
m
+
1
,
1,2
A
m
2
+
m
+
1
+
A
).
(v)
The threshold value is given byY
=
2
A
m
2
+
m
+
1
+
ln
⁡
A.
The decision asks whether there is a schedule such thatC
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y.It is clear that the reduction can be done in polynomial time, and it is easy to verify thatb
i
>
0 for i
=
1
,
…
,
m
+
1. Assume first that the Equal Products Problem has a solution S such that ∏
i
∈
S
a
i
=
A. Then, we construct a schedule in the following way. If i
∈
S, we assign the jobs J
2
i
-
1 and J
2
i as a batch B
i. If i
∉
S, we assign the job J
2
i
-
1 as a batch B
i. We assign the job J
2
m
+
1 as the last batch B
m
+
1. The jobs are processed on the batch machine in the order of B
1
,
…
,
B
m
+
1. All other jobs are rejected. It is easy to verify that
(1)
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
e
j
=
max
⁡
⁡
{
A
m
2
+
m
∏
i
∈
S
‍
a
i
,
r
m
+
1
}
(
1
+
b
m
+
1
)
+
∑
i
∉
S
‍
ln
⁡
a
i
=
2
A
m
2
+
m
+
1
+
ln
⁡
A
=
Y
.Conversely, suppose that there is a scheduleπ with C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y. We need to show that there is a subset S for the Equal Products Problem with ∏
i
∈
S
a
i
=
A. We have the following claims.Claim 1.
All jobsJ
2
i
-
1 for each 1
≤
i
≤
m
+
1 are accepted and C
max
⁡
(
R
¯
)
≥
2
A
m
2
+
m
+
1.Proof.
If there exists some jobJ
2
i
-
1
(
1
≤
i
≤
m
+
1
) being rejected, then we have C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≥
e
2
i
-
1 = 2
A
m
2
+
m
+
1
+
A
>
Y. It is a contradiction. Since job J
2
m
+
1 is accepted, we have C
max
⁡
(
R
¯
)
≥
r
2
m
+
1
(
1
+
b
2
m
+
1
)
≥
2
A
m
2
+
m
+
1.
From Claim1, we can obtain that only the jobs {
J
2
i
:
1
≤
i
≤
m
} can be rejected.Claim 2.
Only jobJ
2
m
+
1 is processed in the last batch.Proof.
If there exists a jobJ
i (1
≤
i
≤
2
m) with J
2
m
+
1 processed in the same batch B, then we have
(2)
C
max
⁡
=
r
2
m
+
1
(
1
+
b
(
B
)
)
=
r
2
m
+
1
(
1
+
b
i
)
≥
A
m
2
+
m
+
1
(
1
+
A
2
-
1
)
=
A
m
2
+
m
+
3
>
Y
.
Then, we denote byB
m
+
1 the last batch containing only job J
2
m
+
1.Claim 3.
Each batch contains either a single jobJ
2
i
-
1 or two jobs {
J
2
i
-
1
,
J
2
i
} for 1
≤
i
≤
m.Proof.
For jobJ
2
m
-
1, if there exists a job J
i (1
≤
i
≤
2
m
-
2) with J
2
m
-
1 which are processed in the same batch B, then we have C
max
⁡
=
r
2
m
-
1
(
1
+
b
(
B
)
)
=
r
2
m
-
1
(
1
+
b
i
)
≥
A
m
2
+
m
-
2
(
1
+
A
4
-
1
)
=
A
m
2
+
m
+
1
·
A
>
Y.
Thus, we denote byB
m the new batch containing job J
2
m
-
1.
For jobJ
2
m
-
3, if there exists a job J
i (1
≤
i
≤
2
m
-
4) with J
2
m
-
3 which are processed in the same batch B
m
-
1, then we have the completion time of the batch as
(3)
C
(
B
m
-
1
)
≥
r
2
m
-
3
(
1
+
b
(
B
m
-
1
)
)
=
r
2
m
-
3
(
1
+
b
i
)
≥
A
m
2
+
m
-
6
(
1
+
A
6
-
1
)
=
A
m
2
+
m
.
The completion time of batch B
m is
(4)
C
(
B
m
)
=
max
⁡
{
C
(
B
m
-
1
)
,
r
2
m
-
1
}
(
1
+
b
(
B
m
)
)
≥
A
m
2
+
m
+
2
>
Y
.
Therefore, batchB
m
-
1 can only contain either job J
2
m
-
3 or jobs {
J
2
m
-
3
,
J
2
m
-
4
}. Repeat this deduction, we have the correctness of Claim 3. Let B
i be the batch containing job J
2
i
-
1 for 1
≤
i
≤
m.
By Claims2 and 3, we have batch B
i
=
{
J
2
i
-
1
,
J
2
i
} if J
2
i is accepted and batch B
i
=
{
J
2
i
-
1
} if J
2
i is rejected. Let S
=
{
i
:
J
2
i is rejected for 1
≤
i
≤
m
}. Next, we are ready to show that S is a solution of the Equal Products Problem.
SinceC
max
⁡
(
R
¯
)
≥
2
A
m
2
+
m
+
1 and C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
≤
Y
=
2
A
m
2
+
m
+
1
+
ln
⁡
A, we have ∑
j
∈
S
‍
ln
⁡
a
j = ∑
J
2
j
∈
R
‍
e
2
j
≤
ln
⁡
A. If ∏
j
∈
S
‍
a
j
=
X
<
A, we have
(5)
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j
=
max
⁡
⁡
{
r
(
B
m
+
1
)
,
C
(
B
m
)
}
(
1
+
b
m
+
1
)
+
∑
j
∈
S
‍
ln
⁡
a
j
=
2
max
⁡
⁡
{
A
m
2
+
m
+
1
,
A
m
2
+
m
·
∏
i
∈
S
¯
‍
a
i
}
+
ln
⁡
X
>
2
A
m
2
+
m
+
1
·
A
X
+
ln
⁡
X
>
Y
.
It is a contradiction. Hence, we have∏
j
∈
S
‍
a
j
=
A and S is a solution of the Equal Products Problem. This completes the proof.


## 3.2.  Dynamic Programming Algorithms

Lemma 3.
For problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, there exists an optimal schedule such that the accepted jobs are processed in a nonincreasing order of deteriorating rates.Proof.
Otherwise, there exist two accepted jobsJ
i and J
j such that J
j is processed later than J
i, but b
i
<
b
j. Since b
≥
n, there is no limit on the number of jobs in a batch and we can put job J
i into the batch containing job J
j. This does not delay the completion time of any batch. A finite number of repetitions of this procedure yields an optimal schedule of the required form.Based on Lemma3, we only consider the schedules in which the accepted jobs are processed in a nonincreasing order of deterioration rates. Assume that jobs are indexed such that b
1
≥
⋯
≥
b
n.LetF
(
j
,
k
,
E
) denote the optimal objective function value of the following scheduling problem:(i)
the jobs in consideration areJ
1
,
…
,
J
j;
(ii)
J
k is the job with the minimum index in the last batch;
(iii)
the total penalty of rejected jobs isE.In any such schedule, there are two possible cases: eitherJ
j is rejected or J
j is accepted and processed on the batching machine. We distinguish two cases in the following discussion.Case 1.
JobJ
j is rejected. Since J
j is rejected, in the corresponding optimal schedule for J
1
,
…
,
J
j
-
1, J
k is still the job with the minimum index in the last batch and the total rejection penalty among J
1
,
…
,
J
j
-
1 is E
-
e
j. Therefore, we have F
(
j
,
k
,
E
)
=
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j.Case 2.
JobJ
j is accepted. In this case, we consider this problem in the following two cases.
Case
2
.1. If k
=
j, then job J
j starts a new batch. The starting time of job J
j is max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}. Therefore, we have F
(
j
,
k
,
E
)
=
min
⁡
0
≤
k
′
≤
j
-
1
⁡
{
max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}
(
1
+
b
j
)
+
E
}.
Case
2.2. If k
<
j, then job J
j can be assigned to the last batch containing job J
k. Therefore, F
(
j
,
k
,
E
)
=
max
⁡
{
(
F
(
j
-
1
,
k
,
E
)
-
E
)
/
(
1
+
b
k
)
,
r
j
}
(
1
+
b
k
)
+
E.
Combining the above two cases, we design the following dynamic programming algorithm.
Algorithm DP1. Consider the following steps.
Step
1 (initialization). Consider F
(
1,1
,
0
)
=
r
1
(
1
+
b
1
) and F
(
1
,
k
,
E
)
=
∞ for (
k
,
E
)
≠
(
1,0
).
ConsiderF
(
1,0
,
e
1
)
=
t
0
+
e
1 and F
(
1
,
k
,
E
)
=
∞ for (
k
,
E
)
≠
(
0
,
e
1
).
Step
2 (recursion). If k
=
j,
(6)
F
(
j
,
k
,
E
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
F
(
j
-
1
,
k
′
,
E
)
-
E
,
r
j
}
×
(
1
+
b
j
)
+
E
}
,
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j
min
⁡
0
≤
k
′
≤
j
-
1
}
.
Ifk
<
j,
(7)
F
(
j
,
k
,
E
)
=
min
⁡
{
max
⁡
{
F
(
j
-
1
,
k
,
E
)
-
E
1
+
b
k
,
r
j
}
(
1
+
b
k
)
+
E
,
F
(
j
-
1
,
k
,
E
-
e
j
)
+
e
j
{
F
(
j
-
1
,
k
,
E
)
-
E
1
+
b
k
,
r
j
}
}
.
Step
3 (optimal solution). The optimal value is given by min
⁡
{
F
(
n
,
k
,
E
)
:
0
≤
k
≤
n
,
0
≤
E
≤
∑
j
=
1
n
e
j
}.Theorem 4.
AlgorithmDP1 solves the problem 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j in O
(
n
2
∑
j
=
1
n
e
j
) time.Proof.
The correctness of Algorithm DP1 is guaranteed by the above discussion. The recursive function has at mostO
(
n
2
∑
j
=
1
n
e
j
) states; each iteration takes a constant time to execute. Hence, the running time of Algorithm DP
1 is O
(
n
2
∑
j
=
1
n
e
j
).Next, we give another dynamic programming AlgorithmDP
2. Let f
(
j
,
k
,
E
) denote the minimum value of the maximum completion time satisfying the following conditions.(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
J
k is the job with the minimum index in the last batch.
(iii)
The total penalty of rejected jobs isE.In any such schedule, there are two possible cases: eitherJ
j is rejected or J
j is accepted and processed on the batching machine.Case 1.
If jobJ
j is rejected, we have f
(
j
,
k
,
E
)
=
f
(
j
-
1
,
k
,
E
-
e
j
).Case 2.
JobJ
j is accepted.
Case
2.1. If k
=
j, then job J
j starts a new batch; the starting time of job J
j is max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}. Therefore, we have f
(
j
,
k
,
E
)
=
min
⁡
0
≤
k
′
≤
j
-
1
⁡
{
max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}
(
1
+
b
j
)
}.
Case
2.2. If k
<
j, then job J
j can be assigned to the last batch containing job J
k. Therefore, f
(
j
,
k
,
E
)
=
max
⁡
{
f
(
j
-
1
,
k
,
E
)
/
(
1
+
b
k
)
,
r
j
}
(
1
+
b
k
).Combining the above two cases, we design the dynamic programming algorithm as follows.Algorithm DP2. Consider the following steps.Step
1 (initialization). Consider f
(
1,1
,
0
)
=
r
1
(
1
+
b
1
) and f
(
1
,
k
,
E
)
=
∞ for any (
k
,
E
)
≠
(
1,0
).Considerf
(
1,0
,
e
1
)
=
t
0 and f
(
1
,
k
,
E
)
=
∞ for any (
k
,
E
)
≠
(
0
,
e
1
).Step
2 (recursion). If k
=
j,
(8)
f
(
j
,
k
,
E
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
f
(
j
-
1
,
k
′
,
E
)
,
r
j
}
(
1
+
b
j
)
}
,
f
(
j
-
1
,
k
,
E
-
e
j
)
min
⁡
0
≤
k
′
≤
j
-
1
}
.Ifk
<
j,
(9)
f
(
j
,
k
,
E
)
=
min
⁡
⁡
{
max
⁡
⁡
{
f
(
j
-
1
,
k
,
E
)
1
+
b
k
,
r
j
}
(
1
+
b
k
)
,
f
(
j
-
1
,
k
,
E
-
e
j
)
{
f
(
j
-
1
,
k
,
E
)
1
+
b
k
,
r
j
}
}
.Step
3 (optimal solution). The optimal value is determined by min
⁡
{
f
(
n
,
k
,
E
)
+
E
:
0
≤
k
≤
n
,
0
≤
E
≤
∑
j
=
1
n
e
j
}.Theorem 5.
Algorithm DP2 solves the problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j in O
(
n
2
∑
j
=
1
n
e
j
) time.


## 3.3.  An FPTAS

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 the sequel, we assume 0
<
ϵ
≤
1.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, let ϵ
′
=
ϵ
/
2
n and let R
=
{
J
i
1
,
J
i
2
,
…
,
J
i
m
} be the set of the rejected jobs, where i
1
<
i
2
<
⋯
<
i
m. The inflated rejection penalty of the set R with respect to any ϵ
′
>
0 is defined as
(10)
ϕ
ϵ
′
(
R
)
=
{
⌈
e
i
m
+
ϕ
ϵ
′
(
R
-
J
i
m
)
⌉
ϵ
′
,
if
m
≥
1
,
0
,
if
R
=
∅
.Lemma 6 (see [25]).
For any setR of jobs and any ϵ
′
>
0, ϕ
ϵ
′
(
R
)
≤
(
1
+
ϵ
′
)
|
R
|
∑
J
j
∈
R
‍
e
j.Lemma 7 (see [19]).
For any0
<
x
≤
1 and for any integer n
≥
1, (
1
+
(
x
/
n
)
)
n
≤
1
+
2
x holds.Based on Lemmas6 and 7, we have the following theorem.Theorem 8.
For any0
<
ϵ
≤
2, the optimal objective function value for 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
ϕ
ϵ
′
(
R
) is at most (
1
+
ϵ
) times the optimal objective function value for 1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j.Assume that the jobs have been indexed such thatb
1
≥
⋯
≥
b
n and define
(11)
τ
l
=
{
(
1
+
ϵ
′
)
l
,
if
l
≠
-
1
,
0
,
if
l
=
-
1
.Letf
(
j
,
k
,
l
) denote the minimum value of the maximum completion time satisfying the following conditions.(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
In the last batch,J
k is the job with the minimum index.
(iii)
The inflated rejection penalty of the rejected jobs isτ
l.We design a dynamic programming algorithm as follows.Algorithm
A
ϵ. Consider the following steps.Step
1 (initialization). Consider
(12)
f
(
1
,
k
,
l
)
=
{
t
0
,
if
τ
1
=
⌈
e
1
⌉
ϵ
′
,
r
1
(
1
+
b
1
)
,
if
l
=
-
1
,
+
∞
,
otherwise
.Step
2 (recursion). If k
=
j, then
(13)
f
(
j
,
k
,
l
)
=
min
⁡
{
min
⁡
0
≤
k
′
≤
j
-
1
{
max
⁡
{
f
(
j
-
1
,
k
′
,
l
)
,
r
j
}
(
1
+
b
j
)
}
,
min
⁡
-
1
≤
l
′
≤
l
~
f
(
j
-
1
,
k
,
l
′
)
min
⁡
0
≤
k
′
≤
j
-
1
}
.Ifk
<
j, then
(14)
f
(
j
,
k
,
l
)
=
min
⁡
{
max
⁡
{
f
(
j
-
1
,
k
,
l
)
1
+
b
k
,
r
j
}
(
1
+
b
k
)
,
min
⁡
-
1
≤
l
′
≤
l
~
f
(
j
-
1
,
k
,
l
′
)
{
f
(
j
-
1
,
k
,
l
)
1
+
b
k
,
r
j
}
}
,
where l
~ is given by (
1
+
ϵ
′
)
l
~
=
⌊
(
1
+
ϵ
′
)
l
-
e
j
⌋
ϵ
′.Step
3 (output). The optimal value is determined by min
⁡
{
f
(
n
,
k
,
l
)
+
τ
l
:
0
≤
k
≤
n
,
-
1
≤
l
≤
L
}, where L is the smallest integer such that (
1
+
ϵ
′
)
L
≥
(
1
+
ϵ
′
)
n
∑
j
=
1
n
e
j.Theorem 9.
There exists an FPTAS for problem1
|
p
-
b
a
t
c
h
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
j
∈
R
‍
e
j which runs in O
(
(
n
4
/
ϵ
2
)
log
⁡
2
∑
j
=
1
n
e
j
) time.Proof.
The correctness of AlgorithmA
ϵ is guaranteed by the above discussion. We need to compute exactly O
(
n
2
(
L
+
2
)
) values f
(
j
,
k
,
l
) and computation of each value takes O
(
L
) time, where L
=
O
(
(
n
/
ϵ
)
log
⁡
∑
j
=
1
n
e
j
). Hence, the running time of Algorithm A
ϵ is O
(
n
2
L
2
)
=
O
(
(
n
4
/
ϵ
2
)
log
⁡
2
∑
j
=
1
n
e
j
).


## 3.4.  An Optimal Algorithm of One Special Case

The special case where all jobs have the same release dates is considered in this subsection, that is, the problem1
|
p
-batch
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j.We first reindex the jobs in nonincreasing order of their deteriorating rates such thatb
1
≥
⋯
≥
b
n.Lemma 10.
For problem1
|
p
-
b
a
t
c
h
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, in any optimal schedule, if job J
j
(
1
≤
j
≤
n
) is accepted, then the jobs set {
J
i
:
i
≥
j
} is accepted too.Proof.
If jobJ
j is accepted, since b
≥
n, there is no limit on the number of jobs in a batch; the jobs {
J
j
+
1
,
…
,
J
n
} can be accepted and assigned to the current last batch. Obviously, this does not increase the value of the objective function. This completes the proof.Theorem 11.
For problem1
|
p
-
b
a
t
c
h
,
r
j
=
t
0
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j, the optimal function value is min
⁡
{
t
0
(
1
+
b
1
)
,
∑
j
=
1
n
e
j
,
min
⁡
2
≤
j
≤
n
⁡
{
t
0
(
1
+
b
j
)
+
∑
i
=
1
j
-
1
e
i
}
}; the optimal solution can be found in O
(
n
log
⁡
n
) time.


## 4.  Conclusion

In this paper, we focus on the unbounded parallel batch scheduling of deteriorating jobs with release date and rejection. The objective is to minimize the makespan of the accepted jobs plus the total penalty of rejected jobs. We show that it is binary NP-hard; we provide two pseudopolynomial time algorithms and also propose a fully polynomial-time approximation scheme for the problem1
|
p
-batch
,
r
j
,
p
j
=
b
j
t
,
r
e
j
,
b
≥
n
|
C
max
⁡
(
R
¯
)
+
∑
J
j
∈
R
‍
e
j. Furthermore, we show that this problem can be solvable in O
(
n
log
⁡
n
) time when jobs have identical release dates. For future research, it would be interesting to focus on scheduling deteriorating jobs with other objectives. Analysis of the other models of scheduling with rejection is also an interesting research direction.



---

*Source: 270942-2014-07-21.xml*