# Parallel Machine Scheduling with Nested Processing Set Restrictions and Job Delivery Times

Authors: Shuguang Li
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The problem of scheduling jobs with delivery times on parallel machines is studied, where each job can only be processed on a specific subset of the machines called its processing set. Two distinct processing sets are either nested or disjoint; that is, they do not partially overlap. All jobs are available for processing at time 0. The goal is to minimize the time by which all jobs are delivered, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. A list scheduling approach is analyzed and its approximation ratio of 2 is established. In addition, a polynomial time approximation scheme is derived.


---

## Body

## 1. Introduction

The problems of scheduling with processing set restrictions have been extensively studied in the past few decades [1, 2]. In this class of problems, we are given a set of n jobs J
=
{
1,2
,
…
,
n
} and a set of m parallel machines M
=
{
M
1
,
M
2
,
…
,
M
m
}. Each job j can only be processed on a certain subset M
j of the machines, called itsprocessing set, and, on those machines, it takes p
j time units of uninterrupted processing to complete. Each machine can process at most one job at a time. The goal is to find an optimal schedule where optimality is defined by some problem dependent objective.There are several important special cases of processing set restrictions:inclusive,nested,interval, andtree-hierarchical [2]. In the case of inclusive processing set, for any two jobs j
1 and j
2, either M
j
1
⊆
M
j
2 or M
j
2
⊆
M
j
1. In the nested processing set case, either M
j
1
∩
M
j
2
=
ϕ, or M
j
1
⊆
M
j
2, or M
j
2
⊆
M
j
1. In the interval processing set case, the machines are linearly ordered, and each job j is associated with two machine indices a
j and b
j such that M
j
=
{
M
a
j
,
M
a
j
+
1
,
…
,
M
b
j
}. It is easy to see that the inclusive processing set and the nested processing set are two special cases of the interval processing set. In the tree-hierarchical processing set case, each machine is represented by a vertex of a tree, and each job j is associated with a machine index a
j such that M
j consists of the machines on the unique path from M
a
j to the root of the tree.In this paper, we consider the problem of scheduling jobs with nested processing set restrictions on parallel machines. Besides itsprocessing time
p
j and processing set M
j, each job j requires an additionaldelivery time
q
j after completing its processing. If S
j denotes the time job j starts processing, it has been delivered at time L
j
=
S
j
+
p
j
+
q
j, which is called itsdelivery completion time. All jobs are available for processing at time 0. The objective is to minimize the time by which all jobs are delivered, that is, themaximum delivery completion time, L
m
a
x
=
m
a
x
j
L
j. Minimizing the maximum delivery completion time is equivalent to minimizing the maximum lateness from the optimization viewpoint [3]. Following the classification scheme for scheduling problems by Graham et al. [4], this problem is noted: P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x.The motivation for this problem is the scenario in which the jobs (with nested processing set restrictions) are first processed on the machines and then delivered to their respective customers. In order to be competitive, the jobs are needed to be delivered as soon as possible to their customers. Thus, the industry practitioners are required to coordinate job production and job delivery. In manufacturing and distribution systems, finished jobs are delivered by vehicles such as trucks. Since there are sufficient vehicles for delivering jobs, delivery is a nonbottleneck activity. Therefore, we assume that all jobs may be simultaneously delivered. Considering job production and job delivery as one system, we choose the cost function to measure the customer service level. In particular, we are interested in the objective of minimizing the time by which all jobs are delivered.The problem as stated is a natural generalization of strongly NP-hard problemP
∥
C
m
a
x, which corresponds to the special case where all M
j
=
M and all q
j
=
0 [5]. For NP-hard problems, the research focuses on developing polynomial time approximation algorithms. Given instance I of a minimization problem and approximation algorithm A, let A
(
I
) and O
P
T
(
I
) denote the objective value of the solution obtained by algorithm A and the optimal solution value, respectively, when applied to I. If A
(
I
)
/
O
P
T
(
I
)
≤
ρ for all I, then we say that algorithm A hasapproximation ratio
ρ, and A is called ρ-approximation algorithm for this problem. Ideally, one hopes to obtain a family of polynomial time algorithms such that, for any given ε
>
0, the corresponding algorithm is (
1
+
ε
)-approximation algorithm; such a family is called apolynomial time approximation scheme (PTAS) [6].When allM
j
=
M, P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x reduces to the classic scheduling problem P
∥
L
m
a
x. Woeginger [7] provided three fast heuristics for P
∥
L
m
a
x with approximation ratios 2, 2
-
1
/
m, and 2
-
2
/
(
m
+
1
), respectively. For the single machine case with release times 1
∣
r
j
∣
L
m
a
x, Potts [8] presented a 1.5-approximation algorithm, and Hall and Shmoys [9, 10] proposed two PTASs whose running times are O
(
(
n
/
ε
)
O
(
1
/
ε
)
) and O
(
n
log
⁡
n
+
n
(
1
/
ε
)
O
(
1
/
ε
2
)
). For the parallel machines case with release times P
∣
r
j
∣
L
m
a
x, Hall and Shmoys [10] obtained a PTAS with running time O
(
n
p
o
l
y
(
1
/
ε
)
), and Mastrolilli [11] developed a PTAS that runs in O
(
n
+
f
(
1
/
ε
)
), where f
(
1
/
ε
) is a constant that depends exponentially on 1
/
ε. Mastrolilli [11] also presented an improved PTAS for 1
∣
r
j
∣
L
m
a
x that runs in O
(
n
+
(
1
/
ε
)
O
(
1
/
ε
)
) time.When allq
j
=
0, P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x reduces to the problem of minimizing makespan with nested processing set restrictions, P
∣
M
j
(
n
e
s
t
e
d
)
∣
C
m
a
x. There are a number of approximation algorithms for P
∣
M
j
(
n
e
s
t
e
d
)
∣
C
m
a
x: (
2
-
1
/
m
)-approximation algorithm [12], 7/4-approximation algorithm [13], 5/3-approximation algorithm [14], and two PTASs [15, 16].As mentioned above, the classic scheduling problem (without processing set restrictions) of minimizing the maximum delivery completion time and the problem of minimizing makespan with nested processing set restrictions have been studied in the literature. However, to the best of our knowledge, the problem of minimizing the maximum delivery completion time with nested processing set restrictions,P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x, has not been studied to date. In this paper, we first use Graham’slist scheduling [17] to get a simple and fast 2-approximation algorithm. We then derive a polynomial time approximation scheme, which is heavily built on the ideas of [15]. The PTAS result generalizes the approximation schemes of [15, 16], both of which deal with only the special case where all q
j
=
0.The paper is organized into sections as follows. Section2 presents a 2-approximation algorithm which uses list scheduling as a subroutine. The next three sections are devoted to designing the polynomial time approximation scheme. Section 3 shows how to simplify the input instance to get a so-called rounded instance. Section 4 shows how to solve the rounded instance optimally. Section 5 wraps things up to derive the polynomial time approximation scheme. The discussion in Section 6 completes the paper.


## 2. A 2-Approximation Algorithm

In this section, we will present a simple and fast 2-approximation algorithm forP
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x.As observed in [12], nested processing sets have a partial ordering defined by the inclusion relationship and, thus, offer a natural topological sort on jobs, taking more constrained jobs first.We now explore the behavior of Graham’s list scheduling algorithm [17], with jobs sorted to respect nestedness. It does not depend on the delivery times. The algorithm is called Nested-LS.Nested-LSStep 1.
Place all the jobs in a list in the order of the topological sort on jobs, taking more constrained jobs first. SetL
o
a
d
i
=
0, i
=
1,2
,
…
,
m.Step 2.
For the first unscheduled jobj in the list, select a machine M
i
∈
M
j for which L
o
a
d
i is the smallest (ties broken arbitrarily). Assign job j to machine M
i. Set L
o
a
d
i
=
L
o
a
d
i
+
p
j. Repeat this step until all the jobs are scheduled.Theload on a machine is defined to be the total processing time of the jobs assigned to this machine. The quantity L
o
a
d
i represents the current load on machine M
i during the run of Nested-LS, i
=
1,2
,
…
,
m.Theorem 1.
Nested-LS is a 2-approximation algorithm forP
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x that runs in O
(
n
log
⁡
m
n
) time.Proof.
LetO
P
T be the objective value of an optimal schedule. Denote by L
m
a
x the objective value of the schedule generated by Nested-LS. Let j
1 be the first job in the list generated in Step 2 for which L
m
a
x
=
S
j
1
+
p
j
1
+
q
j
1 holds, where S
j
1 denotes the time job j
1 starts processing. Remove all the following jobs from the list. Remove all the machines in M
∖
M
j
1 and all the jobs assigned to these machines. This cannot increase O
P
T and does not decrease L
m
a
x.
A straightforward lower bound onO
P
T is O
P
T
≥
p
j
+
q
j for any job j. By the rule of Nested-LS, at the time when job j
1 is assigned to its machine M
i, M
i is the least-loaded machine among the machines in M
j
1. It follows that S
j
1
<
O
P
T. Consequently, we get L
m
a
x
=
S
j
1
+
p
j
1
+
q
j
1
<
2
O
P
T.
The initial step of sorting the jobs to respect nestedness requiresO
(
n
log
⁡
n
) time. Assigning a job to the least-loaded eligible machine in Step 2 runs in O
(
log
⁡
m
) time. Thus, Nested-LS runs in O
(
n
log
⁡
m
n
) time.


## 3. Simplifying the Input

The nested structure of processing sets can be depicted by rooted treeT
=
(
V
,
E
), in which each processing set is represented by a vertex, and the predecessor relationship is defined by inclusion of the processing sets. Each machine can be regarded as a one-element processing set and thus it corresponds to a leaf in T, even if there are no jobs associated with this processing set. The root of T corresponds to M
=
{
M
1
,
M
2
,
…
,
M
m
}.For each vertexv
∈
V
(
T
), let M
(
v
) denote the set of machines associated with v, which is the disjoint union of all the processing sets associated with the sons of v. Let J
(
v
) denote the set of jobs j for which M
j coincides with M
(
v
).Following [15], we transform tree T into a binary tree as follows. If there is vertex v with at least three sons, create new vertex u as the new father of two sons of v and as a new son of v. Repeat this procedure until we reach a binary tree, which consists of m leaves and of m
-
1 nonleaf vertices. Therefore, we can assume without loss of generality that T is a binary tree.Given instanceI of P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x, let O
P
T
(
I
) be the objective value of an optimal schedule for I. Let A be the objective value of the schedule for I generated by Nested-LS. We have (1)
O
P
T
I
≤
A
≤
2
O
P
T
I
.Letα be some fixed positive integer. Classify jobs as big and small according to their processing times. Job j isbig, if p
j
>
A
/
(
α
(
α
+
1
)
), and otherwise it issmall.ModifyI to get rounded instance I
#
(
α
) as follows:(i)
For each jobj, round its delivery time q
j up to the nearest integer multiple of A
/
α; that is, set rounded delivery time q
j
#
=
q
j
/
(
A
/
α
)
·
(
A
/
α
). Note that there are at most α
+
1 different delivery times in the rounded instance. Let ξ
l
=
(
l
-
1
)
A
/
α denote lth delivery time, l
=
1,2
,
…
,
α
+
1.
(ii)
For each big jobj, round its processing time p
j up to the nearest integer multiple of A
/
(
α
2
(
α
+
1
)
). Let p
j
# denote the rounded processing time of big job j. Note p
j
≤
p
j
#
≤
(
1
+
1
/
α
)
p
j.
(iii)
For each vertexv
∈
V
(
T
), let T
S
l
(
v
) be the total processing time of the small jobs with delivery time ξ
l in J
(
v
). Let T
S
l
#
(
v
) be the value of T
S
l
(
v
) rounded up to the nearest integer multiple of A
/
(
α
(
α
+
1
)
). The small jobs with delivery time ξ
l in J
(
v
) are replaced with T
S
l
#
(
v
)
·
α
(
α
+
1
)
/
A new jobs each of which has delivery time ξ
l and processing time A
/
(
α
(
α
+
1
)
), l
=
1,2
,
…
,
α
+
1.Lemma 2.
There is scheduleΣ
# for I
#
(
α
) with objective value L
#
≤
(
1
+
1
/
α
)
·
O
P
T
(
I
)
+
4
A
/
α.Proof.
LetΣ be an optimal schedule for instance I with objective value O
P
T
(
I
). Recall that the single machine case 1
∥
L
m
a
x can be solved optimally by Jackson’s rule [18]: process the jobs successively in order of nondecreasing delivery times. Hence, we can assume that in Σ on each machine the jobs with the same delivery time are processed together in succession. Let T
S
i
l be the total processing time of the small jobs with delivery time ξ
l processed on machine M
i in Σ. Let T
S
i
l
# be the value of T
S
i
l rounded up to the nearest integer multiple of A
/
(
α
(
α
+
1
)
). Replace the small jobs with delivery time ξ
l processed on machine M
i in Σ by 2
+
T
S
i
l
#
·
α
(
α
+
1
)
/
A slots each of which has delivery time ξ
l and size A
/
(
α
(
α
+
1
)
), i
=
1,2
,
…
,
m, l
=
1,2
,
…
,
α
+
1.
We next explain how to assign all small jobs inI
#
(
α
) to these slots of size A
/
(
α
(
α
+
1
)
). Starting from the leaves of tree T, we work our way towards the root in a bottom-up fashion. Suppose that we are handling vertex v
∈
V
(
T
). At this point, all the descendants of v except v itself have already been handled and some slots have been occupied. Let T
v be the subtree of T rooted at v which contains exactly 2
m
(
v
)
-
1 vertices, where m
(
v
)
=
M
(
v
) denotes the number of machines (leaves) in T
v. Let β
l denote the total processing time of the small jobs with delivery time ξ
l in all descendants of v (including v itself) in instance I, and let β
l
# denote the total processing time of the corresponding small jobs in I
#
(
α
), l
=
1,2
,
…
,
α
+
1. Let γ
l
# denote the total size of the slots with delivery time ξ
l and size A
/
(
α
(
α
+
1
)
) on all machines in descendant leaves of v. We have the following two inequalities: β
l
#
≤
β
l
+
(
2
m
(
v
)
-
1
)
A
/
(
α
(
α
+
1
)
) and γ
l
#
≥
β
l
+
2
m
(
v
)
A
/
(
α
(
α
+
1
)
). Therefore, we get β
l
#
≤
γ
l
#.
LetS
J
l
#
(
v
) denote the set of small jobs j
# in I
#
(
α
) with delivery time q
j
#
=
ξ
l, processing time p
j
#
=
A
/
(
α
(
α
+
1
)
), and processing set M
j
#
=
M
(
v
). Since β
l
#
≤
γ
l
#, when we handle vertex v, there are enough unoccupied slots of size A
/
(
α
(
α
+
1
)
) to accommodate the jobs in S
J
l
#
(
v
). For each job in S
J
l
#
(
v
) (l
=
1,2
,
…
,
α
+
1), we assign an unoccupied slot to it and then mark this slot as occupied.
After we handle the root ofT, we fit all small jobs in I
#
(
α
) into the slots of size A
/
(
α
(
α
+
1
)
) and thereby get an assignment of the small jobs in I
#
(
α
) to m machines. We schedule the small jobs in I
#
(
α
) assigned to machine M
i as follows. If T
S
i
l
=
0 (which means that in Σ machine M
i processes no small job with delivery time ξ
l) but the replacement procedure has assigned some small jobs with delivery time ξ
l to M
i, then we schedule these small jobs on M
i first, l
=
1,2
,
…
,
α
+
1, i
=
1,2
,
…
,
m. We then schedule all the other small jobs assigned to M
i by Jackson’s rule, that is, keeping their order in Σ. (In fact, scheduling all the small jobs assigned to M
i by Jackson’s rule can improve the solution. We schedule them in this way only for ease of the subsequent analysis.)
The big jobs inI
#
(
α
) are easily scheduled. We simply replace every big job in Σ by its rounded counterpart in I
#
(
α
).
LetΣ
# denote the obtained schedule for I
#
(
α
). It remains only to analyze how the objective value changes, when we move from schedule Σ to schedule Σ
#. Rounding up the delivery times may increase the objective value by A
/
α. Rounding up the processing times of the big jobs may increase the objective value by a factor of 1
+
1
/
α. Since there are at most α
+
1 different delivery times in I
#
(
α
), the replacement procedure for the small jobs increases the objective value by (
α
+
1
)
·
3
A
/
(
α
(
α
+
1
)
)
=
3
A
/
α. Hence, L
#, the objective value of Σ
#, is no more than (
1
+
1
/
α
)
·
O
P
T
(
I
)
+
4
A
/
α.Lemma 3.
LetΣ
# be a schedule for I
#
(
α
) with objective value L
#. Then, there is a schedule for I with objective value L
m
a
x
≤
L
#
+
A
/
α.Proof.
We assume without loss of generality that, inΣ
# on each machine, the jobs are scheduled by Jackson’s rule, and thus the small jobs with the same delivery time are processed together in succession on each machine. Let T
S
i
l
# be the total processing time of the small jobs with delivery time ξ
l processed on machine M
i in Σ
#, l
=
1,2
,
…
,
α
+
1, i
=
1,2
,
…
,
m.
We now explain how to assign all small jobs inI to m machines. Starting from the leaves of tree T, we work our way towards the root in a bottom-up fashion, as in the proof of Lemma 2. Suppose that we are handling vertex v
∈
V
(
T
). At this point, all the descendants of v except v itself have already been handled and the associated small jobs have been assigned. Let β
l denote the total processing time of the small jobs with delivery time ξ
l in all descendants of v (including v itself) in instance I, and let β
l
# denote the total processing time of the corresponding small jobs in I
#
(
α
), l
=
1,2
,
…
,
α
+
1. We have β
l
#
≥
β
l.
LetS
J
l
(
v
) denote the set of small jobs j in I with delivery time q
j
=
ξ
l and processing set M
j
=
M
(
v
), l
=
1,2
,
…
,
α
+
1. For each machine M
i
∈
M
(
v
), if T
S
i
l
#
>
0 (which means that in Σ
# machine M
i processes at least one small job with delivery time ξ
l), we assign the small jobs in S
J
l
(
v
) to M
i until the first time that the total processing time of the small jobs with delivery time ξ
l assigned to M
i exceeds T
S
i
l
# (or until there are no unassigned small jobs in S
J
l
(
v
)). Since β
l
#
≥
β
l, each job in S
J
l
(
v
) can be assigned to a machine in M
(
v
).
After we handle the root ofT, we assign all small jobs in I to m machines. The big jobs in I are easily scheduled. We simply replace every rounded big job in Σ
# with its original counterpart in I. We then schedule all the jobs assigned to M
i by Jackson’s rule, that is, keeping their order in Σ
#, i
=
1,2
,
…
,
m.
LetL
m
a
x be the objective value of the obtained schedule for I. Since all small jobs in I have processing time at most A
/
(
α
(
α
+
1
)
) and there are at most α
+
1 different delivery times in I, the replacement procedure for the small jobs may increase the objective value by (
α
+
1
)
·
A
/
(
α
(
α
+
1
)
)
=
A
/
α. The replacement of big jobs will not increase the objective value. Hence, we get L
m
a
x
≤
L
#
+
A
/
α.


## 4. Solving the Rounded Instance Optimally

In this section, we will present an polynomial time optimal algorithm for rounded instanceI
#
(
α
) obtained in the preceding section. The basic idea is to generalize the dynamic programming method used in [15] for solving problem P
∣
M
j
(
n
e
s
t
e
d
)
∣
C
m
a
x.Recall that all jobs in rounded instanceI
#
(
α
) have processing times of form k
A
/
(
α
2
(
α
+
1
)
), where k
∈
{
α
,
α
+
1
,
…
,
α
2
(
α
+
1
)
}. We thus can represent subsets of the jobs in I
#
(
α
) as vectors λ
→
=
(
λ
α
1
,
…
,
λ
α
2
(
α
+
1
)
1
,
…
,
λ
α
α
+
1
,
…
,
λ
α
2
(
α
+
1
)
α
+
1
), where λ
k
l denotes the number of jobs with delivery time ξ
l and processing time k
A
/
(
α
2
(
α
+
1
)
), l
∈
{
1,2
,
…
,
α
+
1
}, k
∈
{
α
,
α
+
1
,
…
,
α
2
(
α
+
1
)
}. Let Λ be the set of all such vectors. Clearly, there are O
(
n
α
2
(
α
+
1
)
) different vectors in Λ. For each vertex v
∈
V
(
T
), set J
(
v
) of jobs j in I
#
(
α
) with M
j
=
M
(
v
) is encoded by vector λ
→
(
v
).Letv
∈
V
(
T
) and λ
→
∈
Λ, where vector λ
→ represents a subset of jobs whose processing sets are proper supersets of M
(
v
). Let f
(
v
,
λ
→
) denote the minimum objective value over all the schedules which process the jobs in the descendants of v and the additional jobs in λ
→ on the machines in M
(
v
). All jobs in the descendants of v must obey the processing set restrictions, whereas the jobs in λ
→ can be assigned to any machine in M
(
v
).All valuesf
(
v
,
λ
→
) can be computed and tabulated in a bottom-up fashion. If v is a leaf, then f
(
v
,
λ
→
) is equal to the objective value of the single machine schedule which processes all the jobs in λ
→
(
v
)
+
λ
→ by Jackson’s rule. If v is a nonleaf vertex, then v has two sons v
1 and v
2, and (2)
f
v
,
λ
→
=
min
⁡
max
⁡
f
v
1
,
μ
→
1
,
f
v
2
,
μ
→
2
:
μ
→
1
,
μ
→
2
∈
Λ
,
μ
→
1
+
μ
→
2
=
λ
→
v
+
λ
→
.Since there areO
(
n
α
2
(
α
+
1
)
) different vectors in Λ and α is a fixed integer that does not depend on the input, all values f
(
v
,
λ
→
) can be computed in polynomial time. Finally, since, for root vertex r, there is no job whose processing set is a proper superset of M
(
r
), the optimal objective value for I
#
(
α
) is achieved by computing f
(
r
,
(
0
,
…
,
0
)
).We establish the following theorem.Theorem 4.
For any fixed integerα, rounded instance I
#
(
α
) can be solved optimally in polynomial time.


## 5. The Approximation Scheme

We can now put things together.Letε be an arbitrarily small positive constant. Set α
∗
=
11
/
ε. Given instance I of P
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x, we get rounded instance I
#
(
α
∗
) as described in Section 3. Solve I
#
(
α
∗
) optimally as described in Section 4. Denote by Σ
# the resulting optimal schedule with objective value L
m
a
x
# for I
#
(
α
∗
). Transform Σ
# into schedule Σ with objective value L
m
a
x for instance I as described in the proof of Lemma 3.By Lemma2, we have L
m
a
x
#
≤
(
1
+
1
/
α
∗
)
·
O
P
T
(
I
)
+
4
A
/
α
∗. Together with Lemma 3, we have L
m
a
x
≤
L
m
a
x
#
+
A
/
α
∗
≤
(
1
+
1
/
α
∗
)
·
O
P
T
(
I
)
+
5
A
/
α
∗. By inequality (1), we have A
≤
2
O
P
T
(
I
). It follows that L
m
a
x
≤
(
1
+
11
/
α
∗
)
·
O
P
T
(
I
)
≤
(
1
+
ε
)
·
O
P
T
(
I
). We have the following theorem.Theorem 5.
ProblemP
∣
M
j
(
n
e
s
t
e
d
)
∣
L
m
a
x admits a polynomial time approximation scheme.


## 6. Concluding Remarks

In this paper, we initiated the study of scheduling parallel machines with job delivery times and nested processing set restrictions. The objective is to minimize the maximum delivery completion time. For this strong NP-hard problem, we presented a simple and fast 2-approximation algorithm. We also presented a polynomial time approximation scheme. A natural open problem is to design fast algorithms with approximation ratios better than 2. It would also be interesting to study the problem with job release times.



---

*Source: 3203728-2016-09-18.xml*