contents
|
. . . . | stochastic scheduling |
|
|
Stochastic Project Scheduling
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: 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:
|
top
