- Forward


Critical Path Methods
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back SMYC Forward
  • The Question:
    • How long will it take to complete a specific (design or implementation) project (or part of a project)?
  • A Review of the Issues:
    • Units Matter
    • Task Details Matter
    • Task Dependencies Matter
    • Personnel Capabilities Matter
Some History
Back SMYC Forward
  • The 1900s:
    • Gantt Charts
  • The 1950s:
    • PERT - used time estimates
    • CPM - used time and cost estimates
  • Since Then:
    • A number of techniques have been developed, all of which use the term "critical path"
An Example
Back SMYC Forward

The Input Data

pert-example_times-and-dependencies
Learning From An Example
Back SMYC Forward
  • Apparently:
    • It's possible to put all of the necessary information in a table
  • Unfortunately:
    • The table can be confusing
  • Allaying the Confusion:
    • Use some discrete math (i.e., a graph)
Vertices
Back SMYC Forward
cpm_vertex
Building the Graph
Back SMYC Forward

Getting Started

cpm-example_task-1
Building the Graph (cont.)
Back SMYC Forward

Adding Dependencies

cpm-example_task-1-2-3-4
Building the Graph (cont.)
Back SMYC Forward

The Entire Process

Building the Graph (cont.)
Back SMYC Forward

The Complete Graph

cpm-example_task-all
Earliest Times
Back SMYC Forward
  • Earliest Initiation Time:
    • \(I^'_i\) is the initiation time for task \(i\) assuming the preceding tasks are completed as early as possible
  • Earliest Completion Time:
    • \(C^'_i = I^'_i + T_i\)
Earliest Initiation Time
Back SMYC Forward
  • For the Initial Task:
    • 0
  • For Other Tasks:
    • \(I^'_j = \max_{i \in {\cal P}_j} C^'_i\) where \({\cal P}_j\) is the set of prerequisite tasks for task \(j\)
Earliest Times (cont.)
Back SMYC Forward

Visualization for Task 1

cpm-example_earliest-1
Earliest Times (cont.)
Back SMYC Forward

Visualization for Tasks 2, 3, and 4

cpm-example_earliest-2-3-4
Earliest Times (cont.)
Back SMYC Forward

Visualization for Task 5

cpm-example_earliest-5
Earliest Times (cont.)
Back SMYC Forward

The Entire Process

Earliest Times (cont.)
Back SMYC Forward

The Entire Graph

cpm-example_earliest-all
Latest Times
Back SMYC Forward
  • Latest Completion Time:
    • \(C^"_i\) is the last time task \(i\) can be completed without delaying the project beyond its earliest time
  • Latest Initiation Time:
    • \(I^"_i = C^"_i - T_i\)
Latest Completion Time
Back SMYC Forward
  • For the Last Task:
    • The earliest completion time
  • For Other Tasks:
    • \(C^"_i = \min_{j \in {\cal S}_i} I^"_j\) where \({\cal S}_i\) is the set of tasks that are subsequent to task \(i\)
Latest Times (cont.)
Back SMYC Forward

Visualization for Tasks 14

cpm-example_latest-14
Latest Times (cont.)
Back SMYC Forward

Visualization for Tasks 13

cpm-example_latest-13
Latest Times (cont.)
Back SMYC Forward

Visualization for Tasks 7 to 14

cpm-example_latest-7-to-14

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.)
Back SMYC Forward

The Entire Process

Latest Times (cont.)
Back SMYC Forward

The Entire Graph

cpm-example_latest-all
Slack Times
Back SMYC Forward
  • Intuition:
    • The difference between the latest completion time and the earliest completion time
  • Formally:
    • \(S_i = C^"_i - C^'_i\)
Slack Times (cont.)
Back SMYC Forward

The Entire Process

Slack Times (cont.)
Back SMYC Forward

The Entire Graph

cpm-example_slack-all
Identifying the Critical Path
Back SMYC Forward
  • Definition:
    • The tasks that can't be delayed without delaying the project
  • Process:
    • Find the tasks that have a slack of \(0\)
Identifying the Critical Path (cont.)
Back SMYC Forward

The Entire Process

There's Always More to Learn
Back -