Theory of Scheduling

10/6/11

In the work we do we create and read schedules that are used for our many projects.

In our daily work we tend to look at scheduling as using Microsoft Project. In our Project Management classes, we focused on the fundamental ideas of the critical path method (CPM) and the Program Review and Evaluation Technique (PERT), two network methods that were developed independently in the 1950's. In this blog I'll talk a little more about the mathematical theory of PERT.

By a network method, it is meant that the logical relationships between project activities are displayed in a graph. PERT recognizes that activity durations are random variables. Let

p_j = duration of activity j
m_j = mean of p_j, (assumed to be known)
s_j² = variance of p_j (assumed to be known)

The PERT model assumes that the activities in the network are statistically independent and that the critical path (CP) in the network contains a "large" number of activities. The latter assumption is so we can apply the central limit theorem (CLT).

Let D_k denote the sum of the durations of activities along path k in the network. If there are many activities on the path, then D_k follows a normal random variable with mean m_k = sum(m_j), for all j in k and variance s_k² = sum(s_j²), for all j in k.

By the CLT, the probability that the project will be completed by due date t is therefore P(D_CP <= t) = f[ (t-m_CP)/s_CP ], where f is the cumulative distribution function for a standard normal random variable.

How do we know m_j and s_j² ? Often there are no similar activities in similar projects to estimate these from. A rule of thumb that has shown success in practice is

O = an optimistic duration for an activity
P = a pessimistic duration for an activity
M = the most likely duration for an activity

These three parameters are incorporated in a beta distribution as a probabilistic model for the duration of the activity. The parameters O and P are the minimum and maximum of the activity duration distribution and M is its mode. The original PERT team recommended

m_j = (O+4M+P)/6 (note that this is a weighted average, weighting the most likely duration more heavily)
s_j = (P-O)/6

There have been many refinements to PERT-type methods over the years that address its simplistic (although very useful and practical) assumptions. The take-away message is that many events are unpredictable and sometimes questions about a project can only be answered in probabilistic terms. For complex projects, with several thousand line items in the schedule, there is no other way.