ACTIVITY NETWORKS

JIM MORROW

Abstract. This is a summary of the important concepts and algorithms associated with \underline{activity networks}. A reference for this material is p. 278-284 of Applied Combinatorics with Problem Solving by B. Jackson and D. Thoro.

An \underline{activity network} is a weighted acyclic digraph with no multiple edges where the weights, w(pq), are all non-negative. By adding dummy activities of weight 0, we may assume that there is a unique node, S, with indegree 0, which will be called the \underline{start} of the network and a unique node, F, with outdegree 0 which will be called the \underline{finish} of the network. The edges are referred to as \underline{activities} and the vertices are \underline{events}. More precisely p is the \underline{start} of activity pq and q is the \underline{finish}. A node may be the start and finish of more than one activity. The \underline{completion time}, T, of the network is defined to be the length of the longest path from S to F. The \underline{earliest starting time}, e(p), of activity pq is defined to be the length of the longest path from S to p. The latest finishing time, l(q), of activity pq is defined to be T − f, where f is the length of the longest path from q to F. The \underline{float time}, fl(pq), of pq is defined to be fl(pq) = l(q) − e(p) − w(pq) = T − f − w(pq) − e(p). A \underline{critical} activity pq is one in which fl(pq) = 0. A \underline{critical path} is a longest path from S to F. An activity is critical if and only if it is on a critical path.

There is an algorithm for computing e(p) which can be easily modified to compute l(q). Here is a summary of it.

1. (Initialize) Set e(p) = 0 for all p.

2. Select a vertex p of indegree 0.

3. If there are no edges pq, stop. For every activity pq and let the new value of e(q) be max{e(q), e(p) + w(pq)}.

4. Remove p and all edges pq.

5. Go to 2.

To compute the length of the longest path from q to F, reverse this algorithm and begin at F.

Date: November 8, 1995.