Which statements correctly describe a time constrained and a resource constrained project schedule?

Introduction

The importance of scheduling and resource allocation problems in project management was recognized over five decades ago (see excellent reviews in Brucker et al. [2], Habibi et al. [11]). From the beginning of the 1960s until recently, researchers usually assumed trade-off functions between both the time and the cost and between the time and the resources (see, e.g., [20]) (see Fig. 1a) and later, also among the time, the cost and the quality [1, 18]. Two main versions of trade-off methods are specified. First, from the 1960s to the 1980s, continuous time–cost relationship problems were addressed extensively in the literature (see, e.g., [9, 17]). Researchers later investigated the discrete version of trade-off methods (see, e.g., [5, 7, 25]). Despite the ease of use, the main concern of the concept of continuous trade-off problems (CTP) is that it is usually hard to specify continuous trade-off functions between the time and the cost, the time and resources, or the cost and the quality. In real projects, decision makers instead choose from technologies (in addition to completion modes) (see Fig. 1b, c).

Moreover, this situation is better described by discrete trade-off problems (DTP) (see Fig. 1b). At the same time, CTP can be solved by fast polynomial algorithms (see, e.g., [10, 19]), while the discrete version of trade-off problems, with the exception of a few kinds of project networks [5] is an NP-hard problem [6]; therefore, the discrete version of time–quality–cost trade-off problems are also NP-hard problems [25]. To solve DTPs, heuristic and metaheuristic algorithms are usually applied [23, 26]. The recent multimode resource-constrained project scheduling problems (MRCPSP) (see an excellent review in Habibi et al. [11]), do not assume any trade-off functions between time and resources or between time and cost (see Fig. 1c). Trade-off methods are successfully used in construction projects [20]; in addition, the discrete version of trade-off methods and MRCPSPs are also successfully used in new product development projects [29] and investment projects [12], but they are difficult to use in software development projects and R&D projects where the project plans are more flexible. The main limitation of these concepts is that they both assume a fixed logic plan, such as a fixed set of tasks and a fixed sequence of completion. The proposed algorithm extends trade-off methods and MRCPSPs in order to handle flexible projects.

Fig. 1

Trade-off methods and multimode problems

Full size image

Previously, Wysocki found that in a [31] study of the practices of software project managers, only 20% of IT projects were managed by a traditional project management (TPM) methodology. Generally, methods for investment and construction projects cannot be directly applied to software development or R&D projects, as these are managed by agile project management (APM) approaches. Currently, hybrid (i.e., combinations of traditional and agile and extreme) approaches are becoming increasingly popular (see, e.g., [16]). However, flexible approaches are thus far not privileges for software development projects [3]. Rapidly changing environments increasingly enforce flexible approaches. Scheduling algorithms can support decision makers to manage projects; however, there are very few algorithmic methods that can support the flexible approaches. Therefore, it is important to study how to extend project scheduling methods to handle flexible and changing environments. Scheduling methods, as agents, can also imitate decision makers; therefore, not only the methods but also the scheduling and management approaches can be modeled (see Table 1).

Table 1 Comparison of the traditional and the flexible approaches

Full size table

While a project manager who follows a traditional project management (TPM) approach can use trade-off or multimode methods to reduce task duration, the agile and extreme project manager tries to restructure the project. If the project structure is flexible (see Table 1), the project duration can be reduced without increasing the project cost by reducing the number of flexible dependencies. However, in real project situations, decision makers can choose from different kinds of technologies; therefore, the TPM and APM approaches should be integrated. Agile approaches usually split the projects into smaller so-called sprints that are usually 2–6 weeks. The content of sprints is specified by the customer and the developers together. However, when running a sprint, unplanned new tasks and new requirements can be involved only until the next sprint.

The extreme project management (XPM) approach must handle the new tasks and new requirements during the implementation of the project. Application management, which can be considered as a combination of project management and process management from a scheduling point of view, also allows management to involve new and unforeseen tasks in the project plan. However, while extreme project management can confirm the extra costs and the increased project duration due to the extra tasks, application management instead emphasizes adhering to a fixed budget and fixed time-frame.Footnote 1

Flexible approaches require flexible project structures and flexible constraints; however, in addition to the opportunity of reorganizing the project, different kinds of technology (completion modes) should also be considered; therefore, traditional and flexible approaches should be combined into hybrid project management approaches (see, e.g., [16, 21, 27]). Nevertheless, hybrid approaches should be supported by algorithmic methods in order to help decision makers ensure the project’s success.

There are different combinations of agile and traditional project management approaches (see, e.g., [16, 21, 27]). However, to the best of our knowledge, there is no exact algorithm that can be used to solve hybrid multimode problems that can handle unplanned tasks and dependencies. Nevertheless, R&D and IT projects, such as introducing and setting up new information systems, may require reorganizing part of the project, and R&D projects may require handling unplanned tasks, particularly in the development phase. However, decreasing the time demands of mandatory tasks and those of the new unplanned tasks may also be an important requirement. Neither the agile nor the extreme approach can handle this situation properly; nor can the traditional approach. Traditional approaches, or network-based methods, assume static logic plans, but the reorganization of projects may produce insufficient reductions in project duration and/or supplementary tasks, and important tasks may excluded from the project due to budget constraints and/or project deadlines. A hybrid project management (HPM) approach can combine the traditional, agile and extreme approaches; however, these kinds of HPM approaches are not yet supported by project planning methods. The proposed algorithm combines the agile, extreme and traditional approaches. This method extends the traditional multimode resource-constrained project scheduling problem by allowing the restructuring and reorganizing of projects and handling unplanned new tasks.

The proposed hybrid time–cost and hybrid time–quality–cost trade-off models multimode methods manage flexible project plans and allow us to restructure or reorganize these project plans in order to satisfy customer and management claims. In contrast to the traditional project scoring and selection methods, there is no need to specify all project alternatives in order to select the most desirable project scenario or the one with the shortest duration or lowest cost.

To handle flexible project plans, matrix-based techniques will be used instead of traditional network-based project planning techniques. This method has already been successfully used to model agile projects [15]. The basis of the proposed matrix-based method is a project domain matrix (PDM) (see [15]) with unplanned tasks. The modified PDM is an \(n+u\) by \(m+u\) matrix, where n is the number of planned tasks; u is the number of unplanned tasks; \(m=n+t+c+q+r\); t is the number of possible durations; c is the number of possible (direct) costs; q is the number of possible quality parameters; and r is the number of possible resource demands of tasks. The PDM has five domains. The first domain is the logic domain (LD) that is described as an n by n project expert matrix (PEM) (see [14]) or numerical dependency structure matrix (NDSM) (see [24]).Footnote 2 Since the PEM has specified and semispecified versions, the PDM is specified if and only if the LD is specified; otherwise, the PDM is semispecified. The other domains are the time domain (TD), cost domain (CD), quality domain (QD) and resource domain (RD). If the demands are deterministic, we say that the PDM is deterministic; otherwise, the PDM is nondeterministic. In this study, the hybrid resource-constrained multimode project scheduling problems (HMRCPSP) are considered: the TD, CD, QD, and RD can contain deterministic values but must have at least two completion modes. Therefore, this version is a deterministic multimodal PDM. While the basis of the proposed model is the PDM, the basis of the proposed method is the expert project ranking (EPR) algorithm (see [15]), which can evaluate specified and semispecified deterministic PDMs. However, the EPR method cannot handle the resource-constrained multimode project scheduling problem, and the unplanned tasks and requirements. Therefore, while EPR can be used to schedule a flexible project plan and can thus be used in agile project management approaches, it cannot address multimodes and extra, unplanned tasks, and therefore cannot be directly used in extreme or hybrid project management.

This paper proposes a hybrid resource constrained multimode project scheduling problem by handling unplanned tasks to bridge APM, XPM and TPM and handle both the challenges of project and the application managements.

Solving hybrid multimode resource-constrained project scheduling problems

In this section, a resource-constrained hybrid multimode resource-constrained project scheduling problem (HMRCPSP) is first specified. Then, a matrix-based model representation will be proposed. At the end of this section, an exact algorithm is proposed for a hybrid multimode resource-constrained project scheduling problem. The decisions for finding the optimum will be directed by score functions and matrices (\(\mathbf {P},\mathbf {Q}\)) and time–quality–cost–resource functions, so we need several definitions and notations before proceeding.

Definitions and problem statements

Definition 1

We call any finite set \(A=\left\{ a_{1},\ldots ,a_{n}\right\} \) the set of possible activities or tasks in the project. The subset of supplementary tasks is \(\widetilde{A}=\left\{ \widetilde{a}_{1},\ldots ,\widetilde{a}_{\sigma }\right\} \subseteq A\), where \(\widetilde{A}\) is any fixed subset of A. Then, \(\overline{A}=A\setminus \widetilde{A}\) is the subset of mandatory tasks. Another subset is \(\hat{A}=\{\widehat{a}_{1},\ldots ,\widehat{a}_{p}\}\subseteqq A\) , the set of planned tasks, so \(\check{A}=A\setminus \hat{A}\) is the subset of unplanned tasks. Then, \(\overline{\hat{A}}=\hat{A}\cap \overline{A}\) is the set of planned mandatory tasks, \(\overline{\check{A}}=\check{A}\cap \overline{A}\) is the set of unplanned mandatory tasks, \(\widetilde{\hat{A}}=\hat{A}\cap \widetilde{A}\) is the set of planned supplementary tasks, and \(\widetilde{\check{A}}=\check{A} \cap \widetilde{A}\) is the set of unplanned supplementary tasks.

Clearly \(A=\overline{\hat{A}}\cup \overline{\check{A}}\cup \widetilde{\hat{A} }\cup \widetilde{\check{A}}\) is a disjoint union (a partition of A).

The mathematical model in Sect. 2 does not distinguish supplementary and planned tasks, similarly, not the mandatory and unplanned ones. This distinction will be interesting in the simulation Sect. 3.

Definition 2

The set of (project) scenarios is    \(\varXi \left( A\right) :=\left\{ S\subseteq A:\overline{A}\subseteq S\right\} \). When we consider a fixed element \(S\in \varXi \left( A\right) \), we call S a realized (project) scenario.

The traditional project management approach allows only mandatory tasks. There is no opportunity to remove tasks or exclude dependencies, while agile approaches prioritize tasks and can handle mandatory and supplementary tasks. While mandatory tasks must be realized, supplementary tasks can be omitted from the project. Decisions about supplementary task realization always have two options: include or exclude. When specifying project constraints, usually only the planned tasks are considered; however, the extreme project management approach allows new, unplanned tasks to be included in the projects. \( S\subseteqq A\) denotes the set of tasks that will be fulfilled by the algorithm. The number of possible project scenarios is \(2^{\sigma }\), where \(\sigma =\left| \widetilde{A}\right| \).

Definition 3

Any function \(P:A\rightarrow \left[ 0,1\right] \) is called a score function of task completion if \(P\left( a_{i}\right) =1\) for \(a_{i}\in \overline{A}\) and \(P\left( a_{i}\right) \in \left[ 0,1\right) \) for \(a_{i}\in \widetilde{A}\).

The function \(Q:A\rightarrow \left[ 0,1\right] \) is called a score function of task exclusion if \(Q\left( a_{i}\right) =0\) for \(a_{i}\in \overline{A}\) and \(Q\left( a_{i}\right) \in (0,1]\) for \(a_{i}\in \widetilde{A}\).

The task completion and exclusion scores can mean either probabilities or importance values.

Example 1

If every task completion score is a probability value, then \(Q=1-P\).

Definition 4

For any associative and monotoneFootnote 3 operation \(\otimes \) on \(\mathbb {R}^{+}\), we define the aggregation function   \(\otimes :\varXi \left( A\right) \rightarrow \mathbb {R}\) as

$$\begin{aligned} \otimes \left( S\right) :=\bigotimes \limits _{a\in S}P\left( a\right) ~\otimes ~\bigotimes \limits _{a\in A\setminus S}Q\left( a\right) , \end{aligned}$$

(1)

where \(\otimes \) indicates \(\varSigma \) or \(\varPi \) (addition or multiplication, respectively) or \(\vee \) or \(\wedge \) (maximum or minimum, respectively).

Example 2

If scores are probability values, then we have \(\otimes =\varPi \).

If scores indicate the importance of task completion, then \(\otimes =\varSigma \).

In phase one, we decide which tasks will be included in the project scenario by maximizing \(\otimes \left( S\right) \), fulfilling certain time, quality and cost requirements.

In phase two, we decide the order in which we will complete these tasks. This order is a relation of tasks, and our algorithm receives three kind of relations (dependencies) as inputs: no dependency, required and flexible. We have to resolve (i.e., decide) all flexible relations.

Definition 5

The relation triplet \(\left( \prec ,\thicksim ,\bowtie \right) \) is a relation representation of a hybrid project plan if for any \(i,j\le n\) and \(i\ne j\), we let

(i)\(a_{i}\prec a_{j}\) represent the strict or required dependencies between tasks \(a_{i}\) and \(a_{j}\), i.e., \(a_{j}\) may not be started unless activity \(a_{i}\) has been completed;

(ii)\(a_{i}\thicksim a_{j}\) represent no dependency between tasks \(a_{i}\) and \(a_{j}\), i.e., the starting time of \(a_{j}\) is not affected by \(a_{i}\); and

(iii)\(a_{i}\bowtie a_{j}\) represents flexible dependencies between tasks \(a_{i}\) and \(a_{j}\).

Remark 1

It is important to note that \(\prec \) is naturally a transitive, irreflexive and asymmetric relation, i.e. a strict partial ordering, which excludes circles like \(a_{1}\prec a_{2}\prec \cdots \prec a_{1}\). Therefore, by a standard topological ordering algorithm, we may assume that \(a_{i}\prec a_{j}\implies i<j\).

While strict dependencies \(a_{i}\prec a_{j}\) between tasks \(a_{i}\) and \(a_{j}\) must be realized (in a sequential way), and \(a_{i}\thicksim a_{j}\) indicates indifference (we may choose either sequential or parallel realization), flexible dependencies (\(\bowtie \)) must be resolved. In this case, we can decide whether these tasks will be completed in a sequential way, i.e., \(a_{i}\prec a_{j}\) will be declared, or in a parallel way, \(a_{i}\thicksim a_{j}\). When we decide that these tasks should be completed in either a sequential or a parallel way, we say that the flexible dependency is realized (or decided). Since for any i, j , \(i\ne j\)exactly one of \(a_{i}\prec a_{j}\) , \(a_{i}\succ a_{j}\) , \(a_{i}\sim a_{j}\) or \(a_{i}\bowtie a_{j}\) holds, and for \(i=j\) (“in the diagonal”), none of these four is valid; then, we have the following result:

Proposition 1

For any binary relations \(\prec ,\thicksim ,\bowtie \) on A, the triplet \(\left( \prec ,\thicksim ,\bowtie \right) \) is a relation representation of a hybrid project plan if and only if \(\left\{ \prec , \prec ^{-1} , \thicksim ,\bowtie \right\} \) is a partition of \(A\times A\setminus \iota \)   ( \(\prec ^{-1}\) is the reverse of \(\prec \) , i.e., \(\succ \), and \(\iota \) is the diagonal) and \(\prec \) is a strict partial ordering.

The easiest way to input and modify all data is by using a special \(n\times n\)matrix\(\mathbf {M}\), which we call a hybrid logic plan. (\(\mathbf {[M]}_{i,j}\) denotes the entry in row i and column j.)

Definition 6

The matrix representation of an input for a hybrid logic plan means any \(n\times n\) matrix with entries \(\emptyset ,X,?\), i.e., \(\mathbf {M}\in \left\{ X,\emptyset ,?\right\} ^{n\times n}\), assuming the following requirements:

(i) for any \(i\le n\),    \(\mathbf {[M]}_{i,i}=``X\)” for \(a_{i}\in \overline{A}\) and \(\mathbf {[M]}_{i,i}=``?\)” for \(a_{i}\in \widetilde{A}\); and

(ii) for any \(i,j\le n\), \(i\ne j\)   \(\mathbf {[M]}_{i,j}=``X\text {''}\iff a_{i}\prec a_{j}\),   \(\mathbf {[M]}_{i,j}=``\emptyset \text {''}\iff a_{i}\thicksim a_{j}\) and \(\mathbf {[M]}_{i,j}=``?\text {''}\iff a_{i}\bowtie a_{j}\).

In the diagonal, \(\mathbf {[M]}_{i,i}=``X\)”, “\(\emptyset \)”, “?” represents that the task \(a_{i}\) will be executed, will not be executed, or will be decided later, respectively. Similarly, \(\mathbf {[M]}_{i,j}=``?\)” for any \(i\ne j\) indicates flexible task dependency, which we have to decide in the algorithm.Footnote 4 The algorithm will change each \(``?''\) to either “X” or “\(\emptyset \)” in \(\mathbf {M}\) step-by-step in the diagonal in phase one, and in the off-diagonal in phase two. From Remark 1, we know that considering the entries X, \(\mathbf {M}\) is an upper triangular matrix both in the input and in all subsequent steps of the algorithm. In what follows, \(\mathbf {M}\) is any such matrix \(\mathbf {M}\in \left\{ X,\emptyset ,?\right\} ^{n\times n}\).

Proposition 2

For any realized project scenario \(S\subseteq A\), the diagonal of the matrix representation does not contain “?”: \(\mathbf {M}_{i,i}=``X\)” for \(a_{i}\in S\) and \(\mathbf {M}_{i,i}=``\emptyset \)” for \(a_{i}\in A\setminus S\). Further, \(\mathbf {M}\) does not contain “?” at all when all flexible dependencies are decided.

Since we plan to omit all tasks \(a\in A\setminus S\), we might also omit the rows and columns of \(\mathbf {M}\) not belonging to S. This might be important in computer runs (saving time and memory) and could be defined axiomatically. We leave these details to the readers.

Similar to Definition 3, we are given score values for each dependency.

Definition 7

Any two matrices\(\mathbf {P},\mathbf {Q}\in \left[ 0,1\right] ^{n\times n}\) are called score functions of the input matrix \(\mathbf {M}\) if

(i)   for every \(i\le n\), we have \(\mathbf {[P]}_{i,i}=P(a_{i})\) and \(\mathbf {[Q]}_{i,i}=Q(a_{i})\);Footnote 5

(ii)   for every \(i,j\le n\), \(i\ne j\) we have:

\(\mathbf {[M]}_{i,j}=``X\text {''}\iff \mathbf {[P]}_{i,j}=1\) and \(\mathbf {[Q]}_{i,j}=0\),

\(\mathbf {[M]}_{i,j}=``\emptyset \text {''}\iff \mathbf {[P]}_{i,j}=0\) and \(\mathbf {[Q]}_{i,j}=1\), and

\(\mathbf {[M]}_{i,j}=``?\text {''}\iff 0<\mathbf {[P]}_{i,j},\mathbf {[Q]}_{i,j}<1\).

Let us emphasize that (i) and (ii) above are requirements for the input matrix \(\mathbf {M}\). While the “?” entries in \(\mathbf {M}\) are changing during the algorithm run, \(\mathbf {P}\) and \(\mathbf {Q}\) remain unchanged.

The off-diagonal values of \(\mathbf {[P]}_{i,j}\) represent the score of realizing the task dependency between \(a_{i}\) and \(a_{j}\), while \(\mathbf {[Q]}_{i,j}\) represents the score of resolving the task dependency between \(a_{i}\) and \(a_{j}\).

From the diagonal of \(\mathbf {M}\), we can provide sharp bounds to \(\otimes \left( S\right) \) (see (1)) in each step of the algorithm.

Definition 8

For any \(\mathbf {M,N}\in \left\{ X,\emptyset ,?\right\} ^{n\times n}\), we say that

(i)\(\mathbf {N}\) is an in-/out-diagonal extension of \(\mathbf {M}\) if all the symbols “X” and “\(\emptyset \)” in \(\mathbf {M}\) remain unchanged in \(\mathbf {N}\), and some (possibly none) of the “?” inside/outside of the diagonal of \(\mathbf {M}\) are changed to “X” or “\(\emptyset \)”. In this case, \(\mathbf {M}\) is a restriction of \(\mathbf {N}\).

(ii) For \(i,j\le n\) and \(\mathbf {[M]}_{i,j}=``?\)”, we denote by \(\mathbf {M}\left[ i,j=X\right] \) and \(\mathbf {M}\left[ i,j=\emptyset \right] \) the matrices if only \(\mathbf {M}_{i,j}\) has been changed to either “X” or “\(\emptyset \)”.

(iii)\(\mathbf {N}\) is an in-/out- diagonal closure of \(\mathbf {M}\) if \(\mathbf {N}\) contains no “?s” in/out of the diagonal and \(\mathbf {N}\) in/out extends \(\mathbf {M}\).

When replacing a “?”, the algorithm makes newer extensions of the recent (or input) matrix, and our goals in phase one and phase two are suitable in- and out-closures of the input matrix, respectively. In-closures represent scenarios, while out-closures decide all flexible dependencies.

Definition 9

$$\begin{aligned} \otimes _{diag}\left( \mathbf {M}\right)&:&=\bigotimes \limits _{\mathbf {[M]}_{i,i}=X}P\left( a_{i}\right) ~\otimes ~\bigotimes \limits _{\mathbf {[M]}_{i,i}=\emptyset }Q\left( a_{i}\right) , \end{aligned}$$

(2)

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right)&:&=\otimes _{diag}\left( \mathbf {M}\right) ~\otimes ~\bigotimes \limits _{\mathbf {[M]}_{i,i}=?}\min \left\{ P\left( a_{i}\right) ,Q\left( a_{i}\right) \right\} , \end{aligned}$$

(3)

$$\begin{aligned} \otimes _{diag}^{\max }\left( \mathbf {M}\right)&:&=\otimes _{diag}\left( \mathbf {M}\right) ~\otimes ~\bigotimes \limits _{\mathbf {[M]}_{i,i}=?}\max \left\{ P\left( a_{i}\right) ,Q\left( a_{i}\right) \right\} . \end{aligned}$$

(4)

For some \(\otimes \) (e.g., multiplying probabilities), \(\otimes _{diag}^{\max }\left( \mathbf {M}\right) \) may be smaller than \(\otimes _{diag}\left( \mathbf {M}\right) \) (see also Definition 7). However, we have the following inequalities.

Theorem 1

For any \(\mathbf {M}\),

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right) \le \otimes _{diag}^{\max }\left( \mathbf {M}\right) . \end{aligned}$$

(5)

For any in-extension \(\mathbf {N}\) of \(\mathbf {M}\),

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right) \le \otimes _{diag}^{\min }\left( \mathbf {N}\right) \le \otimes _{diag}^{\max }\left( \mathbf {N}\right) \le \otimes _{diag}^{\max }\left( \mathbf {M}\right) , \end{aligned}$$

(6)

and for any \(i\le n\),

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right)= & {} \min \left\{ \otimes _{diag}^{\min }\left( \mathbf {M}\left[ i,i=X\right] \right) ~,~\otimes _{diag}^{\min }\left( \mathbf {M}\left[ i,i=\emptyset \right] \right) \right\} \text {,} \end{aligned}$$

(7)

$$\begin{aligned} \otimes _{diag}^{\max }\left( \mathbf {M}\right)= & {} \max \left\{ \otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=X\right] \right) ~,~\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=\emptyset \right] \right) \right\} . \end{aligned}$$

(8)

For any in-closure\(\mathbf {N}\) of \(\mathbf {M}\),

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {N}\right) =\otimes _{diag}\left( \mathbf {N}\right) =\otimes _{diag}^{\max }\left( \mathbf {N}\right) \end{aligned}$$

(9)

and

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right) \le \otimes _{diag}\left( \mathbf {N}\right) \le \otimes _{diag}^{\max }\left( \mathbf {M}\right) . \end{aligned}$$

(10)

For any \(\mathbf {M}\), there are \(\mathbf {N}_{1}\) and \(\mathbf {N}_{2}\) in-closures such that

$$\begin{aligned} \otimes _{diag}^{\min }\left( \mathbf {M}\right) =\otimes _{diag}\left( \mathbf {N}_{1}\right) \quad \text { and}\quad \otimes _{diag}\left( \mathbf {N} _{2}\right) =\otimes _{diag}^{\max }\left( \mathbf {M}\right) {.\quad } \Box \end{aligned}$$

(11)

Corollary 1

If \(\mathbf {M}\) contains no “?” in the diagonal, then for the represented scenario \(S\subseteq A\), we have

$$\begin{aligned} \otimes \left( S\right) =\otimes _{diag}\left( \mathbf {M}\right) . \end{aligned}$$

(12)

In phase three, we will have to decide how to handle the elements of A by choosing elements from the sets of modes called protocols.

Definition 10

(i)   Any finite set of quadruplets \(W=\{ \left( t_{i},q_{i},c_{i}, \mathbf {r}_{i}\right) :i=1,\ldots ,k\} \) , of positive real numbers and the vector \( \mathbf {r}_{i}=\{r_{i,1},..,r_{i,\rho }\} \) is called a discrete multimode protocol (DMMp). We write \(t_{\min }\) , \(t_{\max }\), \(q_{\min }\), \(q_{\max }\), \(c_{\min }\), \(c_{\max }\), \(r_{\min }\) and \(r_{\max }\) instead of \(\min _it_i\), \(\max _it_i\), \(\min _iq_i\),\(\max _iq_i\), \(\min _ic_i\),\(\max _ic_i\), \(\min _{i}\min _{j}r_{i,j}\) and \(\max _{i}\max _{j}r_{i,j}\) respectively.

If for each \(a\in A\) we are given a protocol \(W_{a}\) , then we call the set \(\mathcal {W}=\left\{ W_{a}:a\in A\right\} \) a discrete multimode problem (DMMP) on A.

(ii)   Any positive, continuous, strictly decreasing function   \(w:\left[ t_{\min },t_{\max }\right] \rightarrow \left[ q_{\min },q_{\max }\right] \times \left[ c_{\min },c_{\max }\right] \times \left[ r_{\min },r_{\max }\right] \)    is called a continuous multimode protocol (CMMp) with resource demands, where \(0<t_{\min }\), \(t_{\max },\)\(q_{\min },\)\(q_{\max },\)\(c_{\min },\)\(c_{\max },\)\(r_{\min },\) and \(r_{\max }\) are also assumed. If for each \(a\in A\), we are given a protocol \(w_{a}\). Then, we call the set \( \mathcal {W}=\left\{ w_{a}:a\in A\right\} \) a continuous multimode problem (CMMP).

We interpret \(\left( t,q,c,\mathbf {r}\right) \in W_{a}\) or \(w_{a}\left( t\right) =(q,c,\mathbf {r})\) as paying costc with qualityq and with resource\(\mathbf {r}\) to solve the element \(a\in A\) in timet using the mode assigned to \(\left( t,q,c,\mathbf {r}\right) \). For a parallel explanation of discrete and continuous problems, we write \(\left( t,q,c,\mathbf {r}\right) \in w_{a}\)in both cases. If ( \(t_{i}>t_{j}\Rightarrow c_i\le c_j, r_{i_1}\le r_{j_1},..,r_{i_{\rho }}\le r_{j_{\rho }}\)) and (\(c_k>c_l\Rightarrow q_k\le q_l\)) are satisfied for all \(i,j,k,l=1,..,n\), then a special case of multimode problems, namely, time–quality–resource–cost trade off problems are considered. The elements \(t_{\min }^{a}\), \(t_{\max }^{a}\), \(q_{\min }^{a}\), \(q_{\max }^{a}\), \(c_{\min }^{a}\), \(c_{\max }^{a}\), \( r_{\min }^{a}\) and \( r_{\max }^{a}\) may be different in different protocols \(w_{a}\) (\(W_{a}\)) for each \(a\in A\) in general. The cases \(t_{\min }=\)\(t_{\max }\), \(q_{\min }=\)\(q_{\max }\), \(c_{\min }=\)\(c_{\max }\) or \(r_{\min } = r_{\max }\) are also allowed.

The final goal of our algorithm is an optimal project schedule.

Definition 11

Let \(S\in \varXi \left( A\right) \) be any realized project scenario; \(\mathcal {W}\) is either a CMMP or a DMMP. A project schedule is a set

$$\begin{aligned} \overrightarrow{w}=\left\{ \left( t^{a},q^{a},c^{a},\mathbf {r}^{a}\right) :a\in S\right\} , \end{aligned}$$

(13)

where \(\left( t^{a},q^{a},c^{a},\mathbf {r}^{a}\right) \in w_{a}\) for \(a\in S\).

We are now ready to provide upper and lower bounds for time and cost in each stage (in any phase) of the algorithm, that is, for any matrix \(\mathbf {M}\in \left\{ X,\emptyset ,?\right\} ^{n\times n}\).

Definition 12

(i) For any \(\mathbf {M}\) and \(\mathcal {W}\) DMMP or CMMP, the minimal cost bound is

$$\begin{aligned} C_{\min }\left( \mathbf {M},\mathcal {W}\right) :=\sum _{\mathbf {[M]}_{i,i}=``X\text {''}}c_{\min }^{a}. \end{aligned}$$

(14)

(ii) For any project schedule \(\overrightarrow{w}\) the total project cost of \(\overrightarrow{w}\) is

$$\begin{aligned} \mathbf {c}\left( \overrightarrow{w}\right) :=\sum _{\left( t^{a},q^{a},c^{a},\mathbf {r}^{a}\right) \in w_{a}{~,~}a\in S}c^{a}. \end{aligned}$$

(15)

To quantify project quality, both quality parameters and the task completion scores (\(\mathbf {[P]}_{i,i}\)) are considered.

Definition 13

(i) For any \(\mathbf {M}\) and \(\mathcal {W}\) DMMP or CMMP, the maximal (relative) quality bound is

$$\begin{aligned} Q_{\max }\left( \mathbf {M},\mathcal {W}\right) :=1 . \end{aligned}$$

(16)

(ii) For any project schedule \(\overrightarrow{w}\), the total project quality of \(\overrightarrow{w}\) is

$$\begin{aligned} \mathbf {q}\left( \overrightarrow{w}\right) := \frac{\sum \nolimits _{\left( t^{a},q^{a},c^{a},\mathbf {r}^{a}\right) \in w_{a}{~,~}a\in S}q^{a}}{\sum \nolimits _{a\in A}q_{\max }^{a}}. \end{aligned}$$

(17)

For time bounds, we must not forget the \(\prec \) dependencies.

Definition 14

(i) For any realpath

$$\begin{aligned} \overrightarrow{P}=~``a_{i_{1}}\prec a_{i_{2}}\prec ~\cdots \prec a_{i_{k}}\text {''} \end{aligned}$$

(18)

(\(\mathbf {M}_{i_{j},i_{j+1}}=``X\text {''}\) for \(1\le j<k\)),   the minimal time bound of the path is

$$\begin{aligned} T_{\min }\left( \overrightarrow{P},\mathcal {W}\right) :=\sum _{a\in \overrightarrow{P}}t_{\min }^{a}. \end{aligned}$$

(19)

(ii) \(\overrightarrow{P}\) is the longest minimum path of \( \mathbf {M}\) if \(T_{\min }\left( \overrightarrow{P},\mathcal {W}\right) \) is maximal, assuming that \(\overrightarrow{P}\) contains mandatory tasks only (i.e., assuming \(\mathbf {M}_{i,i}=``X\text {''}\) whenever \(a_{i}\in \overrightarrow{P}\)).

We denote this maximum by

$$\begin{aligned} T_{\min }\left( \mathbf {M},\mathcal {W}\right) :=\max _{P}~T_{\min }\left( \overrightarrow{P},\mathcal {W}\right) . \end{aligned}$$

(20)

Thus, \(\overrightarrow{P}\) is called a critical path, and \( \left\{ a_{i_{1}},a_{i_{2}},\ldots ,a_{i_{k}}\right\} \) is the set of critical activities.

(iii) For any project schedule \(\overrightarrow{w}\), the total project time of \(\overrightarrow{w}\) is

$$\begin{aligned} \mathbf {t}\left( \overrightarrow{w}\right) :=\sum _{\left( t^{a},q^{a},c^{a},\mathbf {r}^{a}\right) \in w_{a}{~,~}a\in \overrightarrow{P}}t^{a}, \end{aligned}$$

(21)

where \(\overrightarrow{P}\) is any longest minimum path.

The length and definition of the longest minimum path do not depend on the project schedule \(\overrightarrow{w}\) since \(t_{min}^{a}\) are summed in Eq. 21. Critical paths are in fact longest minimum paths. Clearly, \(t(\overrightarrow{w})\ge T_{min}(\mathbf {M},\mathcal {W})\) for any \(\mathcal {W}\) and \(\overrightarrow{w}\).

A longest minimum path in any \(\mathbf {M}\) can be found by a standard algorithm within \(O(n+d)\), where n is the number of tasks, and d is the number of dependencies.

Definition 15

Denote \(A(\overrightarrow{w},t)\subseteq A\) the set of running activities in time t for the schedule \(\overrightarrow{w}\). The maximal resource demands for resource k are:

$$\begin{aligned} r_{k}(\overrightarrow{w}):=\max _{t} \sum _{a_{i}\in A(\overrightarrow{w},t)}r_{i,k}, \qquad ~ (k:=1,..,\rho ) \end{aligned}$$

(22)

and the total resource vector is

$$\begin{aligned} \mathbf {r}\left( \overrightarrow{w}\right) :=\left( r_{1}\left( \overrightarrow{w}\right) ,\ldots ,r_{\rho }\left( \overrightarrow{w}\right) \right) . \end{aligned}$$

(23)

Theorem 2

For any \(\mathbf {M}\) and for any in- or out-closure\(\mathbf {N} \) of \(\mathbf {M}\),

$$\begin{aligned}&C_{\min }\left( \mathbf {M},\mathcal {W}\right) \le C_{\min }\left( \mathbf {N} ,\mathcal {W}\right) , \end{aligned}$$

(24)

$$\begin{aligned}&Q_{\max }\left( \mathbf {M},\mathcal {W}\right) \ge Q_{\max }\left( \mathbf {N} ,\mathcal {W}\right) \end{aligned}$$

(25)

and

$$\begin{aligned} T_{\min }\left( \mathbf {M},\mathcal {W}\right) \le T_{\min }\left( \mathbf {N} ,\mathcal {W}\right) . \end{aligned}$$

(26)

Further, for any project schedule \(\overrightarrow{w}\) (for the scenario S , determined by the diagonal of \(\mathbf {N}\))

$$\begin{aligned}&C_{\min }\left( \mathbf {N},\mathcal {W}\right) \le \mathbf {c}\left( \overrightarrow{w}\right) , \end{aligned}$$

(27)

$$\begin{aligned}&Q_{\max }\left( \mathbf {N},\mathcal {W}\right) \ge \mathbf {q}\left( \overrightarrow{w}\right) \end{aligned}$$

(28)

and

$$\begin{aligned} T_{\min }\left( \mathbf {N},\mathcal {W}\right) \le \mathbf {t}\left( \overrightarrow{w}\right) . \end{aligned}$$

(29)

For \(\mathbf {M}\in \left\{ X,\emptyset \right\} ^{n\times n}\) and \( \overrightarrow{w}\), we also use the following notations for total project quality, cost, time and resource demand:

$$\begin{aligned}&TPC\left( \mathbf {M,}\overrightarrow{w}\right) :=\mathbf {c}\left( \overrightarrow{w}\right) , \end{aligned}$$

(30)

$$\begin{aligned}&TPQ\left( \mathbf {M,}\overrightarrow{w}\right) :=\mathbf {q}\left( \overrightarrow{w}\right) \end{aligned}$$

(31)

and

$$\begin{aligned} TPT\left( \mathbf {M,}\overrightarrow{w}\right) :=\mathbf {t}\left( \overrightarrow{w}\right) \end{aligned}$$

(32)

and

$$\begin{aligned} \mathbf {TPR}\left( \mathbf {M,}\overrightarrow{w}\right) :=[r_{1}(\overrightarrow{w})~,..,r_{\rho }(\overrightarrow{w})]^{T}. \end{aligned}$$

(33)

Definition 16

A project structure or net means a deterministic logic plan, i.e., every flexible relation is realized. The triplet \(\mathcal {X}=(S,\prec ,\thicksim )\) represents the project structure of a given scenario \(S\subseteq A\).

The matrix representation of a project structure contains no “?” symbols at all.

In phase two, we have to address the score values of the dependencies on A using the off-diagonal elements of P and Q (see Definition 7).

Definition 17

For any associative operation \(\otimes \) on \(\mathbb {R}\), we define the aggregation function for project structures as

$$\begin{aligned} \otimes _{nd}\left( \mathbf {M}\right) :=\bigotimes \limits _{\mathbf {M} _{i,j}=``X\text {''}~,~i\ne j}\mathbf {P}_{i,j}~\otimes ~\bigotimes \limits _{_{_{ \mathbf {M}_{i,j}=``\emptyset \text {''}~,~i\ne j}}}\mathbf {Q}_{i,j} \end{aligned}$$

(34)

and its extreme values

$$\begin{aligned} \otimes _{nd}^{\min }\left( \mathbf {M}\right)&:&=\otimes _{nd}\left( \mathbf {M}\right) ~\otimes ~\bigotimes \limits _{\mathbf {M}_{i,j}=?,i\ne j}\min \left\{ \mathbf {P}_{i,j},\mathbf {Q}_{i,j}\right\} , \end{aligned}$$

(35)

$$\begin{aligned} \otimes _{nd}^{\max }\left( \mathbf {M}\right)&:&=\otimes _{nd}\left( \mathbf {M}\right) ~\otimes ~\bigotimes \limits _{\mathbf {M}_{i,j}=?,i\ne j}\max \left\{ \mathbf {P}_{i,j},\mathbf {Q}_{i,j}\right\} . \end{aligned}$$

(36)

If \(\mathbf {M}\) is the matrix representation of a realized project structure, \(\otimes _{nd}\left( \mathbf {M}\right) \) gives the score value of this project structure.Footnote 6

Calculating constraints

In all versions of the multimode functions, the maximal/minimal time, quality and cost demands can be determined for all activities. In this way, the maximal/minimal total project time (TPT), total project quality and maximal/minimal total project cost (TPC) can be determined. This feature will be used when calculating the maximal and minimal demands for a project scenario and the maximal/minimal duration of a project structure. In the case of resource-constrained HMRCPSP problems, activities can be supplementary, and the dependencies can be flexible. Unplanned tasks and dependencies can modify the project plan. If we exclude a task from the project, we also exclude the time/quality and cost/resource demands of this activity.

Minimal value of total project cost (\(\hbox {TPC}_{\min }\)) occurs if only mandatory tasks are included in the project with the minimal possible cost.

Maximal value of total project cost (\(\hbox {TPC}_{\max }\)) occurs if all the mandatory and supplementary tasks are included in the project with the maximal possible cost.

Minimal value of total project quality (\(\hbox {TPQ}_{\min }\)) occurs if only mandatory tasks are included in the project with the minimal possible quality parameter.

Maximal value of total project quality (\(\hbox {TPQ}_{\max }\)) occurs if all the mandatory and supplementary tasks are included in the project with the maximal possible quality parameter.

Minimal value of total project resources (\(\mathbf {TPR}_{\min }\)) occurs if only mandatory tasks are included in the project with minimal possible resource demands.

Maximal value of total project resources (\(\mathbf {TPR}_{\max }\)) occurs if all the mandatory and supplementary tasks are included in the project with maximal resource demands.

Minimal value of total project time (\(\hbox {TPT}_{\min }\)) occurs, if only mandatory tasks and fixed dependencies are included to the project, with minimal possible duration.

Maximal value of total project cost (\(\hbox {TPT}_{\max }\)) occurs if all the mandatory and supplementary tasks and all the flexible and fixed dependencies are included in the project with the maximal possible duration.

Minimal value of total project score (\(\hbox {TPS}_{\min }\)) occurs if all the mandatory and supplementary tasks are included, where the score of exclusion is higher than the score of inclusion.

Maximal value of total project score (\(\hbox {TPS}_{\min }\)) occurs if all the mandatory and supplementary tasks are included, where the score of inclusion is higher than the score of exclusion.

Minimal value of dependency scores occurs if all the fixed and flexible dependencies are included, where the score of exclusion is higher than the score of inclusion.

Maximal value of dependency scores occurs if all the fixed and flexible dependencies are included, where the score of inclusion is higher than the score of exclusion.

Instead, phases 1 through 3 are directed by (37)–(56), where the constants \(C_{c}\), \(C_{t}\), \(C_{q}\), \(\mathbf {C_{r}}\), \(C_{diag}\) and \(C_{nd}\) might be varied upon request; however, we assume that \(C_t\in [\text {TPT}_{\min },\text {TPT}_{\max }]\), \(C_c\in [\text {TPC}_{\min },\text {TPC}_{\max }]\), \(C_q\in [\text {TPQ}_{\min },\text {TPQ}_{\max }]\), \(\mathbf {C_r}\in [\mathbf {TPR}_{\min },\mathbf {TPR}_{\max }]\), \(C_{diag}\in [\otimes ^{\min }_{diag},\otimes ^{\max }_{diag}]\), \(C_{nd}\in [\otimes ^{\min }_{nd},\otimes ^{\max }_{nd}]\).

Possible target function

If all constraints are specified, we are ready to specify target functions in all phases of the algorithm. These targets can be different in all phases. We specified several possible target functions, but other target functions can be specified for other applications

Maximize score values in order to select the most desired project plan.

Minimize project duration.

Minimize project cost.

Minimize project quality.

We are now ready to define the problems we will solve in phases one, two and three.

Hybrid multimode resource-constrained project scheduling problem

In this problem, we try to select the most desired project plans with minimal project duration, while keeping all the time/cost/resource/quality constraints.

Problem 1

phase one: Let A be a finite set of activities and \( \mathbf {M}\) be a matrix representation of A. Let \( C_{c}, C_{t}, C_{diag}\in \mathbb {R}^{+}\) be given such that \(C_{\min }\left( \mathbf {M},\mathcal {W}\right) \le C_{c}\), \(T_{\min }\left( \mathbf {M}, \mathcal {W}\right) \le C_{t}\) and \(C_{diag}\le \otimes _{diag}^{\max }\left( \mathbf {M}\right) \). Now, find a scenario\(S\subseteq A\), i.e., an in-closure\(\mathbf {M}^{\prime }\) of \(\mathbf {M}\) such that

$$\begin{aligned} \otimes _{diag}\left( \mathbf {M}^{\prime }\right) \rightarrow \max \end{aligned}$$

(37)

assuming

$$\begin{aligned} C_{\min }\left( \mathbf {M}^{\prime },\mathcal {W}\right)\le & {} C_{c}, \end{aligned}$$

(38)

$$\begin{aligned} T_{\min }\left( \mathbf {M}^{\prime },\mathcal {W}\right)\le & {} C_{t}, \end{aligned}$$

(39)

$$\begin{aligned} \otimes _{diag}\left( \mathbf {M}^{\prime }\right)\ge & {} C_{diag}\text {,} \end{aligned}$$

(40)

$$\begin{aligned} Q_{max}\left( \mathbf {M}^{\prime },\mathcal {W}\right)\ge & {} C_{q}. \end{aligned}$$

(41)

The role of (40) is to stop the algorithm from searching for the maximum in (37) when (40), together with (38), (39) and (41), cannot be achieved.

Problem 2

phase two: Let \(\mathbf {M}^{\prime }\) be a solution to Problem 1 phase one, i.e., a matrix representation of a project scenario \(S\subseteq A\). Let \(C_{t}, C_{nd}\in \mathbb {R} ^{+} \) be given such that \(T_{\min }\left( \mathbf {M}^{\prime },\mathcal {W} \right) \le C_{t}\) and \(C_{nd}\le \otimes _{nd}^{\max }\left( \mathbf {M}^{\prime } \right) \). Now, find a structure, i.e., an off-closure\(\mathbf { M''}\) of \(\mathbf {M}^{\prime }\) such that

$$\begin{aligned} \otimes _{nd}(\mathbf {M''})\rightarrow \max \end{aligned}$$

(42)

assuming

$$\begin{aligned} T_{\min }\left( \mathbf {M''},\mathcal {W}\right)\le & {} C_{t}, \end{aligned}$$

(43)

$$\begin{aligned} \otimes _{nd}\left( \mathbf {M}''\right)\ge & {} C_{nd}. \end{aligned}$$

(44)

The role of (44) is to stop the algorithm from searching for the maximum in (42) when (44), together with (43), cannot be achieved.

After phase two, we are faced with a traditional time–cost trade-off problem; therefore, in phase three, we can specify different kinds of objective functions in Problem 3: phase three/1 and /2.

Problem 3

phase three: Let \(\mathbf {M}\) be a solution to Problem 1 phase two, i.e., a matrix representation of a given project structure \(\mathcal {X}=(S,\prec ,\thicksim )\). Let \(C_{c}, C_{t}\in \mathbb {R}^{+}\) be given such that \(C_{\min }\left( \mathbf {M''}, \mathcal {W}\right) \le C_{c}\) and \(T_{\min }\left( \mathbf {M''},\mathcal {W} \right) \le C_{t}\). Further, let \(\mathbf {C}_{r}\) be any nonnegativeFootnote 7 vector of dimension \(\rho \) such that \(\mathbf {C_r}\in [\mathbf {TPR}_{\min },\mathbf {TPR}_{\max }]\).

Problem 3 phase three/1) Find a project schedule \(\overrightarrow{w}\) such that

$$\begin{aligned} \mathbf {t}\left( \overrightarrow{w}\right) \rightarrow \min \end{aligned}$$

(45)

assuming

$$\begin{aligned} \mathbf {c}\left( \overrightarrow{w}\right)\le & {} C_{c},\end{aligned}$$

(46)

$$\begin{aligned} \mathbf {q}\left( \overrightarrow{w}\right)\ge & {} C_{q},\end{aligned}$$

(47)

$$\begin{aligned} \mathbf {r}\left( \overrightarrow{w}\right)\le & {} \mathbf {C_{r}}. \end{aligned}$$

(48)

Problem 3 phase three/2) Find a project schedule \( \overrightarrow{w}\) such that

$$\begin{aligned} \mathbf {c}\left( \overrightarrow{w}\right) \rightarrow \min \end{aligned}$$

(49)

assuming

$$\begin{aligned} \mathbf {t}\left( \overrightarrow{w}\right)\le & {} C_{t},\end{aligned}$$

(50)

$$\begin{aligned} \mathbf {q}\left( \overrightarrow{w}\right)\ge & {} C_{q},\end{aligned}$$

(51)

$$\begin{aligned} \mathbf {r}\left( \overrightarrow{w}\right)\le & {} \mathbf {C_{r}}. \end{aligned}$$

(52)

Problem 3 phase three/3) Find a project schedule \( \overrightarrow{w}\) such that

$$\begin{aligned} \mathbf {q}\left( \overrightarrow{w}\right) \rightarrow \max \end{aligned}$$

(53)

assuming

$$\begin{aligned} \mathbf {t}\left( \overrightarrow{w}\right)\le & {} C_{t}, \end{aligned}$$

(54)

$$\begin{aligned} \mathbf {q}\left( \overrightarrow{w}\right)\ge & {} C_{q},\end{aligned}$$

(55)

$$\begin{aligned} \mathbf {r}\left( \overrightarrow{w}\right)\le & {} \mathbf {C_{r}}. \end{aligned}$$

(56)

Note that the requirements for all the constants in each phase ensure that this phase has at least one solution and that this matrix can be handled in the next phase.

Modeling flexible project plans

Although the proposed model can be used for both discrete and continuous versions of multimode resource-constrained project scheduling problems, in simulations, we addressed both continuous and discrete versions of MRCPSP. For practical reasons, we use a specific, deterministic, multimodal project domain matrix (PDM) to model the resource-constrained hybrid multimode resource allocation problem. The PDM is an n by m matrix (see, e.g., Table 2), where \(n=\left| A\right| \) is the number of tasks, \(\rho \) is the number of resources, \( m=n+(3+\rho )\omega \) and \(\omega = \left| W \right| \) is the number of modes [15]. The PDM has five domains: the logic domain (LD), time domain (TD), quality domain (QD), cost domain (CD) and resource domain (RD) (see Table 2). In the initial step, \(\mathbf {LD:=P}\), where \(\mathbf {P\in }[0,1]^{n\times n}\) is the score matrix. The diagonal \(\mathbf {[PDM]}_{i,i}=\mathbf {[LD]}_{i,i}=\mathbf {[P]}_{i,i}\) represents the task completion scores, and those out of the diagonal \(\mathbf {PDM}_{i,j}=\mathbf {LD}_{i,j}=\mathbf {P}_{i,j}\)\(\left( i\ne j\right) \) represent the task dependency scores between task \(a_{i}\) and task \(a_{j}\). Empty cells represent the unplanned tasks and their unknown requirements. While specifying constraints, the demands of unplanned tasks are not specified. In the simulation, two contract strategies are compared, the agile strategy, which schedules unplanned task to the next sprint, but the constraints are assumed to be fixed, and the extreme strategy, which involves new tasks with their demands and modifies the constraints considering the unplanned task demands.

TD, QD and CD contain of the corresponding data of multicompletion modes \(\overrightarrow{w_{i}}\in W\) (\(i\le \omega \)) as columns, (minimum, maximum) values while the resource domain (RD) is built up similarly for each resource (the columns are for \(r_{i,j}\) for \(i\le \omega \), \(j\le \rho \), see Table 2).

Kosztyáan [15] shows how to handle and resolve cycles in a PDM. Therefore, without loss of generality, we can assume that there is no cycle in the project net. In other words, the LD of the PDM can be rearranged as an upper triangular matrix.

Table 2 Project Domain Matrix for planned mandatory and supplementary tasks (a) and considering unplanned tasks (b)

Full size table

Example 3

Table 2 shows an example of a project plan. Table 2(a) shows the original project plan, where the PDM is already ready to mark new/unplanned tasks. As shown in Table 1, two contract strategies can handle the unplanned tasks. Following application management (AM), the original constraints are kept, and tasks can be completed provided all demands are not greater than the constraints. Extreme project management modifies the constraint to involve the unplanned tasks (see the last two rows in Table 2), whereas if handling unplanned tasks and dependencies are not allowed, then only task B is the mandatory task. Therefore, \(\hbox {TPT}_{\min }=1\), \(\hbox {TPC}_{\min }=2\), TPR\(_{\min }=[2,1]^T\) can be specified without calculating all possible scenarios. According to Eq. (17), \(\hbox {TPQ}_{\max }=1\), \(\hbox {TPQ}_{\min }=0.8/(4 \times 0.9)=0.22\), while if the unplanned task E is also considered, than minimal values of the total project cost are \(\hbox {TPC}_{\min }= 2\) and \(\hbox {TPQ}_{\min }=(0.8 + 1.0) / (4 \times 0.9 + 1.0) = 0.39\). The minimal duration \(\hbox {TPT}_{\min }=1\) and resource demands TPR\(_{\min }=[2,1]^T\) are not changed. Therefore, if the extra costs/duration/resource demands of the unplanned task can be accepted and the constraint can be modified, it may be beneficial for project scheduling.

The algorithms

Phase one

We are given the matrix \(\mathbf {M}_{0}\in \left\{ X,\emptyset ,?\right\} ^{n\times n}\). Suppose that all the “?” symbols in the diagonal are in the first \(\sigma \) rows (columns). The algorithm sequentially changes these symbols to either “X” or “\(\varnothing \)” in this order; such a change is called a step. These changes are not final, and the original matrix \(\mathbf {M}_{0}\) is also saved. We look for the optimum similar to a “back-and-forth” method, saving information in the bufferB (a set) of possible ways that we might investigate later. After replacing as many elements of \(\mathbf {M}\) as we can (satisfying Eqs. (38), (39), and (41)), we go back to the cases in which B has higher scores \(\otimes _{diag}\) than \(\mathbf {M}\) has. (All the possible variations of \(\mathbf {M}_{0}\) form a binary tree of size \(2^{\sigma }\) with root \(\mathbf {M}_{0}\).)

Here, \(\mathbf {M}\) denotes the actual matrix before the next replacement, so \(\mathbf {[M]}_{j,j}=``?\text {''}\iff i\le j\le \sigma \) for some \(1\le i\le \sigma \), and denote by \(\mathbf {M}\left[ i,i=Y\right] \) the matrix after replacing \(\mathbf {M}_{i,i}\) with Y, where \(Y\in \left\{ X,\emptyset \right\} \).

Before replacing \(\mathbf {[M]}_{i,i}\), we save the other possibility, which we do not follow in the present step, in B. The elements of B are of the form

$$\begin{aligned} \mathbf {b}= & {} \left( i,~\mathbf {[M]}_{1..n,1..n}~,~Y,~\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=Y\right] \right) \right) \end{aligned}$$

(57)

$$\begin{aligned}= & {} \left( i,\overrightarrow{m},Y,\otimes _{\mathbf {b}}\right) , \end{aligned}$$

(58)

where i denotes the element in the diagonal of \(\mathbf {M}\) we are replacing, \(\overrightarrow{m}=\mathbf {M}_{1..n,1..n}\) is the actual content of the diagonal of \(\mathbf {M}\) (specifically, \(\mathbf {M}_{i,i}=``?\text {''}\)), \(Y\in \left\{ X,\emptyset \right\} \) and \(\otimes _{b}=\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=Y\right] \right) \) is the“ideal” score we may achieve by replacing \(\mathbf {M}_{i,i}\) with Y.Footnote 8B may contain several elements with the same \(\otimes _{\mathbf {b}}\) value, but at this moment, we do not know which value can be realized later, i.e., satisfy (38)–(41)

Remark 2

B contains only \(\mathbf {M}\left[ i,i=Y\right] \) extensions that have not yet been investigated but fulfill the bounds of (38)–(41). More precisely, for their extension,

$$\begin{aligned} C_{\min }\left( \mathbf {M}\left[ i,i=Y\right] ,\mathcal {W}\right)\le & {} C_{c}, \end{aligned}$$

(59)

$$\begin{aligned} T_{\min }\left( \mathbf {M}\left[ i,i=Y\right] ,\mathcal {W}\right)\le & {} C_{t}, \end{aligned}$$

(60)

$$\begin{aligned} Q_{\max }\left( \mathbf {M}\left[ i,i=Y\right] ,\mathcal {W}\right)\ge & {} C_{q}, \end{aligned}$$

(61)

$$\begin{aligned} \otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=Y\right] \right)\ge & {} C_{diag}. \end{aligned}$$

(62)

Remark 3

Before starting step i for \(1<i\), at the end of step \(i-1\), we have inserted Y into the \(i-1\)-th entry of \(\mathbf {M}\). Since we are now extending this configuration, B does not contain the corresponding record \(\mathbf {b}=\left( i-1,\overrightarrow{m} ,Y,\otimes _{\mathbf {b}}\right) \).

The algorithm starts a new cycle whenever it goes back to an element of B and starts to replace “?” from the \(i=i_{0}+1\)-th entry of the diagonal. Problem 1 may have a solution if, for at least in one cycle, we are able to step i to \(\sigma \) (satisfying (38)–(41)). Of course, we store all the in-closures \( \mathbf {M}^{\prime }\) of \(\mathbf {M}_{0}\) that were found by the algorithm and may be optimal solutions to Problem 1. If B contains an element \(\mathbf {b}\) with a higher score than \(\mathbf {M} ^{\prime }\) has (i.e., \(\otimes _{\mathbf {b}}>\otimes _{diag}\left( \mathbf {M} ^{\prime }\right) \)), then we start a new cycle from \(\mathbf {b}\). During this cycle, i cannot be increased to \(\sigma \), \(\otimes _{b}=\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=Y\right] \right) \) may fall below \(\otimes _{diag}\left( \mathbf {M}\right) \), or we might obtain a solution better than \(\mathbf {M}^{\prime }\).

START   Let \(i_{0}:=0\), \(i=1\), \(B:=\emptyset \).

GENERAL STEP\(\ \left( 1\le i\le \sigma \right) \), \(\mathbf {M}\) is the actual matrix. Let

$$\begin{aligned} \mathbf {b}_{X}^{i}&:&=\left( i,~\mathbf {M}_{1..n,1..n},~X,~\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=X\right] \right) \right) , \end{aligned}$$

(63)

$$\begin{aligned} \mathbf {b}_{\emptyset }^{i}&:&=\left( i,~\mathbf {M}_{1..n,1..n},\,\emptyset ,\,\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=\emptyset \right] \right) \right) . \end{aligned}$$

(64)

Case (i)   Neither \(\mathbf {b}_{\emptyset }^{i}\) nor \(\mathbf {b} _{X}^{i}\) fulfills (59)–(62) and \(B=\emptyset \). Then, STOP since Problem 1 has no solution.

Case (ii)   Neither \(\mathbf {b}_{\emptyset }^{i}\) nor \(\mathbf {b}_{X}^{i}\) fulfills (59)–(62) but \(B\ne \emptyset \). Recall that in Cases (i) and (ii), B may contain elements of type \(\mathbf {b}=\left( j,\overrightarrow{m},Y,\otimes _{\mathbf {b}}\right) \) only if \(j<i\) by Note 2 and (57), (58), and (63), (64). In Case ii), choose any element \(\mathbf {b}\in B\) such that \(\otimes _{\mathbf {b}}\) is maximal (in B). Then, reset the diagonal of \(\mathbf {M}\) according to \(\overrightarrow{m}\), set \(i:=j\), delete \(\mathbf {b}\) from B, and proceed to the General Step.

Case (iii)   Exactly one of \(\mathbf {b}_{X}^{i}\) or \( \mathbf {b}_{\emptyset }^{i}\) fulfills (59)–(62), say, \( \mathbf {b}_{Y}^{i}\). Let \(\mathbf {M}_{i,i}:=``Y\text {''}\) and go to Step Increasing i.

Case (iv)   Both \(\mathbf {b}_{X}^{i}\) and \(\mathbf {b}_{\emptyset }^{i}\) fulfill (59)–(62).

If \(\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=X\right] \right) \le \otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=\emptyset \right] \right) \), then let \(\mathbf {M}_{i,i}:=``\emptyset \text {''}\), \(B:=B\cup \left\{ \mathbf {b} _{X}^{i}\right\} \), and go to Step Increasing i.

If \(\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=X\right] \right) >\otimes _{diag}^{\max }\left( \mathbf {M}\left[ i,i=\emptyset \right] \right) \), then let \(\mathbf {M}_{i,i}:=``X\text {''}\), \(B:=B\cup \left\{ \mathbf {b} _{\emptyset }^{i}\right\} \), and go to Step Increasing i.

STEP INCREASING\(\left( i\right) \)   If \(i<\sigma \), then let \( i:=i+1\) , and go to the General Step. In the case \(i=\sigma \), go to the Check Step.

CHECK STEP (\(i=\sigma \))   First, save the recent \(\mathbf {M}\) with its \(\otimes _{diag}\left( \mathbf {M}\right) \). If B contains an element \(\mathbf {b}=\left( j,\overrightarrow{m},Y,\otimes _{\mathbf {b} }\right) \) such that

$$\begin{aligned} \otimes _{\mathbf {b}}>\otimes _{diag}\left( \mathbf {M}\right) , \end{aligned}$$

(65)

then go back to \(\mathbf {b}\) and start a new cycle, i.e., reset the diagonal of \(\mathbf {M}\) according to \(\overrightarrow{m}\), set \(i:=j\), delete \(\mathbf {b}\) from B, and go to the General Step.

END of the Algorithm.

(The algorithm is visualized in Fig. 2.)

Fig. 2

Flowchart of the proposed algorithm

Full size image

Remark 4

If we want to find all optimal solutions to Problem 1, then replace (65) with

$$\begin{aligned} \otimes _{\mathbf {b}}\ge \otimes _{diag}\left( \mathbf {M}\right) . \end{aligned}$$

(66)

Of course, we must first save (in an output buffer) the solution(s) we have found so far. Then, we pick the next element \(\mathbf {b} \in B\) in the buffer, reset the diagonal of \(\mathbf {M}\) according to \( \overrightarrow{m}\), set \(i:=j\), delete \(\mathbf {b}\) from B, and go to the General Step.

We call this algorithm the Hybrid Project Ranking Algorithm.

Theorem 3

The saved matrices (in the Check Step) of the above algorithm are exactly the optimal solutions to Problem 1. Specifically, there are no saved matrices if and only if (38)–(40) in Problem 1 has no solution at all.

Proof

In each step, the algorithm chooses the best of (at most) two possibilities but buffers the other for further investigation. The value \(\otimes _{diag}\left( \mathbf {M}\right) \) for each \(\mathbf {M}\) is a sharp upper bound for further continuation of \( \mathbf {M}\). Therefore, all the buffered possibilities with smaller \(\otimes \) than those of the finished (and saved) matrices (in the Check Step) could be deleted from the buffer. Since the algorithm checks each remaining element of the buffer (see the Check Step), at the end, we must obtain each optimal solution. \(\square \)

The result of phase one is to find [depending on the meaning of the completion scores and the aggregation functions (see Definition 4)] the most desired or most probable project scenario. Table 3 shows the results of phase one of Example 3.

Table 3 Results of phase one for Example 3

Full size table

Example 4

At the end of the result of phase one, only two options are allowed: tasks will be included in (“X” see on Table 3) or (because of the low priority) will be excluded from (see “\(\emptyset \)” on Table 3) the project plan. Table 3 shows that in the case of excluding a task from a project plan, all of its demands, completion modes and dependencies are also excluded from the project plan. Similar to the original project plan, minimal and maximal values of demands can be specified without calculating all possible project structures. \(\hbox {TPT}_{\min }=max(4+1,1)=5\) if only planned tasks are considered, and \(\hbox {TPT}_{\min }=max(4+1,1,1)=5\) if both planned and unplanned tasks are considered. \(\hbox {TPC}_{\min }=2+3+4=9\) if only planned tasks are considered, and \(\hbox {TPC}_{\min }=2+3+4+2=11\) if both planned and unplanned are considered. Because task D is excluded, if only planned tasks are considered: \(\hbox {TPQ}_{\max }=3\times 0.9/4\times 0.9=0.75\), while if both planned and unplanned tasks are considered, \(\hbox {TPQ}_{\max }=(3\times 0.9+1)/(4\times 0.9=0.75+1)=0.80\), which shows that if unplanned tasks can be completed, the total project quality can increase.

The goal of phase two is to find the most desired/most probable project structure within a project scenario. However, the project structure always depends on the result of phase one. Therefore, the “highest” scoring project structure can be interpreted only within a specified project scenario.

Phase two

In phase two, the goal is to find the most probable or most desired project structure within the specified project scenario. The algorithm and most of the notation for phase two are the same as in phase one. We have to determine the “?” symbols outside of the diagonal of \(\mathbf {M}\) in a fixed (but arbitrary) order. Before each replacement, we save the other possibility in a buffer, similar to (57), checking the conditions corresponding to (43) and (44), such as (59)–(62), which correspond to (38)–(40). In each step, we have to refresh \(T_{\min }\left( \mathbf {M},\mathcal {W}\right) \) and \(\otimes _{nd}\left( \mathbf {M}\right) \). The properties of the phase two algorithm can be proved along the lines of Theorem 3 and Sect. 2.3.4. That is, the algorithm in phase 2 finds all optimal solutions since it saves and investigates all real candidates in the buffer. The complexity is investigated in Sect. 2.3.4.

Example 5

Following Examples 3 and 4, Table 4 shows the results of phase two

Table 4 Results of phase two for Example 4

Full size table

Minimal and maximal values of demands can also be specified without calculating all possible project plans. \(\hbox {TPT}_{\min }=4+\max (1,4)=8\) if only planned tasks are considered, and \(\hbox {TPT}_{\min }=\max (4+\max (4,1),1)=8\). Since at phase two tasks are already not excluded from the project plan, minimal/maximal values of the cost/quality/resource are not modified.

Phase three

After phase two we obtain a project structure, which represents a traditional multimode resource-constrained project scheduling problem (MRCPSP). In this phase, when considerations of discrete completion modes are specified, we use Creemers [4]’s algorithm to specify the solution of the MRCPSP, and the continuous version of the problem is solved by Monghasemi et al. [18]’s algorithm. If there is no feasible solution to the given algorithm, we should go back to phase two and select the next project structure from the buffer. The optimal output matrix is a kind of domain mapping matrix (DMM), see Table 5, where flexible dependency and uncertain task completion are excluded or included. Therefore, the logic domain (LD) of the output matrix is a dependency structure matrix (DSM), where “X” represents included tasks on the diagonal, and included dependencies are on the out-diagonals of the LD. The optimal output matrix (furthermore, the project schedule matrix (PSM)) contains one vector of time/cost demands (TD,CD) and one vector of quality parameters (QD). The PSM also contains an n by r submatrix of resource demands (RD) and a vector of scheduled start times (SST).

Example 6

Following Example 3 and Examples 4–5, Table 5 shows the results of phase three.

Table 5 Results of phase three for Example 5

Full size table

Table 5 shows that because of the quality constraint, the lowest duration cannot be selected if unplanned tasks are not considered (see Table 5a). In this case, \(\hbox {TPT}=5+\hbox {max}(1,4)=9\), \(\hbox {TPC}=3+5+4=12\), \(\hbox {TPQ}=3 \times 0.9 / 4 \times 0.9 =0.75\), and TPR \(=[3,2]^T\). At the same time, if unplanned tasks are considered, than the lowest duration of tasks can be selected. In this case, TPT is not increased. \(\hbox {TPT}=\hbox {max}(4+\hbox {max}(1,4),1)=8\). \(\hbox {TPC}=2+5+4+3=14\) if every task is completed as early as possible TPR \(=[3,4]^T\), while \(\hbox {TPQ}=(0.8 + 0.9 + 0.9 + 1.0)/(4 \times 0.9 + 1.0) = 0.78\). Example 5 shows that unplanned tasks do not necessarily increase the time demands, and because the growth of relative quality occurs, customers can be more satisfied.

Algorithmic complexity

Briefly, in phase one, \(\otimes _{diag}\left( \mathbf {M}\right) \) is calculated and \(T_{\min }\left( \mathbf {M},\mathcal {W}\right) \) is refreshed (see Definition 14), so each cycle is at most quasilinear, but we have no bounds on the total size of the buffer. Similarly, in phase two, we have to calculate \(T_{\min }\left( \mathbf {M},\mathcal {W}\right) \) and \(\otimes _{nd}\left( \mathbf {M}\right) \), which implies a similar upper bound on time as in phase one. Perhaps some extreme counterexamples may cause exponential running time, but practical runs (see Sect. 3) provided quadratic runs, both in phase one and in phase two.

In more detail, in general, the nth-largest value can be determined within \(O(n\log n)\) computation time (e.g., [22]); however, our decision tree is a special binary heap where a quasilinear search algorithm can be specified. In Sect. 2.3, we saw that the best project structures can be found within \(O(s+d)\), where s is the number of supplementary tasks to be completed (phase one), and d is the number of flexible task dependencies (phase two). If there are no supplementary tasks to be completed, the number of possible project structures depends only on the number of flexible dependencies. If there are d flexible dependencies, then there are \(2^{d}\) possible project plans (phase two). In case of acyclic project networks, the maximal number of flexible dependencies is \(n(n-1)/2\), and in this case, the number of possible project structures is \(2^{n(n-1)/2}\) (phase two). If there are s supplementary tasks, then \(2^{s}\) project scenarios can be specified. In a special case, if \(s=n\) and \(d=n(n-1)/2\), then there are \(2^{n}\) project scenarios (phase one) and \(\sum \nolimits _{j:=0}^{n}\left( {\begin{array}{c}n\\ j\end{array}}\right) 2^{j(j-1)/2}\) project plans (phase two).

The computational demand of the proposed hybrid algorithm with respect to the fulfilled PEM=LD of a specified deterministic PEM is \(O(d)=O(n(n-1)/2)\approx O(n^{2})\) in the case of a fulfilled upper triangular matrix (NDSM) with only mandatory tasks, and the run time \(O(d+s)=O(n+n(n-1)/2)\approx O(n^{2})\) is similar when regarding a fulfilled upper triangular matrix with all supplementary tasks (phase one). For example, when \(n=50\), completely filled upper triangular NDSM and PEM specify \(5,78\cdot 10^{368}\) possible project plans, while our algorithm finds a project structure within \(O(50^{2})\) steps (phase two). However, at the end of the project selection process, where we have a feasible project structure, the proposed algorithm has to call a method for the multimode resource-constrained project scheduling problem. In this case, the complexity of the (MRCPSP) method and the complexity of project selection are multiplied. As MRCPSP are NP-hard problems, the hybrid versions of these problems are also NP-hard problems.

Method of testing project management approaches

The main goal of this section is to test the proposed algorithm and compare it to several state-of-the art algorithms. At the same time, since applied methods can imitate decision makers, different kinds of project management and scheduling approaches can be compared. In this section, the proposed algorithm is tested on the modified MMLIB [28] project database and on generated projects, which were generated by ProGEN [13]. Flexible and traditional approaches are implemented by algorithms from the literature review. Both the continuous version of time–quality–cost trade-off methods and the discrete version of multimode resource-constrained project scheduling problems are compared. The implemented algorithms imitate decision makers (i.e., project managers), who can select a technology (completion mode) from the set of multimodes and/or who can reorganize the project. The main question was to investigate scenarios in which flexible approaches produce more feasible projects.

Data sources and selected initial project plans

The aim of selecting and generating initial project plans is to meet as much as possible the expectations for flexible project management approaches, especially the features of agile, extreme and hybrid projects.

1. 1.

   Vanhoucke [30] showed that flexible projects usually contain more parallel tasks; therefore, according to Vanhoucke [30], the number of parallel tasks is greater than the number of serial tasks.Footnote 9 Nevertheless, one of the most popular agile approaches, the KANBAN method, limits the number of parallel WIP tasks, and allows only 3–5 WIPs. Therefore, in the simulation, the number of WIPs must be lower than 5.

2. 2.

   Projects are usually separated into smaller autonomous subprojects (sprints) (see, e.g., [8]), that should completed within 2–5 weeks; therefore, the number of tasks is limited and should not be greater than 30.

3. 3.

   Projects should contain at least two types of renewable resources (e.g., in software projects, a programmer and a tester).

4. 4.

   Projects should contain at least two completion modes to apply continuous trade-off methods and at least three for testing the discrete version of MRCPSP.

Two kinds of datasets are specified. The logic networks of Dataset A came from the standard project database [30]. Project plans of Dataset B are generated by the standard project generator software ProGen [13].

Use of logic network

Since all applied databases contained logic plans, the original project plans were used. Moreover, 5 project plans (j3031_7, j3035_10, j3042_1, j3031_5, j3064_10) satisfied the above mentioned criteria from Dataset A, and 5 additional project plans were generated by ProGen. Unfortunately, all databases contained neither flexible dependencies/supplementary tasks nor unplanned tasks; therefore, on one hand, score values are attached to the customized rate of tasks and dependencies. The rate of flexible dependencies and supplementary tasks were between 10 and 40% (\(ff\in \{0.1,0.2,..,0.4\}\)) (see an example in Fig. 3a). The proposed algorithm can exclude tasks and dependencies, and the original network can be changed; however, at least the mandatory tasks and fixed dependencies must be completed (see Fig. 3a). On the other hand, the original database does not contain unplanned tasks and dependencies. Therefore, the ratio of unplanned tasks and dependencies are specified between 0 and 40% (\(uf\in {0.0,0.10,..,0.40}\)) (see an example in Fig. 3c). Unplanned tasks and dependencies can contain mandatory tasks and fixed dependencies (see Fig. 3d). This modified dataset is capable of checking flexible management approaches. The modified databases contain 2 datasets, which contain 5–5 original project plans. These project plans contain a flexible project plan with 4 kinds of flexible rates. Moreover, 5 kinds of ratios of unplanned tasks and dependencies can be attached to the original project plan. Therefore, \(2\times 5\times 4\times 5=200\) logic plans are investigated.

Fig. 3

j3530_10 networks form MMLIB [28]

Full size image

Use of demands

Since quality parameters are missing from every known project database, we have to calculate according to the quality–cost trade-off functions. Only the relative quality functions were calculated. In the case of the continuous version, a higher budget that can allow higher quality is considered.

Moreover, usually an inverse proportionality can be assumed between the cost and quality. The (relative) quality parameters were simulated to the i-th task. In the case of the continuous version of trade-off methods, only two completion modes are specified for minimal/maximal values of durations/cost and resource demands. However, in the discrete version of MCRPSP, a randomized third completion mode is generated for time, cost, quality and resources; therefore, the trade-off assumptions between time–cost, time-resources and cost–quality are not satisfied in this case. Since both the discrete and the continuous version of the problem are examined, \(200\times 2=400\) project plans are specified.

Calculating constraints

All of the traditional approaches, agile project management approaches, and application management approaches specify the budget, deadlines and resource constraints based on only the planned tasks and dependencies. However, the extreme project management approach allows the project managers to confirm the extra cost and duration of unplanned tasks, and the constraints can be modified. Therefore, in the simulation, two kinds of contract strategy are compared. In the first strategy, the constraints are specified by considering only planned tasks. The agile project management approach does not allow new, unplanned tasks and dependencies. Therefore, these new tasks will be completed in a next sprint. However, the application management approach can confirm new tasks for which the original budget constraint allows their completion.

The other contract strategy is the flexible contract strategy, where the new tasks can increase the budget and can modify the deadline.

In the simulation, the five constraints (\(C_t\),\(C_c\),\(C_q\),\(C_s\),\(\mathbf {C_r}\)) were between the possible minimal and maximal values of demands. Then, Eq. (67) calculates:

$$\begin{aligned} C_x=C_x\%\left( \text {TPX}_{\max }-\text {TPX}_{\min }\right) +\text {TPX}_{\min } \end{aligned}$$

(67)

where \(C_x\) represents the constraints (i.e., \(C_x\in \{C_t, C_c, C_q, C_s, \mathbf {C_r}\}\)) and TPX represents the total project time/cost/quality/score/resources, respectively. \(C_x\%\in \{0.7,0.9\}\), if \(C_x\% \in \{C_t,C_c,C_{ri}\}, i=1,..,\rho \) and \(C_x\%\in \{1-0.7,1-0.9\}=\{0.1,0.3\}\), if \(C_x\% \in \{C_q,C_s\}.\)

Two kinds of contract strategies and \(2^5\) kinds of constraints on 400 project plans specified \(400\times 2\times 2^5 =25{,}600\) problems.

Target function

Though different kinds of target functions can be considered, we only want to specify the most desired project plan (maximal total project scores), where the completion time of the project is minimal.

Applied agents

Applied algorithms imitate decision makers. The traditional project management approach does not allow flexible dependencies and supplementary tasks; therefore, all flexible dependencies are considered as fixed and all supplementary tasks are considered as mandatory tasks. In the case of discrete completion modes, we obtain an MRCPSP problem, which was solved by Creemers [4]’s algorithm, while the continuous version of the problem was solved by Monghasemi et al. [18]’s algorithm. These algorithms imitate the decision maker who follows a traditional project management approach. Furthermore, these algorithms are called Traditional Project Management agents (TPMa).

To implement Agile Project Management agents (APMa), we used Kosztyán [15]’s Exact Project Ranking (EPR) algorithm. This algorithm does not consider different kinds of completion modes. Therefore, only minimal (so called normal) time demands and their cost/quality/resource demands are considered. Furthermore, this algorithm is called the Agile Project Management agent (APMa).

Despite that the original version of EPR does not allow the unplanned tasks and dependencies, the proposed extension of the PDM matrix and the extension of the set of activities can capably solve the problem. If the constraints are calculated based only on the planned tasks, and there is no chance to modify the constraints, the algorithm imitates the application management approach; therefore, the modified version of EPR is called an Application Management agent (AMa). However, if the extra demands can modify the constraints, than the modified EPR can imitate the decisions of the extreme project managers, and this algorithm, henceforward, is called the eXtreme Project Management agent (XPMa).

The proposed algorithm handles both the supplementary and the unplanned tasks and dependencies, and in addition, it can handle the multimode of completion modes. The decision maker can combine the multimode and the project screening techniques to reorganize the project. This algorithm can imitate the decision maker who follows the hybrid project management approach. Therefore this algorithm is, furthermore, called the Hybrid Project Management agent (HPMa).

Feasibility and the scheduling performance

On one hand, one of the main aspects of comparing the examined agents is to specify feasible project plans, namely, which agent and which project management approach can solve more problems.

On the other hand, it is also important to determine which feasible method can save more time, cost and resources. Therefore, the scheduling performances are specified as follows:

$$\begin{aligned} TPT\%= & {} C_t/TPT-1 \end{aligned}$$

(68)

$$\begin{aligned} TPC\%= & {} C_c/TPC-1 \end{aligned}$$

(69)

$$\begin{aligned} \overline{TPR}\%= & {} Mean(C_{r_i}/TPR_i-1), i=1,..,\rho \end{aligned}$$

(70)

$$\begin{aligned} TPQ\%= & {} TPQ/C_q-1 \end{aligned}$$

(71)

$$\begin{aligned} TPS\%= & {} TPS/C_s-1 \end{aligned}$$

(72)

All scheduling performances are between \([0,\infty ]\), specifically, 0 if the total project time/cost/quality/score/resource and the given constraints are equal. The scheduling performances are 1 if half of the budget, duration, resource demands, etc. can be saved. A greater value can produce higher scheduling performance.

The verification of optimality is a considerably hard problem because in this case, we should specify all the possible project structures, and we should find an optimal solution in a fixed project structure. However, because of the problem complexity (see Sect. 2.3.4), this kind of testing works only in small problems. Therefore, we tested the proposed algorithm only in small projects, where the logic domain was \(5\times 5\).

Results

If unplanned tasks are not allowed, three kinds of algorithms can be compared, both for the continuous version of the time–quality–cost trade-off problem (CTQCTP) and the discrete version of the multimode resource-constrained project scheduling problem (MRCPSP). TPMa represents the traditional project management approach, where every (not only mandatory, but supplementary) task and all (not only fixed, but flexible) tasks are included in the project; therefore, we obtain either the traditional (resource-constrained) CTQCTP or an MRCPSP problem. To imitate CTQCTP, we used Creemers [4]’s algorithm, while in the case of MRCPSP, Monghasemi et al. [18]’s is implemented.

Results of feasibility test and verification optimality

Given the large number of project scenarios and project structures in the cases of flexible projects (see Sect. 2.3.4) and the NP-hardness of MRCPSP-s, the feasibility is first checked. The question was to determine which method can produce a more feasible project.

Considering all databases and all the continuous and discrete problems, the feasibility rate was 72.03%. Despite that the agile project management approach (implemented by Kosztyán [15]) cannot handle multimodes and trade-offs, the feasibility rate was 78.64%.

More feasible projects could be specified if the flexibility factor was higher (see Fig. 4).

However, the proposed HPMa can produce projects that are 98.83% flexible.

Fig. 4

Comparing feasibility. HPMa represents the proposed algorithm, APMa represents Kosztyán [15]’s expert project ranking algorithm, TPMa follows Creemers [4]’s algorithm for trade-off problems and Monghasemi et al. [18]’s algorithm for solving MRCPSP

Full size image

Figure 4 shows that in the case of more flexible projects, the agile project management approach produces more feasible projects, while the traditional project management approaches perform better if the flexibility ratio is lower. Because the characteristics of project management agents are not different when considering dataset A and dataset B, we combined these datasets and show results on the joined dataset.

Verification of optimality of the proposed method was performed in two steps. First, without using resource constraints, flexible task dependencies, and supplementary tasks, the optimal solution of a CTQTCP problem can be specified by Creemers [4]’s algorithm. In this case, we used the original project plans where there were no supplementary tasks and flexible dependencies. Since phase three of the proposed method also applies Creemers [4]’s algorithm, the original algorithm and the proposed algorithm produced the same results. Similarly, if trade-offs are not considered, Kosztyán [15]’s algorithm can specify the optimal solution. In this case, the proposed and Kosztyán [15]’s algorithm produced the same results. After the first step, we specified random \(5\times 5\) logic domains, which is quite small to specify all possible project scenarios and all project structures. According to the complexity of the problem, the number of possible project plans is \(\sum \nolimits _{j:=0}^{5}\left( {\begin{array}{c}5\\ j\end{array}}\right) 2^{j(j-1)/2}=1450\) (see Sect. 2.3.4). For all possible project plans without resource constraints, Kosztyán [4]’s and the proposed algorithm are compared, and both algorithms could find the optimal solution. However, this mode of verification cannot be used for larger matrices because for a \(6\times 6\) logic domain, the possible project plan is 979,841.

Comparing scheduling performance

Both XPMa and AMa are based on the modification of Kosztyán [15]’s algorithm. Figure 5 shows that HPMa produces the most feasible project. At the same time, the ratio of feasibility can be increased if the constraints are not fixed as in AM but are flexible as in XPM.

Figure 6 shows the scheduling performances for MRCPSP problems, where greater values are better (shows lower TPT, TPC, TPR and higher TPQ, TPS; see Eqs. (68)–(72)). The HPMa produces the lowest TPT because the scheduling performance of the total project time (TPT%), 2.18, is the best for the proposed algorithm, but the cost of this performance is such that the other scheduling performance indicators are better for TPMa and APMa algorithms (see Fig. 6a).

Although TPMa has produced the lowest ratio of feasible project plans, TPMa reduces the most cost demands for feasible project plans.

APMa is the most effective for increasing quality and allocating resources. Figure 6b shows that HPMa can reduce the TPT most effectively while keeping more tasks, but XPMa and AMa can reduce cost and resources most effectively.

Fig. 5

Results of management agents in the case of unplanned tasks

Full size image

Fig. 6

Comparing scheduling performances for project management approaches

Full size image

Discussion

In flexible project environments, flexible approaches, such as agile and extreme project management approaches, can specify more feasible projects; therefore, these approaches can be more successful than the traditional approaches. At the same time, if there are more completion modes, hybrid approaches can handle both the flexibility and the selection from completion modes. This combination of approaches can produce the most feasible projects. The other advantage of the hybrid approach is that it can be used in cases of both flexible (ff is high) and nonflexible environments (ff is low). On one hand, if there is no flexible dependency and supplementary task, the HPMa is the equivalent of TPMa. On the other hand, if there is only one completion mode and we consider only planned tasks, HPMa is the equivalent of APMa. At the same time, in the flexible project environment when unplanned tasks can also be included in the project, HPMa is equivalent to AMa if constraints are fixed, but HPMa \(=\) XPMa if the constraint is flexible. Nevertheless, in the general case, if more than one completion mode (technology) is specified, in a flexible project environment HPMa can use both traditional and flexible scheduling techniques in order to specify feasible projects. Figure 5 shows that the flexible environment (higher flexibility factor) can increase the rate of flexibility more than the number of unplanned tasks. However, if extra costs and extra efforts of unplanned tasks are considered, the ratio of flexibility can be increased. Although Fig. 6 shows results only for MRCPSP, where trade-offs between time and cost, cost and quality, time and resources are not assumed, a kind of trade-off between methods can be observed. Figure 6 shows that the proposed HPMa can reduce TPT most effectively, but this method is not superior. Traditional and flexible project management approaches, such as APMa, XPMa, AMa can save more money and more resources. Flexible approaches can provide greater increases in quality and can be more effective in resource allocation. HPMa can be most effective for reducing time because this approach can reorganize the project and can select from completion modes, while other approaches use only one technique; however, other methods can save more resources and can produce more quality, while HPMa is usually closer to the constraints.

Summary and conclusion

The proposed hybrid multimode resource-constrained project scheduling problem approach may bridge the agile and traditional project management approaches. If there are no flexible dependencies or supplementary task completions, the problem amounts to the traditional MRCPSP problem. The hybrid project management (HPM) approach combines methods (e.g., TQCTP. MRCPSP) from traditional project management, and structuring and scoring techniques from agile project management.

The proposed algorithm is a fast, efficient method that supports the hybrid project management approach. The algorithm is able find an optimal solution according to predefined preferences over factors such as time, cost and quality. The proposed algorithm is able to handle unplanned tasks; therefore, this method can be used in a continuously changing environment. This paper shows that a hybrid approach can be an adequate alternative to flexible project management approaches. Traditional and flexible approaches can and should be combined in order to specify more feasible projects, and increase the scheduling performance of the project duration.

The developed matrix-based method and proposed exact algorithm may be important and essential components of a project expert system supporting strategic decision making, particularly in cases of large, complex, and flexible projects.

Limitations and future works

The proposed model extends the traditional multimode resource-constrained project scheduling problem; however, in this model, only renewable resources (e.g., human resources) and one nonrenewable resource (e.g., cost demand) are considered. In project management, renewable, nonrenewable, and semirenewable resources may also be important parameters. Therefore, this extension will be considered in future research. Another possible application of this method is in risk management and risk analysis. Supplementary and unplanned task completions can model changes in management or client claims. Flexible task dependency can model technological changes. In these cases, a more appropriate matrix-based model could be specified, and the efficiency on risk mitigation of traditional and flexible project management approaches can be compared for different kinds of project plans.

Which statement best sums up the use of project management software to conduct resource constrained smoothing?

What is the technique called which is used when the project is resource constrained?

What does resource smoothing seek to improve for a time constrained project?

What aspects of a project may be finalized once resources are applied to a project plan?