New strategies for stochastic resource-constrained project scheduling

Abstract

We study the stochastic resource-constrained project scheduling problem or SRCPSP, where project activities have stochastic durations. A solution is a scheduling policy, and we propose a new class of policies that is a generalization of most of the classes described in the literature. A policy in this new class makes a number of a priori decisions in a preprocessing phase, while the remaining scheduling decisions are made online. A two-phase local search algorithm is proposed to optimize within the class. Our computational results show that the algorithm has been efficiently tuned toward finding high-quality solutions and that it outperforms all existing algorithms for large instances. The results also indicate that the optimality gap even within the larger class of elementary policies is very small.

Appendix: Exact evaluation of GP-policies for exponential distributions

In this appendix, we describe an exact evaluation procedure for the expected makespan of a feasible GP-policy ${\varPi }(L,X,Y)$, when each activity i has an exponentially distributed duration with rate parameter $\lambda _{i}$.

We use a Markov chain in which a state is represented by a pair (I, O), where I and O are the sets of idle and ongoing activities, respectively. The set F of finished activities is fully defined by given choices for I and O. In a state (I, O), an activity $i \in N$ is eligible to start if the following three conditions hold:

• 1. $i \in I$,

• 2. $j \in F$ for all j for which $(j,i) \in A$,

• 3. $r_{ik} \le \left( a_{k} - \sum _{j \in O} r_{jk} \right)$ for all $k \in K$.

For a given state (I, O), let H denote the set of eligible activities and $W\subseteq H$ the set of activities to be started in that state (following the given policy ${\varPi }(L,X,Y)$). Activities $i\in H$ are considered in order of L for inclusion into W and are included if the following two conditions apply:

• 1. $j \in \left( O \cup F \right)$ for all j for which $(j,i) \in Y$,

• 2. $j \in F$ for all j for which $(j,i) \in X$.

If $\left| W \right| > 0$, then an immediate transition is made toward state $(I{\setminus }W, O \cup W)$. Otherwise (if W is empty), no activities are started and a transition takes place after completion of the first activity in O. The probability that an activity $i \in O$ finishes first equals $\lambda _{i}/\sum _{j \in O} \lambda _{j}$. The time until the first completion is exponentially distributed and has expected value $\left( \sum _{i \in O} \lambda _{i} \right) ^{-1}$.

With each state (I, O), we associate a value function G(I, O) that represents the expected time when state (I, O) is visited, and $\pi (I,O)$ denotes the probability that the state is visited. We stepwise update both values. If $W\ne \emptyset$, then $\pi (I{\setminus }W, O \cup W)$ is increased by $\pi (I,O)$ and $G(I{\setminus }W, O \cup W)$ is increased by $G(I,O)\pi (I,O)$. Otherwise ($W=\emptyset$), probability $\pi (I , O{\setminus }\left\{ i \right\} )$ is increased by $\pi (I,O)\lambda _{i}/\sum _{j \in O} \lambda _{j}$, and value function $G(I , O{\setminus }\left\{ i \right\} )$ is augmented with $\left( G(I,O) + \left( \sum _{i \in O} \lambda _{i} \right) ^{-1} \right) \pi (I,O)\lambda _{i}/\sum _{j \in O} \lambda _{j}$.

Memory rather than computation time is typically the bottleneck when evaluating a Markovian PERT network. In our implementation, we have used techniques described in Creemers et al. (2010) and Creemers (2015) to delete states from memory when they are no longer needed.