Stochastic Project Scheduling

Participants: Prof. Dr. Rolf H. Möhring,
Frederik Stork
Arfst Ludwig
Supported by: Deutsche Forschungsgemeinschaft (DFG), within the research program "Resource-Constrained Project Scheduling - Models, Methods, and Applications".

Project description:

Features of the Resource-Constrained Project Scheduling Problem (RCPSP) are precedence constraints among given activities, resource constraints, and performance measures to be optimized (e.g. project makespan). In contrast to deterministic scheduling, we assume activity durations to be random according to a given probability distribution.

Like its deterministic counterpart, the stochastic version of the RCPSP is NP-hard. We are currently developing branch-and-bound algorithms for determining policies that minimize the expected project makespan. The algorithms base on so called Earliest-Start (ES) and preselective policies which represent certain extensions of the underlying precedence relation and are thus independent from the activity durations. The resource constraints are represented by so called minimal forbidden sets, which are minimal sets of pairwise technologically independent activities that are not allowed to be scheduled simultaneously due to some limited resources. Each resource conflict on a forbidden set can be settled by either selecting two activities and adding a precedence constraint between them to the partial order (ES policies) or by selecting one activity which is not allowed to start before at least one of the other activities of the forbidden set has been completed (preselective policies). To handle the stochastic activity durations simulation techniques are used.

For the case without resource constraints, it is still #P-complete to evaluate the distribution function of the project makespan, even at one point only. However, there exist several methods to compute stochastic bounds for this distribution function. We have implemented the bounds of Kleindorfer and Dodin and a heuristic procedure proposed by Spelde. All these methods modify the underlying partial order into a series-parallel partial order to facilitate the calculation of the resulting project cost. While the methods of Kleindorfer and Dodin require complete knowledge of the distribution of the individual activity durations, the procedure of Spelde can also cope with incomplete information. Only expectation and variance are required for each activity. The quality of the solution can be controlled by the number of paths that are critical with high probability.

Figure 1: Stochastic bounds Figure 1: The results of a procedure proposed by Spelde for different numbers of paths

Both scenarios (with and without resource constraints) will be combined to a two-stage tool. The first step will construct a reasonably good ES- or preselective policy, which than serves as the starting point for a detailed stochastic analysis via the bounding procedures described above.

See also: