Keywords

1 Introduction

Project scheduling is a highly relevant and complex issue in most real-world organizations [1, 2]. Project scheduling generally involves defining feasible start times and human resource assignments for the project activities, such that a given optimization objective is achieved. Moreover, to define human resource assignments, it is necessary to consider the available knowledge about the effectiveness of human resources respecting the project activities. This is important since the development and the results of project activities mainly depend on the effectiveness of the human resources assigned to such activities [1, 2].

In the past four decades, many kinds of project scheduling problems have been formally presented and addressed in the literature. However, to the best of the author’s knowledge, only few project scheduling problems consider human resources with different effectiveness levels [3, 4], a very important aspect of real-world project scheduling. These project scheduling problems suppose very different assumptions in respect of the effectiveness of human resources.

The project scheduling problem presented in [5] supposes that the effectiveness level of a human resource depends on several factors inherent to its work context (i.e., the project activity to which the resource is assigned, the skill to which the resource is assigned within the project activity, the set of human resources assigned to the project activity, and the attributes of the resource). This assumption about the effectiveness of human resources is really valuable. This is because, in real-world project scheduling problems, human resources generally have different effectiveness levels with respect of different work contexts, and therefore, the effectiveness level of a human resource is considered with respect of the factors inherent to its work context [1, 2]. To the best of the author’s knowledge, the influence of the work context on the effectiveness level of human resources is not considered in other project scheduling problems presented in the literature. The problem presented in [5] also considers a valuable optimization objective for project managers: maximizing the effectiveness of the sets of human resources assigned to the project activities.

The project scheduling problem presented in [5] is a variant of the known RCPSP (Resource Constrained Project Scheduling Problem) [6] and, therefore, is an NP-Hard optimization problem. Because of this, heuristic search and optimization algorithms are required to solve different problem instances in an acceptable amount of time. In this respect, to the best of the author’s knowledge, four heuristic search and optimization algorithms have been presented so far in the literature to solve this problem. Specifically, a traditional evolutionary algorithm was presented in [5]. In [7], a traditional memetic algorithm was presented which includes a hill-climbing algorithm into the framework of an evolutionary algorithm. In [8], a hybrid evolutionary algorithm was presented which incorporates an adaptive simulated annealing algorithm within the framework of an evolutionary algorithm. In [9,10,11], a hybrid evolutionary algorithm was presented which utilizes semi-adaptive crossover and mutation processes, and an adaptive simulated annealing algorithm.

These four algorithms follow the stages of the traditional evolutionary cycle (i.e., parent selection, crossover, mutation, and survival selection stages) to develop the evolutionary search. Nevertheless, these algorithms use non-adaptive processes to carry out all or many of the stages of the evolutionary cycle. In this respect, the four algorithms use non-adaptive parent selection and survival selection processes, and the first three of these algorithms use non-adaptive crossover and mutation processes. The fourth of these algorithms uses semi-adaptive crossover and mutation processes; however, the adaptability of the behavior of these processes during the evolutionary search is very limited.

In this paper, the project scheduling problem presented in [5] is addressed with the aim of proposing a better heuristic search and optimization algorithm to solve it. In this respect, an adaptive hybrid evolutionary algorithm is proposed which utilizes adaptive processes to develop the different stages of the evolutionary cycle (i.e., adaptive parent selection, survival selection, crossover, mutation and simulated annealing processes). These processes adapt their behavior based on the diversity of the algorithm’s population. The utilization of these adaptive processes is meant for improving the performance of the evolutionary search [12,13,14].

The above-mentioned adaptive hybrid evolutionary algorithm is proposed mainly because of the following reasons. Evolutionary algorithms with adaptive selection, crossover and mutation processes have been proven to be more effective than evolutionary algorithms with non-adaptive selection, crossover and mutation processes in the resolution of a wide variety of NP-Hard optimization problems [12,13,14,15,16,17]. Thus, the proposed adaptive hybrid evolutionary algorithm could outperform the heuristic search and optimization algorithms presented so far in the literature to solve the addressed problem.

The remainder of the paper is organized as follows. Section 2 presents a brief review of project scheduling problems reported in the literature which consider the effectiveness of human resources. Section 3 describes the project scheduling problem addressed. Section 4 presents the adaptive hybrid evolutionary algorithm proposed for the problem. Section 5 presents the computational experiments developed to evaluate the performance of the adaptive hybrid evolutionary algorithm and also an analysis of the results obtained. Finally, Sect. 6 presents the conclusions of the present work.

2 Related Works

Over the past four decades, different kinds of project scheduling problems which consider the effectiveness of human resources have been presented in the literature [3, 4]. However, these project scheduling problems suppose very different assumptions concerning the effectiveness of human resources. In this regards, to the best of the author’s knowledge, only few project scheduling problems consider human resources with different effectiveness levels [3, 4], a very important aspect of real-world project scheduling problems. In this section, the focus is on reviewing the main assumptions about the effectiveness that have been considered in project scheduling problems presented in the literature.

In the multi-skill project scheduling problems presented in [19,20,21,22,23], project activities require a given number of skills for their development, and a given number of human resources for each skill required. The human resources available for the project activities master one or several skills. These problems suppose that the human resources that master a given skill have the same effectiveness level in respect of such skill.

In the skilled workforce project scheduling problems presented in [24,25,26], each project activity requires only one human resource with a given skill. Moreover, the human resources available for project activities master one or several skills. These problems suppose that the human resources which master a given skill have the same effectiveness level in relation to such skill.

The multi-skill project scheduling problem reported in [27] considers hierarchical levels of skills. In this regard, the problem supposes that the human resources which master a given skill have different effectiveness levels in respect of such skill. Moreover, the project activities of this problem require a given number of skills for their development, a given minimum level of effectiveness for each one of the skills required, and a given number of human resources for each pair skill-level. Then, this problem supposes that the human resource sets feasible for a given project activity have the same effectiveness level with respect to the development of such activity.

In the multi-skill project scheduling problems presented in [28,29,30], most project activities require only one human resource with a given skill. The human resources available for project activities master one or several skills. These problems suppose that the human resources which master a given skill have different effectiveness levels in respect of such skill. In addition, these problems suppose that the effectiveness level of a human resource in a given project activity only depends on the effectiveness level of the human resource with respect to the skill required for the activity.

In contrast with the project scheduling problems previously mentioned, the project scheduling problem presented in [5] supposes that the effectiveness level of a human resource depends on several factors inherent to its work context. Then, different effectiveness levels can be defined for each human resource regarding different work contexts. This assumption about the effectiveness of human resources is really important. This is because, in the context of real-world project scheduling problems, human resources have very different effectiveness levels in respect of different work contexts, and therefore, the effectiveness level of a human resource is considered in respect of the factors inherent to its work context [1, 2]. To the best of the author’s knowledge, the influence of the work context on the effectiveness level of human resources is not considered in other project scheduling problems presented in the literature. Based on the mentioned above, the project scheduling problem presented in [5] supposes a valuable and novel assumption concerning the effectiveness level of human resources in the context of project scheduling problems.

3 Project Scheduling Problem Description

In this paper, the project scheduling problem introduced in [5] is addressed. A description of this problem is presented below.

Suppose that a project contains a set A of N activities, A = {1, …, N}, that has to be scheduled. Specifically, a starting time and a human resource set have to be defined for each project activity of the set A. The duration, human resource requirements, and precedence relations of each project activity are known.

The duration of each project activity j is notated as dj. Besides, it is considered that pre-emption of project activities is not allowed. This means that, when a project activity starts, it must be developed period by period until it is completed. Specifically, the dj periods of time must be consecutive.

Among the project activities, there are precedence relations. This is because usually each project activity requires results generated by other project activities. Thus, the precedence relations establish that each project activity j cannot start until all its immediate predecessors, given by the set Pj, have completely finished.

To be developed, project activities require human resources skilled in different knowledge areas. Specifically, each project activity requires one or several skills and also a given number of human resources for each skill required.

It is considered that qualified workforce is available to develop the activities of the project. This workforce is made up of a number of human resources, and each human resource masters one or several skills.

Set SK contains the K skills required in order to develop the activities of the project, SK = {1, …, K}, and set ARk contains the available human resources with skill k. Then, the term rj,k represents the number of human resources with skill k required for activity j of the project. The values of the terms rj,k are known for each project activity.

It is considered that a human resource cannot take over more than one skill within a given activity, and also a human resource cannot be assigned more than one activity at the same time.

Based on the assumptions previously mentioned, a human resource can be assigned different project activities but not at the same time, can take over different skills required for a project activity but not simultaneously, and can belong to different possible sets of human resources for each activity.

Therefore, different work contexts can be defined for each available human resource. It is considered that the work context of a human resource r, denoted as Cr,j,k,g, is made up of four main components. In this respect, the first component refers to the project activity j which r is assigned (i.e., the complexity of j, the domain of j, etc.). The second component refers to the skill k which r is assigned within project activity j (i.e., the tasks associated to k within j). The third component is the set of human resources g that has been assigned j and that includes r (i.e., r must work in collaboration with the other human resources assigned to j). The fourth component refers to the attributes of r (i.e., his or her educational level regarding different knowledge areas, his or her level regarding different skills, his or her experience level regarding different tasks and domains, the kind of labor relation between r and the other human resources of g, etc.). In respect of the attributes of r, it is considered that these attributes could be quantified from available information about r (e.g., curriculum vitae of r, results obtained from evaluations made to r, information about the participation of r in already executed projects, etc.).

The four components previously mentioned are considered the main factors that determine the effectiveness level of a human resource. Because of this, it is assumed that the effectiveness level of a human resource depends on all the components of his or her work context. Then, different effectiveness levels can be considered for each human resource in respect of different work contexts.

The effectiveness level of a human resource r, in respect of a possible context Cr,j,k,g for r, is notated as erCr,j,k,g. The term erCr,j,k,g refers to how well r can take over, within activity j, the tasks associated to skill k, considering that r must work in collaboration with the other human resources of set g. The term erCr,j,k,g takes a real value over the range [0, 1]. The values of the terms erCr,j,k,g inherent to each human resource available for the project are known. It is considered that these values could be obtained from available information regarding the participation of the human resources in already carried out projects.

The problem of scheduling a project involves to determine feasible start times (i.e., the precedence relations among the project activities must not be violated) and feasible human resource assignments (i.e., the human resource requirements of project activities must be met) for project activities such that the optimization objective is achieved. In this respect, an optimization objective valuable for project managers is considered. This optimization objective implies maximizing the effectiveness of the sets of human resources assigned to the project activities. This objective is modeled by Formulas (1) and (2).

Formula (1) maximizes the effectiveness of the sets of human resources assigned to the N project activities. In this formula, set S contains all the feasible schedules for the project in question. The term e(s) refers to the effectiveness level of the sets of human resources assigned to the project activities by schedule s. The term R(j, s) refers to the set of human resources assigned to activity j by schedule s. The term eR(j,s) refers to the effectiveness level corresponding to R(j, s).

Formula (2) estimates the effectiveness level of the set of human resources R(j,s). This effectiveness level is estimated by calculating the mean effectiveness level of the human resources belonging to R(j, s).

For a more detailed discussion of the project scheduling problem described here and, in particular, of Formulas (1) and (2), the readers are referred to the work [5] which has introduced this problem.

$$ \mathop {\hbox{max} }\limits_{\forall s \in S} \,\left( {e(s) = \sum\limits_{j = 1}^{N} {e_{R(j,s)} } } \right) $$
(1)
$$ e_{R(j,s)} = \frac{{\sum\limits_{r = 1}^{{\left| {R(j,s)} \right|}} {e_{{rC_{r,j,k(r,j,s),R(j,s)} }} } }}{{\left| {R(j,s)} \right|}} $$
(2)

4 Adaptive Hybrid Evolutionary Algorithm

To solve the addressed problem, an adaptive hybrid evolutionary algorithm is proposed. This algorithm utilizes adaptive processes to develop the different stages of the evolutionary cycle. These processes adapt their behavior according to the diversity of the evolutionary algorithm population, to promote either the exploration or exploitation of the search space. The utilization of these adaptive processes aims to enhance the performance of the evolutionary search [12,13,14].

The general behavior of the algorithm is described as follow. This algorithm is an iterative or generational process. This process starts from an initial population of solutions. Each solution encodes a feasible schedule for the project to be scheduled. Besides, each solution has a fitness value that represents the quality of the related schedule in respect of the optimization objective of the addressed problem. As mentioned in Sect. 3, such objective implies maximizing the effectiveness of the sets of human resources assigned to the project activities. The iterative process ends when a predefined number of iterations or generations is reached. Once this happens, the iterative process provides the best solution of the last population as a solution to the problem.

In each iteration, the algorithm develops the following stages. First, an adaptive parent selection process is applied in order to determine which solutions of the current population will compose the mating pool. Once the mating pool is composed, the solutions in the mating pool are paired, and a crossover process is applied to each pair of solutions with an adaptive crossover probability in order to generate new feasible ones. Then, a mutation process is applied to each solution generated by the crossover process, with an adaptive mutation probability. The mutation process is applied in order to introduce diversity in the new solutions generated by the crossover process. Then, an adaptive survival selection process is applied to create a new population from the solutions in the current population and the new solutions generated by crossover and mutation. Finally, an adaptive simulated annealing algorithm is applied to each solution of the new population, excepting the best solution of this population. The best solution remains in the population. Thus, the adaptive simulated annealing algorithm modifies the solutions of the new population.

4.1 Encoding of Solutions

In order to encode the solutions of the population, the encoding introduced in [5] for project schedules was used. By using this encoding, each solution is encoded by two lists with a length equal to N, considering that N is the number of activities in the project to be scheduled.

The first list is a traditional activity list. Each position on this list contains a different activity j of the project. Each activity j of the project can appear on this list in any position higher than the positions of all its predecessor activities. The activity list represents a feasible order in which the activities of the project can be added to the schedule.

The second list is an assigned resources list. This list contains information about the human resources of each skill k assigned to each activity of the project. Specifically, position j on this list contains a detail about the human resources of each skill k assigned to activity j of the project.

To decode or build the schedule related to the encoding previously described, the serial schedule generation method presented in [5] was used. By this method, each activity j is scheduled at the earliest possible time.

In order to generate the encoded solutions of the initial population according to the encoding previously described, the random generation process introduced in [5] was used. By using this process, a very diverse initial population is obtained. This is meant in order to avoid the premature convergence of the evolutionary search [12].

4.2 Fitness Function

To evaluate the encoded solutions, a fitness function specially designed was used. Considering a given encoded solution, the fitness function decodes the schedule s from the solution by using the serial schedule generation method mentioned in Sect. 4.1. Then, the fitness function calculates the value of the term e(s) corresponding to s (Formulas (1) and (2)). This value defines the fitness value of the solution. Note that the term e(s) takes a real value over the range [0, …, N].

To calculate the value of term e(s), the fitness function uses the values of the terms erCr,j,k,g inherent to s (Formula 2). As mentioned in Sect. 3, the values of the terms erCr,j,k,g inherent to each available human resource r are known.

4.3 Adaptive Parent Selection Process

To develop the parent selection on the current population, an adaptive tournament selection process was defined. This process is an adaptive variant of the well-known tournament selection process with replacement [12].

In this process, the tournament size T is defined by Formula (3), where PD refers to the diversity of the current population, and PDMAX refers to the maximum PD attainable. Then, TH and TL refer to the upper and lower bounds for the tournament size, respectively.

The term PD is defined by Formula (4), where fmax is the maximal fitness of the current population, favg is the average fitness of the current population, and (fmax − favg) is a measure of the diversity of the current population. This measure has been proposed by Srinivas and Patnaik [31], and is one of the population diversity measures most well-known in the literature [12].

The term PDMAX is defined by Formula (5), where fMAX and fMIN represent to the maximum and minimum fitness values attainable, respectively. Note that fMAX and fMIN correspond to the upper and lower bounds of the fitness function described in Sect. 4.2.

By Formula (3), the tournament size T is adaptive according to the diversity of the current population. Specifically, when the population is very diverse, T is increased, promoting the selection of the solutions with high fitness values. This favors the exploitation of the search space. When the diversity of the population reduces, T is decreased, increasing the selection chances of the solutions with low fitness values. This is meant to preserve the diversity of the population and thus to favor the exploration of the search space, with the aim of avoiding the premature convergence of the evolutionary search.

$$ T = \left\lceil {\frac{PD}{{PD_{MAX} }}*\left( {T^{H} - T^{L} } \right) + T^{L} } \right\rceil $$
(3)
$$ PD = \left( {f_{max} - f_{avg} } \right) $$
(4)
$$ PD_{MAX} = \left( {f_{MAX} - f_{MIN} } \right) $$
(5)

4.4 Adaptive Crossover and Adaptive Mutation Processes

In relation to the crossover process and the mutation process, processes feasible for the encoding of solutions were defined.

The crossover process is composed by a crossover operator feasible for activity lists and a crossover operator feasible for assigned resources lists. Regarding the crossover for activity lists, the one-point crossover operator for activity lists [18] was applied. Regarding the crossover for assigned resources lists, the uniform crossover operator was applied [12].

The mutation process is composed by a mutation operator feasible for activity lists and a mutation operator feasible for assigned resources lists. In relation to the mutation for activity lists, a variant of the simple shift operator for activity lists [18] was applied. In relation to the mutation for assigned resources lists, the random resetting operator [12] was applied.

These crossover and mutation processes are applied with adaptive crossover and mutation probabilities, respectively. In this regards, an adaptive crossover probability APc and an adaptive mutation probability APm were defined by Formulas (6)–(7). In these formulas, PD refers to the diversity of the current population, and PDMAX refers to the maximum PD attainable, as was mentioned in Sect. 4.3. In Formula (6), the terms CH and CL represent to the upper and lower bounds for the crossover probability, respectively. In Formula (7), the terms MH and ML represent to the upper and lower bounds for the mutation probability, respectively. The term fmax is the maximal fitness of the population, fmin is the minimal fitness of the population, and f is the fitness of the solution to be mutated.

By Formula (6)–(7), APc and APm are adaptive according to the diversity of the current population. In this respect, when the diversity of the population reduces, APc and APm are increased, promoting the exploration of the search space. This is important for preventing the premature convergence of the evolutionary search. When the population is very diverse, APc and APm are decreased, promoting the exploitation of the search space. Therefore, probabilities APc and APm are adaptive according to the diversity of the population, to promote either the exploitation or exploration of the search space.

By Formula (7), APm is also adaptive according to the fitness of the solution to be mutated. In this respect, lower values of APm are defined for high-fitness solutions, and higher values of APm are defined for low-fitness solutions. This is meant in order to preserve high-fitness solutions, while disrupting low-fitness solutions to promote the exploration of the search space.

$$ AP_{c} = \left( {\frac{{PD_{MAX} - PD}}{{PD_{MAX} }}} \right)*\left( {C^{H} - C^{L} } \right) + C^{L} $$
(6)
$$ AP_{m} = \left( {\frac{{f_{max} - f}}{{f_{max} - f_{min} }}} \right)*\left( {\frac{{PD_{MAX} - PD}}{{PD_{MAX} }}} \right)\;*\left( {M^{H} - M^{L} } \right)\; + M^{L} $$
(7)

4.5 Adaptive Survival Selection Process

The survival selection process is applied to create a new population from the solutions in the current population (parent solutions) and the new solutions generated by crossover and mutation (offspring solutions).

To develop the survival selection, an adaptive deterministic crowding process was defined. This process is an adaptive variant of the well-known deterministic crowding process [12, 32].

In this process, offspring solutions compete with their respective parent solutions to be included in the new population. Specifically, each offspring competes with its closest parent, considering that the closeness between an offspring solution and a parent solution is defined based on the distance between their fitness values. When the fitness value of an offspring solution is better than that of its closest parent solution, the offspring solution is accepted for the new population. Otherwise, when the fitness value of an offspring solution is not better than that of its closest parent solution, the offspring solution is accepted for the new population with a probability poffspring. If the offspring solution is not accepted, the parent solution is accepted for the new population directly.

The probability poffspring is defined as follows: exp(−ΔDC/T), where ΔDC is the difference between the fitness value of the parent solution and the fitness value of the offspring solution, and the term T is defined according to the diversity of the current population. Specifically, T is inversely proportional to the diversity of the current population, and is calculated as follows: T = 1/PD, where PD refers to the diversity of the current population, as was mentioned in Sect. 4.3.

By the definition of the probability poffspring, this probability is adaptive based on the diversity of the current population. In this respect, when the population is very diverse, the value of T is very low, and therefore the probability poffspring of the process is also low. Thus, the process preserves the best solutions for the new population, favoring the exploitation of the search space. When the diversity of the population decreases, the value of T increases, and therefore the probability poffspring of the process also increases. Thus, the process introduces diversity into the new population, favoring the exploration of the search space. This is important to prevent the premature convergence of the evolutionary search.

4.6 Adaptive Simulated Annealing Algorithm

After obtaining a new population by the survival selection process, an adaptive simulated annealing algorithm was applied to each solution of this population, except to the best solution of this population which is maintained. This adaptive simulated annealing algorithm is a variant of the one presented in [9,10,11], and is described below.

The adaptive simulated annealing algorithm is an iterative process. This process starts from a given encoded solution s, and a given initial value T0 for the temperature parameter. The iterative process ends when a given number of iterations I is reached, or the current value Ti of the temperature parameter is lower than or equal to 0. After this happens, the solution obtained by the process is provided.

In each iteration, the process generates a new encoded solution s’ from the current encoded solution s by applying a move operator. Then, the process analyzes if the current solution s should be replaced by the new solution s’. When the fitness value of the current solution s is worse than that of the new solution s’, the process replaces to the solution s by the new solution s’. Otherwise, when the fitness value of the current solution s is better than or equal to that of the new solution s’, the process replaces to the solution s by the new solution s’ with a probability pnew_solution. This probability is defined as follows: pnew_solution = exp(−ΔSA/Ti), where ΔSA is the difference between the fitness value of the current solution s and the fitness value of the new solution s’, and Ti is the current value of the temperature parameter. The probability pnew_solution mainly depends on the current value Ti of the temperature parameter. If Ti is high, pnew_solution is also high, and if Ti is low, pnew_solution is also low. The value Ti of the temperature is reduced by a given cooling factor α at the end of each iteration.

The initial value T0 of the temperature parameter is defined before applying the simulated annealing algorithm to the solutions of the population. In this case, the value T0 is defined according to the diversity of the population. In particular, T0 is inversely proportional to the diversity of the population, and is calculated as follows: T0 = 1/PD, where PD refers to the diversity of the population, as mentioned in Sect. 4.3. By this definition of T0, when the population is diverse, the value T0 is low, and therefore the probability pnew_solution of the algorithm is also low. Thus, the algorithm fine-tunes the solutions of the population, promoting the exploitation of the search space. When the diversity of the population reduces, the value T0 increases, and therefore the probability pnew_solution of the algorithm also increases. Thus, the algorithm introduces diversity into the population, promoting the exploration of the search space. This is important for avoiding the premature convergence of the evolutionary search. Based on the above-mentioned, the algorithm is adaptive according to the population diversity, in order to promote either the exploitation or exploration of the search space.

This simulated annealing algorithm utilizes a move operator in order to generate a new encoded solution from a given encoded solution. In this respect, a move operator feasible for the encoding of solutions was defined. This move operator is composed by a move operator feasible for activity lists and a move operator feasible for assigned resources lists. In respect of the move operator for activity lists, the adjacent pairwise interchange operator [18] was applied. For assigned resources lists, an operator which is a variant of the random resetting operator [12] was applied.

5 Computational Experiments

To develop the computational experiments, the six instance sets introduced in [7] were used. Table 1 presents the main characteristics of these six instance sets. Each instance set contains 40 instances. Each instance of these six instance sets contains information about a number of activities to be scheduled, and information about a number of available human resources for developing these activities. For a more detailed description of these instance sets, the readers are referred to [7].

Table 1. Main characteristics of the instance sets introduced in [7].
Full size table

Each instance of these six instance sets has a known optimal solution with a fitness value e(s) equal to N (N refers to the number of activities in the instance). These know optimal solutions are considered here as references to evaluate the performance of the adaptive hybrid evolutionary algorithm.

The adaptive hybrid evolutionary algorithm was evaluated on the six instance sets. Specifically, the algorithm was run a number of 40 times on each instance of the six instance sets. In order to develop these runs, the parameter setting detailed in Table 2 was used. It is necessary to mention that such parameter setting was defined based on exhaustive preliminary experiments that showed that this setting led to the best and most stable results.

Table 2. Parameter setting of the adaptive hybrid evolutionary algorithm
Full size table

Table 3 presents the results obtained by the adaptive hybrid evolutionary algorithm for each of the six instance sets. The second column presents the average percentage deviation from the optimal value (Av. Dev. (%)) for each instance set. The third column presents the percentage of instances for which the optimal value was reached at least once among the 40 runs developed (Opt. (%)).

Table 3. Results obtained by the adaptive hybrid evolutionary algorithm
Full size table

For the instance sets j30_5, j30_10, j60_5, j60_10 and j120_5 (i.e., the five less complex instance sets), the algorithm obtained Av. Dev. (%) values equal to 0% and Opt. (%) values equal to 100%. These results indicate that the algorithm has reached an optimal solution in each of the 40 runs developed on each instance of these sets.

For the instance set j120_10, the algorithm obtained an Av. Dev. (%) value equal to 0.01%. Considering that the instances of j120_10 have known optimal solutions with a fitness value e(s) equal to 120, this result indicates that the average fitness value of the solutions obtained by the algorithm is 119.99. Therefore, the algorithm has reached very high-fitness solutions for the instances of j120_10. Moreover, the algorithm obtained an Opt. (%) value equal to 100% for j120_10. This result indicates that the algorithm has reached an optimal solution at least once among the 40 runs developed on each instance of j120_10.

5.1 Comparison with Competing Heuristic Algorithms

To the best of the author’s knowledge, four heuristic search and optimization algorithms have been presented so far in the literature to solve the addressed problem: a traditional evolutionary algorithm [5], a traditional memetic algorithm [7] which incorporates a hill-climbing algorithm into the framework of an evolutionary algorithm, a hybrid evolutionary algorithm [8] which integrates an adaptive simulated annealing algorithm into the framework of an evolutionary algorithm, and a hybrid evolutionary algorithm [9,10,11] which utilizes semi-adaptive crossover and mutation processes as well as an adaptive simulated annealing algorithm.

The four algorithms above-mentioned utilize non-adaptive parent selection and survival selection processes to develop the evolutionary search. Besides, the first three of these algorithms use non-adaptive crossover and mutation processes. The fourth of these algorithms uses semi-adaptive crossover and mutation processes; however, the adaptability of the behavior of these processes during the evolutionary search is very limited.

In [7,8,9], the four algorithms above-mentioned have been evaluated on the six instance sets presented in Table 1. The results obtained by each of the four algorithms for these six instance sets are detailed in Table 4, as were reported in [7,8,9].

Table 4. Results obtained by the heuristic algorithms reported in the literature for the addressed problem
Full size table

According to the results in Table 4, the performance of the algorithm presented in [9,10,11] is better than those of the algorithms presented in [5, 7, 8]. Thus, the algorithm presented in [9,10,11] may be considered as the best algorithm presented so far in the literature for solving the addressed problem.

Below, the performance of the algorithm presented in [9,10,11] is compared with that of the adaptive hybrid evolutionary algorithm proposed here. For simplicity, the algorithm presented in [9,10,11] will be referred as algorithm HEA.

Comparing the results obtained by the algorithm HEA (as detailed in Table 4) with those obtained by the adaptive hybrid evolutionary algorithm (as detailed in Table 3), the following points may be mentioned. Both algorithms have obtained an optimal effectiveness level for j30_5, j30_10, j60_5 and j60_10 (i.e., the four less complex instance sets). However, the effectiveness level obtained by the adaptive hybrid evolutionary algorithm for j120_5 and j120_10 (i.e., the two more complex instance sets) is significantly higher than that obtained by the algorithm HEA. Therefore, the adaptive hybrid evolutionary algorithm outperforms the algorithm HEA on the more complex instance sets. This is mainly because of the following reasons.

The adaptive hybrid evolutionary algorithm uses adaptive processes (i.e., adaptive parent selection, crossover, mutation, and survival selection processes) to develop the evolutionary search. Such processes adapt their behavior according to the population diversity, to promote either the exploration or exploitation of the search space, and therefore, improve the performance of the evolutionary search. In contrast with the adaptive hybrid evolutionary algorithm, the algorithm HEA utilizes non-adaptive processes (i.e., non-adaptive parent selection and survival selection processes) and semi-adaptive processes (i.e., semi-adaptive crossover and mutation processes) to develop the evolutionary search. The non-adaptive processes disregard the population diversity, and are not able to adapt their behavior during the evolutionary search to improve the performance of the evolutionary search. The semi-adaptive processes consider the population diversity; however, the adaptability of the behavior of these processes during the evolutionary search is very limited. Based on the mentioned above, the adaptive hybrid evolutionary algorithm has significant advantages to develop the evolutionary search.

6 Conclusions and Future Work

In this paper, an adaptive hybrid evolutionary algorithm was proposed to solve the project scheduling problem introduced in [5]. This problem considers a valuable optimization objective for project managers. Such objective involves maximizing the effectiveness of the sets of human resources assigned to the project activities.

The proposed adaptive hybrid evolutionary algorithm uses adaptive processes to develop the different stages of the evolutionary cycle (i.e., adaptive parent selection, survival selection, crossover, mutation and simulated annealing processes). These processes adapt their behavior according to the diversity of the evolutionary algorithm population, to promote either the exploration or exploitation of the search space. The utilization of these adaptive processes is meant to improve the evolutionary search.

The performance of the adaptive hybrid evolutionary algorithm was evaluated on six instance sets with very different complexity levels. After that, the performance of this algorithm on these six instance sets was compared with those of the algorithms previously reported in the literature for solving the addressed problem. Based on the obtained results, it may be stated that the proposed adaptive hybrid evolutionary algorithm significantly outperforms the algorithms previously reported.

In future works, other adaptive processes will be evaluated into the framework of the hybrid evolutionary algorithm. In particular, other adaptive parent selection, adaptive survival selection, adaptive crossover and adaptive mutation processes will be evaluated. Besides, other population diversity measures will be evaluated to adapt the behavior of the adaptive processes during the evolutionary search.