# An Adapted Firefly Algorithm for Product Development Project Scheduling with Fuzzy Activity Duration

Authors: Minmei Huang; Jijun Yuan; Jing Xiao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Efficient scheduling plays an important role in product development project management, especially for the product development project with fuzzy activity times. In this research a trapezoidal fuzzy number is used to represent fuzzy activity duration, and an improved magnitude of the trapezoidal fuzzy number is adopted for fuzzy time comparison. Firstly, a mathematical model for the scheduling problem with minimizing the project completion time for the product development project is established. Then, an adapted fuzzy firefly algorithm is developed to solve the model. The priority value based coding method is used; the fuzzy parallel schedule generation scheme is adopted to generate feasible solutions, and the brightness comparisons are made before updating fireflies’ locations in the proposed algorithm. Finally, the performance of the proposed algorithm is presented by computational experiments based on PSPLIB benchmarks. An example of resource allocation of an electronic product development project is also used to illustrate the effectiveness and efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

Product development has become a source of competitive advantage for many industries in recent years [1]. In order to bring the new product to the market as early as possible, it is essential to schedule product development project efficiently with the constraints of time, resources, and cost. Because of the uniqueness of new product development project and the influence of uncertainty, the precise prediction of activity duration is difficult. Thus the activity duration is always estimated by experts’ experiences and is usually imprecise. In resource constrained project scheduling problems (RCPSP), time parameters are considered to be deterministic. Thus traditional approaches for RCPSP cannot accommodate product development project in uncertain environment.Some research has been performed on fuzzy resource constrained project scheduling problems. The methods in the literature can be grouped into two categories: the heuristic methods and the artificial intelligence based methods.(
1
) For heuristic methods, traditional critical path method (CPM), plan evaluation, and review technique (PERT) were adopted to solve project scheduling problems with uncertain times without resource constraints [2, 3]. Hapke and Slowinski [4] extended the known priority heuristic method for solving RCPSP with fuzzy time parameters. Bhaskar et al. [5] proposed a heuristic method for resource constrained project scheduling problem with fuzzy activity times. The heuristic method was based on priority rule for parallel schedule generation scheme, and the proposed priority rule was called Schedule Performance Index (SPI). (
2
) For artificial intelligence based methods, Wang [1] proposed the fuzzy beam search algorithm to determine a schedule with the minimum schedule risk, and the start time of each activity was selected to maximize the minimum satisfaction degrees of all temporal constraints. Wang [6] developed a genetic algorithm based on fuzzy set theory for uncertain product development projects. Ke and Liu [7] built three types of fuzzy models to solve the project scheduling problem with fuzzy activity duration and developed a hybrid intelligent algorithm to solve the fuzzy models.The metaheuristics firefly algorithm (FA) inspired from intelligent social behavior of fireflies was recently presented by Yang [8]. Firefly algorithm is one of the biology-derived algorithms and it was proved by Yang [9] that FA is more efficient than particle swarm algorithms when dealing with multimodal functions. The FA has also been applied successfully to nonlinear design problems [10], constrained continuous optimization tasks [11], permutation flowshop scheduling problems [12], and resource constrained project scheduling problems [13, 14]. Yuan [15] proposed a modified firefly algorithm to solve multiobjective constraint optimization problem, and the proposed method was applied to the optimization design of motor product family. Yang [16] developed a multiobjective firefly algorithm (MOFA) for continuous optimization, and Luna et al. [17] applied MOFA to the software project scheduling problem.The objective of this research is to develop an effective method by adapting firefly algorithm to handle product development project scheduling problem with fuzzy activity duration times. The paper is organized as follows. In Section2 fuzzy set theory is used to represent uncertain activity duration; the magnitude of trapezoidal fuzzy number is employed to rank the fuzzy time parameters, and then the mathematical model for the problem is described. Section 3 proposes the fuzzy firefly algorithm, which is based on priority value coding and parallel schedule generation scheme, and an example is used to illustrate the algorithm. Computational experiments on 30 benchmark datasets and an electronic product development project are conducted in Section 4. Finally, Section 5 concludes the paper, and the future research directions are proposed.


## 2. Problem Description

### 2.1. Definition on Fuzzy Activity Duration

For most product development projects, it is difficult to precisely give activity durations. Activity durations are often estimated by human experts and confronted with vague and imprecise judgmental statements [6]. Therefore, fuzzy set theory can be used for estimating the activity times. A trapezoidal membership function can represent the most general form of a fuzzy number. We represent the activity duration with a trapezoidal fuzzy number in this paper.Various definitions for the concept of fuzzy numbers are presented in literature. In this paper two of them are used for fuzzy activity duration.Definition 1 (see [18]).
A fuzzy activity durationA
~ is a fuzzy set like u
:
R
→
[
0,1
] satisfying the following properties:(1)
u is upper semicontinuous;
(2)
u
(
x
)
=
0 if x is outside of interval [
a
,
d
];
(3)
there are real numbersa, b, c, and d such that a
≤
b
≤
c
≤
d and
(i)
u
(
x
) is monotonic increasing on [
a
,
b
];
(ii)
u
(
x
) is monotonic decreasing on [
c
,
d
];
(iii)
u
(
x
)
=
1, b
≤
x
≤
c;
and the membership functionu can be expressed as(1)
u
(
x
)
=
x
-
a
b
-
a
,
a
≤
x
<
b
,
1
,
b
≤
x
<
c
,
d
-
x
d
-
c
,
c
≤
x
<
d
,
0
,
otherwise
.A fuzzy activity duration represented by four real parametersa, b, c, and d can be written as A
~
=
(
a
,
b
,
c
,
d
) and denoted by a trapezoidal (
a
,
b
,
c
,
d
) (see Figure 1).Figure 1
Activity duration represented by trapezoidal fuzzy number.If two fuzzy activity durations are defined asA
~
=
(
a
1
,
b
1
,
c
1
,
d
1
) and B
~
=
(
a
2
,
b
2
,
c
2
,
d
2
), respectively, then the following operations can be expressed asAddition:(2)
A
~
⊕
B
~
=
a
1
+
a
2
,
b
1
+
b
2
,
c
1
+
c
2
,
d
1
+
d
2
.
Subtraction:(3)
A
~
Θ
B
~
=
a
1
-
d
2
,
b
1
-
c
2
,
c
1
-
b
2
,
d
1
-
a
2
.
Maximum:(4)
max
⁡
{
A
~
,
B
~
}
=
max
⁡
a
1
,
a
2
,
max
⁡
b
1
,
b
2
,
max
⁡
c
1
,
c
2
,
max
⁡
d
1
,
d
2
.
Minimum:(5)
min
⁡
{
A
~
,
B
~
}
=
min
⁡
a
1
,
a
2
,
min
⁡
b
1
,
b
2
,
min
⁡
c
1
,
c
2
,
min
⁡
d
1
,
d
2
.Ma et al. [19] proposed another definition called fuzzy number in the parametric form.Definition 2 (see [19]).
A fuzzy activity durationA
~ is a pair (
u
_
,
u
-
) of functions (
u
_
(
r
)
,
u
-
(
r
)
), 0
≤
r
≤
1 which satisfy the following requirements:(1)
u
_
(
r
) is a bounded monotonic increasing left continuous function;
(2)
u
-
(
r
) is a bounded monotonic decreasing left continuous function;
(3)
u
_
(
r
)
≤
u
-
(
r
)
,
0
≤
r
≤
1.The fuzzy trapezoidal number can be represented asA
~
=
(
x
0
,
y
0
,
σ
,
β
), with left fuzziness σ
>
0 and right fuzziness β
>
0, and the membership function is presented as follows:(6)
u
(
x
)
=
x
-
x
0
+
σ
σ
,
x
0
-
σ
≤
x
≤
x
0
,
1
,
x
0
≤
x
≤
y
0
,
y
0
+
β
-
x
β
,
y
0
≤
x
≤
y
0
+
β
,
0
,
otherwise
,and its parametric form is described as follows:(7)
u
_
(
r
)
=
x
0
-
σ
+
σ
r
,
u
-
(
r
)
=
y
0
+
β
-
β
r
,and if x
0
=
y
0 then A
~ is a triangular fuzzy number, denoted by A
~
=
(
x
0
,
σ
,
β
).In this paper, Definition1 is used to express fuzzy activity duration, while in scheduling procedure the fuzzy activity duration is transformed into parametric form by Definition 2 in order to compare the fuzzy times.


### 2.2. Comparison of Fuzzy Times

While solving product development project scheduling problems, it is required to compare fuzzy times to generate a feasible solution. For example, the start time of an activity must be greater than or equal to the maximum finish time of its predecessors. Many methods have been developed to rank fuzzy numbers. For example, Asady and Zendehnam [20] developed a method based on distance minimization. Abbasbandy and Hajjari [21] proposed a method for ranking the trapezoidal fuzzy numbers that can overcome some drawbacks of distance minimization, while there still exit shortcomings in their methods. In this paper an improved magnitude of the trapezoidal fuzzy number proposed by Ezzati et al. [22] is adopted, which is easy to handle and will overcome the above drawbacks.Definition 3 (see [22]).
For a trapezoidal fuzzy timet
~
j
=
x
0
,
y
0
,
σ
,
β with parametric form t
~
j
=
(
u
_
(
r
)
,
u
-
(
r
)
), we define(8)
Mag
t
~
j
=
1
2
∫
0
1
u
_
r
+
u
-
r
+
x
0
+
y
0
f
r
d
r
,
Mag
′
t
~
j
=
1
2
∫
0
1
u
_
′
r
-
u
-
′
r
-
u
_
1
+
u
-
1
d
r
,where the weight functionf
(
r
) is nonnegative and increasing on (
0,1
) with f
(
0
)
=
0, f
(
1
)
=
1, and ∫
0
1
f
(
r
)
d
r
=
1
/
2. Function f
(
r
) can be chosen according to the actual situation. In this paper we use  f
(
r
)
=
r.
For any two trapezoidal fuzzy timest
~
i and t
~
j, the improved magnitude of the trapezoidal fuzzy time t
~
j compared with t
~
i is defined as(9)
R
j
i
t
~
j
,
δ
j
i
=
Mag
t
~
j
+
δ
j
i
Mag
′
t
~
j
,where(10)
δ
j
i
=
0
,
Mag
(
t
~
i
)
≠
Mag
(
t
~
j
)
1
,
Mag
t
~
i
=
Mag
t
~
j
.
And the improved magnitude of the trapezoidal fuzzy timet
~
i compared with t
~
j is defined as R
i
j
(
t
~
j
,
δ
i
j
)
=
Mag
(
t
~
j
)
+
δ
i
j
Mag
′
(
t
~
j
). It is obvious that δ
j
i
=
δ
i
j.
The ranking of these two fuzzy numbers can be defined as(1)
R
i
j
(
t
~
i
,
δ
i
j
)
>
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
≻
t
~
j;
(2)
R
i
j
(
t
~
i
,
δ
i
j
)
<
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
≺
t
~
j;
(3)
R
i
j
(
t
~
i
,
δ
i
j
)
=
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
~
t
~
j.
Then we formulate:t
~
i
⪰
t
~
j, if and only if t
~
i
≻
t
~
j or t
~
i
~
t
~
j; t
~
i
⪯
t
~
j, if and only if t
~
i
≺
t
~
j or t
~
i
~
t
~
j.


### 2.3. Problem Formulation

The product development project scheduling problem can be described as follows. A project can be split inton activities. Because of the technological constraints, there are precedence constraints in activities. Different kinds of resources are required when performing activities. The resources are limited, so the project is resource constrained. We assume in this paper that activities in product development project are single modes; activity durations are represented by trapezoidal fuzzy numbers; preemption is not allowed; only renewable resources are considered. The objective is to minimize the project completion time (makespan). Notation section gives some notations which are used in this paper.The product development project scheduling problem with fuzzy activity duration can be described as follows:(11)
min
⁡
C
~
(12)
s.t.
s
~
1
=
b
~
(13)
c
~
j
=
s
~
j
⊕
t
~
j
,
∀
j
,
j
=
1,2
,
…
,
n
(14)
s
~
j
⪰
max
⁡
h
∈
P
j
c
~
h
,
∀
j
,
j
=
2,3
,
…
,
n
(15)
∑
j
∈
A
t
~
r
j
k
⪯
R
k
,
∀
k
,
k
=
1,2
,
…
,
K
(16)
C
~
=
s
~
n
.In the formulation, the objective function (11) minimizes the project fuzzy makespan. Equation (12) shows that the first activity must start at the project fuzzy ready time. Equation (13) calculates the fuzzy finish time for each activity j. Constraint (14) represents that activity must follow the precedence relationships; that is, the fuzzy start time of activity j should be greater than or equal to the fuzzy finish times of all its predecessors. Constraint (15) forces the total units of resource utilized to be no greater than the available resource capacity for every time period. Equation (16) represents that the fuzzy completion time (makespan) of product development project is the fuzzy start time of the dummy end activity.


## 2.1. Definition on Fuzzy Activity Duration

For most product development projects, it is difficult to precisely give activity durations. Activity durations are often estimated by human experts and confronted with vague and imprecise judgmental statements [6]. Therefore, fuzzy set theory can be used for estimating the activity times. A trapezoidal membership function can represent the most general form of a fuzzy number. We represent the activity duration with a trapezoidal fuzzy number in this paper.Various definitions for the concept of fuzzy numbers are presented in literature. In this paper two of them are used for fuzzy activity duration.Definition 1 (see [18]).
A fuzzy activity durationA
~ is a fuzzy set like u
:
R
→
[
0,1
] satisfying the following properties:(1)
u is upper semicontinuous;
(2)
u
(
x
)
=
0 if x is outside of interval [
a
,
d
];
(3)
there are real numbersa, b, c, and d such that a
≤
b
≤
c
≤
d and
(i)
u
(
x
) is monotonic increasing on [
a
,
b
];
(ii)
u
(
x
) is monotonic decreasing on [
c
,
d
];
(iii)
u
(
x
)
=
1, b
≤
x
≤
c;
and the membership functionu can be expressed as(1)
u
(
x
)
=
x
-
a
b
-
a
,
a
≤
x
<
b
,
1
,
b
≤
x
<
c
,
d
-
x
d
-
c
,
c
≤
x
<
d
,
0
,
otherwise
.A fuzzy activity duration represented by four real parametersa, b, c, and d can be written as A
~
=
(
a
,
b
,
c
,
d
) and denoted by a trapezoidal (
a
,
b
,
c
,
d
) (see Figure 1).Figure 1
Activity duration represented by trapezoidal fuzzy number.If two fuzzy activity durations are defined asA
~
=
(
a
1
,
b
1
,
c
1
,
d
1
) and B
~
=
(
a
2
,
b
2
,
c
2
,
d
2
), respectively, then the following operations can be expressed asAddition:(2)
A
~
⊕
B
~
=
a
1
+
a
2
,
b
1
+
b
2
,
c
1
+
c
2
,
d
1
+
d
2
.
Subtraction:(3)
A
~
Θ
B
~
=
a
1
-
d
2
,
b
1
-
c
2
,
c
1
-
b
2
,
d
1
-
a
2
.
Maximum:(4)
max
⁡
{
A
~
,
B
~
}
=
max
⁡
a
1
,
a
2
,
max
⁡
b
1
,
b
2
,
max
⁡
c
1
,
c
2
,
max
⁡
d
1
,
d
2
.
Minimum:(5)
min
⁡
{
A
~
,
B
~
}
=
min
⁡
a
1
,
a
2
,
min
⁡
b
1
,
b
2
,
min
⁡
c
1
,
c
2
,
min
⁡
d
1
,
d
2
.Ma et al. [19] proposed another definition called fuzzy number in the parametric form.Definition 2 (see [19]).
A fuzzy activity durationA
~ is a pair (
u
_
,
u
-
) of functions (
u
_
(
r
)
,
u
-
(
r
)
), 0
≤
r
≤
1 which satisfy the following requirements:(1)
u
_
(
r
) is a bounded monotonic increasing left continuous function;
(2)
u
-
(
r
) is a bounded monotonic decreasing left continuous function;
(3)
u
_
(
r
)
≤
u
-
(
r
)
,
0
≤
r
≤
1.The fuzzy trapezoidal number can be represented asA
~
=
(
x
0
,
y
0
,
σ
,
β
), with left fuzziness σ
>
0 and right fuzziness β
>
0, and the membership function is presented as follows:(6)
u
(
x
)
=
x
-
x
0
+
σ
σ
,
x
0
-
σ
≤
x
≤
x
0
,
1
,
x
0
≤
x
≤
y
0
,
y
0
+
β
-
x
β
,
y
0
≤
x
≤
y
0
+
β
,
0
,
otherwise
,and its parametric form is described as follows:(7)
u
_
(
r
)
=
x
0
-
σ
+
σ
r
,
u
-
(
r
)
=
y
0
+
β
-
β
r
,and if x
0
=
y
0 then A
~ is a triangular fuzzy number, denoted by A
~
=
(
x
0
,
σ
,
β
).In this paper, Definition1 is used to express fuzzy activity duration, while in scheduling procedure the fuzzy activity duration is transformed into parametric form by Definition 2 in order to compare the fuzzy times.


## 2.2. Comparison of Fuzzy Times

While solving product development project scheduling problems, it is required to compare fuzzy times to generate a feasible solution. For example, the start time of an activity must be greater than or equal to the maximum finish time of its predecessors. Many methods have been developed to rank fuzzy numbers. For example, Asady and Zendehnam [20] developed a method based on distance minimization. Abbasbandy and Hajjari [21] proposed a method for ranking the trapezoidal fuzzy numbers that can overcome some drawbacks of distance minimization, while there still exit shortcomings in their methods. In this paper an improved magnitude of the trapezoidal fuzzy number proposed by Ezzati et al. [22] is adopted, which is easy to handle and will overcome the above drawbacks.Definition 3 (see [22]).
For a trapezoidal fuzzy timet
~
j
=
x
0
,
y
0
,
σ
,
β with parametric form t
~
j
=
(
u
_
(
r
)
,
u
-
(
r
)
), we define(8)
Mag
t
~
j
=
1
2
∫
0
1
u
_
r
+
u
-
r
+
x
0
+
y
0
f
r
d
r
,
Mag
′
t
~
j
=
1
2
∫
0
1
u
_
′
r
-
u
-
′
r
-
u
_
1
+
u
-
1
d
r
,where the weight functionf
(
r
) is nonnegative and increasing on (
0,1
) with f
(
0
)
=
0, f
(
1
)
=
1, and ∫
0
1
f
(
r
)
d
r
=
1
/
2. Function f
(
r
) can be chosen according to the actual situation. In this paper we use  f
(
r
)
=
r.
For any two trapezoidal fuzzy timest
~
i and t
~
j, the improved magnitude of the trapezoidal fuzzy time t
~
j compared with t
~
i is defined as(9)
R
j
i
t
~
j
,
δ
j
i
=
Mag
t
~
j
+
δ
j
i
Mag
′
t
~
j
,where(10)
δ
j
i
=
0
,
Mag
(
t
~
i
)
≠
Mag
(
t
~
j
)
1
,
Mag
t
~
i
=
Mag
t
~
j
.
And the improved magnitude of the trapezoidal fuzzy timet
~
i compared with t
~
j is defined as R
i
j
(
t
~
j
,
δ
i
j
)
=
Mag
(
t
~
j
)
+
δ
i
j
Mag
′
(
t
~
j
). It is obvious that δ
j
i
=
δ
i
j.
The ranking of these two fuzzy numbers can be defined as(1)
R
i
j
(
t
~
i
,
δ
i
j
)
>
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
≻
t
~
j;
(2)
R
i
j
(
t
~
i
,
δ
i
j
)
<
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
≺
t
~
j;
(3)
R
i
j
(
t
~
i
,
δ
i
j
)
=
R
j
i
(
t
~
j
,
δ
j
i
), if and only if t
~
i
~
t
~
j.
Then we formulate:t
~
i
⪰
t
~
j, if and only if t
~
i
≻
t
~
j or t
~
i
~
t
~
j; t
~
i
⪯
t
~
j, if and only if t
~
i
≺
t
~
j or t
~
i
~
t
~
j.


## 2.3. Problem Formulation

The product development project scheduling problem can be described as follows. A project can be split inton activities. Because of the technological constraints, there are precedence constraints in activities. Different kinds of resources are required when performing activities. The resources are limited, so the project is resource constrained. We assume in this paper that activities in product development project are single modes; activity durations are represented by trapezoidal fuzzy numbers; preemption is not allowed; only renewable resources are considered. The objective is to minimize the project completion time (makespan). Notation section gives some notations which are used in this paper.The product development project scheduling problem with fuzzy activity duration can be described as follows:(11)
min
⁡
C
~
(12)
s.t.
s
~
1
=
b
~
(13)
c
~
j
=
s
~
j
⊕
t
~
j
,
∀
j
,
j
=
1,2
,
…
,
n
(14)
s
~
j
⪰
max
⁡
h
∈
P
j
c
~
h
,
∀
j
,
j
=
2,3
,
…
,
n
(15)
∑
j
∈
A
t
~
r
j
k
⪯
R
k
,
∀
k
,
k
=
1,2
,
…
,
K
(16)
C
~
=
s
~
n
.In the formulation, the objective function (11) minimizes the project fuzzy makespan. Equation (12) shows that the first activity must start at the project fuzzy ready time. Equation (13) calculates the fuzzy finish time for each activity j. Constraint (14) represents that activity must follow the precedence relationships; that is, the fuzzy start time of activity j should be greater than or equal to the fuzzy finish times of all its predecessors. Constraint (15) forces the total units of resource utilized to be no greater than the available resource capacity for every time period. Equation (16) represents that the fuzzy completion time (makespan) of product development project is the fuzzy start time of the dummy end activity.


## 3. Fuzzy Firefly Algorithm for Product Development Project Scheduling with Fuzzy Activity Duration

### 3.1. Coding

In the paper a firefly algorithm is adapted to solve the project scheduling problem. The classic firefly algorithm was developed by Yang [8–10], and it was based on the idealized behavior of the flashing characteristics of fireflies. The flashing characteristics can be idealized as follows.(1)
All fireflies are unisex so that one firefly is attracted to other fireflies regardless of their sex.
(2)
Attractiveness is proportional to their brightness; thus for any two flashing fireflies, the less bright one will move towards the brighter one. The attractiveness and brightness of two fireflies decrease as distance between them increases. If no one is brighter than a particular firefly, it moves randomly.
(3)
The brightness or light intensity of a firefly is affected or determined by the landscape of the objective function to be optimized.LetX
=
(
x
i
k
)
pop
×
n
=
X
1
,
X
2
,
…
,
X
pop
T denote pop fireflies in the searching space. Vector X
i denotes the location of firefly i (i
=
1,2
,
…
,
pop) in the population, and X
i can be translated to a possible solution of the scheduling problem. In order to provide an activity sequence satisfying precedence relationships, priority value based real number coding method is employed to represent the firefly location. A firefly location X
i is a priority value list with n entries written as X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
n
), where x
i
k is the priority of activity k
(
k
=
1,2
,
…
,
n
). An example of priority value representation is shown in Table 1. Consider a project with six activities numbered from 1 to 6; the number in the position j of the list represents the priority of activity j. For example, the priority of activity 4 is 0.2. When decoding, the activity with greater priority value will be considered first.Table 1
An example of priority value representation.
Activity numberk
1
2
3
4
5
6
Priority valueX
i
0.1
0.5
0.4
0.2
0.3
0.7


### 3.2. Decoding

Many researchers have concluded that the parallel schedule generation scheme gives generally better results than the serial schedule generation scheme [4]. So in this paper parallel schedule generation scheme is adopted to generate feasible schedule from priority value list. For each firefly at location X
i, the fuzzy parallel schedule generation scheme is described as follows.Step 1 (initialization).
The current fuzzy momentt
~ is set to b
~, the set SA of activities scheduled by time t
~ is set to ϕ, and the temporal set T
~ that stores fuzzy time is set to ϕ.Step 2.
Compose a setE
(
t
~
) of activities which have not been scheduled yet and whose immediate predecessors have been completed by time t
~.Step 3.
Find activitye who has the greatest priority value in the priority list X
i, and for each time period from t
~ to t
~
⊕
t
~
e,if the available renewable resources satisfy the requirements of activitye,
activitye’s fuzzy start time: s
~
e
=
t
~,
activitye’s fuzzy finish time: c
~
e
=
t
~
⊕
t
~
e;
allocate required resources to activitye, update resource availabilities;
insertc
~
e into set T
~;
removee from E
(
t
~
);
inserte into SA;
else, if resource availabilities cannot satisfy the requirements ofe, remove e from E
(
t
~
).Step 4.
IfE
(
t
~
)
≠
ϕ, go to Step 3; else t
~
=
min
⁡
(
T
~
), remove t
~ from T
~, and go to Step 5.Step 5.
If the number of activities in setSA
<
n, go to Step 2; else a feasible schedule is obtained and fuzzy completion time for the project f
(
X
i
)
=
C
~, stop.Note that because the finish times of activities inT
~ are all fuzzy numbers, the fuzzy ranking method called improved magnitude of the trapezoidal fuzzy number described in Section 2.2 is used to select the smallest activity finish time in Step 4.


### 3.3. Brightness and Attractiveness

There are two important issues in the firefly algorithm about brightness and attractiveness. The attractiveness of a firefly is determined by its brightness. As for project scheduling, the objective is to minimize the project completion time. For a firefly at a particular locationX
i, if the objective function f
(
X
i
) for the project decoded by fuzzy parallel schedule generation scheme described in Section 3.2 is greater than others, then the firefly is less bright. The brightness I
(
X
i
) of a firefly at a particular location X
i can be chosen as I
(
X
i
)
∝
1
/
f
(
X
i
). Because the completion time is a fuzzy number, the magnitude of trapezoidal fuzzy number is used to represent the light intensity of firefly i compared with firefly j; that is(17)
I
i
j
X
i
=
1
R
i
j
f
X
i
,
δ
i
j
.The attractiveness varies depending on the distanced
i
j between firefly i and firefly j. Light intensity decreases when the distance increases from its source, and light is also absorbed in the media. As a firefly’s attractiveness is proportional to the light intensity seen by adjacent fireflies, attractiveness function β
(
d
i
j
) of a firefly can be a monotonically decreasing function presented as(18)
β
d
i
j
=
β
0
e
-
γ
d
i
j
,where d
i
j is the distance between firefly i and firefly j, γ is the light absorption coefficient, and β
0 is the attractiveness at d
i
j
=
0. We take β
0
=
1, γ
=
1.


### 3.4. Distance and Movement

Two firefliesi and j at X
i and X
j can be decoded to two schedules with two fuzzy project completion times. The distance between these two fireflies cannot be represented directly by the Cartesian distance. We use the difference between the improved magnitudes of these two fuzzy completion times as the distance d
i
j; that is(19)
d
i
j
=
X
i
-
X
j
=
R
i
j
(
f
(
X
i
)
,
δ
i
j
)
-
R
j
i
(
f
(
X
j
)
,
δ
j
i
)
.IfI
i
j
(
X
i
)
<
I
j
i
(
X
j
), firefly i will be attracted by j, the movement is determined by(20)
X
i
′
=
X
i
+
β
0
e
-
γ
d
i
j
X
j
-
X
i
+
λ
rand
-
1
2
,where vector X
i
′
=
(
x
i
1
′
,
x
i
2
′
,
…
,
x
i
n
′
) is the new location after moving, the second term is determined by the attractiveness, the third term is randomization with the randomization parameter λ and a random number rand drawn uniformly from (0, 1).If fireflyi at X
i is the brightest in the population, then it will move randomly by(21)
X
i
′
=
X
i
+
λ
rand
-
1
2
.


### 3.5. Algorithm Procedure

The procedure of fuzzy firefly algorithm for product development project with fuzzy activity duration is given in Figure2, and described as follows.Figure 2
Procedure of fuzzy firefly algorithm.Step 1 (initialization).
Sett
=
1; generate initial population with the population size pop and the location of firefly i is X
i, i
=
1,2
,
…
,
pop.Step 2 (decoding).
For each firefly at locationX
i, use fuzzy parallel schedule generation scheme to generate a feasible schedule.Step 3 (brightness computation).
For each firefly at locationX
i, calculate Mag
(
f
(
X
i
)
) and Mag
′
(
f
(
X
i
)
) by (8), which will be used in (17) to calculate the firefly’s brightness compared with other fireflies.Step 4 (choosing the optimal solution).
For the brightest firefly in thetth generation, move randomly by (21).Select the brighter position fromX
i and X
i
′ as the optimal solution of the present generation.Step 5 (stopping criteria checking).
Updatet
=
t
+
1.
Ift
≤
maxiteration, go to Step 6.
Else go to Step7.Step 6 (firefly moving).
Every firefly is compared with all the other fireflies in the population except itself. That is, compare fireflyi
(
i
=
1,2
,
…
,
pop
) with firefly j
(
∀
j
=
1,2
,
…
,
pop, and j
≠
i
), if I
i
j
(
X
i
)
<
I
j
i
(
X
j
), move firefly i towards firefly j by (20); update location of firefly i after each movement.
Go to Step2.Step 7.
The optimal solution is found; output the result and stop.


### 3.6. An Example

An example is used to illustrate the method developed in this paper. We consider a project which consists of nine activities and is represented by AON shown in Figure3. The first and the last activities are dummy start and dummy end activities, respectively. Only one kind of renewable resource is considered in this example. The total availability of the resource is 5 units in every moment. The fuzzy project ready time is set to b
~
=
(
0,0
,
0,0
). The corresponding activity information is listed in Table 2.Table 2
Activity parameters.
Act. number
Fuzzy duration
Resource required
1
(0, 0, 0, 0)
0
2
(4, 6, 9, 12)
1
3
(7, 9, 11, 14)
2
4
(6, 8, 10, 12)
4
5
(7, 8, 10, 11)
3
6
(2, 3, 5, 6)
1
7
(5, 7, 8, 10)
4
8
(9, 12, 14, 16)
3
9
(0, 0, 0, 0)
0Figure 3
AON of an example.There are three possible paths from the dummy start to the dummy end node. The paths and their lengths without resource constraints, respectively, arePath 1: 1-2-3-6-8-9, fuzzy path length: (22, 30, 39, 48);
Path 2: 1-2-4-7-8-9, fuzzy path length: (24, 33, 41, 50);
Path 3: 1-2-5-7-8-9, fuzzy path length: (25, 33, 41, 49).Figure4 shows the lengths of the paths. It is clear that Path 1 is the shortest. By the fuzzy ranking method proposed by Abbasbandy and Hajjari [21], the lengths of Path 2 and Path 3 are equal. However, it is evident from Figure 4 that the result is not reasonable. We use the improved magnitude of the trapezoidal fuzzy number, the magnitude of the two paths arethe improved magnitude of path 2:37
+
13
=
50;
the improved magnitude to path 3:37
+
12
=
49.Figure 4
Path length.As50
>
49, (
24,33,41,50
)
≻
(
25,33,41,49
), we know that path 2 is the critical path, and the project completion time without resource constraints is (
24,33,41,50
).When resource constraints are considered, the fuzzy firefly algorithm is used to solve this problem. The population of fireflies ispop
=
4, set maxiteration
=
2, the randomization parameter in (20) and (21) is set to λ
=
0.1. The fuzzy start times and finish times of each activity are listed in Table 3. It shows the project completion time is (31, 42, 52, 64). Figure 5 presents the fuzzy Gantt chart without dummy start and end activities. The resource usage profile for all lower bounds (optimistic case) of α-level activity durations at α
=
1 is calculated and presented in Figure 6.Table 3
Activities’ start times and finish times.
Activity number
Fuzzy start time
Fuzzy finish time
1
(0, 0, 0, 0)
(0, 0, 0, 0)
2
(0, 0, 0, 0)
(4, 6, 9, 12)
3
(4, 6, 9, 12)
(11, 15, 20, 26)
4
(11, 15, 20, 26)
(17, 23, 30, 38)
5
(4, 6, 9, 12)
(11, 14, 19, 23)
6
(11, 15, 20, 26)
(13, 18, 25, 32)
7
(17, 23, 30, 38)
(22, 30, 38, 48)
8
(22, 30, 38, 48)
(31, 42, 52, 64)
9
(31, 42, 52, 64)
(31, 42, 52, 64)Figure 5
Fuzzy Gantt chart for the example project.Figure 6
The resource usage profile atα
=
1 in the optimistic case.


## 3.1. Coding

In the paper a firefly algorithm is adapted to solve the project scheduling problem. The classic firefly algorithm was developed by Yang [8–10], and it was based on the idealized behavior of the flashing characteristics of fireflies. The flashing characteristics can be idealized as follows.(1)
All fireflies are unisex so that one firefly is attracted to other fireflies regardless of their sex.
(2)
Attractiveness is proportional to their brightness; thus for any two flashing fireflies, the less bright one will move towards the brighter one. The attractiveness and brightness of two fireflies decrease as distance between them increases. If no one is brighter than a particular firefly, it moves randomly.
(3)
The brightness or light intensity of a firefly is affected or determined by the landscape of the objective function to be optimized.LetX
=
(
x
i
k
)
pop
×
n
=
X
1
,
X
2
,
…
,
X
pop
T denote pop fireflies in the searching space. Vector X
i denotes the location of firefly i (i
=
1,2
,
…
,
pop) in the population, and X
i can be translated to a possible solution of the scheduling problem. In order to provide an activity sequence satisfying precedence relationships, priority value based real number coding method is employed to represent the firefly location. A firefly location X
i is a priority value list with n entries written as X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
n
), where x
i
k is the priority of activity k
(
k
=
1,2
,
…
,
n
). An example of priority value representation is shown in Table 1. Consider a project with six activities numbered from 1 to 6; the number in the position j of the list represents the priority of activity j. For example, the priority of activity 4 is 0.2. When decoding, the activity with greater priority value will be considered first.Table 1
An example of priority value representation.
Activity numberk
1
2
3
4
5
6
Priority valueX
i
0.1
0.5
0.4
0.2
0.3
0.7


## 3.2. Decoding

Many researchers have concluded that the parallel schedule generation scheme gives generally better results than the serial schedule generation scheme [4]. So in this paper parallel schedule generation scheme is adopted to generate feasible schedule from priority value list. For each firefly at location X
i, the fuzzy parallel schedule generation scheme is described as follows.Step 1 (initialization).
The current fuzzy momentt
~ is set to b
~, the set SA of activities scheduled by time t
~ is set to ϕ, and the temporal set T
~ that stores fuzzy time is set to ϕ.Step 2.
Compose a setE
(
t
~
) of activities which have not been scheduled yet and whose immediate predecessors have been completed by time t
~.Step 3.
Find activitye who has the greatest priority value in the priority list X
i, and for each time period from t
~ to t
~
⊕
t
~
e,if the available renewable resources satisfy the requirements of activitye,
activitye’s fuzzy start time: s
~
e
=
t
~,
activitye’s fuzzy finish time: c
~
e
=
t
~
⊕
t
~
e;
allocate required resources to activitye, update resource availabilities;
insertc
~
e into set T
~;
removee from E
(
t
~
);
inserte into SA;
else, if resource availabilities cannot satisfy the requirements ofe, remove e from E
(
t
~
).Step 4.
IfE
(
t
~
)
≠
ϕ, go to Step 3; else t
~
=
min
⁡
(
T
~
), remove t
~ from T
~, and go to Step 5.Step 5.
If the number of activities in setSA
<
n, go to Step 2; else a feasible schedule is obtained and fuzzy completion time for the project f
(
X
i
)
=
C
~, stop.Note that because the finish times of activities inT
~ are all fuzzy numbers, the fuzzy ranking method called improved magnitude of the trapezoidal fuzzy number described in Section 2.2 is used to select the smallest activity finish time in Step 4.


## 3.3. Brightness and Attractiveness

There are two important issues in the firefly algorithm about brightness and attractiveness. The attractiveness of a firefly is determined by its brightness. As for project scheduling, the objective is to minimize the project completion time. For a firefly at a particular locationX
i, if the objective function f
(
X
i
) for the project decoded by fuzzy parallel schedule generation scheme described in Section 3.2 is greater than others, then the firefly is less bright. The brightness I
(
X
i
) of a firefly at a particular location X
i can be chosen as I
(
X
i
)
∝
1
/
f
(
X
i
). Because the completion time is a fuzzy number, the magnitude of trapezoidal fuzzy number is used to represent the light intensity of firefly i compared with firefly j; that is(17)
I
i
j
X
i
=
1
R
i
j
f
X
i
,
δ
i
j
.The attractiveness varies depending on the distanced
i
j between firefly i and firefly j. Light intensity decreases when the distance increases from its source, and light is also absorbed in the media. As a firefly’s attractiveness is proportional to the light intensity seen by adjacent fireflies, attractiveness function β
(
d
i
j
) of a firefly can be a monotonically decreasing function presented as(18)
β
d
i
j
=
β
0
e
-
γ
d
i
j
,where d
i
j is the distance between firefly i and firefly j, γ is the light absorption coefficient, and β
0 is the attractiveness at d
i
j
=
0. We take β
0
=
1, γ
=
1.


## 3.4. Distance and Movement

Two firefliesi and j at X
i and X
j can be decoded to two schedules with two fuzzy project completion times. The distance between these two fireflies cannot be represented directly by the Cartesian distance. We use the difference between the improved magnitudes of these two fuzzy completion times as the distance d
i
j; that is(19)
d
i
j
=
X
i
-
X
j
=
R
i
j
(
f
(
X
i
)
,
δ
i
j
)
-
R
j
i
(
f
(
X
j
)
,
δ
j
i
)
.IfI
i
j
(
X
i
)
<
I
j
i
(
X
j
), firefly i will be attracted by j, the movement is determined by(20)
X
i
′
=
X
i
+
β
0
e
-
γ
d
i
j
X
j
-
X
i
+
λ
rand
-
1
2
,where vector X
i
′
=
(
x
i
1
′
,
x
i
2
′
,
…
,
x
i
n
′
) is the new location after moving, the second term is determined by the attractiveness, the third term is randomization with the randomization parameter λ and a random number rand drawn uniformly from (0, 1).If fireflyi at X
i is the brightest in the population, then it will move randomly by(21)
X
i
′
=
X
i
+
λ
rand
-
1
2
.


## 3.5. Algorithm Procedure

The procedure of fuzzy firefly algorithm for product development project with fuzzy activity duration is given in Figure2, and described as follows.Figure 2
Procedure of fuzzy firefly algorithm.Step 1 (initialization).
Sett
=
1; generate initial population with the population size pop and the location of firefly i is X
i, i
=
1,2
,
…
,
pop.Step 2 (decoding).
For each firefly at locationX
i, use fuzzy parallel schedule generation scheme to generate a feasible schedule.Step 3 (brightness computation).
For each firefly at locationX
i, calculate Mag
(
f
(
X
i
)
) and Mag
′
(
f
(
X
i
)
) by (8), which will be used in (17) to calculate the firefly’s brightness compared with other fireflies.Step 4 (choosing the optimal solution).
For the brightest firefly in thetth generation, move randomly by (21).Select the brighter position fromX
i and X
i
′ as the optimal solution of the present generation.Step 5 (stopping criteria checking).
Updatet
=
t
+
1.
Ift
≤
maxiteration, go to Step 6.
Else go to Step7.Step 6 (firefly moving).
Every firefly is compared with all the other fireflies in the population except itself. That is, compare fireflyi
(
i
=
1,2
,
…
,
pop
) with firefly j
(
∀
j
=
1,2
,
…
,
pop, and j
≠
i
), if I
i
j
(
X
i
)
<
I
j
i
(
X
j
), move firefly i towards firefly j by (20); update location of firefly i after each movement.
Go to Step2.Step 7.
The optimal solution is found; output the result and stop.


## 3.6. An Example

An example is used to illustrate the method developed in this paper. We consider a project which consists of nine activities and is represented by AON shown in Figure3. The first and the last activities are dummy start and dummy end activities, respectively. Only one kind of renewable resource is considered in this example. The total availability of the resource is 5 units in every moment. The fuzzy project ready time is set to b
~
=
(
0,0
,
0,0
). The corresponding activity information is listed in Table 2.Table 2
Activity parameters.
Act. number
Fuzzy duration
Resource required
1
(0, 0, 0, 0)
0
2
(4, 6, 9, 12)
1
3
(7, 9, 11, 14)
2
4
(6, 8, 10, 12)
4
5
(7, 8, 10, 11)
3
6
(2, 3, 5, 6)
1
7
(5, 7, 8, 10)
4
8
(9, 12, 14, 16)
3
9
(0, 0, 0, 0)
0Figure 3
AON of an example.There are three possible paths from the dummy start to the dummy end node. The paths and their lengths without resource constraints, respectively, arePath 1: 1-2-3-6-8-9, fuzzy path length: (22, 30, 39, 48);
Path 2: 1-2-4-7-8-9, fuzzy path length: (24, 33, 41, 50);
Path 3: 1-2-5-7-8-9, fuzzy path length: (25, 33, 41, 49).Figure4 shows the lengths of the paths. It is clear that Path 1 is the shortest. By the fuzzy ranking method proposed by Abbasbandy and Hajjari [21], the lengths of Path 2 and Path 3 are equal. However, it is evident from Figure 4 that the result is not reasonable. We use the improved magnitude of the trapezoidal fuzzy number, the magnitude of the two paths arethe improved magnitude of path 2:37
+
13
=
50;
the improved magnitude to path 3:37
+
12
=
49.Figure 4
Path length.As50
>
49, (
24,33,41,50
)
≻
(
25,33,41,49
), we know that path 2 is the critical path, and the project completion time without resource constraints is (
24,33,41,50
).When resource constraints are considered, the fuzzy firefly algorithm is used to solve this problem. The population of fireflies ispop
=
4, set maxiteration
=
2, the randomization parameter in (20) and (21) is set to λ
=
0.1. The fuzzy start times and finish times of each activity are listed in Table 3. It shows the project completion time is (31, 42, 52, 64). Figure 5 presents the fuzzy Gantt chart without dummy start and end activities. The resource usage profile for all lower bounds (optimistic case) of α-level activity durations at α
=
1 is calculated and presented in Figure 6.Table 3
Activities’ start times and finish times.
Activity number
Fuzzy start time
Fuzzy finish time
1
(0, 0, 0, 0)
(0, 0, 0, 0)
2
(0, 0, 0, 0)
(4, 6, 9, 12)
3
(4, 6, 9, 12)
(11, 15, 20, 26)
4
(11, 15, 20, 26)
(17, 23, 30, 38)
5
(4, 6, 9, 12)
(11, 14, 19, 23)
6
(11, 15, 20, 26)
(13, 18, 25, 32)
7
(17, 23, 30, 38)
(22, 30, 38, 48)
8
(22, 30, 38, 48)
(31, 42, 52, 64)
9
(31, 42, 52, 64)
(31, 42, 52, 64)Figure 5
Fuzzy Gantt chart for the example project.Figure 6
The resource usage profile atα
=
1 in the optimistic case.


## 4. Computational Experiments

Two experiments are conducted. In the first experiment, we use the proposed method to solve benchmark problems and discuss the results. In the second experiment an electronic product development project scheduling problem proposed by Wang [1] is studied. The algorithm is coded in MATLAB7.8.


### 4.1. Numerical Experiments and Results

In order to test the proposed fuzzy firefly algorithm, we have taken 30 datasets from PSPLIB [23] and generated instances with fuzzy activity duration. The 10 instances are chosen from benchmarkj301, 10 fromj302, and 10 fromj601, respectively. As the activity duration of benchmarks in PSPLIB is deterministic, we use the following method to generate fuzzy activity duration. The deterministic duration can be denoted by t
j, the fuzzy activity duration is denoted by t
~
j
=
a
j
,
b
j
,
c
j
,
d
j, the method to generate fuzzy activity times is as follows:(22)
c
j
=
t
j
,
(23)
a
j
=
floor
rand
t
j
*
1
-
40
%
,
t
j
,
(24)
b
j
=
ceil
rand
t
j
*
1
-
40
%
,
t
j
,
(25)
d
j
=
ceil
rand
t
j
,
t
j
*
1
+
30
%
.Equation (22) sets c
j
=
t
j, that is the pessimistic case of α-level activity duration when α
=
1. Equations (23) and (24) show that a
j and b
j are randomly generated from the interval (
t
j
*
(
1
-
40
%
)
,
t
j
). The floor function is used to generate an integer for a
j, and the lower value is bounded by 1. The ceiling function is used to generate an integer for b
j, and b
j
>
a
j. d
j is randomly generated from the interval (
t
j
,
t
j
*
(
1
+
30
%
)
) and the ceiling function is used to generate an integer for the pessimistic estimation as shown in (25).Though the optimal solutions for problem datasetsj301 andj302 are known and the lower bounds ofj601 problems are also given in PSPLIB, they are solutions for problems with deterministic activity duration. We calculate the critical path lower bounds for problems with fuzzy activity duration without considering resource constraints, denoted by c
~
cplb. The solution obtained by our proposed method is compared with c
~
cplb, the difference from lower bound is denoted by dev and computed as follows:(26)
dev
=
R
c
~
n
,
δ
-
R
c
~
cplb
,
δ
,where R
(
c
~
n
,
δ
) and R
(
c
~
cplb
,
δ
) are the improved magnitudes of the project makespan and the critical path lower bound, respectively.In this paper the parameters for performing fuzzy firefly algorithm were set as follows: population sizepop
=
10, maximum iteration maxiteration
=
10, and the randomization parameter λ
=
0.1. The computational results are shown in Table 4.Table 4
Results for numerical experiments.
Number
Optimal solution or lower bound
Critical path lower boundc
~
cplb
Fuzzy makespanc
~
n
Difference dev.
1
43
(27, 35, 38, 50)
(32, 39, 43, 55)
4.5833
2
47
(31, 38, 42, 52)
(35, 45, 50, 61)
7.3333
3
47
(30, 39, 43, 52)
(35, 46, 51, 62)
7.5000
4
62
(39, 46, 55, 67)
(47, 54, 62, 74)
7.5000
5
39
(22, 26, 31, 43)
(28, 36, 40, 54)
9.3333
6
48
(26, 35, 38, 52)
(33, 42, 49, 61)
8.8333
7
60
(44, 53, 60, 76)
(48, 57, 64, 81)
4.0833
8
53
(38, 47, 53, 68)
(43, 51, 57, 73)
4.1667
9
49
(29, 38, 42, 51)
(35, 45, 51, 63)
8.1667
10
45
(27, 34, 37, 45)
(34, 42, 45, 61)
8.5833
11
38
(26, 32, 34, 44)
(28, 35, 38, 49)
3.5000
12
51
(32, 39, 46, 55)
(37, 44, 51, 62)
5.1667
13
43
(29, 41, 43, 54)
(29, 41, 43, 54)
0
14
43
(27, 38, 42, 52)
(28, 39, 43, 54)
1.0833
15
51
(35, 47, 51, 63)
(35, 47, 51, 63)
0
16
47
(37, 46, 47, 59)
(37, 46, 47, 59)
0
17
47
(31, 38, 47, 57)
(31, 38, 47, 57)
0
18
54
(36, 46, 50, 61)
(41, 49, 55, 70)
4.5000
19
54
(38, 46, 51, 65)
(49, 57, 63, 79)
11.6667
20
43
(30, 36, 41, 52)
(29, 37, 44, 59)
2.1667
21
77
(60, 70, 77, 94)
(62, 74, 83, 100)
4.8333
22
68
(45, 58, 65, 79)
(49, 65, 73, 89)
7.4167
23
68
(44, 60, 67, 85)
(53, 66, 74, 90)
6.5833
24
91
(56, 75, 79, 97)
(67, 85, 93, 115)
12.4167
25
73
(47, 58, 68, 86)
(58, 73, 78, 101)
12.5833
26
66
(32, 46, 52, 67)
(47, 61, 66, 85)
14.8333
27
72
(44, 51, 60, 75)
(55, 69, 77, 97)
17.3333
28
75
(51, 62, 71, 89)
(59, 75, 80, 99)
10.6667
29
85
(56, 65, 75, 89)
(63, 79, 92, 111)
15.3333
30
80
(52, 67, 76, 98)
(59, 75, 84, 104)
7.7500The numbers in column two show the optimal solutions forj30 problems and lower bounds forj60 problems with deterministic activity duration. The third column represents the critical path lower bounds for the problems with trapezoidal fuzzy activity duration. The fourth column represents the best solutions obtained by the proposed fuzzy firefly algorithm. It shows that the third number of the best solution for eleven problems (1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 26) is the same as the optimal solution. For problems 7, 8, 13, 15, 16, 17, and 21, the third number of the critical path lower bounds is the same as optimal solution, which means the resource constraints for these problems are not binding [5]. Our method gains the optimal solutions for problems 13, 15, 16, 17. The fifth column represents the deviations of the best solution from the critical path lower bound. The deviations of the 4 problems discussed above are zeros. The deviations for other problems vary between 1.0833 and 17.3333. It also indicates that the deviation is greater when there are more activities in a project, because the difficulty of solvingj60 is greater than that ofj30.


### 4.2. The Experiment on Electronic Product Development Project

Wang [1] provides an electronic product development project, which consists of 7 phases and is divided into 51 activities. We add dummy start and end activities to the project, and the information of this project is shown in Table 5. The project ready time is b
~
=
(
0,0
,
0,0
). There are 4 types of resources: system engineers, software engineers, hardware engineers, and supporting engineers. The resource availability of each type of resource is 5, 4, 5, 4, respectively.Table 5
Project data for an electronic product development project [1].
Act.number
Fuzzy durationt
~
j
Resource required
SuccessorsS
j
r
j
1
r
j
2
r
j
3
r
j
4
1
(0, 0, 0, 0)
0
0
0
0
2
2
(5, 6, 6, 7)
3
0
0
0
3
3
(10, 12, 12, 13)
5
3
3
2
4, 5
4
(4, 5, 5, 6)
4
2
4
2
6
5
(7, 8, 8, 10)
4
2
2
2
6
6
(2, 4, 4, 6)
5
0
0
0
7
7
(3, 4, 4, 5)
4
2
2
2
8
8
(2, 3, 3, 4)
4
3
3
2
9, 10, 11, 13
9
(2, 3, 3, 5)
0
4
2
0
14
10
(3, 4, 4, 6)
2
1
5
3
15
11
(4, 5, 5, 6)
4
0
0
0
12
12
(7, 9, 9, 10)
5
0
0
0
16
13
(3, 4, 4, 5)
3
0
0
1
16
14
(1, 2, 2, 3)
3
2
0
1
16
15
(1, 2, 2, 3)
3
0
3
2
16
16
(1, 2, 2, 2)
4
2
2
2
17
17
(3, 4, 4, 5)
5
2
2
0
18, 19
18
(4, 5, 5, 6)
5
2
4
2
20
19
(4, 5, 5, 6)
4
2
4
3
20
20
(5, 6, 6, 7)
5
2
3
4
21, 22, 23
21
(5, 7, 7, 9)
4
0
0
0
24
22
(3, 5, 5, 7)
5
1
4
4
24
23
(4, 5, 5, 6)
0
3
0
0
24
24
(1, 2, 2, 3)
5
1
1
1
25
25
(8, 10, 10, 12)
2
1
5
3
26, 27, 28
26
(4, 5, 5, 6)
2
1
5
3
30
27
(4, 6, 6, 8)
0
0
4
3
29
28
(6, 7, 7, 8)
0
4
0
2
30
29
(10, 12, 12, 14)
2
2
4
4
30
30
(1, 2, 2, 4)
4
2
2
2
31, 32, 33, 39, 40, 42
31
(9, 11, 11, 10)
4
2
3
0
34
32
(10, 13, 13, 14)
5
0
3
2
37
33
(8, 10, 10, 11)
0
0
4
2
38
34
(6, 8, 8, 9)
4
3
2
0
35
35
(3, 4, 4, 5)
4
2
3
3
36
36
(4, 6, 6, 7)
2
2
0
4
41
37
(1, 3, 3, 4)
0
0
2
0
41
38
(3, 4, 4, 5)
0
0
2
2
41
39
(1, 2, 2, 3)
1
0
3
1
41
40
(2, 3, 3, 4)
0
0
2
2
41
41
(1, 1, 1, 2)
4
0
4
3
45, 46, 49
42
(3, 4, 4, 5)
0
4
0
0
43
43
(1, 2, 2, 3)
3
3
0
0
44
44
(1, 2, 2, 3)
3
0
3
0
45, 46
45
(3, 4, 4, 5)
2
3
4
1
52
46
(4, 5, 5, 6)
2
2
4
2
47
47
(4, 5, 5, 6)
5
2
2
3
48
48
(3, 4, 4, 5)
2
0
4
2
52
49
(5, 7, 7, 8)
2
0
2
3
50
50
(6, 8, 8, 10)
4
2
3
2
51
51
(2, 3, 3, 5)
4
2
3
3
52
52
(2, 4, 4, 7)
4
2
3
3
53
53
(0, 0, 0, 0)
0
0
0
0
—The proposed fuzzy firefly algorithm is used to solve the electronic product development project. The project makespan obtained by the proposed method is (178, 235, 235, 288), and the fuzzy finish times for the solutions are shown in Table6. Figure 7 shows the resource usage for every type of resource. The utilization rates for system engineers, software engineers, hardware engineers, and supporting engineers are 69.4%, 41.1%, 56.3%, and 51.7%, respectively. Wang’s results show that the project makespan is (180, 239, 239, 294), and the resource utilization rates are 0.69, 0.33, 0.56, and 0.51 [1]. The comparison shows that our method can improve the resource utilization rate of software engineers and finish the project earlier. When considering the allocation of more resources to help complete the project earlier, Wang [1] provides 12 schedules under distinct resource availability. Table 7 shows that our results have the same effect with 3 of the schedules proposed by Wang, which illustrates that our method can allocate resource more effectively, and shorten the makespan without adding more resources to the project.Table 6
Solutions for the electronic product development project.
Act. number
Fuzzy finish timec
~
j
1
(0, 0, 0, 0)
2
(5, 6, 6, 7)
3
(15, 18, 18, 20)
4
(19, 23, 23, 26)
5
(26, 31, 31, 36)
6
(28, 35, 35, 42)
7
(31, 39, 39, 47)
8
(33, 42, 42, 51)
9
(35, 45, 45, 56)
10
(40, 51, 51, 63)
11
(37, 47, 47, 57)
12
(49, 64, 64, 78)
13
(40, 51, 51, 62)
14
(41, 53, 53, 65)
15
(42, 55, 55, 68)
16
(50, 66, 66, 80)
17
(53, 70, 70, 85)
18
(57, 75, 75, 91)
19
(61, 80, 80, 97)
20
(66, 86, 86, 104)
21
(71, 93, 93, 113)
22
(74, 98, 98, 120)
23
(70, 91, 91, 110)
24
(75, 100, 100, 123)
25
(83, 110, 110, 135)
26
(101, 133, 133, 163)
27
(87, 116, 116, 143)
28
(107, 140, 140, 171)
29
(97, 128, 128, 157)
30
(108, 142, 142, 175)
31
(135, 176, 176, 213)
32
(126, 165, 165, 200)
33
(116, 152, 152, 186)
34
(141, 184, 184, 222)
35
(144, 188, 188, 227)
36
(148, 194, 194, 234)
37
(127, 168, 168, 204)
38
(121, 159, 159, 195)
39
(136, 178, 178, 216)
40
(118, 155, 155, 190)
41
(149, 195, 195, 236)
42
(111, 146, 146, 180)
43
(112, 148, 148, 183)
44
(145, 190, 190, 230)
45
(152, 199, 199, 241)
46
(169, 222, 222, 270)
47
(173, 227, 227, 276)
48
(176, 231, 231, 281)
49
(157, 206, 206, 249)
50
(163, 214, 214, 259)
51
(165, 217, 217, 264)
52
(178, 235, 235, 288)
53
(178, 235, 235, 288)Table 7
Comparison of solutions under different resource availabilities.
Resource availability
Fuzzy project makespan
Our result
5 4 5 4
(178, 235, 235, 288)
Wang [1]
5 4 5 4
(180, 239, 239, 294)
Wang [1]
6 4 5 4
(178, 235, 235, 288)
Wang [1]
6 5 5 4
(178, 235, 235, 288)
Wang [1]
5 4 6 5
(178, 235, 235, 288)Figure 7
The resource usage profile for every resource type atα
=
1 in the optimistic case.
(a)
Resource usage for system engineers
(b)
Resource usage for software engineers
(c)
Resource usage for hardware engineers
(d)
Resource usage for supporting engineers


## 4.1. Numerical Experiments and Results

In order to test the proposed fuzzy firefly algorithm, we have taken 30 datasets from PSPLIB [23] and generated instances with fuzzy activity duration. The 10 instances are chosen from benchmarkj301, 10 fromj302, and 10 fromj601, respectively. As the activity duration of benchmarks in PSPLIB is deterministic, we use the following method to generate fuzzy activity duration. The deterministic duration can be denoted by t
j, the fuzzy activity duration is denoted by t
~
j
=
a
j
,
b
j
,
c
j
,
d
j, the method to generate fuzzy activity times is as follows:(22)
c
j
=
t
j
,
(23)
a
j
=
floor
rand
t
j
*
1
-
40
%
,
t
j
,
(24)
b
j
=
ceil
rand
t
j
*
1
-
40
%
,
t
j
,
(25)
d
j
=
ceil
rand
t
j
,
t
j
*
1
+
30
%
.Equation (22) sets c
j
=
t
j, that is the pessimistic case of α-level activity duration when α
=
1. Equations (23) and (24) show that a
j and b
j are randomly generated from the interval (
t
j
*
(
1
-
40
%
)
,
t
j
). The floor function is used to generate an integer for a
j, and the lower value is bounded by 1. The ceiling function is used to generate an integer for b
j, and b
j
>
a
j. d
j is randomly generated from the interval (
t
j
,
t
j
*
(
1
+
30
%
)
) and the ceiling function is used to generate an integer for the pessimistic estimation as shown in (25).Though the optimal solutions for problem datasetsj301 andj302 are known and the lower bounds ofj601 problems are also given in PSPLIB, they are solutions for problems with deterministic activity duration. We calculate the critical path lower bounds for problems with fuzzy activity duration without considering resource constraints, denoted by c
~
cplb. The solution obtained by our proposed method is compared with c
~
cplb, the difference from lower bound is denoted by dev and computed as follows:(26)
dev
=
R
c
~
n
,
δ
-
R
c
~
cplb
,
δ
,where R
(
c
~
n
,
δ
) and R
(
c
~
cplb
,
δ
) are the improved magnitudes of the project makespan and the critical path lower bound, respectively.In this paper the parameters for performing fuzzy firefly algorithm were set as follows: population sizepop
=
10, maximum iteration maxiteration
=
10, and the randomization parameter λ
=
0.1. The computational results are shown in Table 4.Table 4
Results for numerical experiments.
Number
Optimal solution or lower bound
Critical path lower boundc
~
cplb
Fuzzy makespanc
~
n
Difference dev.
1
43
(27, 35, 38, 50)
(32, 39, 43, 55)
4.5833
2
47
(31, 38, 42, 52)
(35, 45, 50, 61)
7.3333
3
47
(30, 39, 43, 52)
(35, 46, 51, 62)
7.5000
4
62
(39, 46, 55, 67)
(47, 54, 62, 74)
7.5000
5
39
(22, 26, 31, 43)
(28, 36, 40, 54)
9.3333
6
48
(26, 35, 38, 52)
(33, 42, 49, 61)
8.8333
7
60
(44, 53, 60, 76)
(48, 57, 64, 81)
4.0833
8
53
(38, 47, 53, 68)
(43, 51, 57, 73)
4.1667
9
49
(29, 38, 42, 51)
(35, 45, 51, 63)
8.1667
10
45
(27, 34, 37, 45)
(34, 42, 45, 61)
8.5833
11
38
(26, 32, 34, 44)
(28, 35, 38, 49)
3.5000
12
51
(32, 39, 46, 55)
(37, 44, 51, 62)
5.1667
13
43
(29, 41, 43, 54)
(29, 41, 43, 54)
0
14
43
(27, 38, 42, 52)
(28, 39, 43, 54)
1.0833
15
51
(35, 47, 51, 63)
(35, 47, 51, 63)
0
16
47
(37, 46, 47, 59)
(37, 46, 47, 59)
0
17
47
(31, 38, 47, 57)
(31, 38, 47, 57)
0
18
54
(36, 46, 50, 61)
(41, 49, 55, 70)
4.5000
19
54
(38, 46, 51, 65)
(49, 57, 63, 79)
11.6667
20
43
(30, 36, 41, 52)
(29, 37, 44, 59)
2.1667
21
77
(60, 70, 77, 94)
(62, 74, 83, 100)
4.8333
22
68
(45, 58, 65, 79)
(49, 65, 73, 89)
7.4167
23
68
(44, 60, 67, 85)
(53, 66, 74, 90)
6.5833
24
91
(56, 75, 79, 97)
(67, 85, 93, 115)
12.4167
25
73
(47, 58, 68, 86)
(58, 73, 78, 101)
12.5833
26
66
(32, 46, 52, 67)
(47, 61, 66, 85)
14.8333
27
72
(44, 51, 60, 75)
(55, 69, 77, 97)
17.3333
28
75
(51, 62, 71, 89)
(59, 75, 80, 99)
10.6667
29
85
(56, 65, 75, 89)
(63, 79, 92, 111)
15.3333
30
80
(52, 67, 76, 98)
(59, 75, 84, 104)
7.7500The numbers in column two show the optimal solutions forj30 problems and lower bounds forj60 problems with deterministic activity duration. The third column represents the critical path lower bounds for the problems with trapezoidal fuzzy activity duration. The fourth column represents the best solutions obtained by the proposed fuzzy firefly algorithm. It shows that the third number of the best solution for eleven problems (1, 4, 10, 11, 12, 13, 14, 15, 16, 17, 26) is the same as the optimal solution. For problems 7, 8, 13, 15, 16, 17, and 21, the third number of the critical path lower bounds is the same as optimal solution, which means the resource constraints for these problems are not binding [5]. Our method gains the optimal solutions for problems 13, 15, 16, 17. The fifth column represents the deviations of the best solution from the critical path lower bound. The deviations of the 4 problems discussed above are zeros. The deviations for other problems vary between 1.0833 and 17.3333. It also indicates that the deviation is greater when there are more activities in a project, because the difficulty of solvingj60 is greater than that ofj30.


## 4.2. The Experiment on Electronic Product Development Project

Wang [1] provides an electronic product development project, which consists of 7 phases and is divided into 51 activities. We add dummy start and end activities to the project, and the information of this project is shown in Table 5. The project ready time is b
~
=
(
0,0
,
0,0
). There are 4 types of resources: system engineers, software engineers, hardware engineers, and supporting engineers. The resource availability of each type of resource is 5, 4, 5, 4, respectively.Table 5
Project data for an electronic product development project [1].
Act.number
Fuzzy durationt
~
j
Resource required
SuccessorsS
j
r
j
1
r
j
2
r
j
3
r
j
4
1
(0, 0, 0, 0)
0
0
0
0
2
2
(5, 6, 6, 7)
3
0
0
0
3
3
(10, 12, 12, 13)
5
3
3
2
4, 5
4
(4, 5, 5, 6)
4
2
4
2
6
5
(7, 8, 8, 10)
4
2
2
2
6
6
(2, 4, 4, 6)
5
0
0
0
7
7
(3, 4, 4, 5)
4
2
2
2
8
8
(2, 3, 3, 4)
4
3
3
2
9, 10, 11, 13
9
(2, 3, 3, 5)
0
4
2
0
14
10
(3, 4, 4, 6)
2
1
5
3
15
11
(4, 5, 5, 6)
4
0
0
0
12
12
(7, 9, 9, 10)
5
0
0
0
16
13
(3, 4, 4, 5)
3
0
0
1
16
14
(1, 2, 2, 3)
3
2
0
1
16
15
(1, 2, 2, 3)
3
0
3
2
16
16
(1, 2, 2, 2)
4
2
2
2
17
17
(3, 4, 4, 5)
5
2
2
0
18, 19
18
(4, 5, 5, 6)
5
2
4
2
20
19
(4, 5, 5, 6)
4
2
4
3
20
20
(5, 6, 6, 7)
5
2
3
4
21, 22, 23
21
(5, 7, 7, 9)
4
0
0
0
24
22
(3, 5, 5, 7)
5
1
4
4
24
23
(4, 5, 5, 6)
0
3
0
0
24
24
(1, 2, 2, 3)
5
1
1
1
25
25
(8, 10, 10, 12)
2
1
5
3
26, 27, 28
26
(4, 5, 5, 6)
2
1
5
3
30
27
(4, 6, 6, 8)
0
0
4
3
29
28
(6, 7, 7, 8)
0
4
0
2
30
29
(10, 12, 12, 14)
2
2
4
4
30
30
(1, 2, 2, 4)
4
2
2
2
31, 32, 33, 39, 40, 42
31
(9, 11, 11, 10)
4
2
3
0
34
32
(10, 13, 13, 14)
5
0
3
2
37
33
(8, 10, 10, 11)
0
0
4
2
38
34
(6, 8, 8, 9)
4
3
2
0
35
35
(3, 4, 4, 5)
4
2
3
3
36
36
(4, 6, 6, 7)
2
2
0
4
41
37
(1, 3, 3, 4)
0
0
2
0
41
38
(3, 4, 4, 5)
0
0
2
2
41
39
(1, 2, 2, 3)
1
0
3
1
41
40
(2, 3, 3, 4)
0
0
2
2
41
41
(1, 1, 1, 2)
4
0
4
3
45, 46, 49
42
(3, 4, 4, 5)
0
4
0
0
43
43
(1, 2, 2, 3)
3
3
0
0
44
44
(1, 2, 2, 3)
3
0
3
0
45, 46
45
(3, 4, 4, 5)
2
3
4
1
52
46
(4, 5, 5, 6)
2
2
4
2
47
47
(4, 5, 5, 6)
5
2
2
3
48
48
(3, 4, 4, 5)
2
0
4
2
52
49
(5, 7, 7, 8)
2
0
2
3
50
50
(6, 8, 8, 10)
4
2
3
2
51
51
(2, 3, 3, 5)
4
2
3
3
52
52
(2, 4, 4, 7)
4
2
3
3
53
53
(0, 0, 0, 0)
0
0
0
0
—The proposed fuzzy firefly algorithm is used to solve the electronic product development project. The project makespan obtained by the proposed method is (178, 235, 235, 288), and the fuzzy finish times for the solutions are shown in Table6. Figure 7 shows the resource usage for every type of resource. The utilization rates for system engineers, software engineers, hardware engineers, and supporting engineers are 69.4%, 41.1%, 56.3%, and 51.7%, respectively. Wang’s results show that the project makespan is (180, 239, 239, 294), and the resource utilization rates are 0.69, 0.33, 0.56, and 0.51 [1]. The comparison shows that our method can improve the resource utilization rate of software engineers and finish the project earlier. When considering the allocation of more resources to help complete the project earlier, Wang [1] provides 12 schedules under distinct resource availability. Table 7 shows that our results have the same effect with 3 of the schedules proposed by Wang, which illustrates that our method can allocate resource more effectively, and shorten the makespan without adding more resources to the project.Table 6
Solutions for the electronic product development project.
Act. number
Fuzzy finish timec
~
j
1
(0, 0, 0, 0)
2
(5, 6, 6, 7)
3
(15, 18, 18, 20)
4
(19, 23, 23, 26)
5
(26, 31, 31, 36)
6
(28, 35, 35, 42)
7
(31, 39, 39, 47)
8
(33, 42, 42, 51)
9
(35, 45, 45, 56)
10
(40, 51, 51, 63)
11
(37, 47, 47, 57)
12
(49, 64, 64, 78)
13
(40, 51, 51, 62)
14
(41, 53, 53, 65)
15
(42, 55, 55, 68)
16
(50, 66, 66, 80)
17
(53, 70, 70, 85)
18
(57, 75, 75, 91)
19
(61, 80, 80, 97)
20
(66, 86, 86, 104)
21
(71, 93, 93, 113)
22
(74, 98, 98, 120)
23
(70, 91, 91, 110)
24
(75, 100, 100, 123)
25
(83, 110, 110, 135)
26
(101, 133, 133, 163)
27
(87, 116, 116, 143)
28
(107, 140, 140, 171)
29
(97, 128, 128, 157)
30
(108, 142, 142, 175)
31
(135, 176, 176, 213)
32
(126, 165, 165, 200)
33
(116, 152, 152, 186)
34
(141, 184, 184, 222)
35
(144, 188, 188, 227)
36
(148, 194, 194, 234)
37
(127, 168, 168, 204)
38
(121, 159, 159, 195)
39
(136, 178, 178, 216)
40
(118, 155, 155, 190)
41
(149, 195, 195, 236)
42
(111, 146, 146, 180)
43
(112, 148, 148, 183)
44
(145, 190, 190, 230)
45
(152, 199, 199, 241)
46
(169, 222, 222, 270)
47
(173, 227, 227, 276)
48
(176, 231, 231, 281)
49
(157, 206, 206, 249)
50
(163, 214, 214, 259)
51
(165, 217, 217, 264)
52
(178, 235, 235, 288)
53
(178, 235, 235, 288)Table 7
Comparison of solutions under different resource availabilities.
Resource availability
Fuzzy project makespan
Our result
5 4 5 4
(178, 235, 235, 288)
Wang [1]
5 4 5 4
(180, 239, 239, 294)
Wang [1]
6 4 5 4
(178, 235, 235, 288)
Wang [1]
6 5 5 4
(178, 235, 235, 288)
Wang [1]
5 4 6 5
(178, 235, 235, 288)Figure 7
The resource usage profile for every resource type atα
=
1 in the optimistic case.
(a)
Resource usage for system engineers
(b)
Resource usage for software engineers
(c)
Resource usage for hardware engineers
(d)
Resource usage for supporting engineers


## 5. Conclusion

This paper concentrates on the problem of product development project scheduling with fuzzy activity duration. Trapezoidal fuzzy numbers are used to represent the uncertain time parameters; mathematical model for the problem is established, and the fuzzy firefly algorithm is proposed. For the proposed method the improved magnitude of the trapezoidal fuzzy number is adopted in 4 circumstances: deciding the fuzzy start times of activities, representing firefly brightness, calculating the distances between fireflies, and comparing optimal solutions. Computational experiment results indicate that the proposed fuzzy firefly algorithm is helpful for managers to effectively allocate resources with the objective of minimizing project makespan. The future research will extend the fuzzy firefly algorithm to handle multiobjective product development project scheduling problems in an uncertain environment.



---

*Source: 973291-2015-03-17.xml*