Deterministic models for project scheduling and
control suffer from the
fact that they assume complete information and neglect random
influences that occur during project execution. A typical
consequence is the underestimation of the expected project
duration and cost frequently observed in practice. This
phenomenon occurs even in the absence of resource constraints,
and has been the subject of extensive research in discrete
mathematics and operations research.
This article presents a survey on the reasons for this
phenomenon, its complexity, and on methods how to obtain more
relevant information. To this end, we consider scheduling
models with fixed precedence constraints, but (independent)
random processing times. The objective then is to obtain
information about the distribution of the project makespan. We
will demonstrate that this is an #P-complete problem
in general, and then consider several combinatorial methods to
obtain approximate information about the makespan distribution.
