# A Multiagent Evolutionary Algorithm for the Resource-Constrained Project Portfolio Selection and Scheduling Problem

Authors: Yongyi Shou; Wenwen Xiang; Ying Li; Weijian Yao
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

A multiagent evolutionary algorithm is proposed to solve the resource-constrained project portfolio selection and scheduling problem. The proposed algorithm has a dual level structure. In the upper level a set of agents make decisions to select appropriate project portfolios. Each agent selects its project portfolio independently. The neighborhood competition operator and self-learning operator are designed to improve the agent’s energy, that is, the portfolio profit. In the lower level the selected projects are scheduled simultaneously and completion times are computed to estimate the expected portfolio profit. A priority rule-based heuristic is used by each agent to solve the multiproject scheduling problem. A set of instances were generated systematically from the widely used Patterson set. Computational experiments confirmed that the proposed evolutionary algorithm is effective for the resource-constrained project portfolio selection and scheduling problem.


---

## Body

## 1. Introduction

The project portfolio selection problem (PPSP), together with its various extensions, has been widely studied during the last decade. Given a set of project proposals and constraints, the traditional PPSP is to select a subset of project proposals to optimize the organization’s performance objective [1]. Mathematic models have been proposed in the literature. The project portfolio profit is regarded as the natural performance objective and utilized by most models, for example, the zero-one integer programming model [2]. Since the PPSP is an NP-hard problem [3], metaheuristic algorithms such as evolutionary approaches are widely used [4].Most studies on the PPSP generally dissever the inherent relationship between portfolio selection and project scheduling. The traditional PPSP is based on some assumptions. It is assumed that an individual project has a fixed and unchangeable schedule [5]; hence, only the project selection decision is considered to impact the final portfolio profit. However, project scheduling tends to affect the portfolio feasibility by adjusting the start and completion time of its activities [6]. Especially when resources are constrained, scheduling of project activities helps to better utilize the limited resources, and consequently to increase the portfolio profit [5]. Inclusion of project activity scheduling as a subproblem of project portfolio selection helps improve the overall organization performance even though it increases the complexity of decision making. This combined problem is termed as the resource-constrained project portfolio selection and scheduling problem (RCPPSSP). The RCPPSSP can be described as a problem to select an optimal portfolio of projects and schedule their activities to maximize an organization’s stated objectives without exceeding available resources or violating other constraints [7].The RCPPSSP has attracted increasing attention in recent years as a new research problem. Owing to the dual level structure of the RCPPSSP, most algorithms in the current literature are also composed of two parts. In the upper level, decisions are made to select project portfolios. In the lower level, procedures of multiproject scheduling are adopted to improve the performance of the selected portfolio. Due to the NP-hard nature of the project portfolio selection problem, researchers developed heuristics and metaheuristics to improve the solution quality and computational efficiency. For example, an implicit enumeration procedure was developed for all possible project priority sequences with high profit [7]. An ant colony optimization (ACO) based on the max-min ant system [8] was proposed, in which solutions were encoded as walks of agents in a construction graph, and transition probabilities were computed to determine the probability of an arc of the graph being chosen by the agents in the next iteration [8]. An iterative multiunit combinatorial auction algorithm [5] was also used to select project portfolios through a distributed bidding mechanism. In the lower level, heuristics such as greedy heuristic [8] and priority rule-based heuristics [9] are widely adopted for multiproject scheduling.In recent years, agent-based computation has been widely applied in distributed problem solving. An agent is a self-contained problem solving entity [10] which exhibits the properties of autonomy, social ability, responsiveness, and proactiveness [11]. In a multiagent optimization system (MAOS) [12], self-organization agents [13] interact to optimize their own problem solving with limited declarative knowledge and simple procedural knowledge under ecological rationality [12]. Specifically, agents explore in parallel through three types of interactions, namely, cooperation, coordination, and negotiation [14]. Since interactions among the agents contribute to solution diversity and rapid convergence in some cases [15], it is recommended to embed the MAOS in evolutionary algorithms to improve the solution quality [12, 15–18]. Recently, multiagent evolutionary algorithms have been used for single project scheduling [19].The objective of this paper is to develop a multiagent evolutionary algorithm for the RCPPSSP. The master procedure in the upper decision level is designed by combining the neighborhood competition operator and self-learning operator in the multiagent system. A priority rule-based heuristic is adopted for the subprocedure in the lower decision level. In Section2, we present the resource-constrained project portfolio selection and scheduling problem and its mathematical model. Section 3 explains the multiagent evolutionary algorithm that we have developed for the RCPPSP. Computational experiments and results are discussed in Section 4. Finally, we conclude this paper in Section 5.


## 2. Project Portfolio Selection and Scheduling

The objective of the resource-constrained project portfolio selection and scheduling problem is to maximize the project portfolio profit. The problem can be recognized as a dual level decision problem [8].The upper level is to select feasible project portfolios under resource constraints. There are a setΩ of N candidate projects from which we select the optimal portfolio. A pool of K types of limited and renewable resources is available for all projects. It is assumed that there is no other relationship among the projects besides resource competition.The lower level is to solve the multiproject scheduling problem, that is, to determine the start (completion) time of each activity without violating the precedence relations or resource constraints [5]. Given the resource constraints, scheduling project activities within a portfolio helps shorten the project duration and increase the portfolio profit since the project profit is a decreasing function of the project completion time [7].Two sets of decision variables are designed in this paper:x
i is for project selection and c
i
j
t for project activity scheduling, as shown in the following formulae:
(1)
x
i
=
{
1
,
if
project
i
is
included
,
0
,
if
project
i
is
excluded
.
c
i
j
t
=
{
1
,
if
activity
j
of
project
i
completes
at
time
t
,
0
,
otherwise
.The notations used in this paper are listed in Notations for the RCPPSSP section.The RCPPSSP can be formulated as a 0-1 integer programming model [5, 7]:
(2)
max
⁡
∑
i
=
1
N
∑
t
=
E
F
i
J
i
L
F
i
J
i
b
i
t
c
i
J
i
t
(3)
s
.
t
.
∑
t
=
E
F
i
J
i
L
F
i
J
i
c
i
j
t
=
x
i
,
∀
i
,
j
(4)
∑
t
=
E
F
i
J
i
L
F
i
J
i
t
c
i
J
i
t
≤
T
i
,
∀
i
(5)
∑
t
=
E
F
i
j
L
F
i
j
t
c
i
j
t
≤
∑
t
=
E
F
i
h
L
F
i
h
(
t
-
d
i
h
)
c
i
h
t
,
∀
(
i
,
j
)
,
∀
(
i
,
h
)
∈
S
i
j
(6)
∑
(
i
,
j
)
∈
A
t
x
i
r
i
j
k
≤
R
k
,
∀
k
,
t
(7)
x
i
∈
{
0,1
}
,
∀
i
(8)
c
i
j
t
∈
{
0,1
}
,
∀
(
i
,
j
)
,
∀
t
.The objective (2) is to maximize the total profit of the selected project portfolio. Constraint (3) ensures that all activities of a selected project are completed. It also enforces that every activity in unselected projects is not executed. Constraint (4) is to guarantee the selected project is complete before its deadline. Constraint (5) describes the precedence relations among activities which requires an activity to start only after all its predecessors have been completed. Constraint (6) ensures that in each time period the demand on any resource does not exceed its capacity. Formulae (7) and (8) declare the decision variables.


## 3. Multiagent Evolutionary Algorithm

To solve the RCPPSSP, a multiagent evolutionary algorithm (MAEA) is proposed. Corresponding to the dual level structure of the RCPPSSP, the MAEA has two levels as well. The master procedure for the upper level is to select project portfolios and a priority rule-based heuristic [20] is designed as the subprocedure for the lower level to do multiproject scheduling.


### 3.1. Project Portfolio Selection

The multiagent evolutionary algorithm is a combination of two theories: multiagent systems and evolutionary algorithms [17]. Generally, a multiagent system [15] is composed of an environment, a set of objects, a set of agents, a set of relations between objects (agents), and a set of operations. During observation of the environment and interaction with other agents, the fitness value of an agent can be estimated and optimized on the basis of the possessed resources, abilities, and knowledge [17].In this paper a multiagent evolutionary algorithm was proposed to solve the project selection problem. We designed a multiagent system in which each agent selects project portfolios according to its own preferences and environment. The evolution of the agents is realized by the neighborhood competition and self-learning operators. In neighborhood competition, loser agents will be replaced by new generated agents. In this way, the information and knowledge of individual agents will spread to the whole system. The winner agents will conduct self-learning by applying its own knowledge, for which a simple genetic algorithm is developed. Since most multiagent systems adopt the real-valued representation which is not appropriate for the project selection problem, we designed an agent system based on a discrete representation and modified the operators correspondingly.


#### 3.1.1. Multiagent System

The objective function (2) of the RCPPSSP can be simplified as the following formula:
(9)
max
⁡
f
(
x
)
,
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where f(x) denotes the portfolio profit which is equal to ∑
i
=
1
N
∑
t
=
E
F
i
J
i
L
F
i
J
i
b
i
t
c
i
J
i
t  and Θ is an N-dimensional search space of the project selection problem. The “x” in boldface represents a vector which is a candidate solution in the search space. The component “x
i” is a 0-1 variable which takes the value of 1 when project i is selected or the value of 0 otherwise.An agent for the RCPPSSP can be defined as follows.Definition 1.
An agent denoted asa represents a candidate solution x to the RCPPSSP. The value of its energy is equal to its value of the objective function in (2):
(10)
a
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
Energy
(
a
)
=
f
(
x
)
.The agenta living in an environment makes decisions autonomously to increase its energy as much as possible. To realize the local perceptivity of agents, the environment is organized as a lattice-like structure which can be defined as follows [16].Definition 2.
All agents live in a lattice-like environment denoted asL. The size of L is L
size
×
L
size. L
size is determined as L
size
=
ρ
×
N
+
1, where 0
<
ρ
<
1.Figure1 illustrates an agent lattice. In the agent lattice, an agent denoted as a
u
v
=
(
a
1
,
a
2
,
…
,
a
N
) is fixed on a lattice point (
u
,
v
), where 1
≤
u
,
v
≤
L
size.Figure 1
Illustration of an agent lattice.


#### 3.1.2. Neighborhood Competition Operator

In the agent lattice, agents compete with their neighbors to gain more resources so that their purposes, that is, objectives of the RCPPSSP, can be achieved. Reference [16] noted that the neighborhood competition operator facilitates information diffusion to the whole lattice. To describe the neighborhood competition operator, we define the neighborhood as follows.Definition 3.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The competing neighborhood of a
u
v is denoted as N
u
v
C. The perceptive range of an agent’s competing neighborhood R
C determines the number of competing neighbors as (
2
R
C
+
1
)
2
-
1, where 0
≤
R
C
≤
(
1
/
2
)
L
size.For example, whenR
C is equal to 1, the number of agents in the neighborhood N
u
v
C is 8.The basic rule for neighborhood competition operator is defined as follows [16].Rule 1.
If the agenta
u
v satisfies (11), it is a loser; otherwise, it is a winner:
(11)
Energy
(
a
u
v
)
<
Energy
(
a
u
v
*
)
.The winner survives in the agent lattice, but the loser perishes and is replaced by a new agenta
u
v
′ generated from the local-best agent a
u
v
* which is defined as
(12)
a
u
v
*
=
(
a
1
*
,
a
2
*
,
…
,
a
N
*
)
∈
N
u
v
C
,
Energy
(
a
u
v
*
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
C
.Two alternative strategies [16] are adopted to generate the new agent a
u
v
′.Strategy 1.
A setD is composed of sequence numbers of the positions where the agent a
u
v takes different values from agent a
u
v
*; that is, D
=
{
i
∣
1
≤
i
≤
N
,
a
i
≠
a
i
*
}. The new agent a
u
v
′
=
(
x
1
′
,
x
2
′
,
…
,
x
N
′
) is determined by formula (13), in which 1
≤
i
≤
N andRandom takes the values of 0 or 1 randomly
(13)
a
i
′
=
{
a
i
*
,
i
∉
D
or
(
i
∈
D
and
Random
=
0
)
,
1
-
a
i
*
,
otherwise
.One example of Strategy1 is presented in Figure 2.Figure 2
Strategy1 to generate a new agent.Strategy 2.
Mutation in the evolutionary algorithm is adopted to transform agenta
u
v
* to a
u
v
′, which is represented in formula (14). In formula (14), 1
≤
i
≤
N and Random is generated randomly in the interval of (0,1)
(14)
a
i
′
=
{
a
i
*
,
Random
>
1
N
,
1
-
a
i
*
,
otherwise
.One example of Strategy2 is presented in Figure 3.Figure 3
Strategy2 to generate a new agent.In this paper a uniform random parameterD
S
∈
(
0,1
) is used to determine which strategy is to be applied to generate the new agent. Firstly, we calculate the similarity between the loser agent a
u
v and the local-best agent a
u
v
* with maximum energy in the neighborhood by the following formula:
(15)
|
D
|
=
∑
i
=
1
N
η
i
,
where η
i
=
{
1
,
a
i
=
a
i
*
0
,
a
i
≠
a
i
*. The higher the value of |
D
| is, the more similar a
u
v to a
u
v
* is and the much lower the chance to get a better solution through  Strategy 1 is indicated.Therefore, the rule to select an appropriate strategy is designed as follows.Rule 2.
When the value of|
D
| satisfies (16), Strategy 1 is adopted to generate new agents. Otherwise, Strategy 2 is adopted:
(16)
|
D
|
N
<
D
S
.


#### 3.1.3. Self-Learning Operator

In order to survive in competition, agents in the lattice may take actions to increase their energy by using their own knowledge [21]. The self-learning operator [16, 21] is designed to help agents achieve this purpose. It is assumed that only winner agents have the chance to conduct self-learning.Definition 4.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The self-learning neighborhood of a
u
v is denoted as N
u
v
L. The perceptive range of an agent’s self-learning neighborhood R
L determines the number of self-learning neighbors as (
2
R
L
+
1
)
2
-
1, where 0
≤
R
L
≤
(
1
/
2
)
L
size.The basic rule for the self-learning operator is defined as follows [16, 21].Rule 3.
If agenta
u
v satisfies (17), it has the chance to execute the self-learning operator:
(17)
Energy
(
a
u
v
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
L
.A simple genetic algorithm (SGA) [22] is adopted to realize the self-learning of agent a
u
v, in which the chromosome takes the same representation as an agent. The hth chromosome in the gth generation is denoted as follows:
(18)
chromosome
h
g
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where 0
≤
g
≤
MaxGA and 1
≤
h
≤
PopSize. MaxGA denotes the maximum number of iterations and PopSize represents the population size. The fitness function of a chromosome is equal to the energy of its corresponding agent.In the self-learning process, the initial population is generated as follows. The first chromosome in the initial population is equal to agenta
u
v and all other chromosomes are generated by the following formula:
(19)
chromosome
h
0
=
{
y
1
,
y
2
,
…
,
y
N
}
,
2
≤
h
≤
PopSize
,
where y
i is determined by
(20)
y
i
=
{
1
-
x
i
,
Random
≤
D
S
,
x
i
,
Random
>
D
S
.Three types of operators are applied to generate the new population in each generation, including selection, crossover, and mutation. Binary tournament [23] is used for selection. The elitist strategy [24] is employed to guarantee convergence of the genetic algorithm. One-point crossover is adopted. A crossover point is randomly selected and then the genes in the two parent chromosomes after the crossover point are exchanged to generate two offspring chromosomes [25]. The mutation locus is also selected randomly. The selected gene is then mutated by negation. The probabilities of crossover and mutation are denoted as p
c and p
m respectively.


#### 3.1.4. Repair Mechanism

In the case of resource constraints and multiproject scheduling, it is possible that some agents (solutions) are infeasible. Especially the neighborhood competition operator and self-learning operator may lead to infeasible agents. Therefore, repair mechanisms are necessary and have been proposed in the relevant literature [8].In this paper, the infeasible agents are repaired by removing projects in sequence under a certain rule. In an RCPPSSP, the profit of a candidate project depends on its completion time which is unknown in advance, so it is inconvenient to apply other rules except the random rule [8]. Given an infeasible portfolio, a random project is selected and removed from the portfolio. This process continues until feasibility is achieved. Once the repaired portfolio is feasible, the new agent representing the repaired feasible portfolio is used to replace the incumbent infeasible agent.


### 3.2. Multiproject Scheduling

A priority rule-based heuristic is applied to schedule the selected projects in the lower decision level. Using the minimal slack (MINSLK) priority rule [26] and the serial schedule generation scheme (SSGS) [27], a multiproject schedule is generated for the selected portfolio. In a multiproject environment, the slack (SLK) of an activity is computed as follows:
(21)
SLK
i
j
=
LF
i
j
-
EF
i
j
,
where LF and EF are the latest and earliest finish times, respectively, which are estimated by the critical path method (CPM).Suppose a subset Φ is selected in the master procedure. In projecti
∈
Φ, there are J
i activities which are denoted as (
i
,
j
). The SSGS heuristic consists of ∑
i
∈
Φ
J
i stages. In each stage g, two disjoint activity sets are identified [27]. The scheduled set S
g includes the activities which are already scheduled; and the decision set D
g contains the unscheduled activities whose predecessors are all in the scheduled set S
g. According to the MINSLK priority rule, the activity with the minimum slack is selected from the decision set and scheduled as early as possible without violating the resource constraints. The activity is then moved from the decision set to the scheduled set. Algorithm 1 shows the pseudocode of the priority rule-based heuristic.Algorithm 1:Pseudocode of the priority rule-based heuristic.
Procedure of the priority rule-based heuristic
BEGIN
INIT: S
0
∶
=
{
}
FOR g
:
=
1 TO ∑
i
∈
Φ
J
i
COMPUTE D
g
SELECT (
i
*
,
j
*
) from D
g /* according to the MINSLK rule */
ASSIGN S
T
i
*
j
* /* as early as possible */
S
g
∶
=
S
g
-
1
∪
{
(
i
*
,
j
*
)
}
ENDFOR
ENDTo determine the feasibility of the multiproject schedule, we set a upper bound for each project’s completion time, denoted asT
i. Specifically, for project i in the selected portfolio Φ, if its completion time goes beyond its upper bound T
i, the portfolio Φ is recognized as infeasible and shall be repaired.


## 3.1. Project Portfolio Selection

The multiagent evolutionary algorithm is a combination of two theories: multiagent systems and evolutionary algorithms [17]. Generally, a multiagent system [15] is composed of an environment, a set of objects, a set of agents, a set of relations between objects (agents), and a set of operations. During observation of the environment and interaction with other agents, the fitness value of an agent can be estimated and optimized on the basis of the possessed resources, abilities, and knowledge [17].In this paper a multiagent evolutionary algorithm was proposed to solve the project selection problem. We designed a multiagent system in which each agent selects project portfolios according to its own preferences and environment. The evolution of the agents is realized by the neighborhood competition and self-learning operators. In neighborhood competition, loser agents will be replaced by new generated agents. In this way, the information and knowledge of individual agents will spread to the whole system. The winner agents will conduct self-learning by applying its own knowledge, for which a simple genetic algorithm is developed. Since most multiagent systems adopt the real-valued representation which is not appropriate for the project selection problem, we designed an agent system based on a discrete representation and modified the operators correspondingly.


### 3.1.1. Multiagent System

The objective function (2) of the RCPPSSP can be simplified as the following formula:
(9)
max
⁡
f
(
x
)
,
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where f(x) denotes the portfolio profit which is equal to ∑
i
=
1
N
∑
t
=
E
F
i
J
i
L
F
i
J
i
b
i
t
c
i
J
i
t  and Θ is an N-dimensional search space of the project selection problem. The “x” in boldface represents a vector which is a candidate solution in the search space. The component “x
i” is a 0-1 variable which takes the value of 1 when project i is selected or the value of 0 otherwise.An agent for the RCPPSSP can be defined as follows.Definition 1.
An agent denoted asa represents a candidate solution x to the RCPPSSP. The value of its energy is equal to its value of the objective function in (2):
(10)
a
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
Energy
(
a
)
=
f
(
x
)
.The agenta living in an environment makes decisions autonomously to increase its energy as much as possible. To realize the local perceptivity of agents, the environment is organized as a lattice-like structure which can be defined as follows [16].Definition 2.
All agents live in a lattice-like environment denoted asL. The size of L is L
size
×
L
size. L
size is determined as L
size
=
ρ
×
N
+
1, where 0
<
ρ
<
1.Figure1 illustrates an agent lattice. In the agent lattice, an agent denoted as a
u
v
=
(
a
1
,
a
2
,
…
,
a
N
) is fixed on a lattice point (
u
,
v
), where 1
≤
u
,
v
≤
L
size.Figure 1
Illustration of an agent lattice.


### 3.1.2. Neighborhood Competition Operator

In the agent lattice, agents compete with their neighbors to gain more resources so that their purposes, that is, objectives of the RCPPSSP, can be achieved. Reference [16] noted that the neighborhood competition operator facilitates information diffusion to the whole lattice. To describe the neighborhood competition operator, we define the neighborhood as follows.Definition 3.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The competing neighborhood of a
u
v is denoted as N
u
v
C. The perceptive range of an agent’s competing neighborhood R
C determines the number of competing neighbors as (
2
R
C
+
1
)
2
-
1, where 0
≤
R
C
≤
(
1
/
2
)
L
size.For example, whenR
C is equal to 1, the number of agents in the neighborhood N
u
v
C is 8.The basic rule for neighborhood competition operator is defined as follows [16].Rule 1.
If the agenta
u
v satisfies (11), it is a loser; otherwise, it is a winner:
(11)
Energy
(
a
u
v
)
<
Energy
(
a
u
v
*
)
.The winner survives in the agent lattice, but the loser perishes and is replaced by a new agenta
u
v
′ generated from the local-best agent a
u
v
* which is defined as
(12)
a
u
v
*
=
(
a
1
*
,
a
2
*
,
…
,
a
N
*
)
∈
N
u
v
C
,
Energy
(
a
u
v
*
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
C
.Two alternative strategies [16] are adopted to generate the new agent a
u
v
′.Strategy 1.
A setD is composed of sequence numbers of the positions where the agent a
u
v takes different values from agent a
u
v
*; that is, D
=
{
i
∣
1
≤
i
≤
N
,
a
i
≠
a
i
*
}. The new agent a
u
v
′
=
(
x
1
′
,
x
2
′
,
…
,
x
N
′
) is determined by formula (13), in which 1
≤
i
≤
N andRandom takes the values of 0 or 1 randomly
(13)
a
i
′
=
{
a
i
*
,
i
∉
D
or
(
i
∈
D
and
Random
=
0
)
,
1
-
a
i
*
,
otherwise
.One example of Strategy1 is presented in Figure 2.Figure 2
Strategy1 to generate a new agent.Strategy 2.
Mutation in the evolutionary algorithm is adopted to transform agenta
u
v
* to a
u
v
′, which is represented in formula (14). In formula (14), 1
≤
i
≤
N and Random is generated randomly in the interval of (0,1)
(14)
a
i
′
=
{
a
i
*
,
Random
>
1
N
,
1
-
a
i
*
,
otherwise
.One example of Strategy2 is presented in Figure 3.Figure 3
Strategy2 to generate a new agent.In this paper a uniform random parameterD
S
∈
(
0,1
) is used to determine which strategy is to be applied to generate the new agent. Firstly, we calculate the similarity between the loser agent a
u
v and the local-best agent a
u
v
* with maximum energy in the neighborhood by the following formula:
(15)
|
D
|
=
∑
i
=
1
N
η
i
,
where η
i
=
{
1
,
a
i
=
a
i
*
0
,
a
i
≠
a
i
*. The higher the value of |
D
| is, the more similar a
u
v to a
u
v
* is and the much lower the chance to get a better solution through  Strategy 1 is indicated.Therefore, the rule to select an appropriate strategy is designed as follows.Rule 2.
When the value of|
D
| satisfies (16), Strategy 1 is adopted to generate new agents. Otherwise, Strategy 2 is adopted:
(16)
|
D
|
N
<
D
S
.


### 3.1.3. Self-Learning Operator

In order to survive in competition, agents in the lattice may take actions to increase their energy by using their own knowledge [21]. The self-learning operator [16, 21] is designed to help agents achieve this purpose. It is assumed that only winner agents have the chance to conduct self-learning.Definition 4.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The self-learning neighborhood of a
u
v is denoted as N
u
v
L. The perceptive range of an agent’s self-learning neighborhood R
L determines the number of self-learning neighbors as (
2
R
L
+
1
)
2
-
1, where 0
≤
R
L
≤
(
1
/
2
)
L
size.The basic rule for the self-learning operator is defined as follows [16, 21].Rule 3.
If agenta
u
v satisfies (17), it has the chance to execute the self-learning operator:
(17)
Energy
(
a
u
v
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
L
.A simple genetic algorithm (SGA) [22] is adopted to realize the self-learning of agent a
u
v, in which the chromosome takes the same representation as an agent. The hth chromosome in the gth generation is denoted as follows:
(18)
chromosome
h
g
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where 0
≤
g
≤
MaxGA and 1
≤
h
≤
PopSize. MaxGA denotes the maximum number of iterations and PopSize represents the population size. The fitness function of a chromosome is equal to the energy of its corresponding agent.In the self-learning process, the initial population is generated as follows. The first chromosome in the initial population is equal to agenta
u
v and all other chromosomes are generated by the following formula:
(19)
chromosome
h
0
=
{
y
1
,
y
2
,
…
,
y
N
}
,
2
≤
h
≤
PopSize
,
where y
i is determined by
(20)
y
i
=
{
1
-
x
i
,
Random
≤
D
S
,
x
i
,
Random
>
D
S
.Three types of operators are applied to generate the new population in each generation, including selection, crossover, and mutation. Binary tournament [23] is used for selection. The elitist strategy [24] is employed to guarantee convergence of the genetic algorithm. One-point crossover is adopted. A crossover point is randomly selected and then the genes in the two parent chromosomes after the crossover point are exchanged to generate two offspring chromosomes [25]. The mutation locus is also selected randomly. The selected gene is then mutated by negation. The probabilities of crossover and mutation are denoted as p
c and p
m respectively.


### 3.1.4. Repair Mechanism

In the case of resource constraints and multiproject scheduling, it is possible that some agents (solutions) are infeasible. Especially the neighborhood competition operator and self-learning operator may lead to infeasible agents. Therefore, repair mechanisms are necessary and have been proposed in the relevant literature [8].In this paper, the infeasible agents are repaired by removing projects in sequence under a certain rule. In an RCPPSSP, the profit of a candidate project depends on its completion time which is unknown in advance, so it is inconvenient to apply other rules except the random rule [8]. Given an infeasible portfolio, a random project is selected and removed from the portfolio. This process continues until feasibility is achieved. Once the repaired portfolio is feasible, the new agent representing the repaired feasible portfolio is used to replace the incumbent infeasible agent.


## 3.1.1. Multiagent System

The objective function (2) of the RCPPSSP can be simplified as the following formula:
(9)
max
⁡
f
(
x
)
,
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where f(x) denotes the portfolio profit which is equal to ∑
i
=
1
N
∑
t
=
E
F
i
J
i
L
F
i
J
i
b
i
t
c
i
J
i
t  and Θ is an N-dimensional search space of the project selection problem. The “x” in boldface represents a vector which is a candidate solution in the search space. The component “x
i” is a 0-1 variable which takes the value of 1 when project i is selected or the value of 0 otherwise.An agent for the RCPPSSP can be defined as follows.Definition 1.
An agent denoted asa represents a candidate solution x to the RCPPSSP. The value of its energy is equal to its value of the objective function in (2):
(10)
a
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
Energy
(
a
)
=
f
(
x
)
.The agenta living in an environment makes decisions autonomously to increase its energy as much as possible. To realize the local perceptivity of agents, the environment is organized as a lattice-like structure which can be defined as follows [16].Definition 2.
All agents live in a lattice-like environment denoted asL. The size of L is L
size
×
L
size. L
size is determined as L
size
=
ρ
×
N
+
1, where 0
<
ρ
<
1.Figure1 illustrates an agent lattice. In the agent lattice, an agent denoted as a
u
v
=
(
a
1
,
a
2
,
…
,
a
N
) is fixed on a lattice point (
u
,
v
), where 1
≤
u
,
v
≤
L
size.Figure 1
Illustration of an agent lattice.


## 3.1.2. Neighborhood Competition Operator

In the agent lattice, agents compete with their neighbors to gain more resources so that their purposes, that is, objectives of the RCPPSSP, can be achieved. Reference [16] noted that the neighborhood competition operator facilitates information diffusion to the whole lattice. To describe the neighborhood competition operator, we define the neighborhood as follows.Definition 3.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The competing neighborhood of a
u
v is denoted as N
u
v
C. The perceptive range of an agent’s competing neighborhood R
C determines the number of competing neighbors as (
2
R
C
+
1
)
2
-
1, where 0
≤
R
C
≤
(
1
/
2
)
L
size.For example, whenR
C is equal to 1, the number of agents in the neighborhood N
u
v
C is 8.The basic rule for neighborhood competition operator is defined as follows [16].Rule 1.
If the agenta
u
v satisfies (11), it is a loser; otherwise, it is a winner:
(11)
Energy
(
a
u
v
)
<
Energy
(
a
u
v
*
)
.The winner survives in the agent lattice, but the loser perishes and is replaced by a new agenta
u
v
′ generated from the local-best agent a
u
v
* which is defined as
(12)
a
u
v
*
=
(
a
1
*
,
a
2
*
,
…
,
a
N
*
)
∈
N
u
v
C
,
Energy
(
a
u
v
*
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
C
.Two alternative strategies [16] are adopted to generate the new agent a
u
v
′.Strategy 1.
A setD is composed of sequence numbers of the positions where the agent a
u
v takes different values from agent a
u
v
*; that is, D
=
{
i
∣
1
≤
i
≤
N
,
a
i
≠
a
i
*
}. The new agent a
u
v
′
=
(
x
1
′
,
x
2
′
,
…
,
x
N
′
) is determined by formula (13), in which 1
≤
i
≤
N andRandom takes the values of 0 or 1 randomly
(13)
a
i
′
=
{
a
i
*
,
i
∉
D
or
(
i
∈
D
and
Random
=
0
)
,
1
-
a
i
*
,
otherwise
.One example of Strategy1 is presented in Figure 2.Figure 2
Strategy1 to generate a new agent.Strategy 2.
Mutation in the evolutionary algorithm is adopted to transform agenta
u
v
* to a
u
v
′, which is represented in formula (14). In formula (14), 1
≤
i
≤
N and Random is generated randomly in the interval of (0,1)
(14)
a
i
′
=
{
a
i
*
,
Random
>
1
N
,
1
-
a
i
*
,
otherwise
.One example of Strategy2 is presented in Figure 3.Figure 3
Strategy2 to generate a new agent.In this paper a uniform random parameterD
S
∈
(
0,1
) is used to determine which strategy is to be applied to generate the new agent. Firstly, we calculate the similarity between the loser agent a
u
v and the local-best agent a
u
v
* with maximum energy in the neighborhood by the following formula:
(15)
|
D
|
=
∑
i
=
1
N
η
i
,
where η
i
=
{
1
,
a
i
=
a
i
*
0
,
a
i
≠
a
i
*. The higher the value of |
D
| is, the more similar a
u
v to a
u
v
* is and the much lower the chance to get a better solution through  Strategy 1 is indicated.Therefore, the rule to select an appropriate strategy is designed as follows.Rule 2.
When the value of|
D
| satisfies (16), Strategy 1 is adopted to generate new agents. Otherwise, Strategy 2 is adopted:
(16)
|
D
|
N
<
D
S
.


## 3.1.3. Self-Learning Operator

In order to survive in competition, agents in the lattice may take actions to increase their energy by using their own knowledge [21]. The self-learning operator [16, 21] is designed to help agents achieve this purpose. It is assumed that only winner agents have the chance to conduct self-learning.Definition 4.
All agents with a line or diagonal line connecting to agenta constitute the neighborhood of agent a. The self-learning neighborhood of a
u
v is denoted as N
u
v
L. The perceptive range of an agent’s self-learning neighborhood R
L determines the number of self-learning neighbors as (
2
R
L
+
1
)
2
-
1, where 0
≤
R
L
≤
(
1
/
2
)
L
size.The basic rule for the self-learning operator is defined as follows [16, 21].Rule 3.
If agenta
u
v satisfies (17), it has the chance to execute the self-learning operator:
(17)
Energy
(
a
u
v
)
≥
Energy
(
a
)
,
∀
a
∈
N
u
v
L
.A simple genetic algorithm (SGA) [22] is adopted to realize the self-learning of agent a
u
v, in which the chromosome takes the same representation as an agent. The hth chromosome in the gth generation is denoted as follows:
(18)
chromosome
h
g
=
x
=
(
x
1
,
x
2
,
…
,
x
N
)
∈
Θ
,
where 0
≤
g
≤
MaxGA and 1
≤
h
≤
PopSize. MaxGA denotes the maximum number of iterations and PopSize represents the population size. The fitness function of a chromosome is equal to the energy of its corresponding agent.In the self-learning process, the initial population is generated as follows. The first chromosome in the initial population is equal to agenta
u
v and all other chromosomes are generated by the following formula:
(19)
chromosome
h
0
=
{
y
1
,
y
2
,
…
,
y
N
}
,
2
≤
h
≤
PopSize
,
where y
i is determined by
(20)
y
i
=
{
1
-
x
i
,
Random
≤
D
S
,
x
i
,
Random
>
D
S
.Three types of operators are applied to generate the new population in each generation, including selection, crossover, and mutation. Binary tournament [23] is used for selection. The elitist strategy [24] is employed to guarantee convergence of the genetic algorithm. One-point crossover is adopted. A crossover point is randomly selected and then the genes in the two parent chromosomes after the crossover point are exchanged to generate two offspring chromosomes [25]. The mutation locus is also selected randomly. The selected gene is then mutated by negation. The probabilities of crossover and mutation are denoted as p
c and p
m respectively.


## 3.1.4. Repair Mechanism

In the case of resource constraints and multiproject scheduling, it is possible that some agents (solutions) are infeasible. Especially the neighborhood competition operator and self-learning operator may lead to infeasible agents. Therefore, repair mechanisms are necessary and have been proposed in the relevant literature [8].In this paper, the infeasible agents are repaired by removing projects in sequence under a certain rule. In an RCPPSSP, the profit of a candidate project depends on its completion time which is unknown in advance, so it is inconvenient to apply other rules except the random rule [8]. Given an infeasible portfolio, a random project is selected and removed from the portfolio. This process continues until feasibility is achieved. Once the repaired portfolio is feasible, the new agent representing the repaired feasible portfolio is used to replace the incumbent infeasible agent.


## 3.2. Multiproject Scheduling

A priority rule-based heuristic is applied to schedule the selected projects in the lower decision level. Using the minimal slack (MINSLK) priority rule [26] and the serial schedule generation scheme (SSGS) [27], a multiproject schedule is generated for the selected portfolio. In a multiproject environment, the slack (SLK) of an activity is computed as follows:
(21)
SLK
i
j
=
LF
i
j
-
EF
i
j
,
where LF and EF are the latest and earliest finish times, respectively, which are estimated by the critical path method (CPM).Suppose a subset Φ is selected in the master procedure. In projecti
∈
Φ, there are J
i activities which are denoted as (
i
,
j
). The SSGS heuristic consists of ∑
i
∈
Φ
J
i stages. In each stage g, two disjoint activity sets are identified [27]. The scheduled set S
g includes the activities which are already scheduled; and the decision set D
g contains the unscheduled activities whose predecessors are all in the scheduled set S
g. According to the MINSLK priority rule, the activity with the minimum slack is selected from the decision set and scheduled as early as possible without violating the resource constraints. The activity is then moved from the decision set to the scheduled set. Algorithm 1 shows the pseudocode of the priority rule-based heuristic.Algorithm 1:Pseudocode of the priority rule-based heuristic.
Procedure of the priority rule-based heuristic
BEGIN
INIT: S
0
∶
=
{
}
FOR g
:
=
1 TO ∑
i
∈
Φ
J
i
COMPUTE D
g
SELECT (
i
*
,
j
*
) from D
g /* according to the MINSLK rule */
ASSIGN S
T
i
*
j
* /* as early as possible */
S
g
∶
=
S
g
-
1
∪
{
(
i
*
,
j
*
)
}
ENDFOR
ENDTo determine the feasibility of the multiproject schedule, we set a upper bound for each project’s completion time, denoted asT
i. Specifically, for project i in the selected portfolio Φ, if its completion time goes beyond its upper bound T
i, the portfolio Φ is recognized as infeasible and shall be repaired.


## 4. Computational Experiments and Results

This section presents the experiment design and computational analyses for investigating the performances of the proposed multiagent evolutionary algorithm for the RCPPSSP. Based on the design of experiment (DOE) approach, a set of instances was generated systematically. Then parameter configurations of the algorithm were set up through testing of examples. The proposed MAEA was then compared with other algorithms in the literature.


### 4.1. Experiment Design

An RCPPSSP instance consists of a pool of candidate projects, a set of profit profiles of all projects, and the resources available for all projects. Three project pools with 10 projects in each pool and three other pools with 20 projects in each pool were generated randomly by 72 instances with three types of resources and different networks selected from the widely used Patterson set [28]. The above six project pools are denoted as PAT10_1, PAT10_2, PAT10_3, PAT20_1, PAT20_2, and PAT20_3, respectively.It is assumed that a project achieves its base profit if it is complete at its critical path length (CPL) and the profit decreases with a profit decreasing rateλ
1 as its completion time increases. Referring to [7], the base profit B
i and actual profit b
i
t of project i are calculated by formulae (22) and (23), where σ
i denotes the resource utilization coefficient which is subject to a uniform distribution in the interval of [
0.5,1.5
]. The upper bound of project completion time T
i is based on the critical path length by formula (24), and the relaxation rate λ
2 has the value of 0.4 in this paper. Resource tightness ω
k is introduced to estimate the capacity of resource k from its maximum resource demand R
k
max
⁡ in the critical path method:
(22)
B
i
=
σ
i
∑
k
=
1
K
∑
j
=
1
J
i
r
i
j
k
d
i
j
,
(23)
b
i
t
=
B
i
(
1
-
λ
1
(
t
-
CPL
i
)
)
,
(24)
T
i
=
CPL
i
+
min
⁡
{
10
,
λ
2
CPL
i
}
,
(25)
R
k
=
ω
k
R
k
max
⁡
.Two levels of profit decreasing rateλ
1  (2% or 8%) and resource tightness (30% or 60%) were designed, which forms four experiment cells as shown in Table 1. This 22 experimental design crossed with our six project pools yielded 24 instances to test the proposed algorithm.Table 1
Experiment design.
Profit decreasing rate (%)
Resource tightness (%)
Cell 1
2
30
Cell 2
2
60
Cell 3
8
30
Cell 4
8
60


### 4.2. Parameter Configurations

Parameters of the proposed MAEA were determined through experiments, including the maximum generations of agents MaxMA, the lattice sizeL
size, the coefficient D
S, and the perceptive ranges R
C and R
L. The parameters of the SGA for self-learning were also assigned, including the maximum generations MaxGA, the populationsize PopSize, the crossover probability p
c, and the mutation probability p
m.The number of generations and the lattice size were determined firstly. With the increasing size of the agent latticeL and more generations of evolution, the multiagent algorithm is more likely to find the optimal solution in a longer computation time. Through testing on examples, MaxMA was set at 100 in this paper. The suitable lattice size is proportional to the number of candidate projects. We estimated L
size
=
ρ
×
N
+
1 by a coefficient ρ
=
0.4 in this paper. Since the designed 24 instances have 10 or 20 projects, the lattice size L
size takes the values of 5 or 9, respectively.According to Definitions3 and 4, when N
=
10, both perceptive ranges R
C and R
L belong to the set {
1
,
2
}. Similarly, when N
=
20, both R
C and R
L belong to the set {
1
,
2
,
3
,
4
}. Our testing showed that the proposed MAEA has a good performance when R
C
=
R
L
=
1.The coefficientD
S is used to select the strategy of generating new agents to replace loser agents. When D
S is larger, Strategy 1 is more likely to be applied, which means the new agent will be more similar to the best agent in its neighborhood. Consequently, the multiagent algorithm may be easily trapped in a local optimum. However, the stability of the algorithm will be affected when D
S is much smaller. To tradeoff between the convergence and stability, we set D
S to 0.25 according to our experiments.In summary, the parameters for the proposed multiagent evolutionary algorithm were determined as follows:MaxMA
=
100, ρ
=
0.4, R
C
=
R
L
=
1, D
S
=
0.25, MaxGA
=
10, PopSize
=
10, p
c
=
0.6, and p
m
=
0.2.


### 4.3. Computational Results and Comparison

For the above 24 instances, the profits achieved by the proposed MAEA are shown in Table2, as well as the results of two other benchmarking algorithms in [29], namely, Ranking and MKP_ranking methods.Table 2
Profit data for problem instances.
Number
Cell
Project pool
Problem size
Algorithm
Ranking
MKP_ranking
MAEA
1
1
PAT10_1
10
7076.77
7076.77
7754.63
2
1
PAT10_2
10
6343.67
6343.67
7128.61
3
1
PAT10_3
10
7700.29
7700.29
8109.66
4
1
PAT20_1
20
13512.07
13512.07
14987.3
5
1
PAT20_2
20
10510.92
10510.92
11556.38
6
1
PAT20_3
20
11672.9
11672.9
12520.37
7
2
PAT10_1
10
6988.4
6988.4
7289.51
8
2
PAT10_2
10
6199.9
6199.9
6391.59
9
2
PAT10_3
10
7700.29
7700.29
7920.52
10
2
PAT20_1
20
12829.7
12829.7
13703.7
11
2
PAT20_2
20
10033.22
10033.22
10715.38
12
2
PAT20_3
20
11580.28
11580.28
11922.46
13
3
PAT10_1
10
4316.8
4316.8
4871.05
14
3
PAT10_2
10
3850.56
3850.56
4300.49
15
3
PAT10_3
10
4320.24
4320.24
5381.88
16
3
PAT20_1
20
7522.15
7558.27
9288.56
17
3
PAT20_2
20
6323.93
6323.93
7086.58
18
3
PAT20_3
20
7902.9
7902.9
8383.34
19
4
PAT10_1
10
3942.85
3942.85
4441.45
20
4
PAT10_2
10
3850.56
3850.56
3850.56
21
4
PAT10_3
10
4320.24
4320.24
4601.84
22
4
PAT20_1
20
7464.19
7485.53
8472.36
23
4
PAT20_2
20
6176.77
6176.77
6273.44
24
4
PAT20_3
20
7544.8
7544.8
7945.27
Average
7486.85
7489.24
8120.70In the Ranking method, all candidate projects are ranked by a certain priority rule. Projects are then scheduled one by one according to their priorities until the next project makes the portfolio infeasible. It was reported that the greedy “max profit” rule performs best [29] and hence was used in this paper.The MKP_ranking method also involves two stages [29]. In the first stage, the project selection problem is solved as a multidimensional 0-1 knapsack problem (MKP) and then all selected projects are prioritized by the “max profit” rule. In the second stage, all projects selected in the first stage are scheduled sequentially. In case a selected project cannot be scheduled before its deadline due to resource constraints or it has a negative profit, the project is removed from the portfolio.The MAEA and benchmarking algorithms were implemented in C language on a PC with a CPU at 2.0 GHz and 2 GB physical memory. The average computation times are shown in Table3. It is obvious that the profit decreasing rate has a significant role in determining the computation time of the multiagent evolutionary algorithm. If the profit decreases faster after the project’s critical path length as in Cell 3 and Cell 4, the algorithm takes a much longer time to search for portfolios with projects complete in time.Table 3
Average computation times (in seconds).
Ranking
MKP-Ranking
MAEA
Cell 1
0.018
0.061
18.155
Cell 2
0.019
0.064
19.060
Cell 3
0.025
0.082
262.155
Cell 4
0.026
0.085
250.638
Average
0.022
0.073
137.502The average profits of 24 instances achieved by the three algorithms are 7486.85, 7489.24, and 8120.70, respectively. It is observed that the MAEA has a higher average profit than the other two methods.To investigate the performance of the proposed MAEA, the Wilcoxon Signed Ranks Test was applied to analyze the data in Table2. Table 4 shows the paired comparison outcomes of statistical analysis. The profits obtained by the MAEA are significantly higher than the other two methods at a significance level of 0.001.Table 4
Test statistics.
Algorithm
Ranking—MKP_Ranking
Ranking—MAEA
MKP_Ranking—MAEA
Z
−1.342a
−4.197a
−4.197a
Asymp. Sig. (2-tailed)
0.180
0.000
0.000
aBased on negative ranks.


## 4.1. Experiment Design

An RCPPSSP instance consists of a pool of candidate projects, a set of profit profiles of all projects, and the resources available for all projects. Three project pools with 10 projects in each pool and three other pools with 20 projects in each pool were generated randomly by 72 instances with three types of resources and different networks selected from the widely used Patterson set [28]. The above six project pools are denoted as PAT10_1, PAT10_2, PAT10_3, PAT20_1, PAT20_2, and PAT20_3, respectively.It is assumed that a project achieves its base profit if it is complete at its critical path length (CPL) and the profit decreases with a profit decreasing rateλ
1 as its completion time increases. Referring to [7], the base profit B
i and actual profit b
i
t of project i are calculated by formulae (22) and (23), where σ
i denotes the resource utilization coefficient which is subject to a uniform distribution in the interval of [
0.5,1.5
]. The upper bound of project completion time T
i is based on the critical path length by formula (24), and the relaxation rate λ
2 has the value of 0.4 in this paper. Resource tightness ω
k is introduced to estimate the capacity of resource k from its maximum resource demand R
k
max
⁡ in the critical path method:
(22)
B
i
=
σ
i
∑
k
=
1
K
∑
j
=
1
J
i
r
i
j
k
d
i
j
,
(23)
b
i
t
=
B
i
(
1
-
λ
1
(
t
-
CPL
i
)
)
,
(24)
T
i
=
CPL
i
+
min
⁡
{
10
,
λ
2
CPL
i
}
,
(25)
R
k
=
ω
k
R
k
max
⁡
.Two levels of profit decreasing rateλ
1  (2% or 8%) and resource tightness (30% or 60%) were designed, which forms four experiment cells as shown in Table 1. This 22 experimental design crossed with our six project pools yielded 24 instances to test the proposed algorithm.Table 1
Experiment design.
Profit decreasing rate (%)
Resource tightness (%)
Cell 1
2
30
Cell 2
2
60
Cell 3
8
30
Cell 4
8
60


## 4.2. Parameter Configurations

Parameters of the proposed MAEA were determined through experiments, including the maximum generations of agents MaxMA, the lattice sizeL
size, the coefficient D
S, and the perceptive ranges R
C and R
L. The parameters of the SGA for self-learning were also assigned, including the maximum generations MaxGA, the populationsize PopSize, the crossover probability p
c, and the mutation probability p
m.The number of generations and the lattice size were determined firstly. With the increasing size of the agent latticeL and more generations of evolution, the multiagent algorithm is more likely to find the optimal solution in a longer computation time. Through testing on examples, MaxMA was set at 100 in this paper. The suitable lattice size is proportional to the number of candidate projects. We estimated L
size
=
ρ
×
N
+
1 by a coefficient ρ
=
0.4 in this paper. Since the designed 24 instances have 10 or 20 projects, the lattice size L
size takes the values of 5 or 9, respectively.According to Definitions3 and 4, when N
=
10, both perceptive ranges R
C and R
L belong to the set {
1
,
2
}. Similarly, when N
=
20, both R
C and R
L belong to the set {
1
,
2
,
3
,
4
}. Our testing showed that the proposed MAEA has a good performance when R
C
=
R
L
=
1.The coefficientD
S is used to select the strategy of generating new agents to replace loser agents. When D
S is larger, Strategy 1 is more likely to be applied, which means the new agent will be more similar to the best agent in its neighborhood. Consequently, the multiagent algorithm may be easily trapped in a local optimum. However, the stability of the algorithm will be affected when D
S is much smaller. To tradeoff between the convergence and stability, we set D
S to 0.25 according to our experiments.In summary, the parameters for the proposed multiagent evolutionary algorithm were determined as follows:MaxMA
=
100, ρ
=
0.4, R
C
=
R
L
=
1, D
S
=
0.25, MaxGA
=
10, PopSize
=
10, p
c
=
0.6, and p
m
=
0.2.


## 4.3. Computational Results and Comparison

For the above 24 instances, the profits achieved by the proposed MAEA are shown in Table2, as well as the results of two other benchmarking algorithms in [29], namely, Ranking and MKP_ranking methods.Table 2
Profit data for problem instances.
Number
Cell
Project pool
Problem size
Algorithm
Ranking
MKP_ranking
MAEA
1
1
PAT10_1
10
7076.77
7076.77
7754.63
2
1
PAT10_2
10
6343.67
6343.67
7128.61
3
1
PAT10_3
10
7700.29
7700.29
8109.66
4
1
PAT20_1
20
13512.07
13512.07
14987.3
5
1
PAT20_2
20
10510.92
10510.92
11556.38
6
1
PAT20_3
20
11672.9
11672.9
12520.37
7
2
PAT10_1
10
6988.4
6988.4
7289.51
8
2
PAT10_2
10
6199.9
6199.9
6391.59
9
2
PAT10_3
10
7700.29
7700.29
7920.52
10
2
PAT20_1
20
12829.7
12829.7
13703.7
11
2
PAT20_2
20
10033.22
10033.22
10715.38
12
2
PAT20_3
20
11580.28
11580.28
11922.46
13
3
PAT10_1
10
4316.8
4316.8
4871.05
14
3
PAT10_2
10
3850.56
3850.56
4300.49
15
3
PAT10_3
10
4320.24
4320.24
5381.88
16
3
PAT20_1
20
7522.15
7558.27
9288.56
17
3
PAT20_2
20
6323.93
6323.93
7086.58
18
3
PAT20_3
20
7902.9
7902.9
8383.34
19
4
PAT10_1
10
3942.85
3942.85
4441.45
20
4
PAT10_2
10
3850.56
3850.56
3850.56
21
4
PAT10_3
10
4320.24
4320.24
4601.84
22
4
PAT20_1
20
7464.19
7485.53
8472.36
23
4
PAT20_2
20
6176.77
6176.77
6273.44
24
4
PAT20_3
20
7544.8
7544.8
7945.27
Average
7486.85
7489.24
8120.70In the Ranking method, all candidate projects are ranked by a certain priority rule. Projects are then scheduled one by one according to their priorities until the next project makes the portfolio infeasible. It was reported that the greedy “max profit” rule performs best [29] and hence was used in this paper.The MKP_ranking method also involves two stages [29]. In the first stage, the project selection problem is solved as a multidimensional 0-1 knapsack problem (MKP) and then all selected projects are prioritized by the “max profit” rule. In the second stage, all projects selected in the first stage are scheduled sequentially. In case a selected project cannot be scheduled before its deadline due to resource constraints or it has a negative profit, the project is removed from the portfolio.The MAEA and benchmarking algorithms were implemented in C language on a PC with a CPU at 2.0 GHz and 2 GB physical memory. The average computation times are shown in Table3. It is obvious that the profit decreasing rate has a significant role in determining the computation time of the multiagent evolutionary algorithm. If the profit decreases faster after the project’s critical path length as in Cell 3 and Cell 4, the algorithm takes a much longer time to search for portfolios with projects complete in time.Table 3
Average computation times (in seconds).
Ranking
MKP-Ranking
MAEA
Cell 1
0.018
0.061
18.155
Cell 2
0.019
0.064
19.060
Cell 3
0.025
0.082
262.155
Cell 4
0.026
0.085
250.638
Average
0.022
0.073
137.502The average profits of 24 instances achieved by the three algorithms are 7486.85, 7489.24, and 8120.70, respectively. It is observed that the MAEA has a higher average profit than the other two methods.To investigate the performance of the proposed MAEA, the Wilcoxon Signed Ranks Test was applied to analyze the data in Table2. Table 4 shows the paired comparison outcomes of statistical analysis. The profits obtained by the MAEA are significantly higher than the other two methods at a significance level of 0.001.Table 4
Test statistics.
Algorithm
Ranking—MKP_Ranking
Ranking—MAEA
MKP_Ranking—MAEA
Z
−1.342a
−4.197a
−4.197a
Asymp. Sig. (2-tailed)
0.180
0.000
0.000
aBased on negative ranks.


## 5. Conclusions

In this paper, the resource-constrained project portfolio selection and scheduling problem is formulated as a 0-1 integer programming model. The problem has a dual level structure. Project scheduling in the lower level helps increase the portfolio profit by improving the resource allocation among selected projects and rescheduling their activities. A multiagent evolutionary algorithm is proposed to solve the RCPPSSP. The algorithm adopts a dual level structure owing to the nature of the RCPPSSP. In the upper level, agents in an agent lattice are designed to search for feasible portfolios automatically. The neighborhood competition operator and self-learning operator are integrated to accelerate the evolution of agents. In the lower level, each agent adopts a priority rule-based heuristic to conduct multiproject scheduling to better utilize the scarce resources. We conducted an experiment to test the performance of the proposed algorithm. A set of 24 instances were generated from the Patterson set systematically. Computational results show that the proposed multiagent evolutionary algorithm has an outstanding performance.



---

*Source: 302684-2014-04-22.xml*