Stochastic project management: multiple projects with multi-skilled human resources

In (2)–(7), we present our stochastic optimization model in mathematical terms. For a project p and a time period t, we letdenote the set of all possible activities q of project p that could lead to a resource demand in time period t.The objective function in Eq. (2) minimizes the expected external costs. The symbol E denotes the mathematical expectation and \(x^+\) stands for \(\max (x,0)\). The external costs result from that part of the stochastic demand that is not covered by the internally scheduled capacity. The constraints in Eq. (3) ensure that activity q of project p is scheduled exactly once within the pre-defined time window \([ES_{pq},LS_{pq}]\). The condition that activities q must be processed in an ascending order is guaranteed by the constraints in Eq. (4). Equation (5) formulates the capacity constraints for each resource k and time period t: observe that for a resource with efficiency \(\eta _{sk}\), an effective work time of \(x_{ptsk}\) entails a real work time of \(x_{ptsk}/\eta _{sk}\). Finally, the decision variables are defined in Eqs. (6) and (7).

Let us remark that in some cases, external costs grow faster than linearly in dependence of the outsourced work, for example because a selected supplier company has limited capacities itself. To generalize the model above to this situation, the given nonlinear external cost function could be approximated by a piecewise linear function, which can be dealt with by a simple extension of our Eq. (2). Numerical solution techniques for this more complex model are a topic of future research.

As it is seen from the formulation above, our model can be viewed as a tactical two-stage stochastic optimization model with project plan and work assignment as first-stage decisions and outsourcing to external resources as the possible recourse actions. During the ‘real’ project execution, we assume that we get updated information about the realizations of the work package processing times. Our assumed recourse in the case of insufficient internal capacity is the hiring of external resources, where we assume that the information about the work package processing times arrives early enough to hire the necessary external resources. The presented tactical planning approach could be extended including more operative decisions by concerning other recourse actions such as reassignment and rescheduling of internal resources. This could lead to better solutions and new interesting managerial insights but would lead to a more sophisticated planning approach.

Finally, let us recall that our model assumes that the activities q of each project p have to be arranged in a pre-specified linear order analogously as in Kolisch and Heimerl (2012). Nevertheless, due to the requirement of independent work package processing time distributions, an additional assumption, where for each project p and in each time period t not more than one activity q of project p is allowed to be scheduled (no parallel activity processing per project), is needed. If this condition is satisfied, an extension of the developed stochastic solution approach to more general precedence constraints between activities is straightforward. For this extension, the variable \(z_{pqt}\) can again be the indicator variable for the decision that activity q of project p is scheduled in time period t. A constraint \(\sum _q z_{pqt} \le 1\) has to be added, and the precedence constraints have to be expressed by a more flexible set of constraints (Artigues et al. 2008) than those given by Eq. (4).

As mentioned above, the considered project scheduling and staffing problem distinguishes between two decisions: the project scheduling decision where the execution times of the activities q are determined, and the staffing decision where employees are assigned to cover parts of the work packages. Let z and x denote the array of the decision variables \(z_{pqt}\) for project scheduling, and the array of the decision variables \(x_{ptsk}\) for staffing, respectively. By \(\xi \), we denote the random influence in our stochastic model. Abbreviating the total external cost by \(G(z,x,\xi )\) (it depends on \(\xi \) since it is a random variable) and its expected value by \(g(z,x)=E[G(z,x,\xi )]\), our optimization problem can be written as \(\min _{z,x} g(z,x)\), where (z, x) has to satisfy the constraints (3)–(7). For a given project schedule z, we call \(\min _{x} \, g(z,x)\) on the constraint that x is feasible with respect to (5)–(6), the staffing subproblem.

The expected value (EV) problem or mean value problem is obtained from the original stochastic problem by replacing each random variable \(D_{psq}\) by its expected value \({\bar{d}}_{psq} = E(D_{psq})\), so that the distribution of \(D_{psq}\) collapses to the point mass in \({\bar{d}}_{psq}\). With the help of the introduction of the auxiliary variables for the external work time required \(y_{pts}\) per project p time period t and skill s, the following mixed-integer linear problem is obtained:subject to constraints (3), (4), (7), andThe EV problem serves as an approximation for cases where the variances of the random variable \(D_{psq}\) are very low, or, if the variances are larger, as a means to obtain an initial solution for an iterative search procedure

For a pre-defined feasible project schedule z, the staffing problem \(\min _{x} \, g(z,x)\) remains to be solved. Because z is now already fixed,is a random variable that does not depend on any decision anymore, i.e., the distribution of \(D'_{pst}\) is already known. \(D'_{pst}\) represents the effective work time of project p in skill s that has been scheduled for time period t by the given schedule z. Using the random variables \(D'_{pst}\), we can express the staffing problem in the formsubject to constraints (5) and (6).

Obviously, the objective function (12) is nonlinear, but it is not difficult to see that it is at least convex, since the function \(x \mapsto x^+\) is a convex function and the expectation operator, as a linear operator, preserves convexity. Letwith \(h_{psq}(\theta )\) denoting the probability density function of \(D'_{pst}\), such that (12) can be rewritten assubject to (5) and (6). Elementary calculations show thatwith \(H_{pst}\) denoting the cumulative distribution function (CDF) of \(D'_{pst}\).

Our first solution method is a matheuristic approach, i.e., a combination of a metaheuristic with an exact optimization technique. We solve the staffing subproblem by means of the exact Frank–Wolfe algorithm (see, e.g., Clarkson 2010) for convex optimization under linear constraints. This is the topic of Sect. 3.4.1. The scheduling problem is solved by a metaheuristic of Iterated Local Search type, which will be described in Sect. 3.4.2.

Our second solution approach for the stochastic project scheduling and staffing problem is the method of sample average approximation (SAA), see Kleywegt et al. (2002). The SAA method samples scenarios from the given distribution of the random events and approximates the given stochastic problem by the so-called deterministic equivalent, the problem resulting as the average over the scenarios. The deterministic equivalent can be solved by methods from deterministic optimization.

In the case of our problem, we draw a set of N random scenarios, described by the realizations \(d_{psq}^{(1)}, \ldots ,d_{psq}^{(N)}\) of the random variables \(D_{psq}\)\((p \in P, \, s \in S, \, 1 \le q \le d_p)\). Thus, \(d_{psq}^{(n)}\) denotes the demand of work package (p, s, q) in scenario n. The external work time required under scenario n for project p and skill s in time period t will be denoted by the new variable \(y_{pts}^{(n)}\). The deterministic equivalent is then the problem (20)–(22), which is obviously a mixed-integer linear program. Note that \(\Theta _{SAA}(z,x)\) represents the average of the external costs over all scenarios, which approximates the expected external costs, and that the values of the variables \(y_{pts}^{(n)}\) result in (21) by a formula analogous to (9). The mixed-integer linear program (20)–(22) can be solved by standard solvers such as CPLEX. However, for realistic instance sizes and an appropriate number of samples, the problem (20)–(22) can become rather large, such that it may become difficult for the solver even to find a feasible solution within a reasonable time budget.subject to constraints (3)–(7) and

For our computational experiments, we generated test instances by the test instance generator proposed in Heimerl and Kolisch (2010). This test instance generator is inspired by data from the IT department of a large semiconductor manufacturer. However, we had to extend the test instances since in the present paper, the information about the demand of work packages is assumed to be uncertain. In particular, in addition to the parameters number of projects |P|, time window size \(\gamma =LS_p-ES_p\), and number of skills per resource \(\vert S_k \vert \), also a further parameter representing the degree of uncertainty (which will be explained later) had to be varied across the test instances. The database with the instance set is available for download at the website http://​phaidra.​fhstp.​ac.​at/​o:​2529.

Table 1 lists the parameter values for the basic instance structure. For this group of instances, the number of projects is 10, and the earliest start period \(ES_p\) of each project p is drawn from a uniform distribution between 1 and 7. The project length \(d_p\) is set to six periods for each project, and the planning horizon is defined as \(T=12\), which represents annual strategic project scheduling and personnel planning. We choose a time window size \(\gamma =1\) which means that for each activity q, there are two possible start times available, considering precedence constraints. With \(S^{(p)}\) denoting the set of skills required by project p, and with \(S^{(p,q)}\) denoting the set of skills required by activity q of project p, the test instance generator limits the number \(|S^{(p)}|\) of skills per project by a pre-defined bound; moreover, for each activity q of a project p, the test instance generator specifies the number \(|S^{(p,q)}|\) of required skills. For all skills s not contained in \(S^{(p,q)}\), the values \(d_{psq}\) are set to zero. [For details concerning this aspect of the test instance generation, see Heimerl and Kolisch (2010)]. In our case, we chose \(|S^{(p,q)}|= 2\) and limited the total number of skills per project by \(|S^{(p)}|\le 3\). Ten internal resources are assumed (\(|K|=10\)), each owning \(|S_k|=2\) out of \(|S|=10\) skills. The resources have different efficiency values \(\eta _{sk}\) for each skill k they own; these efficiency values are drawn from a truncated normal distribution with an expected value of \(\mu =1\), a standard deviation of \(\sigma =0.25\), and minimum and maximum threshold values of 0.5 and 1.5, respectively. The available capacity per internal resource \(a_{kt}\) is 20 per time period. Note that we do not assume that a time period has a length of one time unit: In our above-mentioned interpretation of the test instances as referring to annual planning, the time unit is a day, and a time period extends over a month, so \(a_{kt}=20\) means that an employee works 20 days per month.

The external cost rates \(c_s^e\) differ for different skills and are drawn from a truncated normal distribution \(TN_{a,b}(\mu ,\sigma )\) with \(\mu =800\), \(\sigma =100\), \(a=600\) and \(b=1000\). In test instance generation, (planned) utilization \(\rho \) is defined as the ratio of the overall expected resource demand to available internal resource capacity. In the basic instance structure, we set \(\rho =1\). For each work package, the test instance generator computes an initial value \([E(D_{psq})]^{init}\) of the expected resource demand from the utilization \(\rho \) and the resource supply values \(a_{kt}\). The actual expected value of the resource demand \(E(D_{psq})\) is then drawn from a normal distribution, with mean \(\mu =[E(D_{psq})]^{init}\) and a coefficient of variation \(CV =0.1\). For the basic instance structure, we assume a symmetric triangular distribution of the actual demand with parameters \((D_{psq}^{min},D_{psq}^{mod},D_{psq}^{max})\), where \(D_{psq}^{mod}=E(D_{psq})\), \(D_{psq}^{max}=D_{psq}^{mod} \cdot c_{max}\), and \(D_{psq}^{min}=D_{psq}^{mod} \cdot c_{min}\). The interval \([c_{min},c_{max}]\) controls the level of uncertainty; if \(c_{min} = c_{max}\), we get the deterministic boundary case. For the basic instance structure, a moderate level of uncertainty is assumed by setting \(c_{min}=0.7\) and \(c_{max}=1.3\). Notice that because we use symmetric triangular distributions in our basic test instances, the expected value \(E(D_{psq})\) is identical to the modal value \(D_{psq}^{mod}\) of the distribution.¹

The basic instance structure is varied then to obtain other instance structures, according to Table 2 which lists the parameters with their used values. For test instance generation, we use a ceteris paribus design, which means that we fix all parameters on the value of the basic instance structure and vary the value of one investigated parameter. This yields \(4+(4-1)+(6-1)+(3-1)=14\) different instance structures. For each instance structure, we generate 10 instances, which leads to 140 test instances. Additionally, for each of these 150 test instances, four different levels of the degree of uncertainty (see Table 3), are investigated. This produces a total of 560 instances.

All tests are performed on a standard PC with an Intel Quad Core Processor. In detail, we used an Intel Xeon E3-1271 v3 processor (Frequency: 3,60GHz) with eight kernels and 32 Gigabytes working memory. All presented algorithms are implemented in Eclipse using Java version 1.7. We use the Java API of ILOG CPLEX version 12.4 for the SAA and the EV model formulations.

There are several design decisions that have to be made when using the Frank–Wolfe algorithm within our matheuristic framework procedure: First of all, two slightly different implementation variants of this algorithm were presented in Sect. 3.4.1. Secondly, the algorithm requires an initial solution; we consider two options for its choice. Finally, it has to be specified how the line search is done; again, two different options will be investigated.

Algorithmic variants We shall compare the basic Algorithm 1 (“old” in Table 4) to the modified Algorithm 2 (“new” in Table 4).

Initial solution For the determination of the initial solution, two alternative approaches are tested. First, we use the MILP solver CPLEX (“lp” in Table 4) to solve the deterministic linear staffing problem defined by the parameters \(d'_{pst}=E(D'_{pst}) = \sum _q {\bar{d}}_{psq} \, z_{pqt}\). Secondly, we apply a greedy staffing heuristic (Felberbauer et al. 2016) to solve the same deterministic counterpart problem heuristically (“gh” in Table 4).

Line search method For the line search step of the algorithm, two methods are analyzed: The first method (“gs” in Table 4) uses Golden Section Search according to Kiefer (1953). The second method (“fs” in Table 4) follows the suggestion in Clarkson (2010): it refrains from determining the \(\arg \min \) in line 13 of Algorithm 1 or line 12 of Algorithm 2, respectively, but uses instead in each iteration i a pre-defined step size \(\vartheta ^* = \vartheta ^*(i)\) depending on the iteration index. The value of \(\vartheta ^*\) is calculated as \(\vartheta ^*=2/(i+2) \, (i=1,2,\ldots )\). It is clear that the value of \(\vartheta ^*\) determined in this way does not produce the minimizer on the line segment between \(u^{[i]}\) and \(g^{[i]}\), but by the special choice of the step sizes (convergence to zero and finiteness of the sum of the squares), the convergence property of the Frank–Wolfe algorithm to the exact overall minimizer of \(\Theta _z\) is preserved (for details, see Clarkson 2010). The advantage of the fixed step sizes scheme is that it does not require an evaluation of the function values \(\Theta _z\) during the execution of the algorithm; it suffices to evaluate the derivatives of \(\Theta _z\).

Combining the two alternative options for each of the three design decisions indicated above, we get \(2^3=8\) different design variants of the Frank–Wolfe algorithm. The following results compare the performance of these eight design variants. For each design variant, we shall report its average solution value sv and its average computation time ct at 1000 randomly selected time schedules \(z=(z_{pqt})\) for a single fixed problem instance generated according to the basic instance structure. In a pretest, it turned out that a number \(i_{max}=1000\) of iterations was sufficient to get close enough to the value \(\Theta _z\) achieved by a much higher number \(10^6\) of iterations. Therefore, we used \(i_{max}=1000\) for all design variants.

The results are shown in Table 4. The comparison between the two algorithmic variants Algorithm 1 and the new Algorithm 2 (immediately applying the best partial derivative for the update of the project plan) shows a slight superiority of Algorithm 1. For the decision on the used initial solution method, the test shows that the computation time for solving the deterministic staffing problem takes in the average \(\approx 3.73\) ms using the LP solver and \(\approx 0.26\) ms using the greedy heuristic. On the other hand, the expected cost of the initial staffing plan x in iteration \(i=1\) according to the greedy heuristic is \(\approx 9\%\) higher than the one obtained by the exact LP solver. Nevertheless, applying a two-tailed sign test to the final results for solution values and computation times shows no significant difference between the performance of the LP solver and the greedy heuristic (significance level \(\alpha = 0.05\)). For larger instances, where the LP solving time increases rapidly, the greedy heuristic can become the only feasible alternative, so that in total, we may give a preference to the greedy heuristic. Concerning the line search method, finally, it can be seen that the pre-defined step sizes scheme clearly outperforms the Golden Section Search: Although Golden Section Search provides faster improvements in the first few iterations than the step sizes scheme, the solution quality after 1000 iteration is not better, and the computation time per iteration is \(\approx 200\) times higher.

Summarizing, the best-performing Frank–Wolfe variant, i.e., variant 5 in Table 4, uses the immediate application of each best partial derivative for the update of the project plan, the greedy heuristic for the calculation of the initial staffing solution, and the pre-defined step sizes scheme.

The crucial parameter of the sample average approximation procedure is the number N of sampled random scenarios. Therefore, the following pretests have been conducted to find an appropriate value of N. It is clear that the objective function of (20) is only an approximation to the true objective function, such that even if the SAA problem is solved exactly, we do not necessarily obtain the exact solution of the original problem. To explore the tradeoff between the two effects of increasing the value of N, namely to improve the accuracy of the objective function estimation on the one hand, and to increase the computation time on the other hand, a subset of our instances has been investigated. We chose the instances of those instances structures where the number of projects is varied as \(|P| \in \lbrace 10,15,20,25 \rbrace \), the time window size is \(\gamma \in \lbrace 0,1,2,3 \rbrace \), and the number of skills per resource as well as the utilization are fixed to the values of the basic instance structure, i.e., \(|S_k|=2\) and \(\rho =1\). The degree of uncertainty was varied as \([c_{min}, \, c_{max}] \in \lbrace [0.9,1.1],\, [0.7,1.3],\, [0.5,1.5],\, [0.2,1.8] \rbrace \). For these instances, we varied the sample size as \(N \in \lbrace 10,20,30,\ldots ,100 \rbrace \) and analyzed the solution time and the achieved solution quality. By the SAA model from Sect. 3.5 with sample size N, we compute the solution \((z_{SAA}^*,x_{SAA}^*)\), where \(z_{SAA}^*\) is the optimal project plan and \(x_{SAA}^*\) is the optimal staffing plan. Now, we compare the obtained objective function value \(\Theta _{SAA}(z_{SAA}^*,x_{SAA}^*)\) of (20) to the true evaluation \(E[G(z_{SAA}^*,x_{SAA}^*,\xi )]\) of the solution \((z_{SAA}^*,x_{SAA}^*)\) according to the underlying exact probability model (cf. the notation in Sect. 3.1). The relative gap between the two evaluations is described byIn Fig. 2, the solution time and the relative solution gap according to Eq. (23) as well as their 95% confidence intervals are depicted in dependence of the sample size N. We show here the special case of \(\vert P \vert =20\) projects and the other parameters as in the basic instance structure. It can be observed that for a sample size of \(N=100\), the solution gap is \(\approx 0.5\%\), i.e., the average objective function value over the scenarios can be considered as a good estimate for the expected external costs. A further observation is that the solution time of the SAA model varies to a considerable extent. This behavior points out a first drawback of relying on the exact solution of the SAA model to solve our problem.

These results were extended by solving all test instances of the instance subset specified at the beginning of this subsection. With an appropriate sample size of \(N=100\) and a computation time limit of 360 sec for the CPLEX solver, we observed that CPLEX was able to solve the SAA problems for all considered test instances. In the average over all considered test instances, a relative gap of \(0.71\%\) according to Eq. (23) was obtained.

This section reports on the numerical comparison of the two presented solution methods, i.e., the developed matheuristic (MH) and the sample average approximation (SAA) approach. Note that by fixing a sample size N, the computation time consumed by the SAA approach is already defined. To ensure a fair comparison between SAA and MH, we computed, for a given test instance structure, the average computation times of the SAA approach for sample sizes \(N = 10, 20,\ldots , 100\) and used each of these ten values as the time budget (termination criterion) for a corresponding run of the MH approach. For each problem instance structure, ten random instances were generated, and for each of these generated instances, ten optimization runs (with different seed values for the random number generator) were executed. This led to 100 solution values for MH and 100 solution values for SAA per time budget. The averages of these solution values for a special instance structure are depicted in Fig. 3. The solution values have been computed based on the determination of the exact objective function value of the solution (z, x) provided by the respective approach, i.e., the value \(E[G(z,x,\xi )]\). The reader will observe that Fig. 3 only contains 9 solution time values instead of 10, as one would expect. This is because sample sizes \(N=80\) and \(N=90\) led to identical solution times, cf. Fig. 2.

The results show that the solution quality of MH is less sensitive to the time budget than that of SAA. Applying a two-tailed sign test to the results of each of the ten different time budgets, we found that the MH results were significantly superior, at significance level \(\alpha =0.05\), for the smallest time budget 14 sec which was the time budget produced by sample size \(N=10\). For larger time budgets, the sign test could not confirm statistically significant superiority at level \(\alpha =0.05\) of either SAA over MH or vice versa. However, this lack of significance may be due to our small sample size of ten instances (in order to ensure independence, we had to take the average over the ten runs of each instance). Summarizing, in the considered instances structure, MH and SAA produce results of a comparable quality in the medium computation time range, with a slight but nonsignificant advantage for SAA. For small computation times, MH is superior.

Next, we compare SAA, applying sample size \(N=100\), to MH, using for both the same time limit of 360 s. Let \((z_{MH}^*,x_{MH}^*)\) and \((z_{SAA}^*,x_{SAA}^*)\) denote the optimal project schedule and staffing plan according to MH and SAA, respectively. To do the comparison, we compute the normalized differenceof the expected external costs. Averaging this measure over all test instances, we obtained a value of 0.1288, indicating that in the average, the SAA solutions are by \(12.88\%\) worse than the MH solutions. However, this result should be interpreted cautiously. The considerable difference can mainly be attributed to test instances where the expected external costs of the optimal solutions are almost zero. Such a situation easily occurs in instances where the number \(\vert S_k \vert \) of skills per resource is high. Investigating the same measure only for the basic instance structure, we find that there is no significant difference between the two solution methods.

Real-world project scheduling problems are often rather large. To investigate which effect an increasing size of the problem instance exerts on the comparison between MH and SAA, we generated test instances where both the number of projects and the number of resources were increased simultaneously as \(|P|=|K|=50,100,150,200,250\), and the parameter values \(\gamma =2\), \(|S_k|=2\) and \(\rho =1\) from Table 1 were used. For the SAA model, we applied CPLEX with default values and set the time limit to 10 h, which is an appropriate time budget for a tactical planning problem. We found that the solver could not provide a feasible integer solution for \(40\%\) of these instances; the share of solvable instances rapidly drops as |P| and |K| become larger than 150. However, even for the instances for which the SAA model can be feasibly solved, the SAA solution is in the average by \(45.57\%\) worse than the MH solution. Additionally, MH needs only a fraction of the SAA solution time to find a good solution.

We conclude that the developed matheuristic is a robust solution procedure that performs well for small and medium-sized test instances, and offers good solutions also where the SAA formulation fails to return a feasible solution. The main drawback of the SAA approach is its poor reliability with respect to the identification of a feasible solution and its volatile solution time. Nevertheless, for not too large instances, the SAA approach is a promising alternative to the application of a (partially) heuristics-based method, especially in cases where powerful hardware is available.

Is the advantage of treating the given project scheduling and staffing method as a stochastic optimization problem substantial enough to justify the increased computational effort, compared to a simplified, deterministic formulation? To shed light on this question, we deepen our experimental analysis in the following two subsections. In Sect. 4.5.1, the accuracy of using the solution value of the expected value problem as a forecast for budget planning is investigated, whereas in Sect. 4.5.2, the value of the stochastic solution is discussed.

In Fig. 5, we plot (i) the expected external costs and (ii) the relative expected external cost increments, both in dependence of different degrees of uncertainty, for the instances of the basic scenario structure. In this figure, the relative expected external cost increments indicate by which percentage the expected external costs increase if the situation \([c_{min},c_{max}]=[0.9,1.1]\) of low uncertainty is replaced by a higher uncertainty interval \([c_{min}, c_{max}]\) for the demand distributions. As one would anticipate, the expected external costs increase as uncertainty increases. A linear regression for the absolute value of the expected external cost shows that the coefficient of correlation is \(R=0.119\), with a p value of 0.017 (significance at level \(\alpha =0.05\)). Comparing the “almost deterministic” situation \([c_{min},c_{max}]=[0.9,1.1]\) to the situation \([c_{min},c_{max}]=[0.2,1.8]\) of poor information on demands, we find a gap of 12%. We would like to emphasize that a degree of uncertainty represented by \([c_{min},c_{max}]=[0.2,1.8]\) (i.e., a distribution allowing real efforts of work packages to exceed estimated efforts by up to 80%) is not extreme from a applied point of view: In areas as software engineering or in the construction industry, even higher overruns occur. Therefore, also the costs of uncertainty can be considerable in practice.

In Heimerl and Kolisch (2010), the authors investigate in a deterministic context how parameters as the number of projects, the time window size etc. influence the optimal costs. We shall extend now their results to the stochastic context of the present paper. In the present subsection, we use the ceteris paribus design explained in Sect. 4.1. That is, the parameters of the basic instance structure of Table 1 are applied, with the exception of modifying one single parameter among the parameters in Table 2.

Influence of the number of projects. First, we investigate the influence of increasing the number of projects on the resulting expected external costs. As Heimerl and Kolisch (2010), we keep the total resource demand constant while increasing the number of projects, which means that for a larger number of projects, the work packages become smaller. This change increases the flexibility of the planner, so one expects decreasing costs of the optimal solutions. This was confirmed indeed in Heimerl and Kolisch (2010) for the deterministic context. We obtained similar results in the stochastic context: In Fig. 6, we depict the expected external costs for four levels of uncertainty as a function of the number of projects (with fixed total demand). Additionally to the mean values, we plot the 95% confidence interval to account for the randomness in test instance generation. Apart from the already known effect that higher degree of uncertainty leads to higher external costs, one can see that all levels of uncertainty show the same behavior for an increasing number of projects: The conjecture that a larger number of smaller work packages is easier to balance across the planning horizon than bigger and fewer work packages is confirmed. Also as expected, we observe that from a certain value on, the potential of the flexibility achieved by reducing work packages sizes diminishes.

Influence of the time window size. In a similar way as it was done for the influence of the number of projects, we investigated also the influence of the time window size on the costs. The results showed that in our test instances, an additional degree of freedom, i.e., a time window size change from zero to one, led to cost savings of around 20%. A further cost reduction of up to 50% was achieved by increasing the time window size \(\gamma \) from 1 to 2. For time window sizes larger than two time periods, the costs did not decrease further.

Influence of the number of skills per resource. In Fig. 7, we plot the expected external costs in dependence of the number of skills per resource. Please note that the situation where the number of skills per resource is \(\vert S_k \vert =10\) represents a situation when all resources posses all skills. It can be observed that the external costs decrease monotonically with increasing \(|S_k|\). Two special findings may be particularly important. First, in the context of the considered set of instances (basic instance structure, with modifications only with respect to \(|S_k|\)), a situation where all employees are extremely specialized, i.e., possess only one skill per person, leads to about the double expected external costs in comparison with a situation where the employees have two skills per person. A further investment in training that causes an increase in the number skills per person from two to four leads to another significant decrease in the expected external costs. Secondly, from a value of about four skills per person on, the investment in additional skills achieves only very limited cost savings. Of course, the quantitative amount of cost reduction depends on the specific characteristics of the test instance set (especially on the chosen parameter value for utilization, here: \(\rho = 1\)). Nevertheless, the results suggest the managerial insight that (i) multi-skilled resources can lead to significant cost savings, but (ii) companies should be aware that over-qualification allows no return on investment.

Influence of the utilization factor. Finally, in Fig. 8, the expected external costs are visualized as a function of the utilization factor \(\rho \), the ratio of the expected demand to the available time capacities of the resources. As expected, Fig. 8 shows that the external costs increase as the utilization increases. In more detail, we find that when starting at 100% utilization, a 20% decrease in utilization leads to a 57% decrease in the expected external costs, whereas a 20% increase in the utilization leads to a rise of costs by 23%.

In the previous tests, we assumed that the triangular distribution of the variables \(D_{psq}\) was symmetric. In practice, distributions of work times are often right-skewed. Therefore, we checked whether or not substantially different results were obtained by a replacement of the symmetric distributions by right-skewed triangular distributions. For this purpose, we took the basic instance structure and changed it as follows: The modal value was defined as \(c_{mode}=c_{min}+(c_{max} - c_{min}) \cdot 0.25\), where \(c_{min}\) and \(c_{max}\) are the minimum and the maximum value of the distribution, respectively. For a series of four test instances, we fixed the expected value \(c_{expected}=( c_{min}+c_{max}+c_{mode})/3\) of the triangular distribution to 1. On this constraint, each of the four instances was constructed in such a way that the length \(c_{max} - c_{min}\) of the support interval of the distribution was gradually increased, taking the values 0.2, 0.6, 1.0 and 1.6, respectively, which corresponds to increasing uncertainty. Figure 9 shows a plot of the results. We see that the plot is very similar to Fig. 5. We conclude that the skewedness of the distribution has little impact on the outcomes.