JMU
Critical Path Methods
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Background
Some History
An Example

The Input Data

images/pert-example_times-and-dependencies.gif
Learning From An Example
Vertices
images/cpm_vertex.gif
Building the Graph

Getting Started

images/cpm-example_task-1.gif
Building the Graph (cont.)

Adding Dependencies

images/cpm-example_task-1-2-3-4.gif
Building the Graph (cont.)

The Entire Process

Building the Graph (cont.)

The Complete Graph

images/cpm-example_task-all.gif
Earliest Times
Earliest Initiation Time
Earliest Times (cont.)

Visualization for Task 1

images/cpm-example_earliest-1.gif
Earliest Times (cont.)

Visualization for Tasks 2, 3, and 4

images/cpm-example_earliest-2-3-4.gif
Earliest Times (cont.)

Visualization for Task 5

images/cpm-example_earliest-5.gif
Earliest Times (cont.)

The Entire Process

Earliest Times (cont.)

The Entire Graph

images/cpm-example_earliest-all.gif
Latest Times
Latest Completion Time
Latest Times (cont.)

Visualization for Tasks 14

images/cpm-example_latest-14.gif
Latest Times (cont.)

Visualization for Tasks 13

images/cpm-example_latest-13.gif
Latest Times (cont.)

Visualization for Tasks 7 to 14

images/cpm-example_latest-7-to-14.gif

Task 6

\({\cal S}_6 = \{10, 13\}\)
\(C^"_6 = \min\{ I^"_{10}, I^"_{13} \} = \min\{15,21\} = 15\)
\(I^"_6 = C^"_6 - T_6 = 15 - 1 = 14\)

Latest Times (cont.)

The Entire Process

Latest Times (cont.)

The Entire Graph

images/cpm-example_latest-all.gif
Slack Times
Slack Times (cont.)

The Entire Process

Slack Times (cont.)

The Entire Graph

images/cpm-example_slack-all.gif
Identifying the Critical Path
Identifying the Critical Path (cont.)

The Entire Process