A mixed-integer linear programming model for solving fuzzy stochastic resource constrained project scheduling problem

Abstract

This paper addresses resource-constrained project scheduling problem with mixed uncertainty of randomness and fuzziness (FS-RCPSP). The activity durations are considered to be fuzzy random variables. A resource flow network based mathematical model with fuzzy random variables is presented. Then, this model is transformed into a mixed-integer linear programming model with crisp variables. The CPLEX 12.6.0.1 solver in AIMMS (2014) is employed for applying the proposed model to solve 960 benchmark instances generated from the well-known sets J30 and J60 in PSPLIB. The computational results are encouraging and indicate the ability of the proposed model to handle the FS-RCPSP.

1 Introduction

Resource constrained project scheduling problem (RCPSP) is a well-known NP-hard problem in scheduling, with the minimization of project duration as the objective subject to precedence and resource constraints. In this problem preemption is not allowed and the resources are considered to be renewable, and also the availability of resources, the resource requirement for each activity, and the activity durations are assumed to be known and fixed. So far, many exact, e.g., Damay et al. (2007) and Kolisch and Hartmann (2006), heuristic, e.g., Tormos and Lova (2001), Pantouvakis and Manoliadis (2006) and Ying et al. (2009), and meta-heuristic, e.g., Zamani (2011), Paraskevopoulos et al. (2012) and Sebt et al. (2013), solution procedures have been proposed for solving this problem with deterministic parameters. However, since the parameters cannot be exactly estimated in most practical situations, it would be more appropriate to consider the uncertainty of parameters in this problem.

In general, the majority of the research efforts to dealing with uncertainty in project scheduling problem concentrated on reactive scheduling, proactive (robust) scheduling, stochastic scheduling, and scheduling under fuzziness (Herroelen and Leus 2005). Reactive project scheduling copes with the uncertainties by repairing or rescheduling of the baseline schedule when an unexpected event occurs at the time of project execution. Some papers being published in this research area are Sadeh et al. (1993), Smith (1994), Van de Vonder et al. (2007), Lambrechts et al. (2008) and Herroelen and Leus (2004a). In proactive project scheduling a baseline schedule, which is protected as much as possible against disruptions during project execution, is built. Some papers in the area of proactive (robust) project scheduling are Lambrechts et al. (2008), Herroelen and Leus (2004a, b), Leus and Herroelen (2004) and Artigues et al. (2013). Most of the research efforts on the stochastic project scheduling concentrate on the Stochastic-RCPSP (S-RCPSP). In this problem, it is assumed that the processing time of each activity is uncertain and there are historical data about the activity durations, and therefore, based on this historical data, a probability distribution is given to each activity. In S-RCPSP no baseline schedule is produced and scheduling is usually done by a dynamic decision process which is called a policy. Based on the observed past up to the decision time t, each policy defines which activity/activities can start at that time. The literature on this area are rather sparse and interested readers are referred to recently published papers such as Ballestin and Leus (2009), Ashtiani et al. (2011) and Fang et al. (2015). Sometimes, due to the lack of historical data, probability distributions are not known for the activity durations. In these situations, activity durations are estimated by some experts and these estimations are often vague and imprecise. To cope with this kind of uncertainty, activity durations are modeled by fuzzy numbers. As the first study on the Fuzzy-RCPSP (F-RCPSP), Hapke et al. (1994) generalized the serial and parallel scheduling schemes to deal with fuzzy parameters. After this study, many other research efforts concentrated on this research area, some of which are Lorterapong (1994), Leu et al. (1999), Wang (2004), Xianggang and Wei (2010), Bhaskar et al. (2011), Atli and Kahraman (2012) and finally Atli and Kahraman (2013).

In real world projects, especially construction projects, it is possible that some activities of a project have been previously performed several times, and therefore we have enough historical data about their durations, but some other activities of this project may seldom or never been performed before and have no historical data. In these situations, randomness and fuzziness appear simultaneously and the corresponding scheduling problem is called fuzzy stochastic scheduling problem. This kind of problems can be treated using mathematical tools that model both randomness and fuzziness. Some of these tools are (Luhandjula 2006): probability of a fuzzy event (Zadeh 1968), probabilistic set (Hirota 1981), fuzzy random variable (Puri and Ralescu 1986; Kruse and Meyer 1987), and random fuzzy variable (Liu 2002a, b). In addition to this list, Buckley (2005) proposed a new type of fuzzy random variable based on his new fuzzy probability theory, which is used in this paper to represent activity durations.

The literature on fuzzy stochastic scheduling is in its burn-in phase, and the study of this research area has been initiated in Itoh and Ishii (2005). They proposed a mathematical programming model for scheduling of an n-job machine. In their model, processing times and due-dates for jobs were considered to be crisp and fuzzy random variables, respectively (Itoh and Ishii 2005). Ke and Liu (2007) for the first time studied a fuzzy stochastic project scheduling problem and made use of random fuzzy variables for representation of uncertainties. Three types of random fuzzy models were proposed for solving the understudy problem: expected cost minimization model, (α, β)-cost minimization model, and chance maximization model. Finally, a hybrid intelligent algorithm was designed for solving the mentioned three models (Ke and Liu 2007). Huang et al. (2009) made use of random fuzzy variables to solve the software project scheduling problem. They proposed an expected cost model for scheduling of a stochastic software project. In addition, a hybrid intelligent algorithm based on genetic algorithm and random fuzzy variables was designed to solve the proposed model (Huang et al. 2009). Nematian et al. (2010) were the first researchers for considering the Fuzzy Stochastic-RCPSP (FS-RCPSP). The ready time, duration, and deadline of activities were considered to be fuzzy random variables and expected value of fuzzy random variables was utilized for transforming the mathematical model with fuzzy random variables to a mixed-integer linear programming model (Nematian et al. 2010). Xu and Zhang (2012) studied the resource constrained multiple project scheduling problems with the mixed uncertainty of fuzziness and randomness. They proposed a multi-objective mathematical model with fuzzy random variables, and transformed it into a multi objective mathematical model with crisp variables. The objective functions of their model are minimizing the total project time and minimizing the total tardiness penalty of multiple projects. Xu and Zhang (2012) solved the model by a hybrid genetic algorithm with fuzzy logic controller (flc-hGA).

In this paper, resource constrained project scheduling problem is considered under the fuzzy random environment. A new simple and efficient approach in fuzzy probability theory, which was presented by Buckley (2005), is utilized to develop a mathematical model for RCPSP with fuzzy random activity durations. This model will be based on the concept of the resource flow network. Then, the proposed model with fuzzy random activity durations is transformed to a mixed integer linear programming (MILP) model with crisp variables and parameters.

The contributions of this paper are threefold: (1) an MILP model is proposed to solve RCPSP when randomness and fuzziness co-exist in the estimates of the durations of activities; (2) the uncertainties are represented by a new approach in fuzzy probability theory and fuzzy random variables; (3) promising results are obtained when the MILP model is applied to solve an extensive set of 960 FS-RCPSP problems created by the ProGen benchmark scheduling problem generator.

The remainder of this paper is organized as follows: in Sect. 2, some preliminaries on fuzzy theory and fuzzy probability theory are presented; Sect. 3 gives a formal description of the problem under study; Sect. 4 provides model formulations; in Sect. 5, the results of computational experiments to test the potency of our method in solving the FS-RCPSP are reported and finally, in Sect. 6, concluding remarks are drawn out.

2 Preliminaries

Before going through the problem description and introducing a mathematical model to solve it, it is necessary to know about some preliminaries. Thus, in this section, some general information is given about fuzzy numbers and fuzzy calculations. Then, the approach of Buckley (2005) in fuzzy probability theory and fuzzy random variables, which are utilized in this paper for treating the uncertainties in activity durations, are discussed. Hereafter, we place a “bar” and a “tilde” over a letter to denote a fuzzy number and a fuzzy random number, respectively. The different index/sets, parameters, and variables are defined in “Appendix”.

2.1 Fuzzy numbers and fuzzy arithmetic

In this subsection, the fuzzy sets, fuzzy numbers, and their related mathematical calculations are presented as follows:

Definition 1

A fuzzy set $\bar{A}$ in the universe of discourse $\varPsi$ is defined by its membership function, $\zeta_{{\bar{A}}} (x)$. A membership function gives values in [0,1] for all $x$ in $\varPsi$.

Definition 2

The support of a fuzzy set $\bar{A}$ is the crisp set of all elements of $\varPsi$ with nonzero membership in $\bar{A}$, and is shown as supp ($\bar{A}$) = [supp⁻($\bar{A}$), supp⁺($\bar{A}$)].

Klir and Yuan (2000) define the generalized left right fuzzy number with the following definition.

Definition 3

A fuzzy set $\bar{A}$ in IR is called a fuzzy number if and only if there exists a closed interval $[a,b] \ne \varphi$ such that:

$$\zeta_{{\bar{A}}} (x) = \left\{ {\begin{array}{*{20}l} 1 \hfill & {for\quad x \in [a,b]} \hfill \\ {l(x)} \hfill & {for{\kern 1pt} \quad x \in ( - \infty ,a)} \hfill \\ {r(x)} \hfill & {for{\kern 1pt} \quad x \in (b,\infty )} \hfill \\ \end{array} } \right.$$

(1)

where $l$ is a function from $( - \infty ,a)$ to [0,1] that is monotonic increasing, continuous from the right such that $l(x) = 0$ for $x \in ( - \infty ,w_{1} )$; $r$ is a function from $(b, + \infty )$ to [0,1] that is monotonic decreasing, continuous from the left such that $r(x) = 0$ for $x \in (w_{2} ,\infty )$(Klir and Yuan 2000).

Membership functions can take many forms, but since the fuzzy numbers are typically defined subjectively and in this way it is usually difficult to find an exact quadratic or higher order functions, researchers had a tendency to use two special linear functions namely, trapezoidal fuzzy number (TrFN) and triangular fuzzy number (TFN). A TrFN is shown as $(a_{1} ,a_{2} ,a_{3} ,a_{4} )$ and has the following membership function:

$$\zeta _{{TrFN}} (x) = \left\{ {\begin{array}{*{20}l} 0 \hfill & {\quad for\quad x \le a_{1} } \hfill \\ {\frac{{(x - a_{1} )}}{{(a_{2} - a_{1} )}}} \hfill & {\quad for\quad a_{1} < x \le a_{2} } \hfill \\ 1 \hfill & {\quad for\quad a_{2} < x \le a_{3} } \hfill \\ {\frac{{(a_{4} - x)}}{{(a_{4} - a_{3} )}}} \hfill & {\quad for\quad a_{3} < x \le a_{4} } \hfill \\ 0 \hfill & {\quad for\quad x \ge a_{4} } \hfill \\ \end{array} } \right.$$

(2)

A TFN is shown as $(a_{1} ,a_{2} ,a_{3} )$ and detailed form of its membership function is as follows (see Fig. 1):

$$\zeta _{{TFN}} (x) = \left\{ {\begin{array}{*{20}l} 0 \hfill & {\quad for\quad x \le a_{1} } \hfill \\ {\frac{{(x - a_{1} )}}{{(a_{2} - a_{1} )}}} \hfill & {\quad for\quad a_{1} < x \le a_{2} } \hfill \\ {\frac{{(a_{3} - x)}}{{(a_{3} - a_{2} )}}} \hfill & {\quad for\quad a_{2} < x \le a_{3} } \hfill \\ 0 \hfill & {\quad for\quad x \ge a_{3} } \hfill \\ \end{array} } \right.$$

(3)

Fig. 1

A triangular fuzzy number (TFN)

In particular, when $a_{2} = a_{3}$, the TrFN is reduced to the TFN; therefore, TFNs are special cases of TrFNs. In this paper, to simplify the calculations, TFNs are employed to represent fuzzy numbers.

The extension principle developed by Zadeh (1975) and later by Yager (1986) is one of the most basic concepts of fuzzy set theory that enables us to extend the domain of a function on fuzzy sets. It is possible to define fuzzy arithmetic operations by applying the concept of extension principle to arithmetic operations.

Definition 4

Let $\bar{A}$, $\bar{B}$ denote two fuzzy numbers, defined on universal set of real numbers IR, that represent the operands $x_{1}$ and $x_{2}$, respectively. Using the extension principle fuzzy arithmetic operation $\bar{A} * \bar{B}$, where $* \in \left\{ { + , - , \times , \div } \right\}$, is defined as

$$\zeta_{{\bar{A} * \bar{B}}} (y) = \mathop {\sup }\limits_{{y = x_{1} * x_{2} }} \left\{ {\hbox{min} (\zeta_{{\bar{A}}} (x_{1} ),\zeta_{{\bar{B}}} (x_{2} ))} \right\}.$$

(4)

The above addition and subtraction operations can be simplified for TFNs as follows:

Definition 5

Let $\bar{A} = (a_{1} ,a_{2} ,a_{3} )$ and $\bar{B} = (b_{1} ,b_{2} ,b_{3} )$ be two TFNs. The addition and subtraction of $\bar{A}$ and $\bar{B}$, are fuzzy numbers calculated as follows:

$$\bar{A} + \bar{B} = (a_{1} + b_{1} ,a_{2} + b_{2} ,a_{3} + b_{3} ),$$

(5)

$$\bar{A} - \bar{B} = (a_{1} - b_{3} ,a_{2} - b_{2} ,a_{3} - b_{1} ).$$

(6)

Many methods have been proposed for comparing two fuzzy numbers, however, none of them is commonly accepted. In this paper, the following method is employed, since it is simple, computationally cheap, and suitable for transforming a model with fuzzy parameters to a model with crisp ones.

Definition 6

Suppose $\bar{A} = (a_{1} ,a_{2} ,a_{3} )$ and $\bar{B} = (b_{1} ,b_{2} ,b_{3} )$ are two TFNs. Then, the following relation is hold (Nematian et al. 2010):

$$\bar{A} \le \bar{B} \Leftrightarrow a_{1} \le b_{1} \& a_{2} \le b_{2} \& a_{3} \le b_{3} .$$

(7)

The fuzzy numbers obtained for the mean value of a project’s makespan can be converted to a crisp value using a defuzzification method. Two common techniques for defuzzification are máxima methods and área-based methods. The advantages of máxima methods are their simplicity and speed (Pham and Castellani 2002) and their major disadvantage is loss of information. The most widely used área-based defuzzification method is the Centroid of Area (COA), which has shown good accuracy and performance on real world problems. Considering these pros and cons the COA method (see Eq. 8) is employed in this paper to defuzzify fuzzy numbers.

$$COA(\bar{A}) = \frac{{\int {\zeta_{{\bar{A}}} (x).xdx} }}{{\int {\zeta_{{\bar{A}}} (x)dx} }}.$$

(8)

2.2 Fuzzy probability theory

Let $X = \{ x_{1} , \ldots ,x_{n} \}$ be a finite set and let $P$ be a probability function defined on all subsets of $X$ with $P(\{ x_{i} \} ) = a_{i} ,1 \le i \le n,0 < a_{i} < 1$ all $i$ and $\sum\nolimits_{i = 1}^{n} {a_{i} } = 1$. Due to the uncertainties in the values of $a_{i}$, each crisp number $a_{i}$ is substituted with a fuzzy number $\bar{a}_{i}$ and it is assumed that $0 < \bar{a}_{i} < 1$ for all i. Then, $X$ together with the $\bar{a}_{i}$ values is a discrete fuzzy probability distribution (Buckley 2005). We write $0 < \bar{a}_{i}$ if 0 < supp⁻($\bar{a}_{i}$), and $\bar{a}_{i} < 1$ if supp⁺($\bar{a}_{i}$) < 1. A fuzzy probability function is presented as $\bar{P}$ such that $\bar{P}(\{ x_{i} \} ) = \bar{a}_{i} ,1 \le i \le n,0 < \bar{a}_{i} < 1$, and a random variable with a fuzzy probability function is called a fuzzy random variable. Buckley (2005) considers the following restriction on the $\bar{a}_{i}$ values: there are $a_{i} \in \bar{a}_{i\alpha } ,\alpha = 1$ so that $\sum\nolimits_{i = 1}^{n} {a_{i} } = 1$. Based on all of these, Buckley (2005) introduces the restricted fuzzy arithmetic as follows:

Definition 7

Let $A = \{ x_{1} ,..,x_{k} \}$, $1 \le k < n$, be a subset of $X$, then $\bar{P}(A)$ is defined as

$$\bar{P}_{\alpha } (A) = \left\{ {\sum\limits_{i = 1}^{k} {a_{i} } \left| {a_{i} \in \bar{a}_{i\alpha } } \right.,\quad 1 \le i \le n,\quad \sum\limits_{i = 1}^{n} {a_{i} } = 1} \right\},\quad {\text{for}}\quad 0 \le \alpha \le 1.$$

(9)

This is a restricted fuzzy arithmetic, because when all probabilities are fuzzy it is insisted that the sum of all the individual probabilities equals one (Buckley 2005). Assuming that $\tilde{X}$ is a fuzzy random variable having fuzzy probability density $f(x,\bar{\theta })$, where $x \in IR$ and $\bar{\theta } = \left\{ {\bar{\theta }_{1} , \ldots ,\bar{\theta }_{Q} } \right\}$ is for parameters $\bar{\theta }_{q}$, $1 \le q \le Q$, the above restricted fuzzy arithmetic for discrete case can be extended to continuous one as:

$$\bar{P}_{\alpha } (\tilde{X} \in [z_{1} ,z_{2} ]) = \left\{ {\int_{{z_{1} }}^{{z_{2} }} {f(x;\theta )dx} \left| {\theta_{q} \in \bar{\theta }_{q\alpha } } \right.,\quad 1 \le q \le Q,\quad \int_{ - \infty }^{ + \infty } {f(x;\theta )dx} = 1} \right\},\quad for\quad 0 \le \alpha \le 1.$$

(10)

Definition 8

The expected value and variance of a fuzzy random variable with a discrete are fuzzy numbers and are defined by their α-cuts as follows:

$$\bar{\mu }_{\alpha } = \left\{ {\sum\limits_{i = 1}^{n} {x_{i} a_{i} } \left| {a_{i} \in \bar{a}_{i\alpha } } \right.,\quad 1 \le i \le n,\quad \sum\limits_{i = 1}^{n} {a_{i} } = 1} \right\}\quad {\text{for}}\quad 0 \le \alpha \le 1,$$

(11)

$$\bar{\sigma }_{\alpha }^{2} = \left\{ {\sum\limits_{i = 1}^{n} {(x_{i} - \mu )^{2} a_{i} } \left| {a_{i} \in \bar{a}_{i\alpha } } \right.,\quad 1 \le i \le n,\quad \sum\limits_{i = 1}^{n} {a_{i} } = 1,\quad \mu = \sum\limits_{i = 1}^{n} {x_{i} a_{i} } } \right\}\quad {\text{for}}\quad 0 \le \alpha \le 1.$$

(12)

Equations (11) and (12) for a fuzzy random variable with a continuous fuzzy probability distribution are extended as follows:

$$\bar{\mu }_{\alpha } = \left\{ {\int_{ - \infty }^{ + \infty } {xf(x;\theta )dx} \left| {\theta_{q} \in \bar{\theta }_{q\alpha } } \right.,\quad 1 \le q \le Q,\quad \int_{ - \infty }^{ + \infty } {f(x;\theta )dx} = 1} \right\}\quad {\text{for}}\quad 0 \le \alpha \le 1,$$

(13)

$$\bar{\sigma }_{\alpha }^{2} = \left\{ \int_{ - \infty }^{ + \infty } {(x - \mu )^{2} f(x;\theta )dx} \left| {\theta_{q} \in \bar{\theta }_{q\alpha } } \right.,1 \le q \le Q,\mu = \int_{ - \infty }^{ + \infty } {xf(x;\theta )dx} \right\} ,\quad {\text{for}}\quad 0 \le \alpha \le 1.$$

(14)

In this research, the processing times of a project’s activities are represented by fuzzy random variables with fuzzy normal density functions.

Definition 9

A fuzzy normal density is shown as $N(\bar{\mu },\bar{\sigma }^{2} )$ that in comparison with the crisp normal density $N(\mu ,\sigma^{2} )$ just the values of $\mu$ and $\sigma^{2}$ have become fuzzy. Based on Definition 8, it can be easily demonstrated that the fuzzy expected value of a fuzzy random variable with fuzzy normal density $N(\bar{\mu },\bar{\sigma }^{2} )$ equals to $\bar{\mu }$ and its fuzzy variance is $\bar{\sigma }^{2}$ (Buckley 2005).

Theorem 1

Let $\tilde{X}$ and $\tilde{Y}$ be two fuzzy random variables and $\lambda \in IR$. The following equations are used for calculation of expected values denoted by $E$ (Nematian et al. 2010):

$$E(\lambda ) = \lambda$$

(15)

$$E(\tilde{X} + \lambda \tilde{Y}) = E(\tilde{X}) + \lambda E(\tilde{Y})$$

(16)

Definition 10

The inequalities “$\tilde{ \le }$” and “$\tilde{ \ge }$” for two fuzzy random variables $\tilde{X}$ and $\tilde{Y}$ are defined as follows (Nematian et al. 2010):

$$\tilde{X}\tilde{ \ge }\tilde{Y} \Leftrightarrow E(\tilde{X}) \ge E(\tilde{Y})$$

(17)

$$\tilde{X}\tilde{ \le }\tilde{Y} \Leftrightarrow E(\tilde{X}) \le E(\tilde{Y})$$

(18)

3 Problem statement

The scope of this study is to model the uncertainties in resource constrained project scheduling problem (RCPSP) by fuzzy probability theory, due to the simultaneous existence of randomness and fuzziness; therefore, the problem under consideration is Fuzzy Stochastic- RCPSP (FS-RCPSP). It is assumed that the uncertainty only exists in the durations of activities. However, extending the proposed model of this paper to a more general situation with uncertainties in other parameters is straightforward.

In FS-RCPSP a single project consisting of n + 2 activities is considered. The activities are numbered 0 to $n + 1$, where 0th and ($n + 1$)th activities are dummy start and end activities, respectively. Each activity j cannot be interrupted once in progress (i.e., preemption is not allowed), and has to be started after all its immediate predecessor activities i ($i \in IP_{j}$) have been finished (i.e., precedence constraint). We have L renewable resources (e.g., equipment and human resources), and each resource $l \in L$ has a limited capacity $R_{l}$ ($1 \le l \le L$) throughout the project duration. Each activity j requires $r_{jl}$ ($0 \le j \le n + 1$, $1 \le l \le L$) units of resource l once in progress. The sum of resource requirements for resource l at any time period t cannot exceed $R_{l}$ (i.e., resource constraint). The processing time of activity j is denoted as $\tilde{d}_{j}$ ($0 \le j \le n + 1$) which are fuzzy random variables. The start and finish time of each activity j are respectively shown by $\tilde{s}_{j}$ and $\tilde{f}_{j}$ ($0 \le j \le n + 1$). The objective is to find precedence and resource feasible completion times for all activities which lead to minimum expected makespan.

Considering the aforementioned description of FS-RCPSP, this problem can be modeled as:

where constraints (20) and (22) are respectively used to impose precedence and resource constraints.

4 Mixed-integer linear programming model for FS-RCPSP

The above mathematical formulation ($M1$) cannot be solved directly, because there is no approach for transferring set $B(t)$ to a linear constraint. Many other linear programming formulations have been proposed for the RCPSP with deterministic activity durations that can be solved directly. One of these formulations is the formulation of Artigues et al. (2003) which is a resource flow network model to solve RCPSP. In this section, making use of the assumptions and concepts introduced by these researchers, a mixed-integer linear programming model is proposed for FS-RCPSP as follows.

In a possible schedule, after completion of each activity, its resources should be transferred to other activity/activities. A resource flow network explicitly demonstrates the amount of resources transferred from one activity to another. It is necessary to notice that, each complete resource flow network corresponds with a possible schedule and the objective of the resource flow network model proposed by Artigues et al. (2003) is to find a resource flow that leads to a minimum project makespan. Let $C_{ij}^{l}$ denote the amount of resource l directly transferred from activity i to activity j. Also, let $x_{ij}$ be a binary variable denoting that activity j is started immediately after the completion of activity i whenever $x_{ij} = 1$, otherwise $x_{ij} = 0$. In addition, suppose that both of the dummy activities require $R_{l}$ units of resource $l \in L$ and their processing times are equal to zero. Considering all of these, the resource flow network model for FS-RCPSP is written as follows:

The objective function (24) minimizes the completion time of the dummy end activity and consequently the completion time of the project. Equation (25) introduces the precedence relations between the activities. Activity i precedes activity j whenever $x_{ij} = 1$, otherwise $x_{ij} = 0$. Constraint (26) is transiting constraint and constraint (27) ensures that no cycles will exist in the network. Constraints (28), (31), and (34) are employed for setting the completion times of activities. Constraints (29), (30), and (33) are resource flow inequalities. By constraint (33) the resource flow values are limited to $\hbox{min} (r_{il} ,r_{jl} )$ of arc $(i,j)$ if the arc exists. Constraints (29) and (30) have been devised to ensure that the incoming flow on node i is equal to the outgoing flow from that node.

The $M2$ mathematical model is a model with fuzzy random parameters. Since the aim of this paper is to develop an MILP model to solve the problem at hand, and also to the best of our knowledge, this model cannot be solved by any of the approaches proposed so far, we have to transform the model into a model with deterministic parameters. To this end, considering the objective of FS-RCPSP which is to minimize the expected makespan of the project, at first, the $M2$ mathematical model is transformed into a model with fuzzy parameters utilizing theorem 1, Definition 10, and concept of expected value of fuzzy random variables. It is worth reminding that all the fuzzy random variables in $M2$ have fuzzy normal probability distribution density and their expected value and variance are assumed to be triangular fuzzy numbers. Therefore,

Since the expected value of a fuzzy random variable with probability density $N(\bar{\mu },\bar{\sigma }^{2} )$ is equal to $\bar{\mu }$, by substituting this value in $M3$ the following model is resulted:

What to do now is to transform the model $M4$, which is a model with fuzzy variables and parameters, to a model with deterministic ones. In the case of objective function, since $\bar{\mu }_{{f_{n + 1} }}$ is a fuzzy number it cannot be minimized, thus we act similar to Buckley and Feuring (2000) and change the problem of minimizing the fuzzy number $\bar{\mu }_{{f_{n + 1} }}$ into a multi-objective problem, and then we change the multi-objective problem into a single objective one. Since it is assumed that $\bar{\mu }_{{d_{i} }}$ for each activity i ($0 \le i \le n + 1$) is a triangular fuzzy number, the $\bar{\mu }_{{f_{n + 1} }}$ will also become a triangular fuzzy number like the one demonstrated in Fig. 2. Let LA be the area under the graph from $f_{n + 1,1}$ to $f_{n + 1,2}$ and RA be the area under the graph from $f_{n + 1,2}$ to $f_{n + 1,3}$. Now, based on the approach of Buckley and Feuring (2000), we can substitute the objective function Min($\bar{\mu }_{{f_{n + 1} }}$) with three objectives: (1) Min($f_{n + 1,2}$), (2) Max(LA), and (3) Min(RA).

Fig. 2

A triangular fuzzy number for $\bar{\mu }_{{f_{n + 1} }}$

It is obvious that, LA is increased by increasing the distance between $f_{n + 1,1}$ and $f_{n + 1,2}$, and vice versa. Thus, we can substitute the objective Max(LA) with Max($f_{n + 1,2} - f_{n + 1,1}$) or Min($f_{n + 1,1} - f_{n + 1,2}$). Similarly, RA is decreased by decreasing the distance between $f_{n + 1,2}$ and f_n+1,3, and vice versa. Therefore, Min)RA(can be substituted with Min($f_{n + 1,3} - f_{n + 1,2}$). In this paper, the weighted sum method (Marler and Arora 2010) is employed to convert the multi-objective problem to a single objective one. Let $\omega_{i} \ge 0,i = 1,2,3$ and $\omega_{1} + \omega_{2} + \omega_{3} = 1$, then we would have the following function to be minimized:

$$Min\begin{array}{*{20}c} {} & {Z = \omega_{1} (f_{n + 1,1} - f_{n + 1,2} )} \\ \end{array} + \omega_{2} (f_{n + 1,2} ) + \omega_{3} (f_{n + 1,3} - f_{n + 1,2} ).$$

(57)

Now constraints, having fuzzy parameters and variables, are transformed into constraints with deterministic ones, and for this purpose, we will make use of Definition 6. Consequently, the following mathematical model ($M5$), which is a mixed-integer linear programming model, is deduced.

This formulation ($M5$) is a mixed integer linear programming model that can be solved by every MILP solver methods and software. The objective function of this model is more flexible for project managers since they can vary the values of $\omega_{1}$, $\omega_{2}$, and $\omega_{3}$ to satisfy their different requirements. Also, by a mutual interaction between manager and contractor, an agreement upon the membership functions of fuzzy numbers can be achieved that will help to make decisions being acceptable for both manager and contractor.

The user of the proposed method of this paper can consider any shape other than triangular fuzzy number for the membership function of fuzzy parameters and accordingly adjust the MILP model, however for any other shape the computation effort will increase. Since models M1–M4 are independent from the shape of fuzzy numbers, this change will affect on model M5 and its related calculations.

5 Computational experiments

With the aim of studying the computational performance of the proposed MILP model, in this section some benchmark problems are solved using this model. All the problems are implemented to optimality with the AIMMS (2014) modeling software running CPLEX 12.6.0.1 as a MILP solver on a laptop with windows 7 operating system, Intel Core 2 Duo and a CPU at 2.00 GHz. AIMMS is a state-of-the-art mathematical modeling environment and its CPLEX solver have found many application in optimizing real world complex problems such as supply chain management (Ebadian et al. 2013), pipeline scheduling problem (Zaghian and Mostafaei 2015; Mostafaei et al. 2015), workforce planning problem (van der Veen et al. 2015), etc.

5.1 Problem set generation

There are benchmark problems for RCPSP with deterministic activity times, but there is no benchmark problem set for RCPSP with fuzzy random activity times. In order to generate some benchmark problems, we take the ProGen project instances with 30 and 60 activities, named J30 and J60, each consisting of 480 problems (i.e., a total of 960 problems) with four types of resources, from the PSPLIB set of benchmark problems (see site: http://www.om-db.wi.tum.de/psplib/data.html) as the base and generate problems with fuzzy random activity durations. Since the processing times of activities are fuzzy normal variables and only their expected values $\bar{\mu }_{{d_{i} }} = (d_{i,1} ,d_{i,2} ,d_{i,3} )$, $0 \le i \le n + 1$, are exploited in our calculations, it would be enough if we generate triangular fuzzy numbers for the activities with regard to their deterministic durations. The mean duration $\bar{\mu }_{{d_{i} }}$ of each activity $i$ is generated as follows: the most likely points $d_{i,2}$, $0 < i < n + 1$, are taken equal to deterministic estimates, the most optimistic times $d_{i,1}$, $0 < i < n + 1$, are calculated as $d_{i,1} = d_{i,2} - 2$ and we bound it by zero, and the most pessimistic times $d_{i,3}$, $0 < i < n + 1$, are calculated as $d_{i,3} = d_{i,2} + 3$. Finally, expected values of dummy start and end activities are set to (0, 0, 0).

5.2 Computational results

The computational results obtained by implementing our proposed mathematical model to solve the aforementioned 960 generated instances are presented in Table 1. In all experiments, values of $\omega_{1}$, $\omega_{2}$, and $\omega_{3}$ were set to be 0.1, 0.8, and 0.1, respectively. There are 48 groups of problems for both J30 and J60, such that each group contains 10 problems. In Tables 1 and 2, for each group the number of problems out of 10 which CPLEX solver in AIMMS could find an integer solution for them, the mean value of these problems’ objective function (Z), the mean value of their defuzzified $\bar{\mu }_{{f_{n + 1} }}$, as well as the mean value of their computation time are indicated. In addition, the average value of optimal makespans reported in PSPLIB for the deterministic version of J30 problems is provided for each group in Table 1 to compare it with the mean of defuzzified $\bar{\mu }_{{f_{n + 1} }}$ for that group. However, As for J60 set some of the optimal solutions are not known, the average value of lower bounds for each group of J60 problems is presented in Table 2.

Table 1 Results of CPLEX 12.6.0.1 solver of AIMMS for problems generated from J30 set

Table 2 Results of CPLEX 12.6.0.1 solver of AIMMS for problems generated from J60 set

For problem set J30, the CPLEX 12.6.0.1 solver in AIMMS (2014) could find integer solutions for 433 out of 480 problems. However, in the case of problem set J60, this solver could just find integer solutions for 329 out of 480 problems. The resulted mean of deffuzified $\bar{\mu }_{{f_{n + 1} }}$ for all the groups in both problem sets J30 and J60 are close to that of crisp makespan and crisp lower bound, respectively. The differences are because we considered RA to be 1.5 times larger than LA. In addition, these differences may be related to our decision in selecting values for $\omega_{1}$, $\omega_{2}$, and $\omega_{3}$ as 0.1, 0.8, 0.1, respectively. The computational times are satisfactory, however, we believe that by improving the performance of CPLEX solver or introducing other algorithms to solve the model these computational efforts can be decreased. Altogether, the results in Tables 1 and 2 show that our MILP model works well and CPLEX 12.6.0.1 obtains quite good results, however this solver’s performance is not acceptable on 47 problems (i.e., about 10% of problems) in J30 set and on 151 problems (i.e., about 31% of problems) in J60 set.

6 Concluding remarks

A mixed-integer linear programming model was developed to solve Fuzzy Stochastic- Resource-Constrained Project Scheduling Problem (FS-RCPSP). A recently proposed approach in fuzzy probability theory and fuzzy random variables utilized to model the RCPSP under fuzzy random environment. The application of fuzzy random variables makes the proposed model more suitable for treating with uncertainties in real world projects where randomness and fuzziness co-exists. The primary model with fuzzy random variables was developed with the help of resource flow network concept. We made use of expected value of fuzzy random variables to transform this primary model to an LP-model with fuzzy variables and parameters. Then, this model was transformed into an MILP model with crisp variables and parameters. For illustrating the performance of the model, the CPLEX 12.6.0.1 solver in AIMMS (2014) was employed for applying the proposed model to solve 960 benchmark instances generated from the well-known sets J30 and J60 in PSPLIB. The results were promising and indicated the ability of our proposed model in handling FS-RCPSP.

This paper has some potential future works: one of the future prospects of the mathematical formulation proposed here is to consider parameters other than activity times (e.g., resource consumption) to be fuzzy random numbers. Besides, the model can be generalized by considering the effect of factors other than expected value like variance of fuzzy random variables to the model. In addition, implementation of other exact, heuristic, and meta-heuristic algorithms to solve the proposed model can be another prospect of future studies.

Appendix: Nomenclatures

The different index/sets, parameters, and variables in this paper are defined as follows:

See Table 3.

Table 3 .