Keywords

1 Introduction

The resource constrained project scheduling problem (RCPSP) involves the scheduling of project activities so that given temporal constraints between activities are satisfied, that the prescribed resource capacities are not exceeded, and a given objective, e.g., the project duration (i.e., makespan) is minimized. However, in contemporary enterprises, single project settings are rare today. Hence, issues involving the simultaneous management of multiple projects (or portfolio of projects) have become more prevalent. According to Payne [1], up to 90 % of all projects worldwide are executed in a multi-project context. Considering this demanding fact, this paper addresses the resource constrained multi-project scheduling problem (RCMPSP), which is an extension of RCPSP, and is considered as the simultaneous scheduling of two or more projects which demand the same scarce resources. Meanwhile, when dealing with multiple projects, two approaches have been used in earlier researches: (1) a single project approach, using dummy activities and precedence arcs to combine multiple projects into a single mega-project or (2) a multi-project approach, maintaining each RCMPSP and a separate critical path per project [2]. Here, this paper took the second approach.

In spite of having high relevance with modern project management practices, RCMPSP has not been studied as comprehensively as single-project scheduling. Moreover, as a generalization of the RCPSP, RCMPSP is also considered to be NP-hard [3], meaning that there are no known algorithms for finding optimal solutions in polynomial time. When using a multi-project approach, two general approaches are used to solve RCMPSPs, namely exact methods and heuristic procedures. Among the few, exact methods are the similar earlier works of Drexl [4]. But those exact methods are limited to solving small problem instances and are impractical for solving large RCMPSPs. On the other hand, most of the heuristic methods used for solving RCMPSPs belong to the class of priority rule based methods [5]. In summary, while various studies have identified potentially important characteristics of RCMPSP and proposed various priority rules, the variety of results and their disagreements, have left project managers lacking clear guidance on which priority rule to use in a particular situation.

Although using a large variable neighborhood search (LNS) approach for various problems, such as the vehicle routing problem [6] and travelling salesman problem [7] already exists, to the best of our knowledge no heuristic of this type has yet been proposed for RCMPSP. To fill this gap, we propose a new variable neighborhood search based heuristic, which we named evolutionary local search heuristic with variable neighborhood (ELSH-VN) for RCMPSP. As opposed to only considering activity sequences or generating sub-problems, this ELSH-VN approach considers overall partial schedules that are generated from a parallel schedule generation scheme.

The primary objective of this research was to develop an evolutionary algorithm for solving RCMPSPs. Besides of that, justifying feasibility of different priority rules for this type of NP-hard problems (i.e., RCMPSPs) was another secondary target. Hence, we address static RCMPSP with two tardiness objectives, defined as average project delay and average portfolio delay. We have employed a parallel schedule generation scheme to generate an initial baseline schedule of RCMPSP, which was then applied to our proposed evolutionary heuristic, ELSH-VN. The effectiveness of the solution scheme (i.e., ELSH-VN) was then demonstrated through extensive experimentation with 77 randomly generated problem instances. We then described ten different ELSH-VN alternatives, based on different priority rules, to demonstrate the superiority of any particular priority rule. Computational results have been summarized for all priority-rule based ELSH-VNs. Statistical analysis has also been carried out to further show the superiority of any particular priority rule over other ones. In brief, two key contributions have been made over the existing research on standard RCMPSPs. These are: firstly, we propose an approach for variable neighborhood diversification among the activities that represent an initial unbuffered schedule. We also show how to explore those schedules with evolutionary local searching scheme, particularly by enhanced swapping to find optimal or near-optimal results. Secondly, we have considered a set of priority rule based scheduling procedures with our proposed ELSH-VN for RCMPSP. We find significance differences in the performance of the priority rules which implies that several widely advocate priority rules generally do not perform as well as may be thought.

The structure of the paper is as follows: in Sect. 2 we define the basic RCMPSP with two lateness objectives. In Sect. 3, solution approaches and relevant algorithm designs with priority rules are discussed. The experimental studies, along with their results are in Sect. 4. Finally, we provide conclusions in the last section.

2 Problem Description

RCMPSP consists of several projects, where the individual projects have the characteristics of single project, and is similar to the mathematical formulation of Talbot [8]. Here we assumed that each project consists of \( {\text{i}}\, = \,1 \ldots \,I_{v} \) activities with deterministic and non-pre-emptible duration \( d_{vi} \). We further assumed that (i) activities belonging to any particular project have unique characteristics and do not depend on other project’s activities; (ii) there is a precedence relationship among the activities that belong to any particular project, and all predecessors must finish before an activity can start; (iii) resources considered here are only of renewable type; (iv) activities are non-pre-emptive (i.e., cannot be interrupted when in progress); (v) the parameters (durations, capacities and resource requests) are non-negative and integer valued; (vi) there is no dependency relationships among the projects, apart from resource sharing. The binary decision variable \( x_{vit} \) represents 1 if activity i of project v starts at time period t or 0 otherwise. RCMPSP involves finding a schedule for the activities (i.e., determining the start or finish times) that optimizes a performance measure, such as minimizing the average delay in all projects. For measuring delays, each project is associated with a due date. This due date is defined as the lower bound of project completion time without considering any resource constraints. Using the further considerations and notations, as given in the below nomenclature section, the conceptual mathematical formulation for RCMPSP is given below:

2.1 Nomenclature

V :

Set of projects, v = 1 … V

\( I_{v} \) :

Set of activities of project v, i = 1 … \( I_{v} \)

\( Prec_{v} \) :

Set of all precedence relationships of project v

\( S_{vj} \) :

Set of all successors of activity j belonging to project v

\( \left| {S_{vj} } \right| \) :

Number of successors for activity j in project v

\( k \in K \) :

Renewable resources (e.g., Machines)

\( NI_{v} \) :

Number of activities for any particular project v (last activity)

\( R_{k} \) :

Capacity of renewable resource k

\( r_{vik} \) :

Renewable resource k usage of activity i of project v

\( d_{vi} \) :

Duration of activity i of project v

\( ES_{vi} ,\,LS_{vi} \) :

Earliest and latest finish time of activity i of project v

T :

Total planning horizon/upper bound of all projects

\( f_{vi} \) :

Finish time of activity i belonging to project v

\( S_{vi} \) :

Start time of activity i belonging to project v

\( CP_{v} \) :

Critical path duration of the v’th project without resource constraints

$$ {\text{Min}}\,\Phi (\text{F}) $$
(1)
$$ \mathop \sum \limits_{{t = ES_{vj} }}^{{LS_{vi} }} x_{vit} \, = \,1\,for\,\forall i\, \in \,NI_{v} \,and\,\forall v\, \in \,V $$
(2)
$$ \mathop \sum \limits_{{t = ES_{vb} }}^{{LS_{vb} }} \left( {t - d_{vb} } \right)x_{vbt} \, \ge \,\mathop \sum \limits_{{t = ES_{va} }}^{{LS_{va} }} tx_{vat} \,\forall \left( {a,\,b} \right)\, \in \,Prec_{v} \,and\,\forall v\, \in \,V $$
(3)
$$ \mathop \sum \limits_{v = 1}^{V} \mathop \sum \limits_{i = 1}^{{NI_{v} }} \mathop \sum \limits_{q = t}^{{t + d_{vi} - 1}} r_{vik} x_{viq} \, \le \,R_{k} \,\forall k\, \in \,K,\forall t\, \in \,T\,and\,\forall v\, \in \,V $$
(4)
$$ x_{vit} \, \in \,\left\{ {0,\,1} \right\}\,\forall \,v\, \in \,V,\,\forall i\, \in \,I_{v} \,and\,\forall t\, \in \,T $$
(5)

The objective function (1) seeks to optimize a pre-specified performance measure set by the planner. Although a variety of objective functions have been used for RCMPSP, minimizing project duration is commonly used. However, in this study, we seek to minimize project or portfolio delays (tardiness). Hence we considered two different objective functions, which are defined in the following equations:

$$ Average\,Project\,Delay\,\left( {APD} \right)\, = \,\frac{{\mathop \sum \nolimits_{v = 1}^{V} a_{{v/A_{v} }} }}{V}\, \times \,100 $$
(6)
$$ Average\,Portfolio\,Delay\,\left( {APFD} \right)\, = \,\frac{{Max\left( {A_{1} + a_{1} , \ldots ,A_{V} + a_{V} } \right) - Max\left( {A_{1} , \ldots \,,A_{V} } \right)}}{{Max\left( {A_{1} , \ldots ,A_{V} } \right)}}\, \times \,100 $$
(7)

Here in Eqs. (6) and (7), \( A_{v} \) represents the due date of project v, which equals the length of its resource unconstrained critical path (CP). Meanwhile, \( a_{v} \) represents the delay due to resource constraints. Constraint set (2) ensures that all activities of any particular project v are to be scheduled once and only once. Constraint set (3) implies the predecessor relationships for all activities within a project. Here no precedence relationship is considered within projects. Constraint set (4) limits the maximum level of renewable resources used by the activities belonging to any project v. For any particular time period t, the maximum amount of renewable resource usage should be within its availability limit. Finally, constraint set (5) forces the start times to be non-negative.

3 Algorithms

3.1 ELSH-VN

In this section, we present the procedural steps and basics of our proposed Evolutionary Local Search Heuristic with Variable Neighborhood (ELSH-VN). This ELSH-VN procedure is analogous to a descent search, or a hill-climbing approach, with a candidate list strategy. In contrast with a traditional searching strategy, the legal moves for active activities for this heuristic are only those which belong to the candidate list at each stage. The overall procedures of this heuristic are also comparable to Tabu search, in the sense that when a move or swapping is effected, the activity concerned is unlikely to be moved back to its old position, until it is encountered again while searching the sequence, or unless the resulting sequence leads to the best makespan so far. An evolutionary local search strategy was developed, where the primary focus was to increase the neighborhood search space with varied dimensions, and to allow activities to swap among both its direct and indirect successors and predecessors, even though it may take slightly more computational time than the traditional variable neighborhood approach.

For implementing that evolutionary local searching scheme among diversified neighborhood activities, at first, an initial feasible schedule matrix was generated by following some schedule generation scheme (in this paper we executed the parallel schedule generation scheme (PSGS) [9]). Later on, with that initial schedule, each activity was swapped or moved, in both forward and backward directions, while maintaining both their direct and indirect precedence relations. Following this iterative procedure, after meeting the stopping criteria, if possible, another updated schedule was generated with better makespan performance. It is worth noting however, that in either move strategy, not every move leads to a new schedule due to resource contradictions. Therefore, to find whether a move does lead to a change in schedule, at first, resource constraints should be satisfied with each of the newly generated schedules, by only calculating their start or finish times. If none changes, then the overall schedule will remain the same and it is worthless to re-compute it. Moreover, extensive experimentation has shown that the better the initial solution with which ELSH-VN for RCMPSP is started, the better on average the final solution will be. For better clarification, the step-wise overall solution scheme of ELSH-VN is given below.

Algorithm: Step-wise procedure of ELSH-VN

3.2 Priority Rules

In order to assess the performance of the proposed ELSH-VN, we have considered, for comparison, a set of scheduling procedures with different priority rules. Since different activities have different features (resource, duration combination), so selecting a set of (or single) active activities is always complicated. Therefore, proposing and switching some priority based rules for use among the active activities may resolve this issue and accelerate performance [10]. We compiled a set of 10 popular priority rules from the literature (shown in Table 1), some of which have already proved to be successful in a single project environment. The main motivation for selecting these different scheduling procedures was to see whether ELSH-VN with default activity selection rule (i.e., random selection rule) is competitive with other possible priority rules. As well as to see if any other combination of priority rules with ELSH-VN can give a better approach.

Table 1 Priority rules
Full size table

4 Experimental Results and Analysis

Extensive numerical experiments have been carried out with the aim of assessing the performance of our proposed ELSH-VN for RCMPSP. A comparative evaluation has also been made with the compiled set of 10 priority rules. The computational experiments have been performed on an Intel core i7 processor with 16.00 GB RAM and a 3.40 GHz CPU. All procedures were coded and solved in Matlab, R2015b. ELSH-VN was employed for generated RCMPSP instances, while the maximum iteration number, \( iter_{max} \), was set as 1000 and the maximum number of algorithm runs, \( {\text{run}}_{ \hbox{max} } \) was set as 30. The maximum solving time for all projects under each instance was set as 500 s. An in-depth analysis of the properties of RCMPSP, and the behavior of a scheduling method, is barely possible based on just a single RCMPS instance. Therefore, motivated by Browning and Yassine [16], we followed a pragmatic approach to generate additional test instances for RCMPSP, which will then be used to evaluate our proposed ELSH-VN in more detail.

4.1 Generation of Test Projects

Depending on different instance characteristics, we generated some test instances for RCMPSP. Among a few, Network complexity (C), Normalized average resource loading factor (NARLF) and Modified average utilization factor (MAUF) are the most important characteristics for generating multi-project instances. Details on these characteristics can be found in the earlier work of Browning and Yassine [2]. To maximize possible insights, we considered seven NARLF and 11 MAUF levels [17]. In addition to that, we considered a high project complexity measure for each project (i.e., C = 0.69) while all of the individual resources MAUFs were not equal (i.e., showing \( \left. { \sigma_{MAUF}^{2} = 0.25} \right) \). Thus, we generated 7 × 11 = 77 test problems for this experiment. As standard problem generators and test sets such as ProGen/PSPLIB cannot create multi-project problems to these specifications, we used a test problem generator developed by Browning and Yassine [16]. For better understandings, a brief summary of this experimental set up and test project generation is outlined in Table 2.

Table 2 Experimental design (C.F: Constant Factor; M.F: Main Factor)
Full size table

4.2 Experimental Results for Priority Rule Based ELSH-VN

Table 3 summarizes the performance of our proposed ELSH-VN for our newly generated 77 RCMPSP instances. Here we considered four different posterior measures to justify the performance of ELSH-VN, namely: average project delay (APD) as percentage, average portfolio delay (APFD) as percentage, lower total makespan (LTM) after 30 runs and finally total computational time (TCPU) per run in seconds. As mentioned before, ten different priority rules were executed under ELSH-VN and the comparative results are outlined in Table 3. As of that table, the random selection rule based ELSH-VN showed best performance in comparison to other priority rules, while MAXSLK and LST are quite competitive. Irrespective of priority rules, the TCPUs for each heuristic are nearly consistent and per run time it is always 0.207 s or less.

Table 3 Performance of different priority rule based ELSH-VN
Full size table

Starting with APD, Fig. 1 shows the graphical representation on the impact of different MAUF values on APDs. As evident from this figure, the winning priority rule (i.e., the one with the smallest average percentage delay) is RSR. Surprisingly among LST, MPT, MAXSLK and SASP, there is no significance difference of their respective APD values and so they are apparently tied for second place. Obvious losers include MINSLK as the worst and LCFS as second worst. To investigate the margin of superiority for RSR over others, it is important to have a comprehensive statistical analysis on all proposed algorithms. Since our considered problems are complex in nature and there is a high chance of greater precedence constraints, priority rules that depend on precedence relationships might show lesser influence on minimizing APDs [2].

Fig. 1
figure 1

APD versus MAUF level

Full size image

As evident from Fig. 2, a similar trend can also be found for APFDs. While APD affects the effects of delay on the projects individually, APFD only accounts for delays that lengthen the overall portfolio of projects. As a consequence, while individual project managers would care more about APDs, portfolio managers would have reason to focus on APFDs. Interestingly, here also RSR, LST and MAXSLK show the least (or lesser) APFD values than the other rules.

Fig. 2
figure 2

APFD versus MAUF level

Full size image

In addition to analyzing the influence of MAUF on minimizing project delays, we also carried out numerical experimentation on the project data to see the possible impact of NARLFs. The NARLF interaction plot shown in Fig. 3 exhibits the superiority of RSR at all levels, followed by MAXSLK and SASP. MINSLK and LCFS are placed as worst priority rules because of their inefficiency at minimizing APDs. Meanwhile, Fig. 4 plots the relative values of APFD for different levels of NARLF. Similar conclusion can be drawn for APFDs as well. However, as evident in Fig. 4, RSR and MAXSLK show similar APFDs if the value of NARLF is zero. Again for NARLF equals −1, the MAXSLK priority rule shows even better results than the RSR priority rule, which can be considered an important finding of this research.

Fig. 3
figure 3

APD versus NARLF level

Full size image
Fig. 4
figure 4

APFD versus NARLF level

Full size image

4.3 Statistical Comparison

As illustrated in the previous section, apart from the RSR priority rule, there is no firm evidence on the superiority of any particular priority rules over others. Hence to assist decision making and to evaluate the overall performance of all priority rule based ELSH-VNs, we used a ranking procedure based on a non-parametric test, called the Friedman test [18]. The Friedman test is often used for a randomized complete block design when the normality assumption is not satisfied or the data is ordinal. Under each instance, for each of the priority rule based ELSH-VN, relative ranks were calculated by considering the two major performance measures (APD and APFD) described in Sect. 4.2. Relevant rankings are summarized in Table 4. As evident from Table 4, RSR shows the least relative rank value, which shows its significant superiority. Considering APD as a performance measure, FCFS can be considered as the second best, while for APFD measures, the MAXSLK priority rule placed second.

Table 4 Rank measurement of different priority rule based ELSH-VN using friedman test
Full size table

From this Friedman test, we can easily conclude the superiority of any particular algorithm over another, depending on number of nodes and types of statistical distributions. However, to analyze the difference between the best one and the second best one, we have also carried out another statistical test, the Wilcoxon signed ranks test [19]. Using a 5 % significance level, we assigned one of three signs (+, − and ≈), where “+” means that the first algorithm is significantly better than the second one, “−” means that it is significantly worse and ‘≈’ represents that there is no significant difference between these algorithms. According to Table 5, it shows that the RSR priority rule convincingly outperformed its nearest competitive priority rules (i.e., FCFS or MAXSLK). We speculate that the superior performance of MAXSLK over others (except RSR) here may be due to the generally high constraining values of AUF which characterizes our generated instances. Moreover, while intelligence based priority rules work better for single mode RCPSPs, but for RCMPSPs, rules without intelligence (i.e., RSR) works better than others. The appropriate reasoning behind this superiority of RSR is still needs to be researched.

Table 5 Wilcoxon signed ranks test results for comparing the best performing algorithms
Full size table

5 Conclusions

In this paper, we considered the RCMPSP with deterministic activity durations and temporal relations. To solve RCMPSP, we developed a variable neighborhood search based greedy algorithm, ELSH-VN. The suitability and appropriateness of that heuristic was then studied by incorporating ten different priority rules. In order to conduct computational experiments with RCMPSP, a large set of test instances has been generated. To judge the superiority of any particular priority-rule based ELSH-VN, we carried out a comprehensive statistical analysis based on both the Friedman and Wilcoxon tests. This statistical comparison, and extensive simulation-based experiment, revealed that the RSR outperformed others, while FCFS and MAXSLK algorithms are insignificantly superior to others, especially when the performance measures were like average project delay or average portfolio delay.

Because of its ongoing practical relevance, RCMPSP is quite common in modern industry, which makes efficient algorithms for them valuable. Decisions about which activities to do when (based on resource allocations) have a substantial effect on project completion time. Hence there is a necessity of choosing suitable priority rules to select appropriate activity. In this context, this paper dealt with ten different priority rules to compare and contrast. Importantly, our experimentation shows that previously published results do not always correspond with their performance on RCMPSP. While widely advocated rules such as MINSLK, SASP and LST did not perform well, our study revealed that the RSR outperformed others.

Future research is possible, for example, considering multiple modes to reflect alternative speeds of the production processes. Also, including additional priority rules, comparing with other schedule generation schemes, exploring other RCMPSP formulations (i.e., allowing activity pre-emption, stochastic activity durations, or uncertain resources) can also be important extensions of this paper.