# A Novel MOEA/D for Multiobjective Scheduling of Flexible Manufacturing Systems

Authors: Xinnian Wang; Keyi Xing; Chao-Bo Yan; Mengchu Zhou
Journal: Complexity
 (2019)

---

## Abstract

This paper considers the multiobjective scheduling of flexible manufacturing systems (FMSs). Due to high degrees of route flexibility and resource sharing, deadlocks often exhibit in FMSs. Manufacturing tasks cannot be finished if any deadlock appears. For solving such problem, this work develops a deadlock-free multiobjective evolutionary algorithm based on decomposition (DMOEA/D). It intends to minimize three objective functions, i.e., makespan, mean flow time, and mean tardiness time. The proposed algorithm can decompose a multiobjective scheduling problem into a certain number of scalar subproblems and solves all the subproblems in a single run. A type of a discrete differential evolution (DDE) algorithm is also developed for solving each subproblem. The mutation operator of the proposed DDE is based on the hamming distance of two randomly selected solutions, while the crossover operator is based on Generalization of Order Crossover. Experimental results demonstrate that the proposed DMOEA/D can significantly outperform a Pareto domination-based algorithm DNSGA-II for both 2-objective and 3-objective problems on the studied FMSs.


---

## Body

## 1. Introduction

Themultiobjective optimization problem (MOP, the abbreviations and their meanings are given in Table 1) is an optimization problem that may have a number of conflicting objectives to be considered, and decision-makers need to determine an optimal trade-off among the objectives. This problem presents in many real-life applications [1–4]. APareto optimal solution to an MOP is a candidate for the optimal trade-off [5]. Most MOPs have a lot of or even an infinite number of Pareto optimal solutions, and the set of all the Pareto optimal solutions in the objective space is called asPareto front (PF). The decision-makers desire a fair approximation to the PF to make final decisions.Multiobjective evolutionary algorithms (MOEAs) work with populations of candidate solutions to MOPs and therefore are able to find good approximations to the PF in a single run.Table 1
Descriptions of abbreviations.
Abbreviation
Description
Abbreviation
Description
MOP
Multi-objective optimization problem
DE
Differential evolution
PF
Pareto front
DDE
Discrete differential evolution
MOEA
Multi-objective evolutionary algorithm
GOX
Generalization of order crossover
SPEA2
Improving the strength Pareto evolutionary algorithm
PNS
Petri net for scheduling
NSGA-II
Nondominated sorting genetic algorithm II
DAP
Deadlock avoidance policy
MOEA/D
MOEA based on decomposition
EP
External population
MODTLBO/D
Multi-objective discrete teaching-learning-based optimization with decomposition
S3PRs
Systems of simple sequential processes with resources
IMOEA/D
Improved MOEA/D
DNSGA-II
Deadlock-free NSGA-II
FMS
Flexible manufacturing system
NPS
Number of Pareto solutions
AGV
Automated guided vehicle
MID
Mean ideal distance
PN
Petri net
RAS
Rate of achievement to objectives simultaneouslyTo produce Pareto optimal vectors that are distributed evenly along the PF and therefore can approximate the PF, many MOEAs evaluate the solutions based on Pareto domination like SPEA2 [6] and NSGA-II [7]. Multiobjective evolutionary algorithm based on decomposition (MOEA/D) [8], which decomposes an MOP into a number of single-objective subproblems, is another effective MOEA framework. In an MOEA/D, the objective to each subproblem is a weighted aggregation of some individual objectives. Based on the distances between the weighted aggregation vectors, the neighborhood relationships among the subproblems can be found out. Each subproblem is then solved according to the information mainly from the neighboring subproblems. There are a few significant studies that apply it in dealing with multiobjective problems in different areas. Chen et al. [9] proposed a multiobjective discrete method called MODTLBO/D for solving the community detection problem of complex networks. They adopted a multiobjective decomposition method and introduced a neighbor-based mutation. For multiobjective job shop scheduling problem, Zhao et al. [10] developed an improved multiobjective evolutionary algorithm based on decomposition (IMOEA/D). Experimental results demonstrate that their IMOEA/D can converge better than Pareto dominance-based MOEAs.A flexible manufacturing system (FMS) is a computer-controlled manufacturing system that is comprised of finite resources and can process multitypes of jobs. Different from the traditional production environments such as job shops and flow shops, FMSs often encounter deadlock problems due to high degrees of route flexibility and resource sharing. Once a deadlock appears, the whole or partial system will be indefinitely blocked and cannot finish manufacturing tasks. Developing effective control and scheduling approaches to avoid deadlocks while optimizing the performance of the system is of paramount importance in practice.Scheduling of FMSs contains both deadlock control and optimization of objectives and therefore is more difficult. A few works have been published on this area [4, 11–23]. Most of them involve deadlock problems and some also concerns different optimization objectives such as the back-tracking and distance travel of AGVs [4], AGV’s fleet size [11], and total energy consumption [21, 22]. However, none of them takes multiobjective optimization into consideration.This work addresses the multiobjective scheduling problem of deadlock-prone FMSs for the first time and proposes a deadlock-free multiobjective evolutionary algorithm based on decomposition (DMOEA/D) and Petri net (PN) models. Our DMOEA/D can decompose a multiobjective FMS scheduling problem into several single-objective subproblems and optimizes all the subproblems in a single run by evolving a population of solutions. In each generation, a solution for solving a subproblem is reproduced by a new proposed discrete differential evolution (DDE) algorithm. In DDE, the mutation operator is based on the hamming distance between two randomly selected solutions. The Generalization of Order Crossover (GOX) [24] is used as the crossover operator. Two illustrated examples are used to demonstrate the efficiency of the proposed algorithm. Since there is no work reported for the multiobjective scheduling of FMSs considering deadlock situations, we just compare our proposed DMOEA/D with a NSGA-II based MOEA on these examples.This work presents an effective approach for organizations and production managers to enhance their competitiveness in manufacturing versatile, route-flexible, and time-critical productions concerning two or more different scheduling objectives.The rest of the paper is organized as follows. Section2 introduces the FMSs studied in the paper and their Petri net models and defines the considered multiobjective scheduling problem. Section 3 introduces some basics of MOEA/D and DDE and develops a multiobjective scheduling algorithm based on them. A performance comparison between two developed scheduling algorithms is made, and the experimental results are show in Section 4. Section 5 concludes the paper.


## 2. PN Models of FMSs

PN is a widely used mathematical tool for modeling the dynamic behaviors of FMSs and many other manufacturing systems [15–17, 25–27]. This section briefly introduces some basics of PNs first and then the PN models of FMSs for multiobjective scheduling. For more details of PNs, readers may refer to [28].


### 2.1. Definitions of Petri Nets

LetZ
0
=
{
0,1
,
2
,
…
} and Z
k
=
{
1,2
,
…
,
k
}. A marked PN is a 4-tuple N
=
(
P
,
T
,
F
,
M
0
), whereP is a finite set of places,T is a finite set of transitions, F
⊆
(
P
×
T
)
∪
(
T
×
P
) is the set of directed arcs, and M
0
:
P
→
Z
0 is the initial marking ofN. For a given node x
∈
P
∪
T, its preset is defined as x
•
=
{
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F
} and postset x
•
=
{
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F
}. Given a markingM and a place p
∈
P, denoteM(p) as the number of tokens inp atM. A string α
=
x
1
x
2
⋯
x
k is called apath in the PN, where x
i
∈
P
∪
T and (
x
i
,
x
i
+
1
)
∈
F, i
∈
Z
k
-
1.A transitiont
∈
T is enabled atMif ∀
p
∈
t
•, M
(
p
)
>
0, denoted as M
[
t
>. An enabled transitiont can fire atM, yielding M
′, denoted as M
[
t
>
M
′, where M
′
(
p
)
=
M
(
p
)
-
1, ∀
p
∈
t
•
\
t
•, M
′
(
p
)
=
M
(
p
)
+
1, ∀
p
∈
t
•
\
•
t, and otherwise M
′
(
p
)
=
M
(
p
). A sequence of transitions α
=
t
1
t
2
⋯
t
k is feasible fromM if M
i
[
t
i
>
M
i
+
1 holds for i
∈
Z
k, where M
1
=
M.


### 2.2. Placed Timed PN Models of FMSs

An FMS studied in our work is comprised ofm types of resources, denoted as R
=
{
r
i
,
i
∈
Z
m
}, and is capable to processn types of jobs, denoted as Q
=
{
q
j
,
j
∈
Z
n
}. More definitions and constraints are described as follows:(1)
The number of type-q
j jobs to be processed is φ
(
q
j
), and the total number of jobs is Φ
=
∑
j
∈
Z
n
φ
(
q
j
).
(2)
The capacity of type-r
i resources is denoted asC(r
i), which is a positive integer and marks the maximum jobs that typer
i resources can handle simultaneously.
(3)
A processing route of a type-q
j job, w
k
=
o
k
1
o
k
2
⋯
o
k
l
(
w
k
), is a predefined sequence of operations, wherel(w
k) is the total number of operations in route w
k ando
kl is thelth operation in w
k. A job may be processed on more than one route and can choose its routes while processing. Let Ω
=
{
w
k
∣
k
∈
Z
Ω
} be the set of all processing routes and Ω
j
⊆
Ω be the set of routes for type-q
j jobs, respectively.
(4)
Each operation needs one unit resource, and any two consecutive operations of a job need different resource types. For operationo
kl, letR(o
kl) denote the resource needed for processingo
kl.
(5)
The processing timed(o
kl) for operationo
kl is predefined. Letc(o
kl) denote the completion time ofo
kl.
(6)
No pre-emption is allowed.Now we can establish a PN model for FMS considered in this paper.For type-q
j jobs, leto
js ando
je be two virtual operations representing the storages of raw and processed type-q
j jobs, respectively. Operationso
js ando
je do not need any resource. Then, route w
k with these two fictitious operations for type-q
j jobs can be defined as w
k
=
o
j
s
o
k
1
o
k
2
⋯
o
k
l
(
w
k
)
o
j
e. Identical operations shared by different routes are merged as one operation.A processing routew
k
=
o
j
s
o
k
1
o
k
2
⋯
o
k
l
(
w
k
)
o
j
e in the PN model is modelled as a path of places and transitions a
k
=
p
j
s
t
k
1
p
k
1
t
k
2
p
k
2
⋯
t
k
l
p
k
l
⋯
t
k
l
(
w
k
)
p
k
l
(
w
k
)
t
k
(
l
(
w
k
)
+
1
)
p
j
e, wherep
js andp
je represent operationso
js ando
je, respectively, andp
kl is an operation place that represents operationo
kl;t
kl is a transition that indicates the start ofo
kl and the completion of o
k
(
l
-
1
). A token in operation placep
kl means that operationo
kl of a job is being processed. In these ways, the marked PN model of processing routes for type-q
j jobs is defined as(1)
N
j
=
P
j
∪
p
j
s
,
p
j
e
,
T
j
,
F
j
,
M
j
0where P
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
p
k
1
,
p
k
2
,
…
,
p
k
l
(
w
k
)
}, T
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
t
k
1
,
t
k
2
,
…
,
t
k
(
l
w
k
+
1
)
}, and F
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
(
p
j
s
,
t
k
1
), (
t
k
1
,
p
k
1
),(
p
k
1
,
t
k
2
), …, (
p
k
l
(
w
k
)
,
t
k
(
l
(
w
k
)
+
1
)
), (
t
k
(
l
w
k
+
1
)
,
p
j
e
)
}.M
j0 is the initial marking, where M
j
0
(
p
j
s
)
=
φ
(
q
j
) and M
j
0
(
p
)
=
0, ∀
p
∈
P
j
∪
{
p
j
e
}. InN
j, ∀
t
∈
T
j, |
t
•
|
=
|
•
t
|
=
1. An operation placep is a split place if p
∈
P
j, |
p
•
|
>
1. At a split place, a job is able to choose the processing routes.For type-r
i resources, assign a resource place denoted also byr
i. Tokens inr
i represent the number of available type-r
i resources. LetC(r
i) denote the initial marking ofr
i.DenoteR(p) andP
R as the resource needed by operation placep and the set of all resource places, respectively. Then, in our PN model, add arcs fromR(p) to each transition in •
p denoting the occupation ofR(p), and add arcs from each transition in p
• toR(p) denoting the releasing ofR(p). The set of all arcs related to resource places is denoted asF
R. Then, the marked PN model of our studied FMS can be defined as(2)
N
=
P
∪
P
s
∪
P
f
∪
P
R
,
T
,
F
,
M
0where P
=
∪
j
∈
Z
n
P
j, P
s
=
{
p
j
s
∣
j
∈
Z
n
}, P
f
=
{
p
j
e
∣
j
∈
Z
n
}, T
=
∪
j
∈
Z
n
T
j, F
=
F
Q
∪
F
R, and F
Q
=
∪
j
∈
Z
n
F
j. The initial markingM
0 is defined as M
0
(
p
j
s
)
=
φ
(
q
j
), ∀
p
j
s
∈
P
s; M
0
(
p
)
=
0, ∀
p
∈
P
∪
P
f; and M
0
(
r
i
)
=
C
(
r
i
), ∀
r
i
∈
P
R.In this paper, processing times needed by operations are described by a place-timed PN. Each operation placep is assigned with a time delayd(p), denoting its processing time, d
(
p
)
=
0, ∀
p
∈
P
s
∪
P
f
∪
P
R. Such PN model for an FMS is called PNS [17].Example 1.
Consider an FMS shown in Figure1. It contains four machinesr
1,r
2,r
3, andr
4. Machinesr
1,r
2, andr
4 can hold one job at the same time while machiner
3 can hold two. Then the resource set is R
=
{
r
1
,
r
2
,
r
3
,
r
4
}, with initial markings C
(
r
1
)
=
C
(
r
2
)
=
C
(
r
4
)
=
1, and C
(
r
3
)
=
2. This FMS is able to process two types of jobs,q
1 andq
2. Type-q
1 jobs can be processed sequentially onr
1,r
2, andr
4, or onr
1,r
3, andr
4; while type-q
2 jobs are processed onr
4,r
3, andr
1. Thus, there are two processing routes for type-q
1 jobs, w
1
=
o
1
s
o
11
o
12
o
13
p
1
e and w
2
=
o
1
s
o
21
o
22
o
23
o
1
e, while type-q
2 jobs are processed on one route, w
3
=
o
2
s
o
31
o
32
o
33
o
2
e. Note that o
11
=
o
21 and o
13
=
o
23 are processed on machinesr
1 andr
4, respectively. Then routes w
1 and w
2 can be modelled as w
1
=
p
1
s
t
11
p
11
t
12
p
12
t
13
p
13
t
14
p
1
e and w
2
=
p
1
s
t
11
p
11
t
22
p
22
t
23
p
13
t
14
p
1
e, respectively, while route w
3 is modelled as w
3
=
p
2
s
t
31
p
31
t
32
p
32
t
33
p
33
t
34
p
2
e. Figure 2(a) shows the PN model of this system, in which the jobs of typesq
1andq
2 are to be processed are 2 and 1, respectively.Figure 1
The FMS in Example1.Figure 2
(a) The PNS of an FMS and (b) its deadlock situation.
(a)
(b)When all operations of all jobs are completed, the system reaches its final marking, denoted asM
f, where M
f
(
p
i
e
)
=
M
0
(
p
j
s
) and ∀
p
j
e
∈
P
f; M
f
(
p
)
=
0, ∀
p
∈
P
∪
P
s; and M
f
(
r
i
)
=
C
(
r
i
), ∀
r
i
∈
P
R. A sequence of transitions α is complete and feasible if M
0
[
a
>
M
f. Such a sequence in the PNS is afeasible scheduleto the considered FMS.Note that an improper schedule of a PNS may lead to deadlock situations, and the system can thus never reach its final marking. Consider a reachable markingM
1
=
2
p
22
+
p
31
+
r
1
+
r
2 in Figure 2(b). It is clear that a circular wait for resourcesr
3 andr
4 arises and no transition can be fired.


## 2.1. Definitions of Petri Nets

LetZ
0
=
{
0,1
,
2
,
…
} and Z
k
=
{
1,2
,
…
,
k
}. A marked PN is a 4-tuple N
=
(
P
,
T
,
F
,
M
0
), whereP is a finite set of places,T is a finite set of transitions, F
⊆
(
P
×
T
)
∪
(
T
×
P
) is the set of directed arcs, and M
0
:
P
→
Z
0 is the initial marking ofN. For a given node x
∈
P
∪
T, its preset is defined as x
•
=
{
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F
} and postset x
•
=
{
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F
}. Given a markingM and a place p
∈
P, denoteM(p) as the number of tokens inp atM. A string α
=
x
1
x
2
⋯
x
k is called apath in the PN, where x
i
∈
P
∪
T and (
x
i
,
x
i
+
1
)
∈
F, i
∈
Z
k
-
1.A transitiont
∈
T is enabled atMif ∀
p
∈
t
•, M
(
p
)
>
0, denoted as M
[
t
>. An enabled transitiont can fire atM, yielding M
′, denoted as M
[
t
>
M
′, where M
′
(
p
)
=
M
(
p
)
-
1, ∀
p
∈
t
•
\
t
•, M
′
(
p
)
=
M
(
p
)
+
1, ∀
p
∈
t
•
\
•
t, and otherwise M
′
(
p
)
=
M
(
p
). A sequence of transitions α
=
t
1
t
2
⋯
t
k is feasible fromM if M
i
[
t
i
>
M
i
+
1 holds for i
∈
Z
k, where M
1
=
M.


## 2.2. Placed Timed PN Models of FMSs

An FMS studied in our work is comprised ofm types of resources, denoted as R
=
{
r
i
,
i
∈
Z
m
}, and is capable to processn types of jobs, denoted as Q
=
{
q
j
,
j
∈
Z
n
}. More definitions and constraints are described as follows:(1)
The number of type-q
j jobs to be processed is φ
(
q
j
), and the total number of jobs is Φ
=
∑
j
∈
Z
n
φ
(
q
j
).
(2)
The capacity of type-r
i resources is denoted asC(r
i), which is a positive integer and marks the maximum jobs that typer
i resources can handle simultaneously.
(3)
A processing route of a type-q
j job, w
k
=
o
k
1
o
k
2
⋯
o
k
l
(
w
k
), is a predefined sequence of operations, wherel(w
k) is the total number of operations in route w
k ando
kl is thelth operation in w
k. A job may be processed on more than one route and can choose its routes while processing. Let Ω
=
{
w
k
∣
k
∈
Z
Ω
} be the set of all processing routes and Ω
j
⊆
Ω be the set of routes for type-q
j jobs, respectively.
(4)
Each operation needs one unit resource, and any two consecutive operations of a job need different resource types. For operationo
kl, letR(o
kl) denote the resource needed for processingo
kl.
(5)
The processing timed(o
kl) for operationo
kl is predefined. Letc(o
kl) denote the completion time ofo
kl.
(6)
No pre-emption is allowed.Now we can establish a PN model for FMS considered in this paper.For type-q
j jobs, leto
js ando
je be two virtual operations representing the storages of raw and processed type-q
j jobs, respectively. Operationso
js ando
je do not need any resource. Then, route w
k with these two fictitious operations for type-q
j jobs can be defined as w
k
=
o
j
s
o
k
1
o
k
2
⋯
o
k
l
(
w
k
)
o
j
e. Identical operations shared by different routes are merged as one operation.A processing routew
k
=
o
j
s
o
k
1
o
k
2
⋯
o
k
l
(
w
k
)
o
j
e in the PN model is modelled as a path of places and transitions a
k
=
p
j
s
t
k
1
p
k
1
t
k
2
p
k
2
⋯
t
k
l
p
k
l
⋯
t
k
l
(
w
k
)
p
k
l
(
w
k
)
t
k
(
l
(
w
k
)
+
1
)
p
j
e, wherep
js andp
je represent operationso
js ando
je, respectively, andp
kl is an operation place that represents operationo
kl;t
kl is a transition that indicates the start ofo
kl and the completion of o
k
(
l
-
1
). A token in operation placep
kl means that operationo
kl of a job is being processed. In these ways, the marked PN model of processing routes for type-q
j jobs is defined as(1)
N
j
=
P
j
∪
p
j
s
,
p
j
e
,
T
j
,
F
j
,
M
j
0where P
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
p
k
1
,
p
k
2
,
…
,
p
k
l
(
w
k
)
}, T
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
t
k
1
,
t
k
2
,
…
,
t
k
(
l
w
k
+
1
)
}, and F
j
=
∪
1
≤
k
≤
|
Ω
j
|
{
(
p
j
s
,
t
k
1
), (
t
k
1
,
p
k
1
),(
p
k
1
,
t
k
2
), …, (
p
k
l
(
w
k
)
,
t
k
(
l
(
w
k
)
+
1
)
), (
t
k
(
l
w
k
+
1
)
,
p
j
e
)
}.M
j0 is the initial marking, where M
j
0
(
p
j
s
)
=
φ
(
q
j
) and M
j
0
(
p
)
=
0, ∀
p
∈
P
j
∪
{
p
j
e
}. InN
j, ∀
t
∈
T
j, |
t
•
|
=
|
•
t
|
=
1. An operation placep is a split place if p
∈
P
j, |
p
•
|
>
1. At a split place, a job is able to choose the processing routes.For type-r
i resources, assign a resource place denoted also byr
i. Tokens inr
i represent the number of available type-r
i resources. LetC(r
i) denote the initial marking ofr
i.DenoteR(p) andP
R as the resource needed by operation placep and the set of all resource places, respectively. Then, in our PN model, add arcs fromR(p) to each transition in •
p denoting the occupation ofR(p), and add arcs from each transition in p
• toR(p) denoting the releasing ofR(p). The set of all arcs related to resource places is denoted asF
R. Then, the marked PN model of our studied FMS can be defined as(2)
N
=
P
∪
P
s
∪
P
f
∪
P
R
,
T
,
F
,
M
0where P
=
∪
j
∈
Z
n
P
j, P
s
=
{
p
j
s
∣
j
∈
Z
n
}, P
f
=
{
p
j
e
∣
j
∈
Z
n
}, T
=
∪
j
∈
Z
n
T
j, F
=
F
Q
∪
F
R, and F
Q
=
∪
j
∈
Z
n
F
j. The initial markingM
0 is defined as M
0
(
p
j
s
)
=
φ
(
q
j
), ∀
p
j
s
∈
P
s; M
0
(
p
)
=
0, ∀
p
∈
P
∪
P
f; and M
0
(
r
i
)
=
C
(
r
i
), ∀
r
i
∈
P
R.In this paper, processing times needed by operations are described by a place-timed PN. Each operation placep is assigned with a time delayd(p), denoting its processing time, d
(
p
)
=
0, ∀
p
∈
P
s
∪
P
f
∪
P
R. Such PN model for an FMS is called PNS [17].Example 1.
Consider an FMS shown in Figure1. It contains four machinesr
1,r
2,r
3, andr
4. Machinesr
1,r
2, andr
4 can hold one job at the same time while machiner
3 can hold two. Then the resource set is R
=
{
r
1
,
r
2
,
r
3
,
r
4
}, with initial markings C
(
r
1
)
=
C
(
r
2
)
=
C
(
r
4
)
=
1, and C
(
r
3
)
=
2. This FMS is able to process two types of jobs,q
1 andq
2. Type-q
1 jobs can be processed sequentially onr
1,r
2, andr
4, or onr
1,r
3, andr
4; while type-q
2 jobs are processed onr
4,r
3, andr
1. Thus, there are two processing routes for type-q
1 jobs, w
1
=
o
1
s
o
11
o
12
o
13
p
1
e and w
2
=
o
1
s
o
21
o
22
o
23
o
1
e, while type-q
2 jobs are processed on one route, w
3
=
o
2
s
o
31
o
32
o
33
o
2
e. Note that o
11
=
o
21 and o
13
=
o
23 are processed on machinesr
1 andr
4, respectively. Then routes w
1 and w
2 can be modelled as w
1
=
p
1
s
t
11
p
11
t
12
p
12
t
13
p
13
t
14
p
1
e and w
2
=
p
1
s
t
11
p
11
t
22
p
22
t
23
p
13
t
14
p
1
e, respectively, while route w
3 is modelled as w
3
=
p
2
s
t
31
p
31
t
32
p
32
t
33
p
33
t
34
p
2
e. Figure 2(a) shows the PN model of this system, in which the jobs of typesq
1andq
2 are to be processed are 2 and 1, respectively.Figure 1
The FMS in Example1.Figure 2
(a) The PNS of an FMS and (b) its deadlock situation.
(a)
(b)When all operations of all jobs are completed, the system reaches its final marking, denoted asM
f, where M
f
(
p
i
e
)
=
M
0
(
p
j
s
) and ∀
p
j
e
∈
P
f; M
f
(
p
)
=
0, ∀
p
∈
P
∪
P
s; and M
f
(
r
i
)
=
C
(
r
i
), ∀
r
i
∈
P
R. A sequence of transitions α is complete and feasible if M
0
[
a
>
M
f. Such a sequence in the PNS is afeasible scheduleto the considered FMS.Note that an improper schedule of a PNS may lead to deadlock situations, and the system can thus never reach its final marking. Consider a reachable markingM
1
=
2
p
22
+
p
31
+
r
1
+
r
2 in Figure 2(b). It is clear that a circular wait for resourcesr
3 andr
4 arises and no transition can be fired.


## 3. DMOEA/D for the Scheduling of FMSs

A multiobjective optimization problem (MOP) is formally stated as follows:(3)
M
i
n
i
m
i
z
e
F
x
=
f
1
x
,
f
2
x
,
…
,
f
L
x
T
S
u
b
j
e
c
t
t
o
x
∈
Πwhere Π is the decision (variable) space andf
i(x) is the objective functions, i
∈
Z
L. A feasiblesolution to MOP can be interpreted into a feasible schedule. Then, the multiobjective scheduling problem studied in this paper is to find a feasible solution x
∗ so thatF(x
∗) is as small as possible.MOEA/D solves an MOP problem by decomposing it into several single-objective optimization subproblems and then solves all the subproblems in a single run by evolving a population of solutions [8]. The population in each generation is composed of best found solutions for these subproblems. The neighbourhood relations among the subproblems are calculated according to the distances between their coefficient vectors. In MOEA/D, each subproblem is then solved based on the information of its neighbouring subproblems.There are a few studies using MOEA/D in different areas recently [5, 8–10, 29–31]. In this work, we focus on the multiobjective scheduling of FMSs and propose a novel DMOEA/D by combining MOEA/D and DDE. PNSs are used to model the systems and deadlock controllers are embedded to avoid deadlocks. The varieties of DMOEA/D are described as follows.


### 3.1. Representation, Interpretation, and Reparation

In this paper, a solutionxin DMOEA/D consists of two sections x
=
(
S
r
;
S
o
), whereS
r stores the route information andS
o is a permutation with repetition of all jobs. Letl(w
s) denote the length of route w
s. Then, each jobJ
i appearsl(J
i) times inS
o, wherel(J
i) = max
⁡
{
l
(
w
s
)
∣
w
s
i
s
a
r
o
u
t
e
o
f
j
o
b
J
i
}. Thejth operation ofJ
i is represented as thejthJ
i inS
o, andS
o is uniquely interpreted as a sequence of operations σ
(
S
o
). Thenx is rewritten as x
=
(
S
r
;
σ
(
S
o
)
). By associating each operation to its corresponding transition, a sequence of transitions α
(
x
), which is taken as a schedule in PNS, can be interpreted from solutionx.Example 2.
Reconsider the PNS in Figure1(a). There are three jobs to be processed: two type-q
1 jobs,J
1 andJ
2, and one type-q
2 job,J
3. The type-q
1 jobs have two routes, w
1 and w
2, while type-q
2 job has only one, w
3. Suppose thatJ
1 andJ
2 are processed by routes w
1 and w
2, respectively. Then, S
r
1
=
(
w
1
,
w
2
,
w
3
) can be taken as the first section of a solutionx
1. Note that the route lengthsl(J
i) are 5, 5, and 4, respectively. Thus, we can represent sectionS
o as a permutation with repetition that consists of fiveJ
1’s, fiveJ
2’s, and fourJ
3’s, for example, S
o
1
=
(
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
).Thenx
1 is represented as x
1
=
(
S
r
1
;
S
o
1
)
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
),S
o1 is interpreted as a sequence of operations σ
(
S
o
1
)
=
(
O
11
,
O
12
,
O
31
,
O
21
,
O
32
,
O
33
,
O
13
,
O
22
,
O
14
,
O
23
,
O
24
,
O
25
,
O
15, O
34
), andx
1 is interpreted as a sequence of transitions α
(
x
1
)
=
(
t
11
t
12
,
t
31
,
t
11
,
t
32
,
t
33
,
t
13
,
t
22
,
t
14
,
t
23
,
t
24
,
t
15
,
t
15
,
t
34
), or for more details, α
(
x
1
)
=
(
t
11
[
O
11
]
,
t
12
[
O
12
]
,
t
31
[
O
31
]
,
t
11
[
O
21
]
,
t
32
[
O
32
]
,
t
33
[
O
33
], t
13
[
O
13
]
,
t
22
[
O
22
], t
14
[
O
14
]
,
t
23
[
O
23
]
,
t
24
[
O
24
]
,
t
15
[
O
25
], t
15
[
O
15
], t
34
[
O
34
]
).The sequence of transitions interpreted from a solution may be infeasible and contain deadlock situations. The feasibility of each solution must be examined and the infeasible ones are repaired. There are some works addressing the deadlock problem of FMSs [32–36], and deadlock-free operations of FMSs can thus be guaranteed. In this work, an Amending Algorithm proposed by [17] is used to obtain a feasible sequence of transitions fromM
0 toM
f. This Amending Algorithm is based on the deadlock avoidance policy (DAP) proposed by [34]. An optimal polynomial complexity DAP for S3PRs without ξ-resources is developed by a one-step look-ahead approach; for S3PRs with ξ-resources, a suboptimal DAP is also derived by reducing the net. A deadlock search algorithm is then proposed for prohibiting deadlock situations.


### 3.2. Objective Functions

Three objective functions are used in the work, makespan, mean completion time, and mean tardiness time.For a given solutionx, let α
(
x
)
=
t
1
t
2
⋯
t
n be its corresponding sequence of transitions. Let f
(
t
k
[
O
i
j
]
) be the firing time of transitiont
k andC
i be the completion time of the last operation of jobJ
i. Note that f
(
t
k
[
O
i
j
]
) is also the start time of operationO
ij. According to the predefined operation sequence and the order in a schedule (sequence of transitions), transition t
k
[
O
i
j
]
(
k
∈
Z
n
) can be fired only after transition t
k
-
1 is fired and operation O
i
(
j
-
1
) is completed. Assume that t
k
-
1 corresponds to operationO
uv andt
u corresponds to operation O
i
(
j
-
1
). We have f
(
t
k
[
O
i
j
]
)
=
max
⁡
{
f
(
t
k
-
1
[
O
u
v
]
)
,
f
(
t
u
[
O
i
(
j
-
1
)
]
)
+
d
(
O
i
(
j
-
1
)
)
}, and the completion time of jobJ
i can be calculated as C
i
=
f
(
t
v
[
O
i
l
(
J
i
)
]
)
+
d
(
O
i
l
(
J
i
)
), where O
i
l
(
J
i
) is the last processed operation of jobJ
i andt
v corresponds to O
i
l
(
J
i
).The makespanC
m
a
x is the completion time of the last job that leaves the system. A minimum C
m
a
x implies a good utilization of machines. It can be defined as(4)
f
1
x
≡
C
m
a
x
=
max
1
≤
i
≤
Φ
⁡
C
iThe mean completion time is the average completion time of all the jobs, and its definition is(5)
f
2
x
≡
C
¯
=
∑
1
≤
i
≤
Φ
C
i
ΦTardiness time of a job is a time delay after the predefined due time. Jobs completed after the due time may cause compensation for customers and loss of goodwill. LetD
i andT
i be the due time and the tardiness time of jobJ
i, respectively. In this paper,D
i is defined as D
i
=
1.5
×
∑
1
≤
j
≤
l
(
J
i
)
d
(
O
i
j
) andT
i is defined as T
i
=
max
⁡
{
C
i
-
D
i
,
0
}. The mean tardiness time is the average tardiness time of all the jobs, and it can be expressed as(6)
f
3
x
≡
T
¯
=
∑
1
≤
i
≤
Φ
T
i
Φ


### 3.3. Decomposition of Multiobjective Optimization

A general MOEA/D must decompose an MOP intoK single-objective optimization problems, whereKis the population size. Several approaches have been proposed for this task and this paper uses the Tchebycheff approach.Given a weight vectorλ
=
(
λ
1
,
λ
2
,
…
,
λ
L
)
T, λ
i
≥
0, ∀
i
∈
Z
L, and ∑
i
∈
Z
L
λ
i
=
1. Then, in the Tchebycheff approach, the optimal solution to the single-objective optimization problem below(7)
M
i
n
i
m
i
z
e
g
t
e
x
∣
λ
=
max
i
∈
Z
L
⁡
λ
i
f
i
x
-
z
i
∗
T
S
u
b
j
e
c
t
t
o
x
∈
Πis a Pareto optimal solution to (3), where z
∗
=
(
z
1
∗
,
z
2
∗
,
…
,
z
L
∗
)
T is the reference point, i.e., z
i
∗
=
m
i
n
x
∈
Π
f
i
x
,
∀
i
∈
Z
L. For each optimal solution of (7), there exists a corresponding Pareto optimal solution of (3). Hence, we can obtain different Pareto optimal solutions by setting different weight vectors.


### 3.4. Discrete Differential Evolution Algorithm

Differential evolution (DE) [37] generally works on a population of candidate solutions, which are represented by floating point numbers. DE generates a mutated solution by adding a weighted difference between two randomly selected solutions to a third one. A trial solution is then generated by crossing the mutated and target solutions. The selection operator in DE determines whether the target solution can be retained in the next generation or not.From the description above, it can be known that the traditional DE cannot be directly used in the multiobjective scheduling of FMSs, since it is originally designed for solving continuous optimization problems and can only generate solutions of floating point numbers [38]. In this subsection, we propose a novel discrete DE (DDE) for generating the solutions to the single-objective optimization problems in our DMOEA/D.The mutated solution at thekth generation x
k
v is constructed based on 3 randomly selected solutions, x
k
a, x
k
b, and x
k
c. LetD denote the hamming distance between solutions x
k
b and x
k
c. In our DDE, the mutation operator is defined as follows:(8)
x
k
v
=
M
u
t
1
x
k
a
,
p
m
,
i
f
D
=
0
M
u
t
D
x
k
a
,
p
m
,
i
f
D
>
0whereMut
i is the mutation withi iterations andp
m is the mutation probability. At each iteration of M
u
t
i
(
x
k
a
,
p
m
), the algorithm generates a random number r
∈
[
0,1
]. If r
<
p
m, select one job in x
k
a randomly and insert it to another position in x
k
a; otherwise, x
k
a remains unchanged. Note that the mutation operator is iterated at least once, even if there is no difference between x
k
b and x
k
c.The trial solutionx
k
u in DDE algorithm is generated by crossing the target solution x
k
i and the mutated solution x
k
v. GOX is used for achieving this. In our DDE, GOX is only applied in the second section of the solution, i.e.,S
o. The length of the crossover string is chosen randomly between N
/
4 and 3
N
/
4.Example 3.
Assume thatx
1
=
(
S
r
1
;
S
o
1
)
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
) is a target solution and x
2
=
(
S
r
2
;
S
o
2
)
=
(
w
1
,
w
1
,
w
3
;
J
1
,
J
2
,
J
2
,
J
1
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
1
,
J
2
,
J
3
) is a mutated solution. Then, according to Section 3.1, their corresponding sequences of operations are σ
(
S
o
1
)
=
(
O
11
,
O
12
,
O
31
,
O
21
,
O
32
,
O
33
,
O
13
,
O
22
,
O
14
,
O
23
,
O
24
,
O
25
,
O
15, O
34
) and σ
(
S
o
2
)
=
(
O
11
,
O
21
,
O
22
,
O
12
,
O
31
,
O
13
,
O
23
,
O
32
,
O
24, O
14, O
33
,
O
15
,
O
25
,
O
34
), respectively. Let the length of a crossover string be 7 and the crossover starts at operationO
31. So the crossover string in S
o
2 is σ
′
=
(
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
) and the corresponding operations areO
31,O
13,O
23,O
32,O
24,O
14, andO
33. Then, delete the jobs that correspond to these operations from S
o
1 and insert σ
′ into S
o
1. The so obtained S
o
3 is (
J
1
,
J
1
,
J
2
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
2
,
J
2
,
J
1
,
J
3
). The first section of the trial solution is inherited directly fromx
1. Then, we have the trial solution x
k
u
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
2
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
2
,
J
2
,
J
1
,
J
3
). Note that the obtained trial solution x
k
u is infeasible and hence should be repaired by Amending Algorithm.
The selection operator in DDE decides whether a trial solutionx
k
u should be a member of the population in the next generation. It is stated as follows:(9)
x
k
i
=
x
k
u
,
i
f
g
t
e
x
k
u
∣
λ
,
z
≤
g
t
e
x
k
-
1
i
∣
λ
,
z
x
k
-
1
i
,
o
t
h
e
r
w
i
s
ewhere z
=
(
z
1
,
z
2
,
…
,
z
L
)
T andz
i is the best objectivef
i found so far.


### 3.5. Framework of DMOEA/D

Letλ
1
,
λ
2
,
…
,
λ
K be a set of uniform spread weight vectors. DMOEA/D decomposes MOP intoK single-objective subproblems with the Tchebycheff approach, and thejth subproblem is(10)
M
i
n
i
m
i
z
e
g
t
e
x
∣
λ
j
,
z
∗
=
max
i
∈
Z
L
⁡
λ
i
j
f
i
x
-
z
i
∗
T
S
u
b
j
e
c
t
t
o
x
∈
Πwhere λ
j
=
(
λ
1
j
,
λ
1
j
,
…
,
λ
i
j
)
T. Given a weight vector λ
j, define the neighbourhood of λ
j as a set of its closest weight vectors in {
λ
1
,
λ
2
,
…
,
λ
K
}. Then, all the subproblems that correspond to these weight vectors in the neighbourhood of λ
j constitute the neighbourhood of thejth subproblem. The population contains the best found solutions for all the subproblems. While DMOEA/D optimizes a subproblem, it only exploits the current solutions to the neighbourhood of the subproblem.In each generation, our proposed DMOEA/D using a Tchebycheff approach contains a population ofK solutions x
1
,
…
,
x
K
∈
Π, wherex
j is the current solution to thejth subproblem and an external population (EP) for storing nondominated solutions found in DMOEA/D. Then, our proposed DMOEA/D can be stated as in Algorithm 1.Algorithm 1:Algorithm DMOEA/D.
Input
K: the number of sub-problems used in DMOEA/D;
λ
1
,
λ
2
,
…
,
λ
K: the set of uniform spread weight vectors;
H: the size of neighborhood of each weight vector;
Initialize
SetE
P
=
⌀, initialize population x
1
,
…
,
x
K
∈
Π;
SetF
j
=
F
(
x
j
), j
∈
Z
K, initialize z
=
(
z
1
,
z
2
,
…
,
z
L
)
T, where z
i
=
m
i
n
x
∈
Π
f
i
x;
Compute the Euclidean distances between any two weight vectors and figure out theH closest ones of each weight vector;
SetE
(
j
)
=
{
j
1
,
j
2
,
…
,
j
H
}, where λ
j
1
,
λ
j
2
,
…
,
λ
j
H are the H closest weight vectors to λ
j.
While(the stopping criterion is not met)
For
(
j
=
1,2
,
…
,
K
)
Randomly select three different neighborsx
a, x
b, and x
c from E(j);
Generate the mutated solutionx
v from x
a, x
b, and x
c;
Generate the trial solutionx
u from x
j andx
v; Amend x
u;
For
(
i
=
1,2
,
…
,
L
)
If
(
z
i
<
f
i
(
x
u
)
)
Setz
i
=
f
i
(
x
u
);
// End For
For (each index j
h
∈
E
(
j
))
If(g
t
e
(
x
u
∣
λ
j
h
,
z
)
≤
g
t
e
(
x
j
h
∣
λ
j
h
,
z
))
Setx
j
h
=
x
u; F
j
h
=
F
(
x
u
);
// End For
Remove all the vectors dominated byF(x
u) from EP;
If(there is no vector dominates F(x
u) and F(x
u) do not exist in EP)
AddF(x
u) into EP;
// End For
// End While
Output EPFrom the algorithm, it can be known thatE(j) contains the indexes ofH closest vectors of λ
j. This paper uses the Euclidean distance to evaluate how close any two weight vectors are. Hence, λ
j itself is its closest vector, j
∈
E
(
j
). Thekth subproblem is in the neighbourhood of thejth subproblem if k
∈
E
(
j
). While considering thejth subproblem in DMOEA/D, sincex
a,x
b, andx
c are the best found solutions to the respective neighbours of thejth subproblem, the reproduced solutionx
u based on them should be a promising one to thejth subproblem. Then, amendx
u by using Amending Algorithm [17]. The so-obtained solutionx
u is therefore feasible and probably better for the neighbours of thejth subproblem. Then, for each neighbourj
h of thejth subproblem, replace x
j
h withx
u ifx
u is better for thejth subproblem. The external population EP is also updated based on the new solutions.Since obtaining the accurate reference pointz
∗ is usually very time-consuming, we usez as a substitute of z
∗ in g
t
e.z is initialized by a problem-specific method and updated according to the quality of generated trial solutions.


## 3.1. Representation, Interpretation, and Reparation

In this paper, a solutionxin DMOEA/D consists of two sections x
=
(
S
r
;
S
o
), whereS
r stores the route information andS
o is a permutation with repetition of all jobs. Letl(w
s) denote the length of route w
s. Then, each jobJ
i appearsl(J
i) times inS
o, wherel(J
i) = max
⁡
{
l
(
w
s
)
∣
w
s
i
s
a
r
o
u
t
e
o
f
j
o
b
J
i
}. Thejth operation ofJ
i is represented as thejthJ
i inS
o, andS
o is uniquely interpreted as a sequence of operations σ
(
S
o
). Thenx is rewritten as x
=
(
S
r
;
σ
(
S
o
)
). By associating each operation to its corresponding transition, a sequence of transitions α
(
x
), which is taken as a schedule in PNS, can be interpreted from solutionx.Example 2.
Reconsider the PNS in Figure1(a). There are three jobs to be processed: two type-q
1 jobs,J
1 andJ
2, and one type-q
2 job,J
3. The type-q
1 jobs have two routes, w
1 and w
2, while type-q
2 job has only one, w
3. Suppose thatJ
1 andJ
2 are processed by routes w
1 and w
2, respectively. Then, S
r
1
=
(
w
1
,
w
2
,
w
3
) can be taken as the first section of a solutionx
1. Note that the route lengthsl(J
i) are 5, 5, and 4, respectively. Thus, we can represent sectionS
o as a permutation with repetition that consists of fiveJ
1’s, fiveJ
2’s, and fourJ
3’s, for example, S
o
1
=
(
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
).Thenx
1 is represented as x
1
=
(
S
r
1
;
S
o
1
)
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
),S
o1 is interpreted as a sequence of operations σ
(
S
o
1
)
=
(
O
11
,
O
12
,
O
31
,
O
21
,
O
32
,
O
33
,
O
13
,
O
22
,
O
14
,
O
23
,
O
24
,
O
25
,
O
15, O
34
), andx
1 is interpreted as a sequence of transitions α
(
x
1
)
=
(
t
11
t
12
,
t
31
,
t
11
,
t
32
,
t
33
,
t
13
,
t
22
,
t
14
,
t
23
,
t
24
,
t
15
,
t
15
,
t
34
), or for more details, α
(
x
1
)
=
(
t
11
[
O
11
]
,
t
12
[
O
12
]
,
t
31
[
O
31
]
,
t
11
[
O
21
]
,
t
32
[
O
32
]
,
t
33
[
O
33
], t
13
[
O
13
]
,
t
22
[
O
22
], t
14
[
O
14
]
,
t
23
[
O
23
]
,
t
24
[
O
24
]
,
t
15
[
O
25
], t
15
[
O
15
], t
34
[
O
34
]
).The sequence of transitions interpreted from a solution may be infeasible and contain deadlock situations. The feasibility of each solution must be examined and the infeasible ones are repaired. There are some works addressing the deadlock problem of FMSs [32–36], and deadlock-free operations of FMSs can thus be guaranteed. In this work, an Amending Algorithm proposed by [17] is used to obtain a feasible sequence of transitions fromM
0 toM
f. This Amending Algorithm is based on the deadlock avoidance policy (DAP) proposed by [34]. An optimal polynomial complexity DAP for S3PRs without ξ-resources is developed by a one-step look-ahead approach; for S3PRs with ξ-resources, a suboptimal DAP is also derived by reducing the net. A deadlock search algorithm is then proposed for prohibiting deadlock situations.


## 3.2. Objective Functions

Three objective functions are used in the work, makespan, mean completion time, and mean tardiness time.For a given solutionx, let α
(
x
)
=
t
1
t
2
⋯
t
n be its corresponding sequence of transitions. Let f
(
t
k
[
O
i
j
]
) be the firing time of transitiont
k andC
i be the completion time of the last operation of jobJ
i. Note that f
(
t
k
[
O
i
j
]
) is also the start time of operationO
ij. According to the predefined operation sequence and the order in a schedule (sequence of transitions), transition t
k
[
O
i
j
]
(
k
∈
Z
n
) can be fired only after transition t
k
-
1 is fired and operation O
i
(
j
-
1
) is completed. Assume that t
k
-
1 corresponds to operationO
uv andt
u corresponds to operation O
i
(
j
-
1
). We have f
(
t
k
[
O
i
j
]
)
=
max
⁡
{
f
(
t
k
-
1
[
O
u
v
]
)
,
f
(
t
u
[
O
i
(
j
-
1
)
]
)
+
d
(
O
i
(
j
-
1
)
)
}, and the completion time of jobJ
i can be calculated as C
i
=
f
(
t
v
[
O
i
l
(
J
i
)
]
)
+
d
(
O
i
l
(
J
i
)
), where O
i
l
(
J
i
) is the last processed operation of jobJ
i andt
v corresponds to O
i
l
(
J
i
).The makespanC
m
a
x is the completion time of the last job that leaves the system. A minimum C
m
a
x implies a good utilization of machines. It can be defined as(4)
f
1
x
≡
C
m
a
x
=
max
1
≤
i
≤
Φ
⁡
C
iThe mean completion time is the average completion time of all the jobs, and its definition is(5)
f
2
x
≡
C
¯
=
∑
1
≤
i
≤
Φ
C
i
ΦTardiness time of a job is a time delay after the predefined due time. Jobs completed after the due time may cause compensation for customers and loss of goodwill. LetD
i andT
i be the due time and the tardiness time of jobJ
i, respectively. In this paper,D
i is defined as D
i
=
1.5
×
∑
1
≤
j
≤
l
(
J
i
)
d
(
O
i
j
) andT
i is defined as T
i
=
max
⁡
{
C
i
-
D
i
,
0
}. The mean tardiness time is the average tardiness time of all the jobs, and it can be expressed as(6)
f
3
x
≡
T
¯
=
∑
1
≤
i
≤
Φ
T
i
Φ


## 3.3. Decomposition of Multiobjective Optimization

A general MOEA/D must decompose an MOP intoK single-objective optimization problems, whereKis the population size. Several approaches have been proposed for this task and this paper uses the Tchebycheff approach.Given a weight vectorλ
=
(
λ
1
,
λ
2
,
…
,
λ
L
)
T, λ
i
≥
0, ∀
i
∈
Z
L, and ∑
i
∈
Z
L
λ
i
=
1. Then, in the Tchebycheff approach, the optimal solution to the single-objective optimization problem below(7)
M
i
n
i
m
i
z
e
g
t
e
x
∣
λ
=
max
i
∈
Z
L
⁡
λ
i
f
i
x
-
z
i
∗
T
S
u
b
j
e
c
t
t
o
x
∈
Πis a Pareto optimal solution to (3), where z
∗
=
(
z
1
∗
,
z
2
∗
,
…
,
z
L
∗
)
T is the reference point, i.e., z
i
∗
=
m
i
n
x
∈
Π
f
i
x
,
∀
i
∈
Z
L. For each optimal solution of (7), there exists a corresponding Pareto optimal solution of (3). Hence, we can obtain different Pareto optimal solutions by setting different weight vectors.


## 3.4. Discrete Differential Evolution Algorithm

Differential evolution (DE) [37] generally works on a population of candidate solutions, which are represented by floating point numbers. DE generates a mutated solution by adding a weighted difference between two randomly selected solutions to a third one. A trial solution is then generated by crossing the mutated and target solutions. The selection operator in DE determines whether the target solution can be retained in the next generation or not.From the description above, it can be known that the traditional DE cannot be directly used in the multiobjective scheduling of FMSs, since it is originally designed for solving continuous optimization problems and can only generate solutions of floating point numbers [38]. In this subsection, we propose a novel discrete DE (DDE) for generating the solutions to the single-objective optimization problems in our DMOEA/D.The mutated solution at thekth generation x
k
v is constructed based on 3 randomly selected solutions, x
k
a, x
k
b, and x
k
c. LetD denote the hamming distance between solutions x
k
b and x
k
c. In our DDE, the mutation operator is defined as follows:(8)
x
k
v
=
M
u
t
1
x
k
a
,
p
m
,
i
f
D
=
0
M
u
t
D
x
k
a
,
p
m
,
i
f
D
>
0whereMut
i is the mutation withi iterations andp
m is the mutation probability. At each iteration of M
u
t
i
(
x
k
a
,
p
m
), the algorithm generates a random number r
∈
[
0,1
]. If r
<
p
m, select one job in x
k
a randomly and insert it to another position in x
k
a; otherwise, x
k
a remains unchanged. Note that the mutation operator is iterated at least once, even if there is no difference between x
k
b and x
k
c.The trial solutionx
k
u in DDE algorithm is generated by crossing the target solution x
k
i and the mutated solution x
k
v. GOX is used for achieving this. In our DDE, GOX is only applied in the second section of the solution, i.e.,S
o. The length of the crossover string is chosen randomly between N
/
4 and 3
N
/
4.Example 3.
Assume thatx
1
=
(
S
r
1
;
S
o
1
)
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
3
,
J
2
,
J
3
,
J
3
,
J
1
,
J
2
,
J
1
,
J
2
,
J
2
,
J
2
,
J
1
,
J
3
) is a target solution and x
2
=
(
S
r
2
;
S
o
2
)
=
(
w
1
,
w
1
,
w
3
;
J
1
,
J
2
,
J
2
,
J
1
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
1
,
J
2
,
J
3
) is a mutated solution. Then, according to Section 3.1, their corresponding sequences of operations are σ
(
S
o
1
)
=
(
O
11
,
O
12
,
O
31
,
O
21
,
O
32
,
O
33
,
O
13
,
O
22
,
O
14
,
O
23
,
O
24
,
O
25
,
O
15, O
34
) and σ
(
S
o
2
)
=
(
O
11
,
O
21
,
O
22
,
O
12
,
O
31
,
O
13
,
O
23
,
O
32
,
O
24, O
14, O
33
,
O
15
,
O
25
,
O
34
), respectively. Let the length of a crossover string be 7 and the crossover starts at operationO
31. So the crossover string in S
o
2 is σ
′
=
(
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
) and the corresponding operations areO
31,O
13,O
23,O
32,O
24,O
14, andO
33. Then, delete the jobs that correspond to these operations from S
o
1 and insert σ
′ into S
o
1. The so obtained S
o
3 is (
J
1
,
J
1
,
J
2
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
2
,
J
2
,
J
1
,
J
3
). The first section of the trial solution is inherited directly fromx
1. Then, we have the trial solution x
k
u
=
(
w
1
,
w
2
,
w
3
;
J
1
,
J
1
,
J
2
,
J
3
,
J
1
,
J
2
,
J
3
,
J
2
,
J
1
,
J
3
,
J
2
,
J
2
,
J
1
,
J
3
). Note that the obtained trial solution x
k
u is infeasible and hence should be repaired by Amending Algorithm.
The selection operator in DDE decides whether a trial solutionx
k
u should be a member of the population in the next generation. It is stated as follows:(9)
x
k
i
=
x
k
u
,
i
f
g
t
e
x
k
u
∣
λ
,
z
≤
g
t
e
x
k
-
1
i
∣
λ
,
z
x
k
-
1
i
,
o
t
h
e
r
w
i
s
ewhere z
=
(
z
1
,
z
2
,
…
,
z
L
)
T andz
i is the best objectivef
i found so far.


## 3.5. Framework of DMOEA/D

Letλ
1
,
λ
2
,
…
,
λ
K be a set of uniform spread weight vectors. DMOEA/D decomposes MOP intoK single-objective subproblems with the Tchebycheff approach, and thejth subproblem is(10)
M
i
n
i
m
i
z
e
g
t
e
x
∣
λ
j
,
z
∗
=
max
i
∈
Z
L
⁡
λ
i
j
f
i
x
-
z
i
∗
T
S
u
b
j
e
c
t
t
o
x
∈
Πwhere λ
j
=
(
λ
1
j
,
λ
1
j
,
…
,
λ
i
j
)
T. Given a weight vector λ
j, define the neighbourhood of λ
j as a set of its closest weight vectors in {
λ
1
,
λ
2
,
…
,
λ
K
}. Then, all the subproblems that correspond to these weight vectors in the neighbourhood of λ
j constitute the neighbourhood of thejth subproblem. The population contains the best found solutions for all the subproblems. While DMOEA/D optimizes a subproblem, it only exploits the current solutions to the neighbourhood of the subproblem.In each generation, our proposed DMOEA/D using a Tchebycheff approach contains a population ofK solutions x
1
,
…
,
x
K
∈
Π, wherex
j is the current solution to thejth subproblem and an external population (EP) for storing nondominated solutions found in DMOEA/D. Then, our proposed DMOEA/D can be stated as in Algorithm 1.Algorithm 1:Algorithm DMOEA/D.
Input
K: the number of sub-problems used in DMOEA/D;
λ
1
,
λ
2
,
…
,
λ
K: the set of uniform spread weight vectors;
H: the size of neighborhood of each weight vector;
Initialize
SetE
P
=
⌀, initialize population x
1
,
…
,
x
K
∈
Π;
SetF
j
=
F
(
x
j
), j
∈
Z
K, initialize z
=
(
z
1
,
z
2
,
…
,
z
L
)
T, where z
i
=
m
i
n
x
∈
Π
f
i
x;
Compute the Euclidean distances between any two weight vectors and figure out theH closest ones of each weight vector;
SetE
(
j
)
=
{
j
1
,
j
2
,
…
,
j
H
}, where λ
j
1
,
λ
j
2
,
…
,
λ
j
H are the H closest weight vectors to λ
j.
While(the stopping criterion is not met)
For
(
j
=
1,2
,
…
,
K
)
Randomly select three different neighborsx
a, x
b, and x
c from E(j);
Generate the mutated solutionx
v from x
a, x
b, and x
c;
Generate the trial solutionx
u from x
j andx
v; Amend x
u;
For
(
i
=
1,2
,
…
,
L
)
If
(
z
i
<
f
i
(
x
u
)
)
Setz
i
=
f
i
(
x
u
);
// End For
For (each index j
h
∈
E
(
j
))
If(g
t
e
(
x
u
∣
λ
j
h
,
z
)
≤
g
t
e
(
x
j
h
∣
λ
j
h
,
z
))
Setx
j
h
=
x
u; F
j
h
=
F
(
x
u
);
// End For
Remove all the vectors dominated byF(x
u) from EP;
If(there is no vector dominates F(x
u) and F(x
u) do not exist in EP)
AddF(x
u) into EP;
// End For
// End While
Output EPFrom the algorithm, it can be known thatE(j) contains the indexes ofH closest vectors of λ
j. This paper uses the Euclidean distance to evaluate how close any two weight vectors are. Hence, λ
j itself is its closest vector, j
∈
E
(
j
). Thekth subproblem is in the neighbourhood of thejth subproblem if k
∈
E
(
j
). While considering thejth subproblem in DMOEA/D, sincex
a,x
b, andx
c are the best found solutions to the respective neighbours of thejth subproblem, the reproduced solutionx
u based on them should be a promising one to thejth subproblem. Then, amendx
u by using Amending Algorithm [17]. The so-obtained solutionx
u is therefore feasible and probably better for the neighbours of thejth subproblem. Then, for each neighbourj
h of thejth subproblem, replace x
j
h withx
u ifx
u is better for thejth subproblem. The external population EP is also updated based on the new solutions.Since obtaining the accurate reference pointz
∗ is usually very time-consuming, we usez as a substitute of z
∗ in g
t
e.z is initialized by a problem-specific method and updated according to the quality of generated trial solutions.


## 4. Illustrative Examples

To the authors’ knowledge, there is still no work reported for the multiobjective scheduling of deadlock-prone FMSs. Thus, to demonstrate the effectiveness of DMOEA/D, we compare it with a NSGA-II (one of the best known MOEAs) based MOEA. Since the DAP used in Section III-A is also embedded, we rename the compared algorithm as DNSGA-II.The stop criteria of two tested algorithms are all set as 1000 generations. The population size is set asK
=
100. For DMOEA/D, the weight vectors are determined by a parameterI. Each weight vector chooses a value from {
0
/
I
,
1
/
I
,
…
,
I
/
I
} and the number of the weight vectors is K
=
C
I
+
L
-
1
L
-
1. For problems with 2-objective,I is set to 99 since C
99
+
2
-
1
2
-
1
=
K
=
100; for problems with 3-objective,I is set to 13 since C
13
+
3
-
1
3
-
1
=
105
>
K
=
100 and DMOEA/D randomly chooses 100 values out of 105. The number of neighbourhoods is H
=
20. The cross ratep
c and the mutation ratep
m are set as 0.8 and 0.2, respectively. All the algorithms are coded by C++ and simulated on a desktop PC with 3.2 GHz processor and 8 GB memory.


### 4.1. Performance Metrics

The number of Pareto solutions (NPS) obtained in a run is an important metric for MOEA. More Pareto solutions mean more candidate schedules for decision makers and therefore have better performance.Mean ideal distance (MID) evaluates how close the solutions on a PF to the ideal point (often referred to point (0, 0)). It can be defined as(11)
M
I
D
=
∑
1
≤
j
≤
N
P
S
Δ
j
N
P
Swhere Δ
j
=
∑
1
≤
i
≤
L
f
j
i
2 andf
ji is theith objective of thejth Pareto solution. Less value ofMIDindicates better performance.The rate of achievement to objectives simultaneously (RAS) evaluates the closeness of objectives. It can be represented as(12)
R
A
S
=
∑
1
≤
j
≤
N
P
S
∑
1
≤
i
≤
L
f
j
i
/
m
i
n
1
≤
i
≤
L
f
j
i
-
1
N
P
SThe lowerRAS value there is, the better solution quality we have.


### 4.2. Case 1

In this subsection, the FMS example inExample
1 is used to test the performance of the algorithms. The processing time of operations is listed in Table 2. 20 instances (FMS01- FMS20) designed by [39] are tested.Table 2
Processing time of operations for the FMS inExample
1.
q
1
q
2
w
1
w
2
w
3
d(O
11): 25
d(O
21): 25
d(O
31): 26
d(O
12): 23
d(O
22): 20
d(O
32): 21
d(O
13): 27
d(O
23): 27
d(O
33): 24Firstly, we study the 2-objective problem with respect to makespan and mean completion time. The scheduling results of FMS01- FMS20 are shown in Table3. The algorithms make 10 independent runs for each instance, and the metrics are averaged.Table 3
Scheduling results of 2-objective problem (FMS01-FMS20).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
FMS01
2.1
2.0
218.33
199.24
0.80
0.76
FMS02
2.0
2.7
412.45
350.20
0.84
0.79
FMS03
2.3
2.4
657.22
584.42
0.91
0.87
FMS04
2.6
2.6
990.17
875.01
1.04
0.98
FMS05
2.8
3.1
1644.12
1436.08
1.08
1.09
FMS06
2.0
2.3
190.50
165.82
0.57
0.55
FMS07
2.8
3.9
361.71
302.64
0.61
0.57
FMS08
3.3
3.8
602.29
537.69
0.72
0.65
FMS09
3.8
4.2
917.27
827.27
1.05
0.97
FMS10
3.9
4.8
1525.18
1354.03
1.10
1.04
FMS11
2.2
1.9
158.93
132.09
0.55
0.41
FMS12
2.4
2.5
323.24
257.43
0.56
0.58
FMS13
3.1
4.0
568.74
516.87
0.72
0.70
FMS14
4.2
4.6
858.91
779.25
0.88
0.83
FMS15
4.5
4.7
1437.07
1320.08
0.98
1.04
FMS16
1.8
1.8
129.86
118.01
0.52
0.43
FMS17
2.4
3.0
242.64
199.14
0.55
0.54
FMS18
3.0
3.2
547.16
508.87
0.72
0.80
FMS19
3.4
4.2
827.83
753.60
0.90
0.92
FMS20
3.6
4.3
1358.92
1182.49
0.97
0.99From Table3, it can be seen that DMOEA/D outperforms DNSGA-II on all 3 metrics for the 2-objective problem. DMOEA/D achieves moreNPSin 16 instances out of 20. This means that DMOEA/D can obtain more Pareto solutions than DNSGA-II for the studied problem. For the metricMID, DMOEA/D significantly outperforms DNSGA-II since it obtains lessMID values for all 20 instances. This indicates that DMOEA/D gets a better convergence than DNSGA-II. For the metricRAS, it seems that the solutions of DMOEA/D have better closeness of objectives as it obtains lowerRASvalues than DNSGA-II in 17 instances out of 20.Figure3 shows a part of nondominated solutions of 2-objective on FMS02-FMS05. We can see that most solutions found by DMOEA/D dominate the ones found by DNSGA-II. DMOEA/D achieves a better approximation to PF than DNSGA-II does.Figure 3
Nondominated solutions of 2-objective problem on instances FMS07-FMS10.Then, the 3-objective problem is studied. The scheduling results are listed in Table4. Each instance makes 10 independent runs and the metrics are averaged.Table 4
Scheduling results of 3-objective problem (FMS01-FMS20).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
FMS01
3.2
4.4
246.15
218.61
10.47
8.54
FMS02
3.9
5.5
486.50
423.76
4.42
2.18
FMS03
4.3
4.1
812.69
703.04
1.89
1.41
FMS04
4.5
4.7
1184.47
1035.12
2.24
1.79
FMS05
4.4
5.2
1982.92
1802.27
2.37
2.02
FMS06
3.5
4.8
207.96
174.29
21.26
19.82
FMS07
4.5
5.0
398.74
341.40
3.10
2.87
FMS08
4.4
6.3
739.06
621.45
1.92
1.27
FMS09
5.8
5.9
1115.63
965.83
2.01
1.61
FMS10
5.5
6.0
1870.84
1685.44
2.24
1.96
FMS11
3.3
2.5
170.02
137.77
30.36
28.23
FMS12
3.5
3.6
320.57
263.89
3.72
3.47
FMS13
3.9
4.9
671.11
589.06
1.82
1.08
FMS14
5.8
6.0
1054.72
946.01
1.87
1.62
FMS15
5.7
6.2
1759.81
1594.49
2.19
1.94
FMS16
2.2
2.6
144.56
112.42
40.66
41.47
FMS17
3.2
2.5
247.30
191.23
12.02
10.76
FMS18
4.0
4.8
617.54
542.48
1.14
0.93
FMS19
5.1
5.2
977.95
856.20
2.06
1.47
FMS20
5.0
5.9
1668.03
1576.65
2.38
2.04As seen in Table4, the results for the 3-objective problem seem in accordance with the conclusions for 2-objective problem. DMOEA/D generally obtains more Pareto solutions (higherNPSvalues in 18 of 20 instances) than DNSGA-II for the studied problem. DMOEA/D also has a better convergence than DNSGA-II, since it obtains lowerMID values in all 20 instances. The solutions obtained by DMOEA/D have better closeness of objectives as it obtains lowerRAS values in 19 instances out of 20.Note that theRAS values of instances with very few jobs (FMS01, FMS06, FMS11, and FMS16) are much higher than the ones of other instances. This is due to the fact that a schedule with very few jobs usually has very little tardiness time, and the objective function mean tardiness time is thus much smaller than the other two.The computational times of DNSGA-II and DMOEA/D on FMS01-FMS20 are almost at the same level. For the 2-objectives problem, the computational times for instances with 10, 20, 40, 60, and 100 jobs are around 5s, 10s, 25s, 40s, and 60s, respectively. For the 3-objectives problem, the computational times for instances with 10, 20, 40, 60, and 100 jobs are around 8s, 15s, 30s, 40s, and 65s, respectively.


### 4.3. Case 2

In this subsection, we use a widely researched FMS example to test the performance of our algorithms. This FMS consists of 3 robotsr
1-r
3, 4 machinesm
1-m
4, and can process 3 types of jobsq
1-q
3. Its PNS with the initial marking of In01 is shown in Figure 4 and the processing time of operations is listed in Table 5. 16 instances (In01-In16) designed by [18] are tested.Table 5
Processing times of operations for the FMS in Figure4.
q
1
q
2
q
3
w
1
w
2
w
3
w
4
d(O
11): 8
d(O
21): 4
d(O
21): 4
d(O
41): 5
d(O
12): 34
d(O
22): 32
d(O
32): 23
d(O
42): 22
d(O
13): 5
d(O
23): 8
d(O
33): 6
d(O
43): 4
d(O
24): 38
d(O
34): 20
d(O
44): 17
d(O
25): 5
d(O
25): 5
d(O
45): 6Figure 4
PNS model of the studied FMS (In01).The 2-objective problem is studied first. The scheduling results of 16 instances are shown in Table6. The algorithms make 10 independent runs for each instance and the metrics are averaged.Table 6
Scheduling results of 2-objective problem (In01-In16).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
In01
1.4
1.6
465.13
384.32
0.69
0.73
In02
1.3
2.0
646.31
563.24
0.81
0.78
In03
1.5
1.7
886.41
752.05
0.99
0.81
In04
1.7
2.1
1089.87
920.63
1.08
0.83
In05
1.4
1.7
396.37
366.64
0.68
0.68
In06
1.6
1.6
526.92
523.22
0.86
0.72
In07
1.5
1.5
691.50
699.44
0.95
0.83
In08
1.5
1.9
882.66
839.75
0.99
0.82
In09
1.6
1.8
339.47
298.18
0.65
0.58
In10
1.5
1.6
476.35
451.60
0.77
0.62
In11
1.7
2.0
585.71
559.66
0.84
0.68
In12
1.6
1.8
719.93
655.98
0.83
0.69
In13
1.4
1.5
328.30
263.18
0.61
0.54
In14
1.6
1.7
465.32
416.40
0.71
0.61
In15
1.6
1.5
550.88
514.23
0.79
0.66
In16
1.7
1.7
687.50
654.51
0.85
0.72From Table6, we can see that DMOEA/D outperforms DNSGA-II on all 3 metrics. It can obtain more Pareto solutions than DNSGA-II in 15 instances out of 16. DMOEA/D also gets a better convergence than DNSGA-II since it obtains lessMID values in 15 instances out of 16. Moreover, the solutions of DMOEA/D have better closeness of objectives than DNSGA-II, since DMOEA/D obtains lowerRAS values in 14 instances out of 16.Figure5 shows a part of nondominated solutions of 2-objective on instances In01-In04. From Figure 5, we can see that the solutions found by DMOEA/D can dominate the ones obtained by DNSGA-II.Figure 5
Non-dominated solutions of 2-objective problem on instances In01-In04.For the 3-objective problem, the scheduling results of In01-In16 are listed in Table7. Each instance makes 10 independent runs and the metrics are averaged.Table 7
Scheduling results of 3-objective problem (In01-In16).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
In01
1.8
2.2
467.16
412.22
4.32
3.53
In02
1.6
1.8
793.22
662.40
3.80
1.98
In03
2.1
2.0
1061.19
847.26
3.52
1.79
In04
2.1
2.1
1299.54
1056.08
3.06
1.43
In05
1.6
1.8
423.02
372.25
4.86
3.08
In06
2.0
2.0
674.95
577.32
4.42
2.06
In07
2.2
2.4
956.23
725.51
3.93
1.90
In08
2.3
2.5
1129.71
909.89
3.69
1.58
In09
1.9
1.9
354.21
319.51
5.23
3.22
In10
2.5
2.6
562.76
460.27
4.97
2.38
In11
1.9
2.1
785.41
636.38
4.48
1.76
In12
2.5
2.8
977.70
761.75
4.01
1.61
In13
2.1
1.8
309.61
263.67
5.82
4.58
In14
2.3
2.5
500.26
432.11
4.78
2.49
In15
2.5
2.7
729.43
572.32
4.73
2.01
In16
2.1
2.4
891.41
681.56
4.24
1.79As seen in Table7, DMOEA/D obtains more Pareto solutions than DNSGA-II in 11 of 16 instances. DMOEA/D also has a better convergence than DNSGA-II, since it obtains lowerMID values in all 16 instances. The solutions obtained by DMOEA/D have better closeness of objectives since it obtains lowerRAS values in all 16 instances.The computational times of DNSGA-II and DMOEA/D on In01-In16 are almost at the same level. For the 2-objectives problem, the computational times for instances with 28, 40, 50, and 60 jobs are around 20s, 55s, 90s, and 120s, respectively. For the 3-objective problem, the computational times for instances with 28, 40, 50, and 60 jobs are around 25s, 65s, 95s, and 130s, respectively.


## 4.1. Performance Metrics

The number of Pareto solutions (NPS) obtained in a run is an important metric for MOEA. More Pareto solutions mean more candidate schedules for decision makers and therefore have better performance.Mean ideal distance (MID) evaluates how close the solutions on a PF to the ideal point (often referred to point (0, 0)). It can be defined as(11)
M
I
D
=
∑
1
≤
j
≤
N
P
S
Δ
j
N
P
Swhere Δ
j
=
∑
1
≤
i
≤
L
f
j
i
2 andf
ji is theith objective of thejth Pareto solution. Less value ofMIDindicates better performance.The rate of achievement to objectives simultaneously (RAS) evaluates the closeness of objectives. It can be represented as(12)
R
A
S
=
∑
1
≤
j
≤
N
P
S
∑
1
≤
i
≤
L
f
j
i
/
m
i
n
1
≤
i
≤
L
f
j
i
-
1
N
P
SThe lowerRAS value there is, the better solution quality we have.


## 4.2. Case 1

In this subsection, the FMS example inExample
1 is used to test the performance of the algorithms. The processing time of operations is listed in Table 2. 20 instances (FMS01- FMS20) designed by [39] are tested.Table 2
Processing time of operations for the FMS inExample
1.
q
1
q
2
w
1
w
2
w
3
d(O
11): 25
d(O
21): 25
d(O
31): 26
d(O
12): 23
d(O
22): 20
d(O
32): 21
d(O
13): 27
d(O
23): 27
d(O
33): 24Firstly, we study the 2-objective problem with respect to makespan and mean completion time. The scheduling results of FMS01- FMS20 are shown in Table3. The algorithms make 10 independent runs for each instance, and the metrics are averaged.Table 3
Scheduling results of 2-objective problem (FMS01-FMS20).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
FMS01
2.1
2.0
218.33
199.24
0.80
0.76
FMS02
2.0
2.7
412.45
350.20
0.84
0.79
FMS03
2.3
2.4
657.22
584.42
0.91
0.87
FMS04
2.6
2.6
990.17
875.01
1.04
0.98
FMS05
2.8
3.1
1644.12
1436.08
1.08
1.09
FMS06
2.0
2.3
190.50
165.82
0.57
0.55
FMS07
2.8
3.9
361.71
302.64
0.61
0.57
FMS08
3.3
3.8
602.29
537.69
0.72
0.65
FMS09
3.8
4.2
917.27
827.27
1.05
0.97
FMS10
3.9
4.8
1525.18
1354.03
1.10
1.04
FMS11
2.2
1.9
158.93
132.09
0.55
0.41
FMS12
2.4
2.5
323.24
257.43
0.56
0.58
FMS13
3.1
4.0
568.74
516.87
0.72
0.70
FMS14
4.2
4.6
858.91
779.25
0.88
0.83
FMS15
4.5
4.7
1437.07
1320.08
0.98
1.04
FMS16
1.8
1.8
129.86
118.01
0.52
0.43
FMS17
2.4
3.0
242.64
199.14
0.55
0.54
FMS18
3.0
3.2
547.16
508.87
0.72
0.80
FMS19
3.4
4.2
827.83
753.60
0.90
0.92
FMS20
3.6
4.3
1358.92
1182.49
0.97
0.99From Table3, it can be seen that DMOEA/D outperforms DNSGA-II on all 3 metrics for the 2-objective problem. DMOEA/D achieves moreNPSin 16 instances out of 20. This means that DMOEA/D can obtain more Pareto solutions than DNSGA-II for the studied problem. For the metricMID, DMOEA/D significantly outperforms DNSGA-II since it obtains lessMID values for all 20 instances. This indicates that DMOEA/D gets a better convergence than DNSGA-II. For the metricRAS, it seems that the solutions of DMOEA/D have better closeness of objectives as it obtains lowerRASvalues than DNSGA-II in 17 instances out of 20.Figure3 shows a part of nondominated solutions of 2-objective on FMS02-FMS05. We can see that most solutions found by DMOEA/D dominate the ones found by DNSGA-II. DMOEA/D achieves a better approximation to PF than DNSGA-II does.Figure 3
Nondominated solutions of 2-objective problem on instances FMS07-FMS10.Then, the 3-objective problem is studied. The scheduling results are listed in Table4. Each instance makes 10 independent runs and the metrics are averaged.Table 4
Scheduling results of 3-objective problem (FMS01-FMS20).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
FMS01
3.2
4.4
246.15
218.61
10.47
8.54
FMS02
3.9
5.5
486.50
423.76
4.42
2.18
FMS03
4.3
4.1
812.69
703.04
1.89
1.41
FMS04
4.5
4.7
1184.47
1035.12
2.24
1.79
FMS05
4.4
5.2
1982.92
1802.27
2.37
2.02
FMS06
3.5
4.8
207.96
174.29
21.26
19.82
FMS07
4.5
5.0
398.74
341.40
3.10
2.87
FMS08
4.4
6.3
739.06
621.45
1.92
1.27
FMS09
5.8
5.9
1115.63
965.83
2.01
1.61
FMS10
5.5
6.0
1870.84
1685.44
2.24
1.96
FMS11
3.3
2.5
170.02
137.77
30.36
28.23
FMS12
3.5
3.6
320.57
263.89
3.72
3.47
FMS13
3.9
4.9
671.11
589.06
1.82
1.08
FMS14
5.8
6.0
1054.72
946.01
1.87
1.62
FMS15
5.7
6.2
1759.81
1594.49
2.19
1.94
FMS16
2.2
2.6
144.56
112.42
40.66
41.47
FMS17
3.2
2.5
247.30
191.23
12.02
10.76
FMS18
4.0
4.8
617.54
542.48
1.14
0.93
FMS19
5.1
5.2
977.95
856.20
2.06
1.47
FMS20
5.0
5.9
1668.03
1576.65
2.38
2.04As seen in Table4, the results for the 3-objective problem seem in accordance with the conclusions for 2-objective problem. DMOEA/D generally obtains more Pareto solutions (higherNPSvalues in 18 of 20 instances) than DNSGA-II for the studied problem. DMOEA/D also has a better convergence than DNSGA-II, since it obtains lowerMID values in all 20 instances. The solutions obtained by DMOEA/D have better closeness of objectives as it obtains lowerRAS values in 19 instances out of 20.Note that theRAS values of instances with very few jobs (FMS01, FMS06, FMS11, and FMS16) are much higher than the ones of other instances. This is due to the fact that a schedule with very few jobs usually has very little tardiness time, and the objective function mean tardiness time is thus much smaller than the other two.The computational times of DNSGA-II and DMOEA/D on FMS01-FMS20 are almost at the same level. For the 2-objectives problem, the computational times for instances with 10, 20, 40, 60, and 100 jobs are around 5s, 10s, 25s, 40s, and 60s, respectively. For the 3-objectives problem, the computational times for instances with 10, 20, 40, 60, and 100 jobs are around 8s, 15s, 30s, 40s, and 65s, respectively.


## 4.3. Case 2

In this subsection, we use a widely researched FMS example to test the performance of our algorithms. This FMS consists of 3 robotsr
1-r
3, 4 machinesm
1-m
4, and can process 3 types of jobsq
1-q
3. Its PNS with the initial marking of In01 is shown in Figure 4 and the processing time of operations is listed in Table 5. 16 instances (In01-In16) designed by [18] are tested.Table 5
Processing times of operations for the FMS in Figure4.
q
1
q
2
q
3
w
1
w
2
w
3
w
4
d(O
11): 8
d(O
21): 4
d(O
21): 4
d(O
41): 5
d(O
12): 34
d(O
22): 32
d(O
32): 23
d(O
42): 22
d(O
13): 5
d(O
23): 8
d(O
33): 6
d(O
43): 4
d(O
24): 38
d(O
34): 20
d(O
44): 17
d(O
25): 5
d(O
25): 5
d(O
45): 6Figure 4
PNS model of the studied FMS (In01).The 2-objective problem is studied first. The scheduling results of 16 instances are shown in Table6. The algorithms make 10 independent runs for each instance and the metrics are averaged.Table 6
Scheduling results of 2-objective problem (In01-In16).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
In01
1.4
1.6
465.13
384.32
0.69
0.73
In02
1.3
2.0
646.31
563.24
0.81
0.78
In03
1.5
1.7
886.41
752.05
0.99
0.81
In04
1.7
2.1
1089.87
920.63
1.08
0.83
In05
1.4
1.7
396.37
366.64
0.68
0.68
In06
1.6
1.6
526.92
523.22
0.86
0.72
In07
1.5
1.5
691.50
699.44
0.95
0.83
In08
1.5
1.9
882.66
839.75
0.99
0.82
In09
1.6
1.8
339.47
298.18
0.65
0.58
In10
1.5
1.6
476.35
451.60
0.77
0.62
In11
1.7
2.0
585.71
559.66
0.84
0.68
In12
1.6
1.8
719.93
655.98
0.83
0.69
In13
1.4
1.5
328.30
263.18
0.61
0.54
In14
1.6
1.7
465.32
416.40
0.71
0.61
In15
1.6
1.5
550.88
514.23
0.79
0.66
In16
1.7
1.7
687.50
654.51
0.85
0.72From Table6, we can see that DMOEA/D outperforms DNSGA-II on all 3 metrics. It can obtain more Pareto solutions than DNSGA-II in 15 instances out of 16. DMOEA/D also gets a better convergence than DNSGA-II since it obtains lessMID values in 15 instances out of 16. Moreover, the solutions of DMOEA/D have better closeness of objectives than DNSGA-II, since DMOEA/D obtains lowerRAS values in 14 instances out of 16.Figure5 shows a part of nondominated solutions of 2-objective on instances In01-In04. From Figure 5, we can see that the solutions found by DMOEA/D can dominate the ones obtained by DNSGA-II.Figure 5
Non-dominated solutions of 2-objective problem on instances In01-In04.For the 3-objective problem, the scheduling results of In01-In16 are listed in Table7. Each instance makes 10 independent runs and the metrics are averaged.Table 7
Scheduling results of 3-objective problem (In01-In16).
Instances
NPS
MID
RAS
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
DNSGA-II
DMOEA/D
In01
1.8
2.2
467.16
412.22
4.32
3.53
In02
1.6
1.8
793.22
662.40
3.80
1.98
In03
2.1
2.0
1061.19
847.26
3.52
1.79
In04
2.1
2.1
1299.54
1056.08
3.06
1.43
In05
1.6
1.8
423.02
372.25
4.86
3.08
In06
2.0
2.0
674.95
577.32
4.42
2.06
In07
2.2
2.4
956.23
725.51
3.93
1.90
In08
2.3
2.5
1129.71
909.89
3.69
1.58
In09
1.9
1.9
354.21
319.51
5.23
3.22
In10
2.5
2.6
562.76
460.27
4.97
2.38
In11
1.9
2.1
785.41
636.38
4.48
1.76
In12
2.5
2.8
977.70
761.75
4.01
1.61
In13
2.1
1.8
309.61
263.67
5.82
4.58
In14
2.3
2.5
500.26
432.11
4.78
2.49
In15
2.5
2.7
729.43
572.32
4.73
2.01
In16
2.1
2.4
891.41
681.56
4.24
1.79As seen in Table7, DMOEA/D obtains more Pareto solutions than DNSGA-II in 11 of 16 instances. DMOEA/D also has a better convergence than DNSGA-II, since it obtains lowerMID values in all 16 instances. The solutions obtained by DMOEA/D have better closeness of objectives since it obtains lowerRAS values in all 16 instances.The computational times of DNSGA-II and DMOEA/D on In01-In16 are almost at the same level. For the 2-objectives problem, the computational times for instances with 28, 40, 50, and 60 jobs are around 20s, 55s, 90s, and 120s, respectively. For the 3-objective problem, the computational times for instances with 28, 40, 50, and 60 jobs are around 25s, 65s, 95s, and 130s, respectively.


## 5. Conclusions

This paper studies the multiobjective scheduling problem of deadlock-prone FMSs. Combining decomposition approaches and DDE, a novel scheduling algorithm called DMOEA/D is proposed based on the PN model of the studied system. DMOEA/D can decompose a multiobjective scheduling problem into a certain number of single-objective subproblems and solves all the subproblems in a single run. The solutions of the subproblems are reproduced by a new proposed DDE algorithm. The mutation operator of DDE is based on the hamming distance between two selected solutions. GOX is used as the crossover operator. Two benchmark examples are used to test the DMOEA/D. Computational results demonstrate that our proposed DMOEA/D can outperform DNSGA-II for both 2-objective and 3-objective problems on the studied FMSs.The advantage of DMOEA/D over DNSGA-II may attribute to the following:(
1
) DMOEA/D optimizes several single-objective optimization problems rather than directly solving the MOP, and hence the diversity of the population is easier to maintain, and more evenly distributed Pareto solutions can thus be obtained; and (
2
) coevolution mechanism between subproblems is used in DMOEA/D, and, hence, DMOEA/D can converge faster and obtain better Pareto solutions than DNSGA-II.For the future work, one research direction is to introduce other efficient local optimization strategies or heuristics to improve the search capability of the proposed algorithm. Another direction is to extend the proposed method to solve the scheduling problem of FMSs with other objectives or constraints, such as energy consumptions, unreliable resources, and maintenance activities, which may be proved both interesting and useful.



---

*Source: 5734149-2019-06-02.xml*