# Parallel-Machine Scheduling with Time-Dependent and Machine Availability Constraints

Authors: Cuixia Miao; Juan Zou
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We consider the parallel-machine scheduling problem in which the machines have availability constraints and the processing time of each job is simple linear increasing function of its starting times. For the makespan minimization problem, which is NP-hard in the strong sense, we discuss the Longest Deteriorating Rate algorithm and List Scheduling algorithm; we also provide a lower bound of any optimal schedule. For the total completion time minimization problem, we analyze the strong NP-hardness, and we present a dynamic programming algorithm and a fully polynomial time approximation scheme for the two-machine problem. Furthermore, we extended the dynamic programming algorithm to the total weighted completion time minimization problem.


---

## Body

## 1. Introduction

Consider the following scheduling problem with deteriorating job and machine availability constrains. There aren independent deteriorating jobs J
=
{
J
1
,
…
,
J
n
} to be processed on m identical parallel machines. The actual processing time of job J
j  (
j
=
1
,
…
,
n
) is p
j
=
α
j
t, where α
j (>0) and t are the deteriorating rate and the starting time of job J
j, respectively. Each job J
j has a weight w
j. All jobs are released at time t
0 (>0). The case with t
0
=
0 is not considered because the job would have its processing rimes equal to zero if t
0
=
0. We assume that the jobs are nonresumable in our problems. Machine M
i  (
1
≤
i
≤
m
) is not continuously available and unavailable during the period I
i
=
[
H
1
(
i
)
,
H
2
(
i
)
). In addition, we assume that t
0
(
1
+
α
max
⁡
)
<
H
1
i
<
H
2
i and H
1
(
i
)
<
t
0
∏
j
=
1
n
‍
(
1
+
α
j
), where α
max
⁡
=
max
⁡
j
=
1
,
…
,
n
{
α
j
}. Otherwise, all the jobs can be finished before the nonavailable period and the problem becomes trivial. Without loss of generality, we assume that all parameters are integral unless stated otherwise.Our objective is to minimize the makespan and the total (weighted) completion time. Following Gawiejnowicz [1], we denote our problems as P
m
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡ and P
m
n
r
-
a
,
p
j
=
α
j
t
∑
‍
(
w
j
)
C
j, where n
r
-
a means nonresumable.The model described above falls into the categories of the scheduling with deteriorating job and the machine scheduling with availability constraints. The scheduling with deteriorating job was first considered by J. N. D. Gupta and S. K. Gupta [2] and Browne and Yechiali [3]. Cheng et al. [4] gave a survey and the monograph by Gawiejnowicz [1] presented this scheduling from different perspectives and covers results and examples. Graves and Lee [5] pointed out that machine scheduling with an availability constraint is very important and is still relatively unexplored. They studied this problem whose maintenance needs to be performed within a fixed period. Lee [6] presented extensive study of single and parallel machine scheduling problems with an availability constraint, with respect to various performance measures and two cases are considered: resumable and nonresumable. A job is said to be resumable if it cannot be finished before the nonavailable interval of a machine and can continue after the machine is available again. On the other hand, a job is said to be nonresumable if it has to restart rather than continue. Ma et al. [7] gave a survey of this scheduling.In this paper, we consider the deteriorating job scheduling with machine availability constraints onm identical parallel machines. The jobs are nonresumable and our objective is to minimize the makespan and the total (weighted) completion time.Relevant Previous Work. Wu and Lee [8] initiated the deteriorating job scheduling with machine availability constraints; they showed that minimizing the makespan of scheduling deteriorating jobs on a single machine with an availability constraint can be transformed into 0-1 integer programming. Ji et al. [9] gave some results for the linear deteriorating jobs with an availability constraint on a single machine. Gawiejnowicz and Kononov [10] considered the complexity and approximability of scheduling resumable proportionally deteriorating jobs. Fan et al. [11] considered the scheduling resumable deteriorating jobs on a single machine with nonavailability constraints. Li and Fan [12] addressed the nonresumable scheduling problem 1
n
r
-
a
,
p
j
=
α
j
t
∑
‍
w
j
C
j. The problems they considered are on the single machine. In this paper, we consider the parallel-machine scheduling problem with deteriorating jobs and machine availability constraints, and we show that the problems are strongly NP-hard and present some algorithms.


## 2. Minimizing the Makespan

In this section, we first show that problemP
m
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡ is NP-hard in the strong sense. Ji and Cheng [13] showed that problem P
m
p
j
=
α
j
t
C
max
⁡ is NP-hard in the strong sense when m is arbitrary. In their problem, all the machines are available all the time. Thus, our problem P
m
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡ is NP-hard in the strong sense when m is arbitrary.In the following, we discuss the Longest Deteriorating Rate (LDR for short) algorithm and List Scheduling (LS for short) algorithm and analyze a lower bound of any optimal schedule.


### 2.1. LDR and LS Algorithms

LS Algorithm. Given a sequence of jobs J
1
,
…
,
J
n, assign the jobs one by one according to the list. Each job is assigned to the machine where the job can be finished as early as possible.LDR Algorithm. Sort the jobs in the nonincreasing order of their deteriorating rates, and then assign the jobs by LS algorithm.C
max
⁡
LDR, C
max
⁡
LS, and C
max
⁡
∗ denote the makespan corresponding LDR, LS, and the optimal solution, respectively.Theorem 1.
C
max
⁡
L
D
R
/
C
max
⁡
∗ can be arbitrarily large even for the two-machine problem P
2
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡.Proof.
Consider a problem with the following instance:t
0
=
1, α
1
=
α
2
=
7, α
3
=
α
4
=
α
5
=
3, H
1
(
1
)
=
H
1
(
2
)
=
64, H
2
(
1
)
=
H
2
(
2
)
=
n, and m
=
2. In the optimal schedule with makespan C
max
⁡
∗
=
64, jobs J
1 and J
2 are scheduled before H
1
(
1
) on the first machine, and jobs J
3, J
4, and J
5 are scheduled before H
1
(
2
) on the second machine. However, C
max
⁡
LDR
=
4
n. As a consequence, C
max
⁡
LDR
/
C
max
⁡
∗
=
4
n
/
64
→
∞ when n
→
∞.Theorem 2.
Ifmin
⁡
i
=
1
,
…
,
m
{
H
1
(
i
)
}
≥
t
0
∏
j
=
1
n
‍
(
1
+
α
j
), then C
max
⁡
L
S
/
C
max
⁡
∗
≤
(
1
+
α
max
⁡
)
(
m
-
1
)
/
m and C
max
⁡
L
D
R
/
C
max
⁡
∗
≤
(
1
+
α
min
⁡
)
(
m
-
1
)
/
m, where α
max
⁡
=
max
⁡
j
=
1
,
…
,
n
{
α
j
} and α
min
⁡
=
min
⁡
j
=
1
,
…
,
n
{
α
j
}.The proof of this theorem is similar to the proofs of Theorems 1 and 3 in Liu et al. [14].


### 2.2. Lower Bound of Any Optimal Schedule

Without loss of generality, lett
0
=
1, H
1
=
max
⁡
i
=
1
,
…
,
m
{
H
1
(
i
)
}, and H
2
=
min
⁡
i
=
1
,
…
,
m
{
H
2
(
i
)
}.Theorem 3.
(1)
C
max
⁡
∗
≥
H
2
1
+
α
min
⁡
n
/
m
H
1
.Proof.
In any optimal schedule, letJ
S
i and J
S
i
B denote the set of jobs scheduled on machine M
i and before H
1
i on M
i  (
i
=
1
,
…
,
m
), respectively. Then, the set of jobs scheduled after H
2
i is J
S
i
/
J
S
i
B, and ∏
J
j
∈
J
S
i
B
‍
(
1
+
α
j
)
≤
H
1
i. We have the load of machine M
i denoted by L
i holding L
i
=
H
2
i
∏
J
j
∈
J
S
i
/
J
S
i
B
‍
(
1
+
α
j
)
≥
H
2
i
∏
J
j
∈
J
S
i
‍
(
1
+
α
j
)
/
H
1
i for i
=
1
,
…
,
m. Note that C
max
⁡
∗
=
max
⁡
i
=
1
,
…
,
m
{
L
i
}. Thus, C
max
⁡
∗
≥
∏
i
=
1
m
‍
L
i
m
≥
H
2
1
⋯
H
2
m
∏
j
=
1
n
‍
(
1
+
α
j
)
/
H
1
1
⋯
H
1
m
m
≥
H
2
(
1
+
α
min
⁡
)
n
/
m
/
H
1.


## 2.1. LDR and LS Algorithms

LS Algorithm. Given a sequence of jobs J
1
,
…
,
J
n, assign the jobs one by one according to the list. Each job is assigned to the machine where the job can be finished as early as possible.LDR Algorithm. Sort the jobs in the nonincreasing order of their deteriorating rates, and then assign the jobs by LS algorithm.C
max
⁡
LDR, C
max
⁡
LS, and C
max
⁡
∗ denote the makespan corresponding LDR, LS, and the optimal solution, respectively.Theorem 1.
C
max
⁡
L
D
R
/
C
max
⁡
∗ can be arbitrarily large even for the two-machine problem P
2
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡.Proof.
Consider a problem with the following instance:t
0
=
1, α
1
=
α
2
=
7, α
3
=
α
4
=
α
5
=
3, H
1
(
1
)
=
H
1
(
2
)
=
64, H
2
(
1
)
=
H
2
(
2
)
=
n, and m
=
2. In the optimal schedule with makespan C
max
⁡
∗
=
64, jobs J
1 and J
2 are scheduled before H
1
(
1
) on the first machine, and jobs J
3, J
4, and J
5 are scheduled before H
1
(
2
) on the second machine. However, C
max
⁡
LDR
=
4
n. As a consequence, C
max
⁡
LDR
/
C
max
⁡
∗
=
4
n
/
64
→
∞ when n
→
∞.Theorem 2.
Ifmin
⁡
i
=
1
,
…
,
m
{
H
1
(
i
)
}
≥
t
0
∏
j
=
1
n
‍
(
1
+
α
j
), then C
max
⁡
L
S
/
C
max
⁡
∗
≤
(
1
+
α
max
⁡
)
(
m
-
1
)
/
m and C
max
⁡
L
D
R
/
C
max
⁡
∗
≤
(
1
+
α
min
⁡
)
(
m
-
1
)
/
m, where α
max
⁡
=
max
⁡
j
=
1
,
…
,
n
{
α
j
} and α
min
⁡
=
min
⁡
j
=
1
,
…
,
n
{
α
j
}.The proof of this theorem is similar to the proofs of Theorems 1 and 3 in Liu et al. [14].


## 2.2. Lower Bound of Any Optimal Schedule

Without loss of generality, lett
0
=
1, H
1
=
max
⁡
i
=
1
,
…
,
m
{
H
1
(
i
)
}, and H
2
=
min
⁡
i
=
1
,
…
,
m
{
H
2
(
i
)
}.Theorem 3.
(1)
C
max
⁡
∗
≥
H
2
1
+
α
min
⁡
n
/
m
H
1
.Proof.
In any optimal schedule, letJ
S
i and J
S
i
B denote the set of jobs scheduled on machine M
i and before H
1
i on M
i  (
i
=
1
,
…
,
m
), respectively. Then, the set of jobs scheduled after H
2
i is J
S
i
/
J
S
i
B, and ∏
J
j
∈
J
S
i
B
‍
(
1
+
α
j
)
≤
H
1
i. We have the load of machine M
i denoted by L
i holding L
i
=
H
2
i
∏
J
j
∈
J
S
i
/
J
S
i
B
‍
(
1
+
α
j
)
≥
H
2
i
∏
J
j
∈
J
S
i
‍
(
1
+
α
j
)
/
H
1
i for i
=
1
,
…
,
m. Note that C
max
⁡
∗
=
max
⁡
i
=
1
,
…
,
m
{
L
i
}. Thus, C
max
⁡
∗
≥
∏
i
=
1
m
‍
L
i
m
≥
H
2
1
⋯
H
2
m
∏
j
=
1
n
‍
(
1
+
α
j
)
/
H
1
1
⋯
H
1
m
m
≥
H
2
(
1
+
α
min
⁡
)
n
/
m
/
H
1.


## 3. Minimizing the Total Completion Time

In this section, we discuss the total completion time minimization problem.Ji and Cheng [13] showed that problem P
m
p
j
=
α
j
t
∑
C
j is NP-hard in the strong sense when m is arbitrary, which implies that our problem P
m
n
r
-
a
,
p
j
=
α
j
t
∑
C
j is NP-hard in the strong sense when m is arbitrary.


### 3.1. Dynamic Programming Algorithm

In this subsection, we present a dynamic programming algorithm forP
2
n
r
-
a
,
p
j
=
α
j
t
∑
C
j when machine M
2 is always available. For convenience, let t
0
=
1, and let the only nonavailable interval on machine M
1 be [
H
1
(
1
)
,
H
2
(
1
)
), α
=
∏
j
=
1
n
‍
(
1
+
α
j
), and α
j
=
∏
i
=
1
j
‍
(
1
+
α
i
).Smallest Deteriorating Rate (SDR for Short). Sort the jobs in the nondecreasing order of their deteriorating rates such that α
1
≤
α
2
≤
⋯
≤
α
n.Lemma 4.
In any optimal solution to problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j, the jobs scheduled before the nonavailable interval are processed by the SDR order and so are the jobs scheduled after the nonavailable interval and on machine M
2.We can proof this lemma by the interchanging argument.We assume that the jobs are reindexed in the SDR order. Letf
j
(
v
,
u
) denote the optimal value of the objective function satisfying the following conditions:(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
The total processing time ofM
1 before H
1
(
1
) is v.
(iii)
The total processing time ofM
2 is u.To getf
j
(
v
,
u
), we distinguish three cases as follows.Case 1.
JobJ
j is scheduled before H
1
(
1
).
In this case,u does not change. The starting time of J
j is (
v
+
1
)
/
(
1
+
α
j
), the total processing time of M
1 before H
1
(
1
) is (
v
+
1
)
/
(
1
+
α
j
)
-
1
=
(
v
-
α
j
)
/
(
1
+
α
j
) before inserting job J
j, and the completion of J
j is v
+
1. Thus, f
j
v
,
u
=
f
j
-
1
(
v
-
α
j
)
/
(
1
+
α
j
)
,
u
+
v
+
1.Case 2.
JobJ
j is scheduled on machine M
2.
In this case,v does not change. The starting time of J
j is (
u
+
1
)
/
(
1
+
α
j
), the total processing time of M
2 is (
u
+
1
)
/
(
1
+
α
j
)
-
1
=
(
u
-
α
j
)
/
(
1
+
α
j
) before inserting job J
j, and the completion of J
j is u
+
1. Thus, f
j
(
v
,
u
)
=
f
j
-
1
(
v
,
(
u
-
α
j
)
/
(
1
+
α
j
)
)
+
u
+
1.Case 3.
JobJ
j is scheduled after H
2
(
1
).
In this case, bothu and v do not change. The completion of J
j is H
2
(
1
)
α
j
/
(
v
+
1
)
(
u
+
1
) since α
j
=
∏
i
=
1
j
‍
(
1
+
α
i
)
=
(
v
+
1
)
(
u
+
1
)
∏
J
l
∈
J
H
2
(
1
)
j
‍
(
1
+
α
l
), where J
H
2
(
1
)
j denotes the set of jobs scheduled after H
2
(
1
). Thus, f
j
(
v
,
u
)
=
f
j
-
1
(
v
,
u
)
+
H
2
(
1
)
α
j
/
(
v
+
1
)
(
u
+
1
).Combining the above cases, we design a dynamic programming algorithm as follows.Algorithm DP1.Step 1.
Reindex the jobs in nondecreasing order of their deteriorating rates such thatα
1
≤
α
2
≤
⋯
≤
α
n.Step 2 (Initialization).
(2)
f
1
v
,
u
=
v
+
1
v
=
α
1
and
u
=
0
,
u
+
1
v
=
0
and
u
=
α
1
,
H
2
1
1
+
α
1
v
=
0
and
u
=
0
,
∞
otherwise
.Step 3 (Iteration).
(3)
f
j
v
,
u
=
min
⁡
⁡
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
Z
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
min
⁡
⁡
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
∈
¯
Z
,
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
if
v
-
α
j
1
+
α
j
∈
Z
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
if
u
-
α
j
1
+
α
j
∈
Z
,
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
∞
otherwise
.Step 4 (Solution).
The optimal value ismin
⁡
{
f
n
(
v
,
u
)
∣
v
=
0,1
,
…
,
H
1
(
1
)
-
1
;
u
=
0,1
,
…
,
α
-
1
}.Theorem 5.
The problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is solvable in O
(
n
α
H
1
(
1
)
) time by Algorithm DP1.Proof.
The correctness of Algorithm DP1 is guaranteed by the above discussion. Note thatv
=
0,1
,
…
,
H
1
(
1
)
-
1 and u
=
0,1
,
…
,
α
-
1. Thus, the recursive function has at most O
(
(
α
-
1
)
(
H
1
(
1
)
-
1
)
)
=
O
(
α
H
1
(
1
)
) states. Each iteration takes O
(
n
) time to execute. Hence, the running time is O
(
n
α
H
1
(
1
)
).


### 3.2. A Fully Polynomial Time Approximation Scheme

In this subsection, we present a fully polynomial time approximation scheme for problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when machine M
2 is always available. Following Woeginger [15], we show that P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is DP-benevolent, which follows that there exists a fully polynomial time approximation scheme for our problem. For convenience, let t
0
=
1.The fully polynomial time approximation scheme is based on Lemma4 stated in Section 3.2. Thus, we first sort the jobs in the nondecreasing order of their deteriorating rates such that α
1
≤
α
2
≤
⋯
≤
α
n. The dynamic programming algorithm proposed in the following goes through n phases. In the kth (
k
=
1,2
…
,
n
) phase, we input the vector X
k
=
[
α
k
]; meanwhile, a state set S
k is generated. Any state in S
k is a vector [
l
1
,
l
2
,
l
3
,
z
] which encodes a partial schedule for the first k jobs J
1
,
…
,
J
k. The component l
1 represents the total processing time before H
1
(
1
) on machine M
1, l
2 represents the total processing time after H
2
(
1
) on machine M
1, l
3 represents the total processing time on machine M
2, and the component z represents the objective value of the current schedule. The initial set S
0 contains the only state [
1
,
H
2
(
1
)
,
1,0
]. The state S
k is generated from the state S
k
-
1 by three mappings F
1, F
2, and F
3 which are defined as follows:(4)
F
1
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
1
+
α
k
,
l
2
,
l
3
,
z
+
l
1
1
+
α
k
,
F
2
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
,
l
2
1
+
α
k
,
l
3
,
z
+
l
2
1
+
α
k
,
F
3
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
,
l
2
,
l
3
1
+
α
k
,
z
+
l
3
1
+
α
k
.Intuitively, function F
1 puts job J
k at the end before H
1
(
1
) on machine M
1 if it is possible for the given state; and function F
2 puts job J
k at the end after H
2
(
1
) on machine M
1 and function F
3 puts job J
k at the end on machine M
2. Finally, set G
(
l
1
,
l
2
,
l
3
,
z
)
=
z.Combining the above discussion, we design a dynamic programming algorithm as follows.Algorithm DP2.Initializes
0
≔
{
[
1
,
H
2
(
1
)
,
1,0
]
}
For
k
=
1 to n
do
Lets
k
≔
∅
For every [
l
1
,
l
2
,
l
3
,
z
]
∈
s
k
-
1
do
[
l
1
,
l
2
(
1
+
α
k
)
,
l
3
,
z
+
l
2
(
1
+
α
k
)
] assignments s
k
and
[
l
1
,
l
2
,
l
3
(
1
+
α
k
)
,
z
+
l
3
(
1
+
α
k
)
] assignments s
k
If
l
1
(
1
+
α
k
)
≤
H
1
(
1
)
Then
[
l
1
(
1
+
α
k
)
,
l
2
,
l
3
,
z
+
l
1
(
1
+
α
k
)
] assignments s
k
Endfor
Endfor
Outputmin
⁡
{
G
(
l
1
,
l
2
,
l
3
,
z
)
:
[
l
1
,
l
2
,
l
3
,
z
] assignments s
n
}.Note that the number of states in the above dynamic programming is bounded byH
2
(
1
)
n
∏
j
=
1
n
‍
(
1
+
α
j
). There holds the following result.Theorem 6.
There exists a fully polynomial time approximation scheme for problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when one machine is always available.Proof.
The functionsF
1, F
2, and F
3 are vectors of polynomials with nonnegative coefficients and the polynomial functions in F
1, F
2, and F
3 that yield the components are polynomials. Moreover, all polynomials linearly depend on l
1, l
2, l
3, and z. The inequality inside operator “if” can be checked in polynomial time. The objective function G is a polynomial with nonnegative coefficients. Therefore, similar to the example in Section 5.3 of Woeginger [15], it is not hard to verify that the above dynamic programming satisfies the conditions of Lemma 6.1 and Theorem 2.5 from [15]. Thus, problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is DP-benevolent. As a result, there exists a fully polynomial time approximation scheme for problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when one machine is always available.


## 3.1. Dynamic Programming Algorithm

In this subsection, we present a dynamic programming algorithm forP
2
n
r
-
a
,
p
j
=
α
j
t
∑
C
j when machine M
2 is always available. For convenience, let t
0
=
1, and let the only nonavailable interval on machine M
1 be [
H
1
(
1
)
,
H
2
(
1
)
), α
=
∏
j
=
1
n
‍
(
1
+
α
j
), and α
j
=
∏
i
=
1
j
‍
(
1
+
α
i
).Smallest Deteriorating Rate (SDR for Short). Sort the jobs in the nondecreasing order of their deteriorating rates such that α
1
≤
α
2
≤
⋯
≤
α
n.Lemma 4.
In any optimal solution to problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j, the jobs scheduled before the nonavailable interval are processed by the SDR order and so are the jobs scheduled after the nonavailable interval and on machine M
2.We can proof this lemma by the interchanging argument.We assume that the jobs are reindexed in the SDR order. Letf
j
(
v
,
u
) denote the optimal value of the objective function satisfying the following conditions:(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
The total processing time ofM
1 before H
1
(
1
) is v.
(iii)
The total processing time ofM
2 is u.To getf
j
(
v
,
u
), we distinguish three cases as follows.Case 1.
JobJ
j is scheduled before H
1
(
1
).
In this case,u does not change. The starting time of J
j is (
v
+
1
)
/
(
1
+
α
j
), the total processing time of M
1 before H
1
(
1
) is (
v
+
1
)
/
(
1
+
α
j
)
-
1
=
(
v
-
α
j
)
/
(
1
+
α
j
) before inserting job J
j, and the completion of J
j is v
+
1. Thus, f
j
v
,
u
=
f
j
-
1
(
v
-
α
j
)
/
(
1
+
α
j
)
,
u
+
v
+
1.Case 2.
JobJ
j is scheduled on machine M
2.
In this case,v does not change. The starting time of J
j is (
u
+
1
)
/
(
1
+
α
j
), the total processing time of M
2 is (
u
+
1
)
/
(
1
+
α
j
)
-
1
=
(
u
-
α
j
)
/
(
1
+
α
j
) before inserting job J
j, and the completion of J
j is u
+
1. Thus, f
j
(
v
,
u
)
=
f
j
-
1
(
v
,
(
u
-
α
j
)
/
(
1
+
α
j
)
)
+
u
+
1.Case 3.
JobJ
j is scheduled after H
2
(
1
).
In this case, bothu and v do not change. The completion of J
j is H
2
(
1
)
α
j
/
(
v
+
1
)
(
u
+
1
) since α
j
=
∏
i
=
1
j
‍
(
1
+
α
i
)
=
(
v
+
1
)
(
u
+
1
)
∏
J
l
∈
J
H
2
(
1
)
j
‍
(
1
+
α
l
), where J
H
2
(
1
)
j denotes the set of jobs scheduled after H
2
(
1
). Thus, f
j
(
v
,
u
)
=
f
j
-
1
(
v
,
u
)
+
H
2
(
1
)
α
j
/
(
v
+
1
)
(
u
+
1
).Combining the above cases, we design a dynamic programming algorithm as follows.Algorithm DP1.Step 1.
Reindex the jobs in nondecreasing order of their deteriorating rates such thatα
1
≤
α
2
≤
⋯
≤
α
n.Step 2 (Initialization).
(2)
f
1
v
,
u
=
v
+
1
v
=
α
1
and
u
=
0
,
u
+
1
v
=
0
and
u
=
α
1
,
H
2
1
1
+
α
1
v
=
0
and
u
=
0
,
∞
otherwise
.Step 3 (Iteration).
(3)
f
j
v
,
u
=
min
⁡
⁡
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
Z
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
min
⁡
⁡
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
∈
¯
Z
,
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
v
+
1
if
v
-
α
j
1
+
α
j
∈
Z
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
u
+
1
if
u
-
α
j
1
+
α
j
∈
Z
,
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
+
H
2
1
α
j
v
+
1
u
+
1
if
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
∞
otherwise
.Step 4 (Solution).
The optimal value ismin
⁡
{
f
n
(
v
,
u
)
∣
v
=
0,1
,
…
,
H
1
(
1
)
-
1
;
u
=
0,1
,
…
,
α
-
1
}.Theorem 5.
The problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is solvable in O
(
n
α
H
1
(
1
)
) time by Algorithm DP1.Proof.
The correctness of Algorithm DP1 is guaranteed by the above discussion. Note thatv
=
0,1
,
…
,
H
1
(
1
)
-
1 and u
=
0,1
,
…
,
α
-
1. Thus, the recursive function has at most O
(
(
α
-
1
)
(
H
1
(
1
)
-
1
)
)
=
O
(
α
H
1
(
1
)
) states. Each iteration takes O
(
n
) time to execute. Hence, the running time is O
(
n
α
H
1
(
1
)
).


## 3.2. A Fully Polynomial Time Approximation Scheme

In this subsection, we present a fully polynomial time approximation scheme for problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when machine M
2 is always available. Following Woeginger [15], we show that P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is DP-benevolent, which follows that there exists a fully polynomial time approximation scheme for our problem. For convenience, let t
0
=
1.The fully polynomial time approximation scheme is based on Lemma4 stated in Section 3.2. Thus, we first sort the jobs in the nondecreasing order of their deteriorating rates such that α
1
≤
α
2
≤
⋯
≤
α
n. The dynamic programming algorithm proposed in the following goes through n phases. In the kth (
k
=
1,2
…
,
n
) phase, we input the vector X
k
=
[
α
k
]; meanwhile, a state set S
k is generated. Any state in S
k is a vector [
l
1
,
l
2
,
l
3
,
z
] which encodes a partial schedule for the first k jobs J
1
,
…
,
J
k. The component l
1 represents the total processing time before H
1
(
1
) on machine M
1, l
2 represents the total processing time after H
2
(
1
) on machine M
1, l
3 represents the total processing time on machine M
2, and the component z represents the objective value of the current schedule. The initial set S
0 contains the only state [
1
,
H
2
(
1
)
,
1,0
]. The state S
k is generated from the state S
k
-
1 by three mappings F
1, F
2, and F
3 which are defined as follows:(4)
F
1
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
1
+
α
k
,
l
2
,
l
3
,
z
+
l
1
1
+
α
k
,
F
2
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
,
l
2
1
+
α
k
,
l
3
,
z
+
l
2
1
+
α
k
,
F
3
α
k
,
l
1
,
l
2
,
l
3
,
z
=
l
1
,
l
2
,
l
3
1
+
α
k
,
z
+
l
3
1
+
α
k
.Intuitively, function F
1 puts job J
k at the end before H
1
(
1
) on machine M
1 if it is possible for the given state; and function F
2 puts job J
k at the end after H
2
(
1
) on machine M
1 and function F
3 puts job J
k at the end on machine M
2. Finally, set G
(
l
1
,
l
2
,
l
3
,
z
)
=
z.Combining the above discussion, we design a dynamic programming algorithm as follows.Algorithm DP2.Initializes
0
≔
{
[
1
,
H
2
(
1
)
,
1,0
]
}
For
k
=
1 to n
do
Lets
k
≔
∅
For every [
l
1
,
l
2
,
l
3
,
z
]
∈
s
k
-
1
do
[
l
1
,
l
2
(
1
+
α
k
)
,
l
3
,
z
+
l
2
(
1
+
α
k
)
] assignments s
k
and
[
l
1
,
l
2
,
l
3
(
1
+
α
k
)
,
z
+
l
3
(
1
+
α
k
)
] assignments s
k
If
l
1
(
1
+
α
k
)
≤
H
1
(
1
)
Then
[
l
1
(
1
+
α
k
)
,
l
2
,
l
3
,
z
+
l
1
(
1
+
α
k
)
] assignments s
k
Endfor
Endfor
Outputmin
⁡
{
G
(
l
1
,
l
2
,
l
3
,
z
)
:
[
l
1
,
l
2
,
l
3
,
z
] assignments s
n
}.Note that the number of states in the above dynamic programming is bounded byH
2
(
1
)
n
∏
j
=
1
n
‍
(
1
+
α
j
). There holds the following result.Theorem 6.
There exists a fully polynomial time approximation scheme for problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when one machine is always available.Proof.
The functionsF
1, F
2, and F
3 are vectors of polynomials with nonnegative coefficients and the polynomial functions in F
1, F
2, and F
3 that yield the components are polynomials. Moreover, all polynomials linearly depend on l
1, l
2, l
3, and z. The inequality inside operator “if” can be checked in polynomial time. The objective function G is a polynomial with nonnegative coefficients. Therefore, similar to the example in Section 5.3 of Woeginger [15], it is not hard to verify that the above dynamic programming satisfies the conditions of Lemma 6.1 and Theorem 2.5 from [15]. Thus, problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j is DP-benevolent. As a result, there exists a fully polynomial time approximation scheme for problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j when one machine is always available.


## 4. Minimizing the Total Weighted Completion Time

In this section, we extend the dynamic programming algorithm to the total weighted completion time minimization problem, that is,P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
w
j
C
j. We also assume that machine M
2 is always available.We assume that the jobs are reindexed such thatw
1
(
1
+
α
1
)
/
α
1
≥
w
2
(
1
+
α
2
)
/
α
2
≥
⋯
≥
w
n
(
1
+
α
n
)
/
α
n. For convenience, denot this order byWeight Deteriorating Rate (WDR for short).Lemma 7.
In any optimal solution to problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
w
j
C
j, the jobs scheduled before the nonavailable interval are processed by the WDR order and so are the jobs scheduled after the nonavailable interval and on machine M
2.We can proof this lemma by the interchanging argument.We assume that the jobs are reindexed in the WDR order. Similar to the context of Section3.1, let f
j
(
v
,
u
) denote the optimal value of the objective function satisfying the following conditions:(i)
The jobs in consideration areJ
1
,
…
,
J
j.
(ii)
The total processing time ofM
1 before H
1
(
1
) is v.
(iii)
The total processing time ofM
2 is u.We design a dynamic programming algorithm as follows.Algorithm DP3.Step 1.
Reindex the jobs such thatw
1
(
1
+
α
1
)
/
α
1
≥
w
2
(
1
+
α
2
)
/
α
2
≥
⋯
≥
w
n
(
1
+
α
n
)
/
α
n.Step 2 (Initialization).
(5)
f
1
v
,
u
=
w
1
v
+
1
v
=
α
1
and
u
=
0
,
w
1
u
+
1
v
=
0
and
u
=
α
1
,
w
1
H
2
1
1
+
α
1
v
=
0
and
u
=
0
,
∞
otherwise
.Step 3 (Iteration).
(6)
f
j
v
,
u
=
min
⁡
⁡
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
w
j
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
w
j
u
+
1
,
f
j
-
1
v
,
u
+
w
j
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
min
⁡
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
w
j
v
+
1
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
w
j
u
+
1
if
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
Z
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
min
⁡
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
w
j
v
+
1
,
f
j
-
1
v
,
u
+
w
j
H
2
1
α
j
v
+
1
u
+
1
if
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
min
⁡
⁡
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
w
j
u
+
1
,
f
j
-
1
v
,
u
+
w
j
H
2
1
α
j
v
+
1
u
+
1
if
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
∈
¯
Z
,
f
j
-
1
v
-
α
j
1
+
α
j
,
u
+
w
j
v
+
1
if
v
-
α
j
1
+
α
j
∈
Z
,
u
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
-
α
j
1
+
α
j
+
w
j
u
+
1
if
u
-
α
j
1
+
α
j
∈
Z
,
v
-
α
j
1
+
α
j
,
H
2
1
α
j
v
+
1
u
+
1
∈
¯
Z
,
f
j
-
1
v
,
u
+
w
j
H
2
1
α
j
v
+
1
u
+
1
if
H
2
1
α
j
v
+
1
u
+
1
∈
Z
,
v
-
α
j
1
+
α
j
,
u
-
α
j
1
+
α
j
∈
¯
Z
,
∞
otherwise
.Step 4 (Solution).
The optimal value ismin
⁡
{
f
n
(
v
,
u
)
∣
v
=
0,1
,
…
,
H
1
(
1
)
-
1
;
u
=
0,1
,
…
,
α
-
1
}.Theorem 8.
The problemP
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
w
j
C
j is solvable in O
(
n
α
H
1
(
1
)
) time by Algorithm DP3.


## 5. Conclusions

In this paper, we considered the parallel-machine scheduling with time-dependent and machine availability constraints. We showed that our two problemsP
m
n
r
-
a
,
p
j
=
α
j
t
C
max
⁡
(
∑
‍
C
j
) are NP-hard in the strong sense. We analyzed the LDR and LS algorithms and the lower bound of any optimal schedule and presented dynamic programming algorithm and fully polynomial time approximation scheme for the problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
C
j. Furthermore, we extended the dynamic programming algorithm to problem P
2
n
r
-
a
,
p
j
=
α
j
t
∑
‍
w
j
C
j.For future research, the other objectives are worth considering. The design of PTAS for our problems is another worthy topic.



---

*Source: 956158-2015-07-28.xml*