A biased random-key genetic algorithm for the project scheduling problem with flexible resources

Abstract

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an $\mathcal {NP}$-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.

1 Introduction

The resource-constrained project scheduling problem (RCPSP) is a well-known problem that consists of scheduling a set of activities, each of which requiring specific resources that are available in limited quantities. The goal is to minimize the makespan. This problem has been widely studied in the literature along with many variants. For an overview on this topic, the reader can refer to Herroelen and Demeulemeester (1998), Brucker et al. (1999), Hartmann and Briskorn (2010), and Węglarz et al. (2011), as well as to the references therein.

In many RCPSPs, resources are flexible, which means that each resource masters more than one skill. This is particularly true when human resources or multi-purpose machines are involved in a project. Typically, in this context, activities require specific resource units of several skills to be processed. The assignment of a resource to an activity comprehends the decision of the skill it will perform, chosen among the skills required by that activity and mastered by this resource. This extension of the RCPSP defines the basic setting of the so-called resource-constrained project scheduling problem with flexible resources. Hereafter, we will shorten this name and refer to the problem as the project scheduling problem with flexible resources (PSPFR). This problem and some of its variants have been introduced and studied in the literature as we detail next. Li and Womer (2009) develop a hybrid Benders decomposition for a PSPFR whose objective function regards the minimization of the total cost associated with the resources, while assuring that a predefined deadline for the project is satisfied. In such problem, each activity requires only one resource unit per each skill needed for its execution. Correia et al. (2012) propose a mixed-integer linear programming formulation for a PSPFR where the activities may require several resources per each skill needed for their execution. The objective is to minimize the makespan of the project. Several sets of additional inequalities and reduction tests are also proposed. The impact of using fixed and variable costs in a PSPFR is studied by Correia and Saldanha-da-Gama (2014) who develop a mixed-integer model with a non-linear objective function. The model is linearized and is strengthened through the inclusion of additional inequalities. Finally, the enhanced formulation is tested using an off-the-shelf solver. More recently, Correia and Saldanha-da-Gama (2015) propose a general modeling framework for a PSPFR. The authors discuss several modeling issues and propose several procedures for enhancing the models.

Flexible resources have also been considered in the context of project portfolio problems, but, typically, with additional assumptions. For example, in the works by Gutjahr et al. (2008) and Heimerl and Kolisch (2010), no sequencing decisions involving the activities have to be made. The problem studied by Gutjahr et al. (2008) involves the selection of the projects to be executed among a set of available projects. The activities of each project must be executed within specific and predetermined time-windows. Each activity requires resources, each of which mastering several skills at different levels of efficiency that may change over time. Heimerl and Kolisch (2010) address a project scheduling and staffing problem with hierarchical levels of skills where the goal is to minimize the variable costs associated with the resources. A related staffing problem, which also considers that the skills can be performed at different levels of efficiency, was investigated by Walter and Zimmermann (2016). The problem investigated in the current paper is the PSPFR studied by Correia et al. (2012). The methodology proposed in that paper turned out to be effective only for small-sized instances. Almeida et al. (2016) proposed a heuristic for tackling larger instances of such problem by extending the well-known parallel scheduling scheme (Kolisch 1996a, b). Despite the significant advances represented by the work published by Almeida et al. (2016), much work still remains to be done namely in terms of improving the quality of the feasible solutions obtained. The current paper emerges in this context. In particular, we propose a constructive heuristic for the PSPFR based on the serial scheduling scheme as well as a biased random-key genetic algorithm (BRKGA) aiming at coordinating that scheme with the parallel scheduling scheme of Almeida et al. (2016). To the best of the authors’ knowledge, a BRKGA has never been proposed for a PSPFR, although it has been applied successfully to RCPSPs (see Gonçalves et al. 2008; Mendes et al. 2009, and Gonçalves et al. 2011). BRKGA algorithms have also been successfully applied to other optimization problems such as packing (Gonçalves and Resende 2013), facility layout (Gonçalves and Resende 2015), capacitated minimum spanning trees (Ruiz et al. 2015), among others.

We note that the need for the development of heuristics for the PSPFR has also been observed for the RCPSP as attested, for instance, in the works by Hartmann and Kolisch (2000), Kolisch and Hartmann (1999), and Kolisch and Hartmann (2006), who provide valuable contributions in this context.

The remainder of this paper is organized as follows. In Sect. 2, we describe the PSPFR and some of its properties and additional concepts. Sect. 3 is dedicated to the heuristic we propose. Finally, in Sect. 4, we report the computational tests performed to evaluate the BRKGA. The paper ends with an overview of the work done and with some directions for further research.

2 Problem description and properties

As we have already mentioned, the problem studied in this work is the PSPFR studied by Correia et al. (2012). To make the paper self-contained, we describe next the problem. In addition, we introduce some relevant concepts for the remainder of the paper.

Consider a project represented by an activity-on-node network $G=(V,E)$ where $V = \{0, 1, \ldots , j, \ldots , n+1\}$ denotes the set of activities and E is the set of arcs representing the precedence relations between the activities. Activities 0 and $n+1$ are dummy activities that represent the start and the conclusion of the project, respectively. An arc (i, j) is in E if activity i is a direct predecessor of activity j. For every $j \in V {\setminus } \{0\}$, we denote by Pred(j) the set of predecessors of j; for $j \in V {\setminus } \{n+1\}$, Succ(j) is the set of its successors. The weight of an arc (i, j) is denoted by $p_i$ and represents the processing time of activity i. Preemption is not allowed, i.e., once an activity starts being executed, it cannot be interrupted.

A set of renewable resources $\mathcal{R} = \{1,\ldots ,k,\ldots ,K \}$ mastering one or several skills is required to execute the activities. The pool of available skills is denoted by $\mathcal{L} = \{1,\ldots ,l,\ldots ,L\}$. The set of skills mastered by resource $k \in \mathcal{R}$ is denoted by $\mathcal{L}^k$, and the set of skills required by an activity $j \in V$ is represented by $\mathcal{L}_j$. The number of resources mastering skill $l \in \mathcal{L}_j$ required by activity $j \in V$ is denoted by $r_{jl}$. A resource can be involved in only one activity at a time and for a single skill; furthermore, once it is assigned to an activity with a skill, it remains so during the whole processing time of this activity.

The goal of the PSPFR is to determine for each activity $j \in V {\setminus } \{0,n+1\}$, (i) its starting time, hereafter denoted by $S_j$ and (ii) the pairs (resource, skill) that should be assigned to it. The objective is to minimize the project’s makespan.

In the PSPFR, it is also assumed that the values $p_j$ and $r_{jl}$ ($j \in V {\setminus } \{0, n+1\}; l \in \mathcal{L}_j$) are positive integers and are zero for the dummy activities. As a result, the makespan of the project is a positive integer less than or equal to $\sum _{j \in V} p_j$, which is the value obtained by a sequential execution of the activities.

2.1 Additional concepts and properties

The upper bound given by $\sum _{j \in V} p_j$ can usually be improved when some activities can be executed in parallel, i.e., can have their execution overlapping for some time. However, in the PSPFR, it is not trivial to check whether two or more activities can be executed in parallel. The difficulty emerges from the fact that we have (multi-skill) resource constraints in addition to the usual precedence ones. This aspect may be crucial when it comes to obtaining good feasible solutions for the problem. Above all, it is important to have a mechanism, as efficient as possible, to check whether two or more activities can overlap in time. We discuss this issue next.

Assume that, at a given time $t>0$, some activities have already been scheduled to have their execution time starting before t. Denote by UV the activities still to be scheduled and by $W_t$ a subset of UV containing only activities (not necessarily all), such that all their predecessors are already completed at time t (or that have no predecessors). Can we set to t the starting time of all the activities in $W_t$?

This query has a positive answer if all the resources available at time t can meet the skill requirements of all the activities in $W_t$ at the same time. In that case, the literature on PSPFR denominates $W_t$ as a set of compatible activities (see Correia et al. 2012). This concept is equivalent to the notion of feasible set proposed by Mingozzi et al. (1998) for the RCPSP. Checking the existence of precedence relations between each pair of activities can be done straightforwardly. However, this is not the case when we need to verify whether there are enough resources to meet all the skill requirements of the activities in $W_t$ simultaneously.

Let us denote by $\mathcal{Z}_{W_t}$ the set of resources that are available at time t and which master at least one skill required by at least one activity in $W_t$. In addition, denote by $\mathcal{L}_{W_t}$ the set of skills required to process the activities in $W_t$. Checking whether the set of activities $W_t$ is compatible can be done in polynomial time by solving a flow feasibility problem in an appropriate network that we denote by $G_{W_t}=(V_{W_t},E_{W_t})$, which is built as follows:

• The set of nodes $V_{W_t}$ contains: (i) a source node, $v_0$; (ii) a set of nodes—one for each resource in $\mathcal{Z}_{W_t}$; (iii) a set of nodes—one for each skill in $\mathcal{L}_{W_t}$; (iv) a sink node, $v_s$.

• The set of arcs $E_{W_t}$ is defined by: (i) a set of arcs $(v_0, k)$, $k \in Z_{W_t}$ with minimum throughput 0, capacity 1 and unitary cost 0; (ii) a set of arcs (k, l), $l \in (\mathcal{L}^k \cap \mathcal{L}_{W_t})$ with minimum throughput 0, capacity 1 and unitary cost 0; (iii) a set of arcs $(l, v_s)$, $l \in \mathcal{L}_{W_t}$ with minimum throughput and capacity given by $r_{{W_t}l}$ and unitary cost equal to 0, where $r_{{W_t}l}$ denotes the number of resource units required to process skill l for all the activities in $W_t$.

Fig. 1

Illustration of the auxiliary graph $G_{W_t}$

The network $G_{W_t}$ is illustrated in Fig. 1. If a feasible flow exists in this auxiliary network, then we know that there are enough resources to start processing all the activities in $W_t$, at time t. However, as we explain next, we can go deeper in this analysis, which requires revisiting some additional concepts.

2.1.1 Resource weights

A feasible flow in $G_{W_t}$ induces an assignment of the resources in $\mathcal{Z}_{W_t}$ to the skills required by the activities in $W_t$. Such a flow may not be unique due to the flexible nature of the resources, which may render different possibilities of meeting the skill demands of $W_t$ by varying (i) the selected resources from the set $\mathcal{Z}_{W_t}$ or (ii) the skill $l \in \mathcal{L}_{W_t}$ that each resource in (i) is assigned to perform, or both (i) and (ii).

Since each resource k masters a specific set of skills, $\mathcal{L}^k$, we may characterize a resource as being more versatile than others (e.g., by mastering more skills), more important (e.g., by mastering scarce or highly required skills), etc. Hence, to compute feasible solutions, it becomes relevant to determine the best resource to meet each unitary skill demand, because this assignment may have impact in future iterations and thus compromise the quality of the derived schedule. In Almeida et al. (2016), this fact motivated the development of a new concept—the weight of a resource: for some resource $k \in \mathcal{R}$, its weight is denoted by $w_k$ and represents a measure resulting from selecting that resource to execute a skill mastered by it and required by at least one activity $j \in W_t$.

2.1.2 Resource assignment

Almeida et al. (2016) propose assigning the resources to the skills required by $W_t$ by solving a min-cost flow problem in a modified network $\widetilde{G}_{W_t}=(V_{W_t},E_{W_t})$ obtained from $G_{W_t}=(V_{W_t},E_{W_t})$ by replacing the weight of each arc $(v_0, k)$, $k \in \mathcal{Z}_{W_t}$, by the corresponding resource weight, $w_k$. That problem will be named $MCNFP(\widetilde{G}_{W_t})$.

Again, a feasible flow in $\widetilde{G}_{W_t}$ indicates that $W_t$ is a set of compatible activities. However, an optimal solution to $MCNFP(\widetilde{G}_{W_t})$ only provides an assignment of the resources $k \in \mathcal{Z}_{W_t}$ to the skills $l \in (\mathcal{L}^k \cap \mathcal{L}_{W_t})$; it does not indicate the activity each resource is allocated to. In particular, for every $l \in \mathcal{L}_{W_t}$, we obtain a set of resources $\mathcal{X}_{{W_t}l} \subseteq \mathcal{Z}_{W_t}$ that meet the skill requirements of activity l. In Almeida et al. (2016), a heuristic procedure is proposed for assigning the resources with larger weights to the activities with smaller processing times, in an attempt to make those resources (looked as valuable) free as soon as possible and thus available to be assigned to other activities that may need them.

2.1.3 Activity priorities

Likewise for the resources, when we look deeply into the activities, we realize that a sort of ranking can be devised. In an attempt to use some rational mechanism for building that rank, Almeida et al. (2016) computed a priority value, $pv_j$, for each activity $j \in V {\setminus }\{0,n+1\}$ using the well-known activity priority rules already proposed for the RCPSP (Kolisch 1996a; Demeulemeester and Herroelen 2002). In the next section, we show that the priority values for the activities can be dynamically adapted.

3 A new constructive heuristic

In this section, we detail the new heuristic proposed in this work for the PSPFR. We start by reviewing basic aspects related with the underlying metaheuristic, and then, we introduce the specifications for our problem.

3.1 BRKGAs

In a BRKGA, a population of chromosomes evolves over a number of generations until the defined stopping criteria are met (cf. Gonçalves and Resende 2011). Each chromosome encodes a solution of the problem and is represented by an m-dimensional vector of real numbers in the interval [0,1]—the random keys. The BRKGA differs from the classical genetic algorithm in the following aspects: (i) the chromosomes with the best fitness values in one generation (elite population) are copied unchanged to the next generation; (ii) in each generation, a new set of chromosomes is generated from scratch and is included in the population—the mutants, instead of using the classical mutation operators; (iii) a parameterized crossover occurs between a parent selected from the set of elite chromosomes and a parent select from the set of non-elite chromosomes. Algorithm 1 depicts a generic BRKGA where p denotes the number of chromosomes in the population; m is the number of genes in each chromosome; $p_e$ and $p_m$ denote the percentage of elite and mutant chromosomes in the population, respectively; $\rho _e$ represents the probability of a descendant inheriting an allele from its elite parent; U[0, 1] denotes a random number in the interval [0, 1]; g is a generation counter; and finally, $c^*$ and $f^*$ denote, respectively, the best chromosome and its fitness value.

3.2 Application to the PSPFR

In this section, we introduce the structure of the chromosomes and the decoder that we propose for the PSPFR. These are the components of Algorithm 1 that are specific to each particular problem.

3.2.1 Decoder

Since the PSPFR is an extension of the RCPSP, two natural decoders for the former emerge from extending the well-known parallel and serial scheduling schemes existing for the latter designated by PSS and SSS, respectively (cf. Kolisch 1996b).

Although the SSS and the PSS can be looked at as simple heuristic strategies for the RCPSP, their extension to the PSPFR is more complex due to the selection and assignment of the flexible resources to the activities of the project.

The PSS was extended to the PSPFR by Almeida et al. (2016). This is an iterative method where, initially, the time counter is set to 0. In each iteration, which is associated with a specific moment in time t, the set of precedence feasible activities $W_t$ is built. If $W_t$ is empty, the value of t is incremented to the next time in which some activity becomes available for execution due to the completion of all its predecessors. Otherwise, either there are enough resources—among those available at time t—to meet all the skill requirements of the activities in $W_t$, and hence, all these activities are set to start being processed at time t, or this is not the case; and thus, the activity with the smallest priority value is successively removed from $W_t$ until the resulting set is either empty or all the skill requirements of its activities can be met. The reader should refer to Almeida et al. (2016) for all the details.

Concerning the SSS, we propose next its adaptation to the PSPFR. Again, it consists of an iterative procedure that starts by setting the time counter t to 0. In each iteration, the activity $j^*$ with the highest priority value and whose predecessors have already been executed is selected to be scheduled. The time counter t is then set to the maximum completion time across all the predecessors of $j^*$. Activity $j^*$ is scheduled to start at time t if the resources available from time t to time $t + p_{j^*} - 1$ are enough to fulfil all its skill requirements; otherwise, t, is moved forward to the next completion time of the activities already scheduled. Again, the availability of resources is checked. This process repeats until eventually activity $j^*$ is scheduled. In the SSS that we are proposing, the set $W_t$ contains only the activity selected to be scheduled next. This means that, in this case, we no longer need to consider this set. Nevertheless, we keep it for exposition purposes, because this notation was also used in Almeida et al. (2016). The new scheme which we are proposing is fully detailed in Algorithm 2.

In contrast to the PSS, in the SSS which we are proposing, it is possible to have already scheduled activities which start after time t. In fact, when an activity, say $j^*$, is selected to be scheduled, the time t is moved to the maximum completion time of all predecessors of $j^*$. Therefore, it is possible to have other already scheduled activities which have the necessary resources allocated and their starting times higher than t. Hence, for a given time t, deciding whether activity $j^*$ can start being processed at that time, requires checking if the resources available in every time slot where $j^*$ will be in progress, from t to its provisional finish time $t + p_{j^*} - 1$, can fulfil all its skill requirements.

The PSS by Almeida et al. (2016) and the SSS just presented can also be applied to the problem obtained by reversing all the arcs in the precedence network. This problem is equivalent to planning the project backwards starting at the end and moving regressively to the beginning. Naturally, the problem to be solved is the same, but the order by which each activity is scheduled may be different, and hence, a different resource selection and assignment may occur, which results in a schedule with, possibly, a different makespan. This concept of backward planning has already been applied to the RCPSP by Li and Willis (1992), Özdamar (1999), Klein (2000), and Alcaraz and Maroto (2001), to mention a few.

3.2.2 Chromosomes’ structure

The structure of the chromosomes that we propose is inspired on the chromosomes considered by Alcaraz and Maroto (2001, 2006), Hartmann (2002), Gonçalves et al. (2008), Mendes et al. (2009), and Gonçalves et al. (2011). We define a chromosome as having $m=n+K+2$ genes, where n is the number of non-dummy activities, K is the number of resources, and the last two positions are associated with the decoder. In particular, one of the last two genes indicates the scheduling generation scheme (PSS or SSS), while the other refers to the precedence network scheme (original or reversed). Figure 2 illustrates this chromosome structure. A chromosome with a gene indicating whether a PSS or a SSS shall be used was proposed by Hartmann (2002), while Alcaraz and Maroto (2001) consider a chromosome with an additional gene that indicates whether the original or reversed precedence network is used. In Alcaraz and Maroto (2006), both genes were included in a chromosome structure which they propose for the RCPSP. To the best of the authors’ knowledge, a chromosome that includes genes associated with the resources along with a gene for decoder selection and a gene for encoding the precedence network scheme has never been attempted before.

Fig. 2

Generic chromosome for the developed BRKGA

The PSS and SSS for the PSPFR require a priority value, $pv_j$, to each activity $j \in V {\setminus }\{0,n+1\}$ and a weight value, $w_k$, to each resource $k \in \mathcal{R}$. This information will be embedded in the chromosome structure which we propose where each allele is a random uniform number in [0,1]. In particular, the value of the first n genes will give the priority value of the corresponding activity, while the value of the next K genes will give the weights of the resources. The information associated with the last two genes is provided in Table 1.

Table 1 Decoder parameters

Figure 3 illustrates a chromosome within our BRKGA that will be decoded with the PSS applied to the reverse precedence network.

Fig. 3

Example of a chromosome

Using this chromosome structure, the same sequence of activities’ priority values and resources’ weight values may originate four different feasible solutions for the PSPFR, by changing the values of the last two genes. This kind of structure may help diversifying the exploration of the solution space. Another positive feature of this representation is its versatility. In fact, if the values of the last two genes are fixed for all the chromosomes generated in the BRKGA, this means that all chromosomes will be decoded with the same algorithm.

4 Computational experience

In this section, we report the numerical experiments performed to evaluate the performance of the BRKGA. The algorithm and the decoders were coded in C++. The min-cost flow problems were solved by integrating IBM ILOG CPLEX 12.6 with C++ through Concert Technology. All computational experiments were performed on a machine running an Intel Core i7 4770K with 32 GB of RAM.

This section is organized as follows. In Sect. 4.1, we present the benchmark instances used in the tests. In Sect. 4.2, we discuss the fine-tuning of the algorithm. Finally, in Sect. 4.3, the computational results are reported.

4.1 Test instances

Two different sets of instances, hereafter denoted by Set 1 and Set 2, were considered. The Set 1 contains the 216 instances generated by Correia et al. (2012), whereas Set 2 refers to 216 larger instances built using the generator proposed by Almeida et al. (2015), which were already used by Almeida et al. (2016). The reader should refer to those works for all the details regarding the instances used.

From the work by Correia et al. (2012), we know the optimal value for 203 instances of Set 1 and a lower bound for the remaining 13 instances in this set.

Apart from other parameters, the instances were generated with different values of network complexity (NC), skill factor (SF), and modified resource strength (MRS).

4.2 Fine-tuning the BRKGA

By making use of a set of preliminary tests, it was possible to find good values for the parameters of the BRKGA. Nevertheless, to get a hint in terms of good ranges for those parameters, we referred again to Gonçalves et al. (2008), Mendes et al. (2009), and Gonçalves et al. (2011). The preliminary experiments were performed on instances from Set 1, since we know the optimal value for most of them. We start by considering three variants of the BRKGA with regard to the type of decoder employed, namely: (i) all the chromosomes are decoded with the PSS; (ii) all the chromosomes are decoded with the SSS; and (iii) the decoder applied to each chromosome depends on the value of the allele in the position $n + K + 1$. These experiments allow us to evaluate if one of the variants performs better than the others. Regarding the precedence network schemes (original or reversed), the computational results provided by Almeida et al. (2016) indicate no dominance. Moreover it was not even possible to identify any class of instances (defined by SF, NC, and MRS) where a precedence network scheme performs better than the other. Therefore, we decided to use both network schemes to diversify the search space and this means that, in each chromosome, the gene $n+K+2$ indicates the scheme used by the decoder.

Regarding the other BRKGA parameters, Table 2 presents the values considered whose combination originates 36 distinct configurations. Each BRKGA configuration was set to run 5 times for each instance (using a distinct seed for the random number generation at the beginning of each run). Accordingly, for each instance tested, it is possible to compute the average and minimum values for the makespan. The runs are independent from each other and terminate when the maximum number of generations is reached.

Table 2 Preliminary tests—range of values for the BRKGA parameters

We present in Table 3 the overall results for every configuration tested. This table consists of two main sets of columns: (i) columns 4–8 refer to the results after n / 2 generations and (ii) columns 9–13 to the results after $5 \times n$ generations. The scheduling generation scheme considered as well as the values of $p_e$ and $p_m$ are presented in columns 1–3, respectively. Each row depicts the average values for the 216 instances in Set 1. In terms of percentage gaps, their average and minimum values are indicated in columns 4 and 9, and columns 5 and 10, respectively. The average makespan values and their associated standard deviations are presented in columns 6 and 11, and columns 7 and 12, respectively. Columns 8 and 13 contain the CPU time (in seconds) used in the 5 runs until reaching $\frac{n}{2}$ generations and $5 \times n$ generations, respectively. Each gap (in percentage) is computed as $100 \times (Z^\mathcal{B} - Z^{LB})/Z^{LB}$, where $Z^\mathcal{B}$ denotes the upper bound provided by the BRKGA and $Z^{LB}$ denotes the optimal value or the best known lower bound.

The makespan values and gaps presented in Table 3 allow us to conclude that, as expected, with $5 \times n$ generations, it was possible to obtain better upper bounds than those obtained with n / 2 generations. However, this improvement in the quality of the feasible solutions was achieved at the expense of a CPU time one order of magnitude higher, which seems not to be compensatory. Hence, we narrow our analysis using the results obtained after n / 2 generations.

Looking into such results (max. n / 2 generations), we conclude that the use of the PSS in all chromosomes provided the best results in terms of the average percentage gaps and CPU time. However, the use of both decoders yielded the best minimum gaps for the majority of the combinations of $p_e$ and $p_m$. Among the six combinations of $p_e$ and $p_m$, we adopt $p_e=10\%$ and $p_m=30\%$, since this combination originated the best average and minimum gaps.

Table 3 BRKGA—results for the preliminary tests

In Almeida et al. (2016), we observe that higher percentage gaps were obtained for instances having less resources. Since those instances were also the ones that required less computational time, we take advantage of this behavior and consider a population size determined not only by the number of activities (n) but also by the number of resources (K) in each instance. Once again, we used all the instances in Set 1 and tested a population $p = 5 \times \lceil \frac{n \times n}{K}\rceil$, considering the adopted values of $p_e$ and $p_m$, and decoding all chromosomes with the PSS. By fixing the number of activities (which is 20 for all these instances), such value for p originates larger population sizes for the instances with a smaller number of resources. The preliminary computations show that this p value yields an improvement in the average solution gaps (when compared to the population of size $p = 5 \times n$) of roughly 6%, at the expense of an 8% increase in the total time, for the BRKGA configuration having $p_e=10\%, p_m=30\%$ and only the PSS decoder.

Considering the information resulting from the preliminary computations, we decided to deepen our computational tests considering the following configurations: (i) $p = 5 \times \lceil \frac{n \times n}{K}\rceil$, $p_e = 10\%$, $p_m = 30\%$, $\rho _e = 0.7$, and $\delta = PSS$; (ii) $p = 5 \times \lceil \frac{n \times n}{K}\rceil$, $p_e = 10\%$, $p_m = 30\%$, $\rho _e = 0.7$, and $\delta = Both$. The maximum number of generations assumed as the stopping criterion is n / 2.

4.3 Computational results

We discuss separately the results obtained for instances in Sets 1 and 2. In what follows, we denote the BRKGA with the single decoder PSS as $\mathrm{BRKGA}_\mathrm{PSS}$ and the BRKGA with the two decoders as $\mathrm{BRKGA}_\mathrm{Both}$.

4.3.1 Results for the instances in $Set\, 1$

In Table 4, we present the results for the instances in Set 1 considering the 36 groups induced by the values of SF, NC, and MRS. Each row aggregates six instances. The gaps were computed as explained above. In Table 5, we summarize these results.

The information presented in Tables 4 and 5 is organized as follows: columns 1–3 indicate the characteristics of the instances; columns 4–10 contain the results obtained with the $\mathrm{BRKGA}_\mathrm{PSS}$. In particular, columns 4, 5, and 6 are associated with the average, minimum, and maximum gaps achieved; columns 7 and 8 depict the average makespan values and their associated standard deviation, respectively; and column 9 contains the total CPU time (seconds) required to perform the 5 runs; columns 10–14 contain the same information as before but for $\mathrm{BRKGA}_\mathrm{Both}$; finally, columns 15–16 contain the gaps obtained by the heuristic proposed in Almeida et al. (2016) and the corresponding CPU time.

From Table 4, we observe that the average, minimum, and maximum gaps achieved by the $\mathrm{BRKGA}_\mathrm{PSS}$ improve the results provided by Almeida et al. (2016) in 26, 27, and 23 out of the 36 classes of instances, respectively. In terms of average and minimum gaps, the $\mathrm{BRKGA}_\mathrm{PSS}$ achieved the same results as the heuristic of Almeida et al. (2016) in 8 classes of instances, 7 of which correspond to a gap of 0.0%. The 12 classes of instances whose minimum gaps obtained by the $\mathrm{BRKGA}_\mathrm{PSS}$ are highlighted in boldface indicate that the $\mathrm{BRKGA}_\mathrm{PSS}$ was able to find the optimal value of all these 72 instances, but the constructive heuristic of Almeida et al. (2016) was not.

Table 4 Set 1: Comparative analysis$\textendash \textendash$Detail

The higher gaps yielded by the $\mathrm{BRKGA}_\mathrm{PSS}$ are associated with instances with $\mathrm{SF}=\text{ var. }$, $\mathrm{NC}=1.5$, and $\mathrm{MRS}=0.1667$. The higher values of the standard deviation of the makespan occur more often in the sets of instances associated with the smallest values of MRS, which correspond to the hardest instances with a fewer resources, hence having larger population sizes and thus being more time consuming.

The last row of Table 4 presents the average results across all the 216 instances in Set 1. We observe that the overall average gap provided by the multi-pass heuristic was improved by the $\mathrm{BRKGA}_\mathrm{PSS}$ from 2.65 to 1.10% (average gaps) and to 0.79% (minimum gaps).

In terms of CPU time, the $\mathrm{BRKGA}_\mathrm{PSS}$ requires an average time of one minute, while the heuristic by Almeida et al. (2016) needs, on average, 1 s. However, the supremacy of the $\mathrm{BRKGA}_\mathrm{PSS}$ is clear in terms of the quality of the obtained gaps and 1 min of average time is still negligible when we look into the difficulty of the PSPFR.

Table 5 Set 1: Comparative analysis—Summary

Similar conclusions can be drawn from the results obtained when using $\mathrm{BRKGA}_\mathrm{Both}$. In fact, the $\mathrm{BRKGA}_\mathrm{Both}$ achieves better results than those obtained by the heuristic of Almeida et al. (2016) for 26 classes out of 36 classes of instances both in terms of average and minimum gaps. Regarding the maximum gaps, better results were obtained for 22 classes of instances out of 36 classes. The 9 classes of instances whose minimum gaps obtained by the $\mathrm{BRKGA}_\mathrm{Both}$ are highlighted in boldface indicate that the $\mathrm{BRKGA}_\mathrm{Both}$ was able to find the optimal value of all these 54 instances, but the heuristic of Almeida et al. (2016) was not.

In Table 4, we can also observe the supremacy of the $\mathrm{BRKGA}_\mathrm{Both}$ over the $\mathrm{BRKGA}_\mathrm{PSS}$ regarding average gaps for 4 classes of instances, regarding minimum gaps for also 4 classes of instances and in terms of maximum gaps for 7 classes of instances. Furthermore, the $\mathrm{BRKGA}_\mathrm{Both}$ was able to reach the optimal solutions for the 12 instances in the classes defined by $\mathrm{SF}=\text{ var. }, \mathrm{NC}=1.8, \mathrm{MRS}=0.2083$, and $\mathrm{SF}=0.5, \mathrm{NC}=1.5, \mathrm{MRS}=0.1875$, whereas this was not the case with the $\mathrm{BRKGA}_\mathrm{PSS}$. This behavior may be associated with the use of the SSS decoder which was also the responsible for the $\mathrm{BRKGA}_\mathrm{Both}$ requiring a slightly higher computational time than the $\mathrm{BRKGA}_\mathrm{PSS}$.

From Table 5 and considering the $\mathrm{BRKGA}_\mathrm{PSS}$, one can conclude that as the SF decreases, the gaps also decrease, while the computational time increases. This increase may be justified by the fact that instances with a smaller SF have fewer resources and thus originate larger population sizes. For instances having $\mathrm{SF} = 0.5$, the $\mathrm{BRKGA}_\mathrm{PSS}$ produced solutions that correspond to an improvement of 6 and 22.8 times the results of Almeida et al. (2016), for average and minimum percentage gaps, respectively. Concerning NC, we observe that an increase in this parameter leads, as expected, to a reduction in the gaps of the BRKGA. The $\mathrm{BRKGA}_\mathrm{PSS}$ was able to reduce the minimum gaps of the instances having $\mathrm{NC}=2.1$ to nearly 0.0%.

The instances having $\mathrm{MRS}=0.1625$ were the ones where the $\mathrm{BRKGA}_\mathrm{PSS}$ produced the smallest gaps with values of 0.16% and 0% for average and minimum gaps, respectively. We point out that all these instances have $\mathrm{SF}=0.5$ and thus correspond to cases that were among the hardest to tackle by the procedure of Almeida et al. (2016). In this subset of “harder” instances, we also find those with small values of $\mathrm{MRS}$, such as $\mathrm{MRS}=0.1250$, where the BRKGA originates a minimum gap of 0.83%. This correspond to a major improvement, since the heuristic of Almeida et al. (2016) produced gaps roughly six times higher.

The $\mathrm{BRKGA}_\mathrm{Both}$ improve the results obtained by the $\mathrm{BRKGA}_\mathrm{PSS}$ for $\mathrm{MRS}=0.1563$ and $\mathrm{MRS}=0.1875$, regarding average gaps and for $SF=1$, $\mathrm{MRS}=0.1875$, and $\mathrm{MRS}=0.2083$ in terms of minimum gaps.

4.3.2 Results for the instances in Set 2

The heuristic of Almeida et al. (2016) provides the optimal makespan for five instances in Set 2 and an upper bound on that value for the remaining ones. This is all the information that can be used for evaluating the performance of the BRKGA which we are proposing.

A closer look into the results of Almeida et al. (2016) reveals the unsuitability of using an off-the-shelf solver to tackle the mixed-integer linear programming formulation proposed by Correia et al. (2012) for the instances in Set 2. In fact, it was observed that, after 10 h of CPU time, CPLEX was unable to find a solution of at least the same quality of the one produced by the heuristic of Almeida et al. (2016) for 156 instances (more than 70% of the instances in Set 2). For the remaining 60 instances, the solver required, on average, 4861 s of CPU time to find a solution with at least the same objective value. Therefore, the development of efficient heuristics for the PSPFR is of great relevance and the CPU time which they consume shall be assessed considering the effort required by an alternative approach, such as the use of a solver. We will observe that the $\mathrm{BRKGA}_\mathrm{PSS}$ and $\mathrm{BRKGA}_\mathrm{Both}$ improve the solutions provided by the heuristic of Almeida et al. (2016), on average. Hence, we expect the solver to require an even greater CPU time to reach a solution of at least the same quality of that obtained by either BRKGA configuration.

To evaluate the results provided by the $\mathrm{BRKGA}_\mathrm{PSS}$ and by the $\mathrm{BRKGA}_\mathrm{Both}$ and due to the lack of information regarding the optimal solutions of almost all instances, we introduce a new concept referred to as Performance Ratio (PR). This is a relative ratio that we compute both for the makespan values ($\mathrm{PR}_\mathrm{m}$) and for the gaps ($\mathrm{PR}_\mathrm{g}$) as follows: $\mathrm{PR}_\mathrm{m}=\frac{Z^{\mathcal{B}^*} - Z^H}{Z^H} \times 100 \%$, and $\mathrm{PR}_\mathrm{g} =\frac{D^{\mathcal{B}^*} - D^H}{D^H} \times 100 \%$. In the previous expressions, $Z^{\mathcal{B}^*}$ ($D^{\mathcal{B}^*}$) denotes the best upper bound (minimum gap) provided by the $\mathrm{BRKGA}_\mathrm{PSS}$ or by the $\mathrm{BRKGA}_\mathrm{Both}$ and $Z^H$ ($D^H$) denotes the upper bound (gap) obtained by the heuristic of Almeida et al. (2016).

Table 6 Set 2: Comparative analysis—detail

Suppose that for some instance, and considering the $\mathrm{BRKGA}_\mathrm{PSS}$, we obtain $D^{\mathcal{B}^*}$=8% and $D^H=$10%.¹ In this case, $\mathrm{PR}_\mathrm{g}$ = -20%, which indicates that the $\mathrm{BRKGA}_\mathrm{PSS}$ provides a gap 20% lower than the heuristic proposed by Almeida et al. (2016).

The analysis of improvements involving the makespan ($\mathrm{PR}_\mathrm{m}$) is also of great interest in particular when no lower bound besides the critical path length is available. In fact, the latter is often a poor lower bound for this problem (Correia et al. 2012), because it only considers information related to the precedence network.

Table 7 Set 2: Comparative analysis—summary

Table 6 details the results for each class of instances. Each row of this table aggregates six instances. The results are then summarized in Table 7.

Tables 6 and 7 are organized as follows: columns 1–3 contain the characteristics of each class of instances; columns 5–9 present the results obtained by the $\mathrm{BRKGA}_\mathrm{PSS}$. In particular, columns 5 and 6 show the results associated with the $\mathrm{PR}_\mathrm{m}$ and $\mathrm{PR}_\mathrm{g}$, respectively; columns 7–9 present the average makespan, standard deviation, and total CPU time required by the 5 runs, respectively; columns 10–14 refer to the results provided by the $\mathrm{BRKGA}_\mathrm{Both}$ and follow the above structure of 5–9; column 15 depicts the total time required by the heuristic of Almeida et al. (2016).

We note that the $\mathrm{BRKGA}_\mathrm{PSS}$ found the optimal solutions for all the five instances for which Almeida et al. (2016) also found the optimal value. These instances are indicated in column 4 and they were not used to compute the values presented in Tables 6 and 7.

From Table 6, we observe the $\mathrm{BRKGA}_\mathrm{PSS}$ performed better than the heuristic of Almeida et al. (2016) in all the 36 classes of instances. The best results in terms of $\mathrm{PR}_\mathrm{m}$ were generally attained for the instances with smaller values of $\mathrm{MRS}$, with a particular emphasis for the instances having $SF=0.5$ and $\mathrm{MRS}=0.0625$. In fact, the class of instances which reported the highest improvement regarding $\mathrm{PR}_\mathrm{m}$ (− 13.86%) is actually defined by $SF=0.5$, $\mathrm{NC}=1.5$, and $\mathrm{MRS}=0.0625$. The $\mathrm{PR}_\mathrm{g}$ values seem to follow a different direction. This result may be related to the fact that smaller makespans are associated with higher values of $\mathrm{MRS}$ (thus allowing a greater degree of parallelization) for fixed values of SF and $\mathrm{NC}$. In fact, the class of instances with $SF=0.5$, $\mathrm{NC} = 2.1$ and $\mathrm{MRS} = 0.0938$ is the one associated with the smallest improvement in the makespan and the one having the greatest improvement in the gap. $\mathrm{BRKGA}_\mathrm{Both}$ improved the results of the $\mathrm{BRKGA}_\mathrm{PSS}$ for 25 out of the 36 classes of instances and the best results have been found in the same class of instances where the $\mathrm{BRKGA}_\mathrm{PSS}$ performed the best. The average time required to solve all the instances was 9% higher than the one required by the $\mathrm{BRKGA}_\mathrm{PSS}$ which, nonetheless, is still negligible considering both the difficulty of the PSPFR and the disastrous performance of a solver as reported in Almeida et al. (2016) and described at the beginning of this section. Looking into Table 7, we conclude that the quality of the results achieved by the $\mathrm{BRKGA}_\mathrm{PSS}$ increases and the computational effort decreases as the values of SF become smaller. Instances having $SF = 0.5$ are associated with higher values of standard deviation of makespan—as observed for the instances in Set 1. These instances can, in fact, be looked at as “difficult” to tackle. Moreover it is for these instances that the best results regarding both $\mathrm{PR}_\mathrm{m}$ and $\mathrm{PR}_\mathrm{g}$ were achieved.

Concerning the network complexity ($\mathrm{NC}$), we observe that an increase in its value leads to a slight decrease in the CPU time. Instances having higher values of $\mathrm{NC}$ tend to be easier, because a smaller number of activities are likely to be processed in parallel due to the increased number of precedence relations. Amongst the different $\mathrm{NC}$ values, the largest improvements in terms of both $\mathrm{PR}_\mathrm{m}$ and $\mathrm{PR}_\mathrm{g}$ were achieved for the instances having $\mathrm{NC} = 1.8$.

Regarding $\mathrm{MRS}$, the best results for $\mathrm{PR}_\mathrm{m}$ and $\mathrm{PR}_\mathrm{g}$ are associated with $\mathrm{MRS} = 0.0625$ and $\mathrm{MRS} = 0.0938$, respectively. The latter can be explained by the fact that the instances with higher $\mathrm{MRS}$ are also the ones associated with smaller values of the average makespan. As discussed before, these instances typically allow a greater degree of parallelization, and hence, their corresponding optimal values can be closer to the value of the associated critical path length.

We observe overall values of $\mathrm{PR}_\mathrm{m} = -5.69\%$ and $\mathrm{PR}_\mathrm{g} = -21.10\%$ for the $\mathrm{BRKGA}_\mathrm{PSS}$. This represents a significant improvement over the results obtained by Almeida et al. (2016). The $\mathrm{BRKGA}_\mathrm{Both}$ achieved the best results for this set of instances with an overall $\mathrm{PR}_\mathrm{m} = -6.05\%$ and a $\mathrm{PR}_\mathrm{g} = -22.25\%$ and may hence be more appropriate for dealing with instances of large dimensions. In fact, the use of the two decoders may have contributed to a better exploration of the search space of feasible solutions which is larger for the instances in Set 2.

5 Conclusions

In this paper, we proposed a BRKGA for the PSPFR along with a new constructive heuristic for this problem based on a serial scheduling generation scheme (SSS). The BRKGA considers two decoding algorithms: the PSS heuristic proposed by Almeida et al. (2016) and the SSS.

Computational experiments were performed on 432 instances of the problem, partitioned into two sets. The computational results indicate that the BRKGA with the single decoder PSS provides the best results for the smaller sized instances, whereas the BRKGA with the two decoders, the PSS and SSS, achieves the best results for the set of larger instances. Furthermore, we could observe that the proposed approximate method is extremely robust in the sense that it has the ability of finding solutions of a similar quality for a given instance, in distinct runs.

Some directions for future research include the development of fast algorithms for deriving good lower bounds for the PSPFR. This would be of great relevance, since it would allow a more accurate evaluation of heuristics specially when it comes to tackling large-scale instances.

The fact that quite effective heuristic schemes exist for the PSPFR encourages the study of extensions of the problem investigated in this work. Some possibilities include non-homogeneous resources, multiple-skill contribution of a resource to the execution of an activity and preemption.

Another interesting direction for further research concerns the application to the PSPFR of a genetic algorithm whose chromosomes are encoded according to an activity list representation instead of random keys. This is something that requires using another genetic algorithm, since in a BRKGA, as the name indicates, all alleles are random values (random keys) in the interval [0,1].

Another aspect that we are neglecting in this work concerns the cost of the resources. The problem that we have studied emerges, for instance, in the context of software development and construction projects where the salary of the (human) resources is fixed and independent from the effort they put on the project. However, if this is not the case (e.g. in some consulting projects), then like for many project scheduling problem, accounting for time and cost may be altogether relevant for the decision-making process. This is an interesting and challenging research direction to explore.