Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem

In RCPSP, a set of tasks is given, while every task is described by its duration, start and finish dates. Tasks are non-preemptive. It means any task cannot be withdrawn if it has been started. Tasks are related to each other by precedence relations, describing which tasks are needed to be completed before some others could be started. Tasks that have to be finished before the start time of another task are called predecessors. In classical RCPSP, resource units are provided. Every resource owns a finite number of units (represented as integer numbers) that could be assigned to various tasks, while tasks require some number of units to be performed. Cumulative number of units of tasks assigned to specified resource in a given period cannot exceed a number of units owned by resource. Not only one resource can be assigned to a given task but also one task can be assigned to given resource in given timestamp. In classical RCPSP, two dummy activities are added: start and finish tasks. It is because, in RCPSP, every task besides the start one has predecessors. Hence, finish time of the last, dummy finish task is the finish time of schedule and the duration of a project could be computed as duration between start time of dummy start task and finish time of finish dummy task. The goal of RCPSP is to find such task-to-resource assignments to make the final schedule feasible and as shortest as possible. Combinatorial nature of the RCPSP makes it NP-hard.

A solution of RCPSP is a feasible schedule—the one in which resource units and precedence constraints are preserved.

MS-RCPSP extension adds the skills domain to classical RCPSP. Every task requires some skills at given familiarity level to be performed, while every resource disposes some skills pool—subset of skill types (e.g., developer, analyst, tester, architect, etc.) defined in a project with given familiarity level. Therefore, the resource \(R\) is capable of performing the task \(T\) only if \(R\) disposes skill required by \(T\) at the same or higher level. The capabilities of performing tasks by resources could be presented as skill matrix. Sample skill matrix is shown in the Fig. 1.

In the skill matrix presented in the Fig. 1, skills required by task to be performed have been written over task definition, while skills owned by resources have been written next to resource definition. This figure presents sample resource capabilities: resource \(R1\) disposes skills \(Q1\) and \(Q2\) with familiarity levels 3 and 2, respectively. It is capable of performing tasks \(T1\), \(T3\) and \(T4\) because all of those mentioned tasks require skill owned by \(R1\) at no higher level than it has. \(R1\) cannot be assigned to \(T2\), because this task requires totally different skill that \(R1\) does not dispose of, even at the lowest familiarity level. Analogously, resource \(R2\) can be assigned to task \(T2\), resource \(R3\) is a proper one for task \(T3\) and, finally, resource \(R4\) can perform tasks \(T1\), \(T2\) and \(T3\). Even though \(R3\) disposes of skill \(Q2\), it cannot be assigned to \(T1\) and \(T3\) because those tasks require \(Q2\) at higher familiarity level that this resource disposes.

As a result of consultations with representatives of various enterprises, we decided to introduce some practical changes in classical RCPSP extended to MS-RCPSP model. Firstly, we introduced resource salary (as an hourly wage) paid for performed work. In that case, resources are regarded only as human ones varied by their salary. We also resigned from introducing start and finish dummy activities as our approach assumes that there could be some tasks that are not connected by precedence relations with any other. Hence, we cannot define the project duration, start time and finish time based on dummy activities.

What is more, resources are not described by units—any resource cannot be assigned to more than one task in an overlapping period—dedicated resources (Bianco et al. 1998). If such a situation occurs, the conflict is detected and should be resolved. The conflict fixing procedure is presented in Sect. 4.4. Schedule feasibility for such modified problem is extended from classical RCPSP schedule feasibility definition by skills domain—only resources capable of performing given tasks can be assigned to them.

Feasible Project Schedule (PS) consists of \(J=1,...,n\) tasks and \(K=1,...,m\) resources. A non pre-emptive duration \(d_j\), start time \(S_j\) and finish time \(F_j\) is defined for each task. Predecessors of given task \(j\) are defined as \(P_j\). Each resource is defined by its hourly rate salary \(s_k\) and owned skills \(Q^k=1,...,r\), while pool of owned skills is a subset of all skills defined in project \(Q^k \in Q\). Value \(l_q\) denotes the level of given skill, while \(h_q\) describes its type and \(q_j\) is a skill required by \(j\) to be performed. Therefore, by \(J^k\) subset of tasks that can be performed by \(k\) resource is defined. Duration of a project schedule is denoted as \(\tau \). Cost of performing \(j\) task by \(k\) resource is denoted as \(c_j^k=d_j*s_k\), where \(s_k\) describes the salary of resource \(k\) assigned to \(j\). For simplicity, we have modified the task’s performance cost from \(c_j^k\) to \(c_j\), because only one resource can be assigned to given task. Hence, there is no need to distinguish various costs for the same task. Moreover, we have introduced variable defining whether \(k\) is assigned to \(j\) in given time \(t\): \(U_{j,k}^t \in \{0;1\}\). If \(U_{j,k}^t=1\), \(k\) is assigned to \(j\) in \(t\). Analogously, \(k\) is not assigned to \(j\) in \(t\) if \(U_{j,k}^t = 0\).

Feasible project schedule (PS) belongs to the set of all feasible and non-feasible solutions (violating precedence, resource and skills constraints) : \(\mathrm{PS} \in \mathrm{PS}_{\mathrm{all}}\).

Formally, the problem could be regarded as optimization (minimization) problem and stated as follows:Subject to: Equation 1 denotes the duration and cost optimization, respectively. Depending on the evaluation function configuration (described below), various optimization modes could be used in an optimization process. \(f_{\tau }(\mathrm{PS})\) is an evaluation function of project schedule’s duration, while \(f_\mathrm{C}(\mathrm{PS})\) is an evaluation function of project schedule’s performance cost.

The first constraint (Eq. 2) preserves the positive values of resource salaries and ability to perform at least one task by every resource. Equation 3 states that every task has positive finish date and duration, while Eq. 4 shows the precedence constrains rule. Next two equations: Eq. 5 introduces skill constraints and transforms RCPSP into MS-RCPSP. Constraint (Eq. 6) describes that any resource can be assigned to no more than one task in given time during the project. The last constraint (Eq. 7) says that each task must be performed in schedule PS by one resource assignment.

As it was mentioned, the proposed approach allows to set various objectives of optimization: duration- or cost-oriented one. Those two aspects are normalized, weighted and summarized. Normalization is necessary because of different domains of both aspects that are in opposition to each other. Setting optimization as more, cost-oriented causes enlarging the project duration; while setting as more important, the duration aspect of optimization could increase the cost of the project.

The detailed formulation of the evaluation function is presented in Sect. 4.2.

Because of NP-hard (combinatorial) nature of investigated problem, we have decided to present an estimation of solution space size (SS). It has been computed as follows:The above estimation is valid for all solutions, including non-feasible ones. Computing factorial of tasks number provides the number of combinations of ordering tasks within the timeline. It is easy to notice that such estimation allows to set any order, skipping precedence constraints. The second element of Eq. 8 provides the number of resource-to-task assignments, including a situation that the same resource is assigned to all tasks and no skill constraints are preserved.

To imagine how big the solution space could be, let’s take into account a sample project schedule with 100 tasks and \(20\) resources. Using Eq. 8, the solution space size is equal to \(\mathrm{SS}(100,20)=1.19*10^{288}\) solutions, including both feasible and infeasible ones.

In the first step of classical ACO, the surface of \(n\) edges is obtained. For each resource in each edge, the initial pheromone value is set. Then, \(p\) ants are defined by choosing random capable resource to \(j\) task. To reduce the influence of non-determinism and make search more directed, we have decided to introduce a heuristic initialization in hybrid called HAntCO. In HAntCO, one ant has assigned schedule obtained by heuristic described in Skowroński et al. (2013b). This ant is set as favorable—it can leave much more pheromone than any other ant in a colony. Other ants in the colony are defined in the same way as in classical ACO initial colony definition.

Heuristic used to obtain an initial solution is varied depending on the optimization mode. For the duration optimization mode (DO), the successors’ list size (SLS) heuristic has been used, as it provided the best results for DO mode. In this method, tasks are sorted by a number of successors they have in ascending order. Then, for every task from ordered list, a resource is assigned. The decision which resource should be assigned is determined by the earliest time when given resource would finish its previous tasks it has been assigned to.

For cost optimization (CO) mode, resources are sorted ascending by their standard salary rate and then are assigned to tasks from the list given in project definition, preserving skill constraints and avoiding conflicts, by assigning a given task-to-resource no earlier than all previously assigned tasks to resource would be finished.

In the next step, each solution is evaluated to set the pheromone value for each ant in the next iteration. The amount of pheromone left in every iteration is set according to the ant chosen as the best.

As the stopping criterion, the number of iterations with no change of global best solution has been proposed in this approach. It is notated as \(\gamma \).

The probability of selecting resource \(k\) to task \(j\) in edge selection bases on the roulette method is computed as follows:where \(\alpha \) is a weight for pheromone values influence. This value is the parameter of ACO approach and should be provided by the user. \(p^k_j\) is a pheromone value stored in the edge containing information about \(k\) resource performing \(j\) task.

Evaluation function is formulated as follows:where \(w_{\tau }\) is the weight of duration component, \(f_{\tau }(\mathrm{PS})\) is the duration evaluation component, \(f_\mathrm{c}(\mathrm{PS})\) is the cost evaluation component. Both components are non-negative values, while \(w_{\tau } \in [0;1]\).

Summing both components’ weight to 1 ensures that changing the importance of one aspect would cause also some changes of second aspect’s importance.

The time component \(f_{\tau }(\mathrm{PS})\) is calculated as follows:where \(\tau _{\mathrm{max}}\) is the maximal (pessimistic) possible duration of the schedule PS, computed as the sum of all tasks’ duration. It occurs when all tasks are performed serially in project: one-by-one. No matter how many and how flexible resources are.

The cost component \(f_\mathrm{c}(\mathrm{PS})\) is defined as follows:where \(c_{\mathrm{min}}\) is the minimal schedule cost—the total cost of all tasks assigned to the cheapest resource, \(c_{\mathrm{max}}\) is the maximal schedule cost—a total cost of all tasks assigned to the most expensive resource. Note: \(c_{\mathrm{max}}\) and \(c_{\mathrm{min}}\) do not involve skill constraints. It means that \(c_{\mathrm{min}}\) value could be reached only for non-feasible solution. Analogously to \(c_{\mathrm{max}}\).

Pheromone evaporates iterative. It means the pheromone value is decreased by the same value (\(\mu \)) in every iteration, as it was stated in the Eq. 13.Obtained results for various update pheromone methods strongly depend on values set for the following parameters used in ACO:In the proposed approach, three strategies of setting pheromones have been researched: \(ALL\) (Liang et al. 2004), \(ELITE\) (Merkle et al. 2002) and \(DIFF\). The last of the proposed ones is the new one, proposed by the authors of this paper.

A conflict appears when more than one task is assigned to the same resource in overlapping periods. In that case, it should be fixed by the following procedure.

It is performed by shifting one of conflicting task’s start date. Consequently, the finish date of that task also has to be shifted to keep the task duration. The decision which of conflicting tasks should be shifted depends on which of them starts earlier. If they are set to start at exactly the same time, task to be shifted is selected by the way, which was firstly added to project definition. Furthermore, we do not investigate the velocity of resources. Therefore, job duration is constant regardless of assigned resource and skills it owns.

Conflict fixing procedure illustration is presented in the Fig. 2.

Tasks \(T4\) and \(T5\) have been assigned to the Resource \(R2\) in overlapping period. As a conflict fixing result, a new schedule has been presented, where \(T5\) starts just after the \(T4\) should be finished. The \(T5\) has been shifted, because it was initially set to start later than the \(T4\).

Due to evaluating not only the project schedule duration, but also the cost of the schedule, we cannot use the standard PSPLIB benchmark dataset (Kolisch et al. 1996) that does not contain any information about the task performance cost. What is more, PSPLIB dataset instances do not reflect the MS-RCPSP. Hence, lack of benchmark data has encouraged us to prepare the iMOPSE dataset, containing 36 project instances that have been artificially created¹, on the basis of real-world instances, obtained from an international enterprise. We recommend other scientists using iMOPSE dataset as a benchmark for investigating their approaches in solving MS-RCPSP as defined.

Instances of the dataset have been created according to the analysis made in cooperation with experienced project manager from Volvo IT. We were not allowed to get real project data because of their sensitive character for the enterprise. However, we made a statistical analysis of real projects. Then, we prepared artificial dataset instances according to the analysis result, regarding the most common project characteristics, such as a number of tasks, a number of resources, various skill types in enterprise and the structure of critical chain (a number of tasks involved by precedence relations), etc.

The iMOPSE dataset summary is presented in the Table 1. There are two groups of created project instances: one contains 100 tasks and the second—200 tasks. Within each group, project instances are varied by a number of available resources and the precedence relationship complexity. The number of resources for instances from both groups was chosen in a way to preserve constant average resource load and average task relations ratio for given instances. Hence, for project instances with 200 tasks, the number of possible resources and precedence relations is twice bigger than for project instances containing 100 tasks. The skill variety has been set-up to 9 or 15 different skill types for each project instance, while any resource can dispose of exactly six different skill types. Because of the different resources’ and relations’ numbers, the scheduling complexity for each project is varied.

This dataset stands as an extension of dataset presented in Skowroński et al. (2013a, b), Myszkowski et al. (2013), and that is the reason some instances are named with suffix Dx. This suffix refers to dataset instances that have been previously created and presented in those papers. Because of the extension of the dataset, the need of introducing more clear name system has arisen. Suffix has been added to a reference of previously created files, keeping the naming convention applied after dataset extension.

The experiments have been divided into investigating the influence of ACO parameters’ configurations for project duration and performance cost in three various components’ weights in evaluation function: duration optimization (DO: \(w_\tau =1\), see. Eq. 10), balanced optimization (BO: \(w_\tau =0.5\)) and cost optimization (CO: \(w_\tau =0\)). Because of the stochastic nature of ACO-based methods, each experiment for given parameter configuration has been repeated ten times. For K–S test and t test, each experiment has been repeated 50 times (see Tables 9, 10). On the other hand, deterministic character of heuristics allowed us to obtain results for those methods in only one iteration for every parameters’ configuration.

The further step of the conducted experiments was to compare results obtained for random initial solution with boosting initial solution using described hybrids. Initial solution has been previously obtained using the above-mentioned heuristics and then set them as input for ACO and made those results as more favorable in local search by enhancing the pheromone value left in this path representing initial solution. We decided to use SLS(D) (Skowroński et al. 2013b) for DO mode and RS(A) (Skowroński et al. 2013b) for CO mode optimization within HAntCO hybrid. Because of some code refactoring, we were able to tune our heuristics and obtain a better solution than the found ones in Skowroński et al. (2013b). That is the reason why the results of those heuristics in this paper are slightly better than the results in Skowroński et al. (2013b) for given dataset instances.

To present averaged results in detail (see Table 4), a standard deviation measure (\(\sigma \)) has been introduced and applied to each average value, presented as a percentage value in relation to the average. We have also added information about the best found solution for a given method (see Table 2) that have been compared with the results obtained by most promising heuristics, described in Skowroński et al. (2013b).

Both for the best and averaged results, pheromone update methods have been compared and the one that provided best results (shortest duration in DO, smallest cost in CO and smallest evaluation function value in BO) is presented in Tables 2 and 4. The notation for methods used in tables with obtained results is as the following: E—update ELITE pheromone method, A—update ALL, D—update DIFF. If more than one pheromone update methods turned out to be the best and gave the same results, they have been presented both separated by “/” (e.g., E/D—both update DIFF and update ELITE methods gave the same, best results). In Table 2, a sign \(*\) has been also introduced to indicate a situation where all three methods provided the same, regarded as the best, result.

All the results presented in tables have been obtained for given ACO parameter configuration: \(p=12\), \(\mu =0.1\), \(p_{\mathrm{init}}=1.5\), \(\alpha =1\), \(\delta =0.05\), \(p_{\mathrm{min}}=0.05\), \(h_{\mathrm{init}}=1\), \(\beta =0\), \(\gamma =150\), \(\sigma =30\), \(\psi =0.1\), \(\kappa _{\mathrm{init}}=20\). This configuration has been regarded as the best, defined as a result of the previous parameter-tuning experiments. The same configuration has been chosen to be used in every pheromone update method (ALL, ELITE, DIFF), every optimization mode approach (DO, BO, CO) both for ACO and HAntCO approaches.

The processing time was varied in relation to the used update method. For ALL method that could be regarded as the simplest, the processing time was relatively small (from 7 to 90 s, depending on processed dataset instance). However, for ELITE and DIFF methods that are regarded as more complex because of the need of sorting ants and choosing best/worst, the processing time varied from 30 to 270 s per one execution in one CPU for given parameter configuration.²

Our research has been extended by investigating the level of complexity of compared methods. The complexity has been estimated as a number of potential assignments of resources to a given task as dominant operations. As this value is constant regardless of the optimization process and depends only on initial skill constraints, we can compute the level of complexity as a factor of an average number of iterations and a number of possible assignments. The results of those computations are presented in Table 7.

As we decided to set a constant number of iterations in most methods such as TS, EA S and EA C, the complexity level for those methods was easy to compute. For ACO and HAntCO, we decided to get an average number of iterations from all optimization modes (DO, BO, CO) and update pheromone methods (ALL, ELITE, DIFF) as the value that should be multiplied by a number of possible assignments.

Based on the results gathered in Table 7, we can notice that ACO and HAntCO are most processing complex methods. However, the level of complexity for HAntCO is lower than for classical ACO. It is because the number of iterations for hybrids is generally smaller, as searching is started from more directed place in the solution space.

Complexity level of heuristics has been computed as multiplication of a number of possible assignments by 1, as there is only one iteration in heuristic scheduling process. What is more, heuristics are deterministic approaches. Therefore, we always get the same results that are obtained in only one iteration. Hence, heuristic could be used as a powerful tool to get the first glance of optimization possibilities for given dataset instance.

Both for the best and averaged results for classical ACO, ELITE update pheromone method turned out to be the best for DO mode, while DIFF update pheromone method became the most suitable for BO mode. However, it is not possible to get such straightforward conclusions for CO mode, because DIFF method became the most suitable choice for the best obtained results, while both DIFF and ELITE methods provided equally good results for average obtained optimization results.

We have also compared pheromone update methods in hybrids performance. For that approach, ELITE mode turned out to be the most suitable for DO, while any (\(*\)) proposed pheromone update method became equally good for CO mode for most project instances. No difference between pheromone update method has been also observed in 15/36 (42 %) cases in CO. It could lead to conclusion that pheromone update method is not as crucial as for classical ACO. It is because initial solution is preferred—hybrid is more exploitation—than exploration-oriented.

We have also compared how many times heuristics provided better results than the best ones obtained from an application of ACO approaches (see Table 2). For DO, SLS heuristic became better 9 times (25 %); while for CO SA or RS, heuristics became better 18 times (50 %). It shows that classical ACO approach proposed in this paper cannot be fully regarded as better in comparison with heuristic methods. However, combining it with heuristic in hybrid (HAntCO) approach turned out to give usually much better results than any other investigated methods, especially for CO mode.

An interesting fact is that DO mode is generally more stable than other based on the provided results. It has been deducted by counting number of bigger than 10 % \(\sigma \) values in Table 4. For DO, there were no such values, while, for BO, there were 3 over 10 % values (2 for duration aspect and 1 for a cost aspect). Finally, for CO, there were 7 over 10 % values of standard deviation—all for a duration aspect.

An interesting conclusion that could be made regardless of the best or averaged results is that a DIFF strategy provided better solutions in DO mode but mostly for dataset instances containing 200 tasks. The best results obtained by a DIFF strategy were better than obtained by an ELITE in 9 cases for 200 task-project instances (50 %), while ELITE strategy provided only one better solution than a DIFF (5 %). Averaged results obtained in a DIFF mode were better in 12 cases (67 %), while ELITE strategy still provided only one better solution in comparison with a DIFF.

Comparing the best results obtained by ACO and HAnt-CO, it can be noticed that HAntCO outclasses classical ACO, whichever pheromone update method would be used. For DO, classical ACO approach has been better than HAntCO in only 5 from 36 cases; while for CO, HAntCO became better than ACO for every project instance. Analysing averaged results, there are only 3 cases with ACO results better than HAntCO ones. Still only for DO. For CO, ACO has never been better than HAntCO. It proves the legitimacy of using hybrids that become robust way of boosting optimization process.

To get bigger awareness of classical ACO and HAnt-CO approaches’ robustness, we decided to compare the obtained best results for ACO with best results obtained using other methods, as EA (Skowroński et al. 2013a) and TS (Myszkowski et al. 2013). However, we needed to distinguish the best results obtained for DO and CO modes from BO mode, because no heuristic scheduling method has been proposed for BO. Comparison of DO, BO and CO modes is presented in Table 8.

This comparison has been made only for project instances D1–D6, because only those have been investigated in Skowroński et al. (2013a, b), Myszkowski et al. (2013). The compared methods are Taboo Search (TS), specialized Evolutionary Algorithms (EA S), classic EA (EA C), classical ACO, HAntCO and heuristics (H).

The results presented in Table 8 show that both HAnt-CO and TS outclassed other methods in DO mode, obtaining best cost results for half of investigated project instances for each method (D1, D2, D5, D6 for HAntCO and D3, D4 for TS). For CO mode, classical ACO became the best approach for D2 and D3 instances, while HAntCO obtained the best results for the same instances plus D1. However, the most successful approach for these instances is a heuristic one that allowed to get best results in 5/6 cases.

The averaged results of investigated methods are presented in Table 9. It differs slightly from the results in Table 8, as methods are non-deterministic. However, conclusions are very similar: HAntCO outperforms other methods in almost every case or results are comparable. We developed extra statistical analysis to prove a quality of presented method. We have provided the Kolmogorov–Smirnov (K–S test) to investigate the normality of the distribution of gained results. The K–S test proved that results of used methods are normally distributed and t test can be used. Moreover, a sample size around 50 allows the normality assumptions conducive for performing the unpaired \(t\) tests (Flury 1997). We used two tailed t test with 95 % confidence interval (see results in Table 10) for the best and the second best performing methods applied in D1–D6 instances for DO and CO modes.

We found that HAntCO results are the best in most cases. Very interesting results are noticed for EA S, especially for D5 instance (in DO and CO mode) where EA S gives the best (average) solutions.

Only in one case (D3 instance DO mode), ACO gives better average solution. The results are significant in statistical meaning. The statistical significance of results for HAntCO in CO mode comes mostly from the fact that HAntCO is a method directed by a heuristic that finds the best cost-oriented solution (algorithm). Hence, the statistical significance of this method should be mostly investigated in DO mode. In this mode, the results obtained by HAntCO are statistically significant in 3 cases (D1, D2, D6), while DO-oriented results obtained by ACO are statistically significant in only one case (D3). It additionally proves the legitimacy of using proposed hybrid rather than classical ACO approach. We have also investigated results for several methods in BO mode. In this case, classical ACO approach outclassed the rest of examined methods and became the best choice in 5/6 cases. However, it caused enlarging the project schedule duration of analyzed instances and make them mostly the longest from all obtained with various methods. EA with specialized genetic operators gave the smallest project cost for BO mode. It was the best in 5/6 cases. An interesting fact is that the results obtained for ACO are completely different from the results from other methods like TS or EA. The conclusion could be that ACO searches the solution space totally different from the above-mentioned methods. Hence, combining those approaches into one could be possibly effective and potentially give promising results.

After observation that pheromone update method in ACO has an impact on the obtained results depending on selected optimization mode (aspect), we are encouraged to use this outcome and propose an approach more dedicated to multi-objective optimization using Pareto front from various ant populations performing in different pheromone update methods. It could provide us a mechanism to find very good solutions leaving the need of setting optimization mode. It could give us good solutions in DO and BO in the same run of ACO-based run.

As cost-oriented optimization in ACO and HAntCO has not provided significantly better results than other methods investigated in this paper, we discuss a potential application of dedicated neighborhood definition for ants to make them more oriented to search solutions cheaper.

Investigating the comparison of the results obtained for CO and DO modes could lead to conclusion that ACO is a powerful tool for solving MS-RCPSP, especially if it was boosted by initial solution obtained by heuristic (HAntCO). It leads to conclusion that other hybrids should be investigated using the proposed heuristics. Hence, we would examine and compare the results obtained for EA, TS or SA approaches to check, whether boosting initial solution by heuristic provides better results for other metaheuristics.

According to the experiences with ACO of other researchers, ACO can be extended by additional heuristic (Dorigo 1997) to enhance the potential of optimization. We plan to find suitable, problem-specific heuristic that could be used and investigate whether it could make our approach better in solving MS-RCPSP.