On the summary measures for the resource-constrained project scheduling problem

The resource-constrained project scheduling problem is a widely studied problem in the literature. The goal is to construct a schedule for a set of activities, such that precedence and resource constraints are respected and that an objective function is optimized. In project scheduling literature, summary measures are often used as a tool to evaluate the performance of algorithms and to analyze instances and datasets. They can be classified in two groups, network measures describe the precedence constraints of a project, while resource measures focus on the resource constraints of the instance. In this manuscript we make an exhaustive evaluation of the summary measures for project scheduling. We provide an overview of the most prevalent measures and also introduce some new ones. For our tests we combine different datasets from the literature and generate a new set with diverse characteristics. We evaluate the performance of the summary measures on three dimensions: consistency, instance complexity and algorithm selection. We conclude by providing an overview of which measures are best suited for each of the three investigated dimensions.

• 14 July 2023

  A Correction to this paper has been published: https://doi.org/10.1007/s10479-023-05511-2

We acknowledge the support provided by the Special Research Fund (BOF grant no. DOC014-18 Van Eynde) and the National Bank of Belgium for providing the first author with a predoctoral fellowship. The computational resources (Stevin Supercomputer Infrastructure) and services used in this work were provided by the VSC (Flemish Supercomputer Center), funded by Ghent University, FWO and the Flemish Government - department EWI.

Authors and Affiliations

1. Faculty of Economics and Business Administration, Ghent University, Tweekerkenstraat 2, 9000, Ghent, Belgium

   Rob Van Eynde, Mario Vanhoucke & José Coelho

2. Faculty of Economics and Business, University of Barcelona, Diagonal 690, 08014, Barcelona, Spain

   Rob Van Eynde

3. Vlerick Business School, Reep 1, 9000, Ghent, Belgium

   Mario Vanhoucke

4. UCL School of Management, University College London, 1 Canada Square, London, E14 5AA, UK

   Mario Vanhoucke

5. Universidade Aberta, Rua da Escola Politécnica 147, Lisbon, 1269-001, Portugal

   José Coelho

6. INESC TEC, Campus da FEUP, Rua da Escola Politécnica 4200 - 465, Porto, Portugal

   José Coelho

Corresponding author

Correspondence to Mario Vanhoucke.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A: Calculation of measures

In this appendix we will illustrate all discussed measures on the example project of Fig. 6. It consists of 6 activities, the dummy activities and arcs are represented in dashed lines. Table 20 shows the additional information on the project and its activities.

An example project

Full size image

Table 21 shows the values for all the network and resource measures for the example. In the remainder of the appendix, these calculations will be explained.

The earliest start schedule for the example

Full size image

Active schedules for the example with unit durations

Full size image

1.1 A.1 Network measures

This subsection explains the calculations for all network measures. For the measures AD, SA, LA and TF we will not discuss the exact formulas as it would lead us too far, we refer to Vanhoucke et al. (2008) for the details. To explain the general idea behind them we require the definition of progressive level \(\hbox {PL}_i\) and regressive level \(\hbox {RL}_i\) of an activity i. The \(\hbox {PL}_i\) is the number of activities on the longest path from the dummy start to i. The \(\hbox {RL}_i\) equals the length m of the network minus the number of activities on the longest path from i to the dummy end.

• CNC: this measure takes the ratio of the number of non-dummy direct arcs and the number of non-dummy nodes, which amounts to \(\frac{3}{4}=0.75\).

• OS: sum all non-dummy direct and transitive arcs and divide it by the theoretical maximum number of arcs, i.e. \(n(n-1)/2\). For the example, the OS equals \(\frac{3}{(4\cdot 3)/2} = 0.5\).

• SP: calculate the length m of the longest path of non-dummy nodes in the network, in this network \(m=2\). Using the formula, \(\text {SP}=\frac{2-1}{4-1} = 0.33\).

• AD: this indicator measures how equally the activities are distributed over the progressive levels. Because each progressive level has 2 activities, they are equally distributed, so AD=0.

• SA: this indicator counts the number of short arcs in the network, a short arc being an arc (i,j) such that \(\hbox {PL}_i\) = \(\hbox {PL}_j\) - 1. In a network of 4 activities with 2 activities in the first progressive level, at least 2 short arcs have to be present. Furthermore, at most 4 short arcs can be present, i.e. by adding all arcs from activities 1 and 2 to 3 and 4. As there are 3 short arcs in this network, \(\text {SA} = \frac{3-2}{4-2} = 0.50\).

• LA: this measure counts the number of long arcs, where all arcs that are not short are considered long. As all arcs in the network are short, \(\text {LA} = 0\).

• TF: the TF indicator measures the float per activity i, the difference between its regressive and progressive level (\(\text {RL}_i - \text {PL}_i\)). As for each activity the progressive and regressive level are equal, it follows that \(\text {TF}=0\).

• LE: counts the number of linear extensions or precedence feasible activity lists. For the example network, there are 5 possible linear extensions: 1234, 1243, 2134, 2143 and 2413. Note that because 2 is a predecessor of 3, any linear extension where 3 occurs before 2 is not valid. The maximum number is \(n!=24\), so \(\text {LE} = \frac{\log _{10}(5)}{\log _{10}(24)} = 0.51\).

• W: looks at the size w of the maximum precedence feasible subset, which equals 2 in this network. Therefore, \(W=\frac{2-1}{4-1} = 0.33\).

• \(\text {OS}^3\): count \(\mathcal {S}^2\) and \(\mathcal {S}^3\), i.e. the precedence infeasible subsets of cardinality 2 and 3. Recall from the calculation of OS that \(|\mathcal {S}^2|=3\). As the width of the network is 2, all subsets of size 3 are precedence infeasible, so \(|\mathcal {S}^3|= {4\atopwithdelims (){3}} = 4\). Therefore \(\text {OS}^3 = \frac{3 + 4}{6+4} = 0.7\).

• \(\text {OS}^4\): the calculations are to \(\text {OS}^3\), but we also require \(|\mathcal {S}^4|\). As all subsets of size 3 are precedence infeasible, it follows that all subsets of size 4 will also be precedence infeasible, so \(|\mathcal {S}^4|={4\atopwithdelims (){4}} = 1\). It follows that \(\text {OS}^4 = \frac{3+4+1}{6+4+1} = 0.73\).

1.2 A.2 Resource measures

• RF: as there is one resource type and all acitivities require that resource, it follows that \(\text {RF}=1\)

• RU: the calculations are similar to those of RF. As each activity requires one resource type, \(\text {RU}=1\)

• RC: the average resource demand is calculated over all activities, recall that the availability for the resource type is 10. Therefore, \(\text {RC}=\frac{5+8+7+3}{4\cdot 10} = 0.58\).

• RS: looks at the resource unconstrained earliest start schedule, which is shown in Fig. 7. The peak demand \(r^{\max }_1\) is 13, while the minimum availability \(r^{\min }_1\) equals 8. With an availability \(a_k=10\), the RS equals \(\frac{10-8}{13-8}=0.4\).

• \(\text {FS}^2_1\): count the number of feasible subsets of size 2. For the example, these sets are \(\{1,4\}\) and \(\{3,4\}\). As there can at most be 6 feasible subset of size 2 for a network with \(n=4\), it follows that \(\text {FS}^2_1= \frac{2}{6} = 0.33\).

• \(\text {FS}^2_2\): the numerator remains the same as the previous measure, but the denominator changes. As there are 3 precedence feasible subsets of size 2 in the example, \(\text {FS}^2_2 = \frac{2}{3}=0.67\).

• \(\text {FS}^3_1\): now we also incorporate the subset of size 3. There exist no feasible subsets of size 3 in the example, while the theoretical maximum is \({4\atopwithdelims (){3}} = 4\). It follows that \(\text {FS}^3_1 = \frac{2+0}{6+4}=0.2\).

• \(\text {FS}^3_2\): has the same numerator as \(\text {FS}^3_1\), but the denominator changes to the number of precedence feasible subsets. As there exist no precedence feasible subsets of size 3 in the network, \(\text {FS}^3_2 = \frac{2+0}{3+0}=0.67\).

• FE: set all activity durations to 1 and count the number of active schedules for this special case. For the example, 2 active schedules exist, they are shown in Fig. 8. The maximum number of active schedules for a project of 4 activities equals \(n!=24\), so the FE is equal to \(\frac{\log _{10}(2)}{\log _{10}(24)} = 0.22\).

Appendix B: Summary measures of datasets

This appendix provides additional information for all summary measures for all datasets used in this paper. Table 22 shows the ranges of the values per summary measure per dataset. Table 23 exhibits the standard deviation for each of the measures per dataset. This provides an indication of how dispersed the instances are within the range.

Appendix C: Effect of size on CPU-time in DC1

Figures 9 and 10 respectively exhibit the interaction between network or resource measures with instance size and their combined effect on the CPU time. Each row corresponds with one summary measure, each column with a specific instance size.

Interaction effect of network measures and size on CPU for DC1

Full size image

Interaction effect of resource measures and size on CPU for DC1

Full size image

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions