# Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations

Authors: Xuefei Shi; Dehua Xu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear formf
t
=
a
+
b
t with a
≥
0 and b
>
1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b
≥
0 unless P
=
N
P, which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b
>
1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b
≤
1 both from the worst-case bound point of view.


---

## Body

## 1.  Introduction

Scheduling with machine maintenance has attracted many researchers’ attention in the last two decades (see, e.g., [1–13]), where high performance approximation algorithms are of great value not only theoretically but also practically.In a recent paper, Xu et al. [14] study a single machine scheduling problem with multiple maintenance activities which can be formally described as follows. There are n independent jobs J
1
,
J
2
,
…
,
J
n to be processed on a single machine. The processing time of job J
i is p
i. All jobs are nonpreemptive and are available at time zero. The machine can process at most one job at a time. Assume that the machine has just finished a dummy maintenance activity at time zero. The length of the time interval between any two consecutive maintenance activities is T and prefixed. The amount of time needed to perform one maintenance activity is an increasing linear function T
M
(
t
)
=
a
+
b
t of the total processing time t of the jobs that are processed after its latest previous maintenance activity, where a and b are prefixed nonnegative real numbers with b
≤
1. The objective is to schedule all the jobs to the machine such that the makespan, that is, the completion time of the last finished job, is minimized. Extending the well-known three-field α
|
β
|
γ classification scheme suggested by Graham et al. [15], the problem is denoted by 1, M
S
[
T
,
T
], T
M
(
t
)
=
a
+
b
t, b
≤
1
∥
C
max
⁡ in Xu et al. [14]. For simplicity, in what follows, we denote this problem by P
(
b
≤
1
) and its counterpart where b
>
1 by P
(
b
>
1
). Additionally, the problem is denoted by P
(
b
>
0
) if b
>
0.Xu et al. [14] first propose an approximation algorithm named FFD-LS for the problem P
(
b
≤
1
) and then show that its worst-case bound is 2. The underlying idea of their FFD-LS algorithm is straightforward. Viewing the jobs as items, it first packs these items into some bins with the same capacity of T by the classical bin-packing algorithm FFD. Let the “jobs” in each used bin plus a maintenance activity whose duration is computed according to the maintenance function T
M
(
t
) be viewed as a hybrid job. Assign all the hybrid jobs except the last one (i.e., the one with the largest index) to the machine by the classical LS algorithm. Assign the last hybrid jobs to the machine.For the sake of convenience and completeness, the bin-packing problem, the FFD algorithm, the LS algorithm, and the FFD-LS algorithm are presented as follows.Bin-Packing Problem (see, e.g., Coffman et al. [16]). Given n items a
1
,
a
2
,
…
,
a
n, each with a size s
(
a
i
)
∈
(
0
,
W
], we are asked to pack them into a minimum number of W-capacity bins (i.e., partition them into a minimum number m of subsets B
1
,
B
2
,
…
,
B
m such that ∑
a
i
∈
B
j
‍
s
(
a
i
)
≤
W, 1
≤
j
≤
m).Algorithm FFD (see, e.g., Coffman et al. [16]). Sort all the items such that s
(
a
1
)
≥
s
(
a
2
)
≥
⋯
≥
s
(
a
n
); for i
=
1,2
,
…
,
n, item a
i is packed in the first (lowest-indexed) bin into which it will fit; that is, if there is any partially filled bin B
j with level
(
B
j
)
≤
W
-
s
(
a
i
) where level
(
B
j
) is the sum of the sizes of the items that have been packed into bin B
j, we place a
i in the lowest-indexed bin having this property. Otherwise, we start a new bin with a
i as its first item.Algorithm LS (see, e.g., Pinedo [17]). Put all the jobs on a list in arbitrary order; then process the jobs consecutively as early as possible.Algorithm FFD-LS (see Xu et al. [14])Step  1. Construct a bin-packing instance as follows. There are n items a
1
,
a
2
,
…
,
a
n; the size of item a
i is p
i, and the capacity of each bin is T. Using the FFD algorithm, assume that we obtain k used bins B
1
,
B
2
,
…
,
B
k. Let bin B
i be denoted as (
a
1
(
i
)
,
a
2
(
i
)
,
…
,
a
k
i
(
i
)
), where k
i is the number of items in B
i and a
j
(
i
) is the jth item assigned to B
i.Step  2. For i
=
1,2
,
…
,
k, let 𝒥
i
=
(
J
1
(
i
)
,
J
2
(
i
)
,
…
,
J
k
i
(
i
)
,
Ø
i
,
M
(
i
)
), where J
j
(
i
) is the job with a processing time of p
j
(
i
) corresponding to item a
j
(
i
), Ø
i is a dummy job with the processing time of T
-
∑
j
=
1
k
i
‍
p
j
(
i
), and M
(
i
) denotes a maintenance activity with the length of a
+
level
(
B
i
)
b.Step  3. Let 𝒥
i be viewed as a single job with the processing time of T
+
a
+
level
(
B
i
)
b. Assign 𝒥
1
,
𝒥
2
,
…
,
𝒥
k
-
1 to the machine by the LS algorithm. Assign 𝒥
k to the machine.Although the FFD-LS algorithm is originally proposed forP
(
b
≤
1
), it can also be applied to P
(
b
>
1
) without any modification. However, as can be seen in the next section, there exists an example showing that the worst-case bound of the FFD-LS algorithm can be arbitrarily large for P
(
b
>
1
). As a result, we then focus our attention on studying its worst-case bound for P
(
b
>
1
) in detail. Specifically, we think of each interval between two consecutive maintenance activities as a batch with a capacity T and show that its worst-case bound is 2 for P
(
b
>
1
) if the number of nonempty batches in the FFD-LS schedule is not 2. In order to avoid the arbitrarily large worst-case bound, in Section 3, we modify the FFD-LS algorithm and get a new approximation algorithm named FFD-LS2I algorithm with a worst-case bound of 2 for P
(
b
>
1
) by adding a step to the FFD-LS algorithm. In Section 4, we study the nonapproximability of the problem and show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem P
(
b
>
0
), which implies that the FFD-LS2I algorithm is the best possible algorithm for P
(
b
>
1
) and that the FFD-LS is the best possible algorithm for P
(
b
≤
1
) both from the worst-case bound point of view. Finally, in Section 5, we give an answer to another open problem proposed in Xu et al. [14].


## 2. Worst-Case Bound of the FFD-LS Algorithm forP
(
b
>
1
)

Example 1.
Consider the scheduling problemP
(
b
>
1
) with the following instance: n
=
2, T
=
b, p
1
=
b, and p
2
=
1. It is easy to see that the FFD-LS algorithm assigns job J
1 to the first batch and J
2 to the second batch and that the corresponding makespan is C
max
⁡
FFD-LS
=
b
+
a
+
b
2
+
1
=
b
2
+
b
+
a
+
1. Note that the optimal schedule assigns job J
2 to the first batch and J
1 to the second batch and that the optimal makespan is C
max
⁡
*
=
3
b
+
a. Clearly, C
max
⁡
FFD-LS
/
C
max
⁡
*
→
∞ as b
→
∞. In other words, the worst-case bound of the FFD-LS algorithm can be arbitrarily large.
Now, letΛ
=
∑
i
=
1
n
‍
p
i. Let S
* be an optimal schedule with k
* nonempty batches ℬ
1
*
,
…
,
ℬ
k
*
* which are indexed according to the processing order. Recall that we assume that there are totally k bins being used by the FFD algorithm in the first step of the FFD-LS algorithm. So, for consistency, we may assume that there are totally k nonempty batches in the FFD-LS schedule. For convenience, in what follows, these batches are denoted by ℬ
1
,
…
,
ℬ
k which are also indexed according to the processing order. Let the total processing times of the jobs in batch ℬ
i
* and batch ℬ
i be denoted by λ
i
* and λ
i, respectively. It is easy to see that the makespan of the optimal schedule is
(1)
C
max
⁡
*
=
(
k
*
-
1
)
(
T
+
a
)
+
b
(
Λ
-
λ
k
*
*
)
+
λ
k
*
*
and that the makespan of the FFD-LS schedule is
(2)
C
max
⁡
FFD-LS
=
(
k
-
1
)
(
T
+
a
)
+
b
(
Λ
-
λ
k
)
+
λ
k
.
In what follows, we shall study the worst-case bound of the FFD-LS algorithm forP
(
b
>
1
) in detail, which can help us develop a more sophisticated approximation algorithm. Before the study of the worst-case bound, we first present some lemmas.Lemma 2.
For the problemP
(
b
>
1
), the total processing time of the jobs in any two nonempty batches is strictly larger than T in S
*.Proof (by contradiction).
It suffices to show thatλ
i
*
+
λ
j
*
>
T for 1
≤
i
<
j
≤
k
*.
If there exist two batches, sayℬ
i
* and ℬ
j
*, such that λ
i
*
+
λ
j
*
≤
T, where 1
≤
i
<
j
≤
k
*, consider the following two cases.
Case  1
(
1
≤
i
<
j
<
k
*
). Note that λ
i
*
+
λ
j
*
≤
T. Now, reschedule all the jobs of ℬ
i
* into ℬ
j
* and delete ℬ
i
* with the corresponding maintenance activity. Let the new schedule be denoted by S
′. It is easy to see that S
′ is a feasible schedule with a makespan of
(3)
C
max
⁡
′
=
(
k
*
-
2
)
(
T
+
a
)
+
b
(
Λ
-
λ
k
*
*
)
+
λ
k
*
*
.
Comparing (1) with (3), we have C
max
⁡
′
<
C
max
⁡
*, which contradicts the optimality of S
*.
Case  2  (
1
≤
i
<
k
*
and
j
=
k
*
). Similar to Case 1, reschedule all the jobs of ℬ
i
* into ℬ
j
* and delete ℬ
i
* with its corresponding maintenance. Let the new schedule be denoted by S
′′. It is easy to see that S
′′ is a feasible schedule with a makespan of
(4)
C
max
⁡
′′
=
(
k
*
-
2
)
(
T
+
a
)
+
b
(
Λ
-
λ
k
*
*
-
λ
i
*
)
+
(
λ
k
*
*
+
λ
i
*
)
.
Recall that b
>
1. Comparing (1) with (4), we have C
max
⁡
′′
<
C
max
⁡
*, which again contradicts the optimality of S
*.
This completes the proof.Lemma 3.
For problemP
(
b
>
1
), let S
′ be a feasible schedule with two nonempty batches and let S
′′ be a feasible schedule with three nonempty batches. Let the total processing times of the jobs in the first batch of S
′ and in the second batch of S
′ be denoted by λ
1
′ and λ
2
′, respectively. Let the total processing times of the jobs in the first batch of S
′′, in the second batch of S
′′, and in the third batch of S
′′ be denoted by λ
1
′′, λ
2
′′ and λ
3
′′, respectively. If λ
1
′
+
λ
2
′
>
T and λ
i
′′
+
λ
j
′′
>
T for 1
≤
i
<
j
≤
3, then one has C
max
⁡
′
<
C
max
⁡
′′, where C
max
⁡
′ and C
max
⁡
′′ are the makespans of S
′ and S
′′, respectively.Proof.
It is easy to see that(5)
C
max
⁡
′
=
T
+
a
+
b
λ
1
′
+
λ
2
′
,
(6)
C
max
⁡
′′
=
2
(
T
+
a
)
+
b
(
λ
1
′′
+
λ
2
′′
)
+
λ
3
′′
.
Combining (5) with (6), we have
(7)
C
max
⁡
′
=
C
max
⁡
′′
+
(
λ
2
′
-
T
)
-
a
+
b
(
λ
1
′
-
λ
1
′′
-
λ
2
′′
)
-
λ
3
′′
.
Recall that λ
1
′′
+
λ
2
′′
>
T. So we have
(8)
C
max
⁡
′
<
C
max
⁡
′′
+
(
λ
2
′
-
T
)
-
a
+
b
(
λ
1
′
-
T
)
-
λ
3
′′
.
Note that λ
1
′
≤
T and λ
2
′
≤
T. So we have
(9)
C
max
⁡
′
<
C
max
⁡
′′
.
This completes the proof.Lemma 4.
k
≤
3
k
*
/
2.Proof.
View each interval between two consecutive maintenance activities as a bin with capacityT and the jobs J
i as items a
i with a size of p
i. Let k
′ be the minimum number of nonempty bins that is needed to pack all the n items. It is well known that k
≤
3
k
′
/
2 (see Simchi-Levi [18]). Note that k
′
≤
k
*. So we have k
≤
3
k
*
/
2. This completes the proof.Lemma 5.
For the problemP
(
b
>
1
), if T
<
Λ
≤
2
T, then 2
≤
k
*
≤
3 and 2
≤
k
≤
3.Proof.
ByT
<
Λ, it is easy to see that 2
≤
k
* and 2
≤
k since that one batch is clearly not sufficient in any feasible schedule. On the other hand, by Lemma 2, we have k
*
≤
3 for otherwise we have Λ
>
2
T, a contradiction. Note that the total processing time of the jobs in any two batches in the FFD-LS schedule is strictly larger than T. We thus have k
≤
3. To sum up, we have 2
≤
k
*
≤
3 and 2
≤
k
≤
3. This completes the proof.Now, we are ready to evaluate the worst-case bound of the FFD-LS algorithm in detail.Theorem 6.
For the problemP
(
b
>
1
), the worst-case bound of the FFD-LS algorithm is not greater than 2 if Λ
>
2
T.Proof.
By (1), we have
(10)
k
*
=
1
+
C
max
⁡
*
+
(
b
-
1
)
λ
k
*
*
-
b
Λ
T
+
a
.
Note that k
≤
3
k
*
/
2 (see Lemma 4). So we have
(11)
k
≤
3
2
(
1
+
C
max
⁡
*
+
(
b
-
1
)
λ
k
*
*
-
b
Λ
T
+
a
)
.
Substituting (11) into (2), we have
(12)
C
max
⁡
FFD-LS
≤
3
2
C
max
⁡
*
+
1
2
(
T
+
a
)
+
3
2
(
b
-
1
)
λ
k
*
*
-
(
b
-
1
)
λ
k
-
b
2
Λ
.
Now, consider the following two cases.
Case  1 (
Λ
≥
3
T
). In this case, we have
(13)
b
2
Λ
≥
b
2
3
T
>
3
2
(
b
-
1
)
T
.
Substituting (13) into (12), we have
(14)
C
max
⁡
FFD-LS
≤
3
2
C
max
⁡
*
+
1
2
(
T
+
a
)
+
3
2
(
b
-
1
)
(
λ
k
*
*
-
T
)
-
(
b
-
1
)
λ
k
.
Note that λ
k
*
*
≤
T, -
(
b
-
1
)
λ
k
≤
0, and T
+
a
<
C
max
⁡
*. Combining these three inequalities with (14), we have C
max
⁡
FFD-LS
<
2
C
max
⁡
* and we are done.
Case  2 (
2
T
<
Λ
<
3
T
). In this case, it is easy to see that k
*
≥
3 because two batches are obviously not sufficient in any optimal solution. Note that the total processing time of the jobs in any two nonempty batches is strictly larger than T in the FFD-LS schedule. We thus have k
≤
5 for otherwise the total processing times of the jobs will be strictly larger than 3
T, which violates the assumption of this case.
Combiningk
*
≥
3 with (1), we have
(15)
C
max
⁡
*
≥
2
(
T
+
a
)
+
b
(
Λ
-
λ
k
*
*
)
+
λ
k
*
*
.
By simple algebra, we have
(16)
C
max
⁡
*
≥
2
(
T
+
a
)
+
b
Λ
-
(
b
-
1
)
λ
k
*
*
.
Note that 0
<
λ
k
*
*
≤
T. So we have
(17)
C
max
⁡
*
≥
2
(
T
+
a
)
+
b
Λ
-
(
b
-
1
)
T
.
Similarly, combiningk
≤
5, 0
<
λ
k
≤
T, and (2), we have
(18)
C
max
⁡
FFD-LS
<
4
(
T
+
a
)
+
b
Λ
.
By simple algebra, (18) becomes
(19)
C
max
⁡
FFD-LS
<
2
(
2
(
T
+
a
)
+
b
Λ
-
(
b
-
1
)
T
)
-
b
(
Λ
-
2
T
)
-
2
T
.
Substituting (17) into (19), we have
(20)
C
max
⁡
FFD-LS
<
2
C
max
⁡
*
-
b
(
Λ
-
2
T
)
-
2
T
.
Recall that 2
T
<
Λ; we thus have C
max
⁡
FFD-LS
<
2
C
max
⁡
*.
This completes the proof.Theorem 7.
For the problemP
(
b
>
1
), the worst-case bound of the FFD-LS algorithm is not greater than 2 if T
<
Λ
≤
2
T and k
=
3.Proof.
Substitutingk
=
3 into (2), we have
(21)
C
max
⁡
FFD-LS
=
2
(
T
+
a
)
+
b
Λ
-
(
b
-
1
)
λ
3
.
By Lemma5, we have 2
≤
k
*
≤
3. Now, consider the following two cases.
Case  1 (
k
*
=
2
). Substituting k
*
=
2 into (1), we have
(22)
C
max
⁡
*
≥
T
+
a
+
b
(
Λ
-
λ
2
*
)
+
λ
2
*
.
Combining (22) with (21), we have
(23)
C
max
⁡
FFD-LS
=
2
C
max
⁡
*
-
(
b
-
1
)
(
Λ
+
λ
3
-
2
λ
2
*
)
-
Λ
.
Note that Λ
=
λ
1
+
λ
2
+
λ
3. Combining this with (23), we have
(24)
C
max
⁡
FFD-LS
≤
2
C
max
⁡
*
-
(
b
-
1
)
(
(
λ
1
+
λ
3
-
λ
2
*
)
+
(
λ
2
+
λ
3
-
λ
2
*
)
)
-
Λ
.
Note that λ
1
+
λ
3
>
T
≥
λ
2
* and that λ
2
+
λ
3
>
T
≥
λ
2
*. So, by (24), we have C
max
⁡
FFD-LS
≤
2
C
max
⁡
*.
Case  2 (
k
*
=
3
). Substituting k
*
=
3 into (1), we have
(25)
C
max
⁡
*
=
T
+
a
+
b
(
Λ
-
λ
3
*
)
+
λ
3
*
.
Combining (25) with (21), we have
(26)
C
max
⁡
FFD-LS
=
C
max
⁡
*
+
(
b
-
1
)
(
λ
3
*
-
λ
3
)
.
Note that λ
3
*
-
λ
3
≤
T and b
-
1
≤
b. So we have
(27)
C
max
⁡
FFD-LS
≤
C
max
⁡
*
+
b
T
.
Note thatΛ
-
λ
3
*
=
λ
1
*
+
λ
2
*
>
T. Combining this with (25), we have C
max
⁡
*
>
b
T. Substituting this into (27), we have C
max
⁡
FFD-LS
<
2
C
max
⁡
*.
This completes the proof.Theorem 8.
For the problemP
(
b
>
1
), the worst-case bound of the FFD-LS algorithm is not greater than 2 if k
≠
2.Proof.
Consider the following three cases.
Case  1 (
k
=
1
). It is trivially obvious that in this case we have C
max
⁡
FFD-LS
=
C
max
⁡
*, and we are done.
Case  2 (
k
=
3
). Clearly, in this case, we have Λ
>
T. Now, if T
<
Λ
≤
2
T, then, by Theorem 7, we know that the worst-case bound of the FFD-LS algorithm is not greater than 2, and we are done. If 2
T
<
Λ, then by Theorem 6, we know that the worst-case bound of the FFD-LS algorithm is not greater than 2 either, and we are also done. This complete the proof of Case 2.
Case  3 (
k
≥
4
). Clearly, in this case, we have Λ
>
2
T. Again, by Theorem 6, we know that the worst-case bound of the FFD-LS algorithm is not greater than 2, and we are done.
This completes the proof.


## 3. A Modified Approximation Algorithm and Its Worst-Case Bound forP
(
b
>
1
)

We know from Example1 and Theorem 8 that the worst-case bound of the FFD-LS algorithm can be arbitrarily large if k
=
2 and is 2 otherwise. Following the notation in Xu et al. [14], 𝒥
i is the hybrid job which consists of the ith nonempty bin obtained by the FFD algorithm and the corresponding maintenance activity. Note that 𝒥
1 is scheduled before 𝒥
2 in the FFD-LS schedule. So we have λ
1
=
level
(
B
1
) and λ
2
=
level
(
B
2
). In order to avoid the arbitrarily large worst-case bound, as we observe, we only need to add the following step after the FFD-LS algorithm.Step  4. If k
=
2 and level
(
B
2
)
<
level
(
B
1
), interchange 𝒥
1 with 𝒥
2.Let us call this modified algorithm FFD-LS2I, which applies algorithm FFD-LS first and then applies Step 4. Clearly, the computational complexity of the FFD-LS2I isO
(
n
2
). Let the FFD-LS2I schedule be denoted by S
⋆ and let the total processing times of the jobs in the ith batch B
i
⋆ of S
⋆ be denoted by λ
i
⋆. It is easy to see that the number of the nonempty batches in S
⋆ is also k because the fourth step of the FFD-LS2I algorithm does not change the number of batches.In order to show that the worst-case bound of the FFD-LS2I algorithm is 2, by the structure of the FFD-LS2I algorithm and Theorem8, we only need to consider the case k
=
2.Theorem 9.
For the problemP
(
b
>
1
), the worst-case bound of the FFD-LS2I algorithm is not greater than 2 if k
=
2.Proof.
Clearly,k
=
2 implies T
<
Λ
≤
2
T. Hence, by Lemma 4, we have 2
≤
k
*
≤
3. Note that the FFD-LS2I schedule has two nonempty batches and that Lemma 3 indicates that the makespan of a feasible schedule with two batches is always less than that of a feasible schedule with three batches. So we have k
*
=
2.
Substitutingk
*
=
2 into (1), we have
(28)
C
max
⁡
*
=
T
+
a
+
b
(
Λ
-
λ
2
*
)
+
λ
2
*
.
Similar to (2), the makespan of the FFD-LS2I schedule is
(29)
C
max
⁡
FFD-LS
2
I
=
T
+
a
+
b
(
Λ
-
λ
2
⋆
)
+
λ
2
⋆
.
Combining these two equations, we have
(30)
C
max
⁡
FFD-LS
2
I
=
2
C
max
⁡
*
-
T
-
a
-
b
(
Λ
+
λ
2
⋆
-
2
λ
2
*
)
+
(
λ
2
⋆
-
2
λ
2
*
)
.
Note thatλ
1
*
+
λ
2
*
=
Λ
>
T. We claim that λ
2
*
>
T
/
2 for otherwise we have λ
1
*
>
T
/
2 and thus we can get a schedule with a smaller makespan by interchanging all the jobs in the first batch of S
* with those in the second batch of S
*, which clearly violates the optimality of S
*. Combining this with λ
2
⋆
≤
T, we have
(31)
λ
2
⋆
-
2
λ
2
*
≤
λ
2
⋆
-
T
≤
0
.
Case  1 (
4
T
/
3
≤
Λ
≤
2
T
). Note that λ
1
⋆
≤
λ
2
⋆ and that λ
1
⋆
+
λ
2
⋆
=
Λ. So we have λ
2
⋆
≥
2
T
/
3. And thus Λ
+
λ
2
⋆
-
2
λ
2
*
≥
2
T
-
2
λ
2
*. Combining this with λ
2
*
≤
T, we have
(32)
Λ
+
λ
2
⋆
-
2
λ
2
*
≥
0
.
Substituting (31) and (32) into (30), we have
(33)
C
max
⁡
FFD-LS
2
I
≤
2
C
max
⁡
*
-
T
-
a
,
which implies that C
max
⁡
FFD-LS
2
I
<
2
C
max
⁡
*.
Case  2 (
T
<
Λ
<
4
T
/
3
). Consider the schedule S
⋄ which schedules the hybrid job 𝒥
2 first and then the hybrid job 𝒥
1. Let the total processing time of the jobs in the first batch of S
⋄ and in the second batch of S
⋄ be denoted by λ
1
⋄ and λ
2
⋄, respectively. Clearly, λ
1
⋄
+
λ
2
⋄
=
Λ. Note that Step 4 schedules the hybrid job with the highest level last. So we have λ
2
⋄
≤
λ
2
⋆.
Let the makespan of the scheduleS
⋄ be denoted by C
max
⁡
⋄. It is easy to see that
(34)
C
max
⁡
⋄
=
T
+
a
+
b
(
Λ
-
λ
2
⋄
)
+
λ
2
⋄
.
Recall that λ
2
⋄
≤
λ
2
⋆ and b
>
1. Comparing (29) with (34), we have
(35)
C
max
⁡
FFD-LS
2
I
≤
C
max
⁡
⋄
.
Now, consider two subcases.
Subcase 2.1. There is only one job, say job J
u, in the first batch of the schedule S
⋄. Without loss of generality, we assume that the jobs in 𝒥
1 are ordered in nondecreasing order of their processing times; that is, p
1
(
1
)
≥
p
2
(
1
)
≥
⋯
≥
p
k
1
(
1
). Suppose that p
s
(
1
)
≥
p
u
>
p
s
+
1
(
1
). Clearly, we have
(36)
∑
i
=
1
s
‍
p
i
(
1
)
+
p
u
>
T
,
(37)
λ
2
⋄
=
Λ
-
p
u
.
Now, consider the position of jobJ
u in the optimal schedule S
*. If J
u is in the first batch of S
*, then we have λ
2
*
≤
Λ
-
p
u. Combine this with (37), we have λ
2
⋄
≥
λ
2
*. If J
u is in the second batch of S
*, then at least one job, say J
v
(
1
) with 1
≤
v
≤
s, must be assigned to the first batch of S
*. To see this is the case, suppose all the jobs J
1
(
1
)
,
…
,
J
s
(
1
) are assigned to the second batch of S
*. We thus have λ
2
*
≥
∑
i
=
1
s
‍
p
i
(
1
)
+
p
u. Combining this with (36), we have λ
2
*
>
T, which implies that S
* is infeasible, clearly, a contradiction. Now, suppose J
v
(
1
) is in the first batch of S
*, where 1
≤
v
≤
s. Note that p
v
(
1
)
≥
p
u. So we have λ
2
*
≤
Λ
-
p
v
(
1
)
≤
Λ
-
p
u. Combining this with (37), we have λ
2
⋄
≥
λ
2
*. So, in either case, we have λ
2
⋄
≥
λ
2
*. Combining this with (28) and (34), we have C
max
⁡
⋄
≤
C
max
⁡
*. Combining this with (35), we have C
max
⁡
FFD-LS
2
I
≤
C
max
⁡
*, which implies that C
max
⁡
FFD-LS
2
I
=
C
max
⁡
* by the optimality of S
*.
Subcase 2.2. There are at least two jobs in the first batch of the schedule S
⋄. Let J
l be the job with the smallest processing time in the first batch of the schedule S
⋄. Clearly, we have
(38)
λ
1
⋄
≥
2
p
l
,
λ
2
⋄
+
p
l
>
T
≥
λ
2
*
.
Combining (28) with (34), we have
(39)
C
max
⁡
⋄
=
2
C
max
⁡
*
-
T
-
a
-
b
(
Λ
+
λ
2
⋄
-
2
λ
2
*
)
+
(
λ
2
⋄
-
2
λ
2
*
)
.
By (38), we know that
(40)
Λ
+
λ
2
⋄
-
2
λ
2
*
≥
Λ
-
λ
2
⋄
-
2
p
l
.
Recall that Λ
-
λ
2
⋄
=
λ
1
⋄ and that λ
1
⋄
≥
2
p
l. So we have
(41)
Λ
+
λ
2
⋄
-
2
λ
2
*
≥
0
.
By a similar reasoning as in the arguments of deducing (31), we have
(42)
λ
2
⋄
-
2
λ
2
*
≤
λ
2
⋄
-
T
≤
0
.
Substituting (41) and (42) into (39), we have
(43)
C
max
⁡
⋄
≤
2
C
max
⁡
*
-
T
-
a
,
which implies that C
max
⁡
⋄
≤
2
C
max
⁡
*. Combining this with (35), we have C
max
⁡
FFD-LS
2
I
≤
2
C
max
⁡
*.
This completes the proof.Now, we are ready to present the worst-case bound of the FFD-LS2I algorithm.Theorem 10.
For the problemP
(
b
>
1
), the worst-case bound of the FFD-LS2I algorithm is 2 and the bound is tight.Proof.
Ifk
≠
2, it is clear that the FFD-LS2I algorithm is reduced to the FFD-LS algorithm, and thus, by Theorem 8, we know that the worst-case bound of the FFD-LS2I algorithm is not greater than 2. If k
=
2, then, by Theorem 9, we know that the worst-case bound of the FFD-LS2I algorithm is not greater than 2 either. Hence, we have completed the proof that the worst-case bound of the FFD-LS2I algorithm is not greater than 2.
To show that this bound cannot be smaller than 2, consider the following instance. LetT
=
12, p
1
=
8
-
2
/
b, p
2
=
p
3
=
4
+
1
/
b, p
4
=
4, p
5
=
4
-
2
/
b, p
6
=
2
/
b, and a
=
1. It is easy to see that C
max
⁡
FFD-LS
2
I
=
24
+
24
b
+
2
/
b while C
max
⁡
*
=
25
+
12
b. It follows that C
max
⁡
FFD-LS
2
I
/
C
max
⁡
*
=
(
24
+
24
b
)
/
(
25
+
12
b
)
→
2 as b
→
∞.
This completes the proof.


## 4. Nonapproximability

In this section, we shall show that it is impossible to have a polynomial time approximation algorithm with a worst-case bound of less than 2 for the scheduling problemP
(
b
≥
0
) unless P
= NP, which implies that the proposed algorithm FFD-LS2I is the best possible approximation algorithm for P
(
b
>
1
) from the worst-case bound point of view and that the FFD-LS algorithm proposed by Xu et al. [14] is the best possible approximation algorithm for P
(
b
≤
1
) from the same point of view.Note that the caseb
=
0 has been considered in Ji et al. [3] (see the following lemma, that is, Lemma 11), so we only need to consider the case b
>
0, that is, the problem P
(
b
>
0
).Lemma 11 (Ji et al. [3]).
There is no polynomial time approximation algorithm with a worst-case bound less than 2 for the scheduling problemP
(
b
=
0
) unless P
= NP.The underlying idea of our approach for problemP
(
b
>
0
) is by contradiction. Specifically, we shall show that if there exists an approximation algorithm with a worst-case bound of 2
-
ϵ with 0
<
ϵ
<
1 for P
(
b
>
0
) then it can be used to establish a polynomial time algorithm for the well-known NP-complete problem Partition. This clearly leads to a contradiction if P
≠NP. Hence, such an approximation algorithm for the scheduling problem P
(
b
>
0
) cannot exist unless P
= NP.Partition Problem (see, e.g., Garey and Johnson [19]). Given n positive integers h
1
,
h
2
,
…
,
h
n with ∑
i
=
1
n
‍
h
i
=
2
H, does there exist a set X
⊆
{
1
,
2
,
…
,
n
} with ∑
i
∈
X
‍
h
i
=
H?For any fixed positive numberϵ
<
1 and an instance I of the Partition problem, we construct an instance II of the scheduling problem P
(
b
>
0
) as follows. There are n jobs J
1
,
J
2
,
…
,
J
n and the processing time of job J
i is p
i
=
h
i. Let T
=
H and a
=
(
2
T
+
b
T
)
(
1
-
ϵ
)
/
ϵ
+
1. It is clear that this construction can be performed in polynomial time.Theorem 12.
If there exists a polynomial time approximation algorithmA
ϵ with a worst-case bound of 2
-
ϵ for some positive number ϵ
<
1 for the scheduling problem P
(
b
>
0
), then there exists a polynomial time algorithm for the Partition problem.Proof.
Given any instance I of the Partition problem, we construct the corresponding instance II of the scheduling problemP
(
b
>
0
) in polynomial time as stated above. Let C
max
⁡
A
ϵ and C
max
⁡
* be the makespan of the schedule produced by the approximation algorithm A
ϵ and the makespan of an optimal schedule S
* for the instance II of P
(
b
>
0
), respectively. We shall show that the instance I of the Partition problem can be answered by merely comparing the values of C
max
⁡
A
ϵ and 2
(
T
+
a
)
+
b
T.
To see that this is the case, let us apply algorithmA
ϵ to instance II. We claim that if C
max
⁡
A
ϵ
≤
2
(
T
+
a
)
+
b
T then there exists a solution to instance I of the Partition problem and, otherwise, there does not exist a solution to instance I. In what follows, we shall show that this claim is correct.
Case  1
(
C
max
⁡
A
ϵ
≤
2
(
T
+
a
)
+
b
T
). Clearly, we have C
max
⁡
*
≤
2
(
T
+
a
)
+
b
T because C
max
⁡
*
≤
C
max
⁡
A
ϵ. Let k
* be the total number of batches used in S
*. Note that T
=
H and Λ
=
∑
i
=
1
n
‍
p
i
=
2
H, so we have k
*
≥
2.
Letλ
i
* be the total processing time of the jobs in the ith batch of S
*. If k
*
≥
3, then, by (1), we have C
max
⁡
*
≥
2
(
T
+
a
)
+
b
(
Λ
-
λ
k
*
*
)
+
λ
k
*
*. Note that Λ
-
λ
k
*
*
=
∑
i
=
1
k
*
-
1
‍
λ
i
*
≥
λ
1
*
+
λ
2
*
>
T. So we have C
max
⁡
*
>
2
(
T
+
a
)
+
b
T, which contradicts the inequality C
max
⁡
*
≤
2
(
T
+
a
)
+
b
T. This implies that k
*
=
2. That is, the optimal schedule S
* has two nonempty batches. Now, let X be the set of indices of the jobs scheduled in the first batch of the optimal schedules. Clearly we have ∑
i
∈
X
‍
p
i
=
T. Recall that T
=
H and p
i
=
h
i for i
=
1,2
,
…
,
n. So we have ∑
i
∈
X
‍
h
i
=
H, which implies that there exists a solution to the instance I of the Partition problem.
Case  2 (
C
max
⁡
A
ϵ
>
2
(
T
+
a
)
+
b
T
). Recall that the worst-case bound of the algorithm A
ϵ is 2
-
ϵ. So we have
(44)
C
max
⁡
*
≥
C
A
ϵ
2
-
ϵ
>
2
(
T
+
a
)
+
b
T
2
-
ϵ
.
Recall that a
=
(
2
T
+
b
T
)
(
1
-
ϵ
)
/
ϵ
+
1. So we have
(45)
ϵ
=
2
T
+
b
T
2
T
+
b
T
+
a
-
1
.
Substituting (45) into (44), we have
(46)
C
max
⁡
*
>
2
(
T
+
a
)
+
b
T
2
-
(
2
T
+
b
T
)
/
(
2
T
+
b
T
+
a
-
1
)
=
2
T
+
b
T
+
a
+
2
T
+
b
T
2
T
+
b
T
+
2
a
-
2
≥
2
T
+
b
T
+
a
.
If there exists a solution, namely, setX, to the instance I of the Partition problem, let the jobs whose indices belong to the set X be scheduled into the first batch and the remaining jobs the second batch; we then obtain a schedule with a makespan of 2
T
+
a
+
b
T, which clearly contradicts (46). Hence, there does not exist a solution to the instance I of the Partition problem.
This completes the proof.By Theorem10 and the fact that no NP-complete problem can be solved by a polynomial time algorithm unless P
= NP, we have the following result.Theorem 13.
There is no polynomial time approximation algorithm with a worst-case bound less than 2 for the scheduling problemP
(
b
>
0
) unless P
=
N
P.Combining Lemma11 and Theorem 13, we have the following result.Theorem 14.
There is no polynomial time approximation algorithm with a worst-case bound less than 2 for the scheduling problemP
(
b
≥
0
) unless P
=
N
P.Recall that we have showed in Theorem10 that the worst-case bound of the FFD-LS2I algorithm is 2 for P
(
b
>
1
). Combining this with Theorem 14, we have the following result.Theorem 15.
The FFD-LS2I algorithm is the best possible polynomial time approximation algorithm forP
(
b
>
1
) unless P
=
N
P from the worst-case bound point of view.Recall that Xu et al. [14] have showed that the worst-case bound of the FFD-LS algorithm is 2 for P
(
b
≤
1
). Combining this with Theorem 14, we have the following result.Theorem 16.
The FFD-LS algorithm is the best possible polynomial time approximation algorithm forP
(
b
≤
1
) unless P
=
N
P from the worst-case bound point of view.


## 5. An Answer to Another Open Problem

Viewing each batch as a bin, in Remark 3 of Section 4 of the paper of Xu et al. [14], Xu et al. claim that “it seems that it is not necessary for an optimal schedule of 1, M
S
[
T
,
T
], T
M
(
t
)
=
a
+
b
t, b
>
2
+
a
/
T
∥
C
max
⁡ to have the minimum number of bins. Whether this is true may be an interesting problem for further study.” The following example gives an answer to this open problem.Example 17.
Consider the following instance for the scheduling problem under consideration:T
=
20, a
=
1, b
=
12, n
=
8, p
1
=
p
2
=
p
3
=
p
4
=
13, and p
5
=
p
6
=
p
7
=
p
8
=
5. It is easy to see that the minimum number of bins for this instance is 4; see, for example, that job J
i and job J
i
+
4 are packed into bin B
i for i
=
1
,
…
,
4. The corresponding makespan is 729. However, if we assign job J
i to the ith bin for i
=
1
,
…
,
4 and assign the remaining jobs to the fifth bin, we get an optimal schedule with a makespan of 728. Clearly, this implies that it is not necessary for an optimal schedule of the considered scheduling problem to have the minimum number of bins.


## 6. Conclusion

In this paper, we revisited the single machine scheduling problem considered in Xu et al. [14]; we provided an approximation named FFD-LS2I with a worst-case bound of 2 for the case b
>
1. We showed that the FFD-LS2I algorithm is the best possible algorithm for the case b
>
1 and that the FFD-LS algorithm is the best possible algorithm for the case b
≤
1 both from the worst-case bound point of view. We also give an answer to another open problem proposed in Xu et al. [14].Future research may focus on the design of approximation algorithms with a lower time complexity while maintaining the worst-case bound of 2. The other maintenance duration functions such as convex function and concave function are also worth considering.



---

*Source: 547573-2014-02-13.xml*