Critical Path and Slack Time

Project Management

Lab Objective

This lab is designed to give you experience with:

1. graphs, and
2. algorithm development

---

Overview

PERT charts are frequently used in business to organize projects. A PERT chart is a graph that shows the tasks that comprise a project and dependencies among the tasks. The tasks represent vertices and the dependencies represent edges. If A and B are two tasks, then an edge from A to B indicates that task A must be completed before task B can begin. Each task has an estimate of the time it will take to complete that task. In a real PERT chart each task would have an optimistic and pessimistic time, as well as a most-probable time but we will simplify matters by only dealing with a single estimated time.

A PERT chart is used to find the longest path through the graph. This longest path represents the critical path, since the tasks on this path must be started as soon as all predecessor tasks have been completed in order for the project to finish in the minimum amount of time. In contrast, tasks that are not on the critical path can be delayed for some period without affecting the completion time of the project.

Once the critical path is computed one can compute the amount of "slack" time associated with a task. The slack time for a task is the difference between its latest possible starting time and earliest possible starting time, where latest possible starting time is defined as the last time at which the task could be started and still allow the project to be completed in the minimum amount of time. Project managers can use slack times to figure out if it is feasible to divert resources from tasks with large slack times to tasks on the critical path so as to reduce the overall duration of the project.

The following figure shows an example PERT chart:

The first number above each node represents the time to complete that task and the second number represents the slack time for that task. The critical path is A-E-F-G and the minimum completion time is 70 (10 + 25 + 25 + 10). The slack for D is calculated by finding its earliest and latest possible start time. Its earliest start time is 25 (AA + B) and the latest it can start is 40 (70 - G - D) so its slack time is 15.

---

Problem Statement

You are going to read a file contain task and dependency information and then compute: 1) the critical path, 2) the length of the critical path, and 3) the slack time associated with each task. The file name should be a command line argument and you should read the file using the C++ Fields library.

Lines in the input file can have one of the following two formats:

1. task task-name task-time
2. edge fromTask toTask

task and edge are keywords that identify the type of data contained on that line. task-name, fromTask, and toTask are one word character strings and task-time is an integer. You cannot assume that all tasks will precede all edges but you may assume that the from and to tasks must have already been defined when an edge is read.

---

Example Executable

You can find an example executable in ~bvz/courses/302/labs/lab8/pert and a sample input file in project1. project1 encodes the graph shown above. Here would be an example output from running the program on the above graph:

cetus3> pert project1
Critical Path: A E F G
Length: 70
Slack Times
    A           0
    AA         15
    B          15
    C          10
    D          15
    E           0
    F           0
    G           0

Under slack times, the tasks should be indented 4 spaces and left-justified with 15 characters of space allotted. The slack times should be right-justified with 3 characters of space allotted.

Make sure that you handle the case where there is more than one critical path. For example, try changing the task time for AA to 30 and running my example executable. Then change AA back to 15 and change C to 25 and see what happens.