A project can be described by its activities, their duration and the prerequisites of each activity

Activity: a task, characterized by:

• duration
• prerequisites – other tasks that have to be completed in order to start the current task

Event: a point in time, characterized by the completion of one or several activities

A model of a project:

            Directed simple acyclic graph
            Simple graph means: each pair of nodes connected by at most one edge

            Nodes: events

                        Source: starting event

                        Sink: terminating event

            Edges: activities
            Each edge is labeled by a pair: name of the task: duration.
            Dummy activities with duration 0: used to make the graph simple if necessary.

Purpose of the model:

• find the earliest occurrence time of an event
• find the earliest completion time of an activity
• find the slack of an activity: how much the activity can be delayed without delaying the project
• find the critical activities: must be completed on time in order not to delay the project

We use topological sorting to determine the above characteristics of the project.

The earliest occurrence time of an event
EOT(j)= max(earliest completion times of all activities preceding the event)
EOT(source) = 0

The earliest completion time of an activity
ECT(j,k) is equal to EOT(j) + duration(j,k)

Algorithm to compute EOT and ECT

1. Sort the nodes topologically
2. For each event j: initialize EOT(j) = 0
3. For each event i in topological order
For each event j adjacent from i:

            ECT(i,j) = EOT(i)+ duration (i,j)
            EOT(j) = max(EOT(j) , ECT(i,j))

Algorithm to find the slack of activities: latest occurrence time LOT(j)

LOT(sink) = EOT(sink)

Here we use the reverse topological order

For each non-sink event i in the reverse topological order:

            LOT(i) = min(LOT(j) – duration(i,j))

            For each activity (i,j)
                        Slack(i,j) = LOT(j) – ECT(i,j)

Critical activities: slack(j) = 0
Critical path in the project: all edges are activities with slack = 0

Complexity: O(V + E) with adjacency lists, O(V²) with adjacency matrix

Example