CPM / PERT — Project Scheduling Toolkit

A Python implementation of the Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) for project planning, scheduling, and probabilistic analysis.

Built for the Operations Research course — zero external dependencies beyond matplotlib (optional, for visualizations) and tabulate (for pretty-printed tables).

The Algorithm at a Glance

Method	Duration Model	What It Tells You
CPM	Deterministic (single value per activity)	Critical path, float/slack, project duration
PERT	Probabilistic (optimistic, most likely, pessimistic)	Expected duration, variance, probability of meeting a deadline

CPM Pipeline

Activities → Forward Pass → Backward Pass → Float → Critical Path

Forward Pass: Computes Early Start (ES) and Early Finish (EF) for every activity.
- ESⱼ = max(EFᵢ) for all predecessors i of j
- EFⱼ = ESⱼ + dⱼ
Backward Pass: Computes Late Start (LS) and Late Finish (LF).
- LFᵢ = min(LSⱼ) for all successors j of i
- LSᵢ = LFᵢ - dᵢ
Total Float (Slack): TF = LS − ES (or LF − EF)
Critical Path: Activities with TF = 0 — any delay here delays the whole project.

PERT Extension

Uses the beta distribution for each activity's duration:

Expected duration:  tₑ = (O + 4M + P) / 6
Variance:           σ² = ((P − O) / 6)²

Where:

O = optimistic estimate (everything goes right)
M = most likely estimate (business as usual)
P = pessimistic estimate (everything goes wrong)

The project duration follows a normal distribution (Central Limit Theorem), so we can compute:

Probability of completion by a given date: P(T ≤ target)
Days needed for a given confidence level (e.g., 95% confidence)

Project Structure

cpm_pert/
├── main.py                         # CLI entry point
├── pyproject.toml                  # Project configuration (uv)
├── README.md                       # You are here
│
├── cpm_pert/                       # Library package
│   ├── __init__.py                 # Public API exports
│   ├── activity.py                 # Data models: Activity, CPMProject, PERTProject, PertEstimate
│   ├── forward_pass.py             # ES / EF calculation
│   ├── backward_pass.py            # LS / LF / Total Float calculation
│   ├── critical_path.py            # Critical path identification & table report
│   ├── pert.py                     # PERT probabilistic metrics & analysis
│   └── visualize.py                # Network diagram & Gantt chart (matplotlib)
│
├── tests/
│   ├── test_cpm.py                 # 10 unit tests
│
└── .venv/                          # Virtual environment (uv)

Setup

Prerequisites

Python ≥ 3.14
uv (fast Python package manager)

Installation

# 1. Clone or navigate to the project directory
cd /home/sergio/Documents/Escuela/Investigacion\ operaciones/cpm_pert

# 2. Create virtual environment and install dependencies
uv sync

# 3. Activate the virtual environment (optional, uv run works without it)
source .venv/bin/activate

That's it. No extra steps needed.

Quick Start

# Run the bundled example (from the parcial)
uv run python main.py

# With PERT probabilistic analysis
uv run python main.py --pert

# With visualizations
uv run python main.py --network --gantt

# Bigger project (12 activities)
uv run python main.py --build

# Everything at once
uv run python main.py --pert --network --gantt

Example Output

+-------+-------+------+------+------+------+-----------+--------+
|  Act  |  Dur  |  ES  |  EF  |  LS  |  LF  |  Holgura  |  Crít  |
+=======+=======+======+======+======+======+===========+========+
|   A   |   2   | 0.0  | 2.0  | 0.0  | 2.0  |    0.0    |   ✓    |
|   B   |   3   | 2.0  | 5.0  | 2.0  | 5.0  |    0.0    |   ✓    |
|   C   |   6   | 2.0  | 8.0  | 4.0  | 10.0 |    2.0    |        |
|   D   |   5   | 5.0  | 10.0 | 5.0  | 10.0 |    0.0    |   ✓    |
|   E   |   3   | 10.0 | 13.0 | 10.0 | 13.0 |    0.0    |   ✓    |
|   F   |   0   | 10.0 | 10.0 | 13.0 | 13.0 |    3.0    |        |
|   G   |   4   | 13.0 | 17.0 | 13.0 | 17.0 |    0.0    |   ✓    |
+-------+-------+------+------+------+------+-----------+--------+

📏 Project duration: 17.0 days
🔴 Critical path: A → B → D → E → G

CLI Usage

python main.py [OPTIONS]

Option	Description
`--pert`	Include PERT probabilistic analysis
`--build`	Use the larger construction project (12 activities)
`--network`	Show the network dependency graph
`--gantt`	Show the Gantt chart
`--save PATH`	Save charts to disk (appends `_network.png` / `_gantt.png`)

Examples

# PERT analysis with confidence levels
uv run python main.py --pert

# Save visualizations to files
uv run python main.py --network --gantt --save ./output/chart

# Full analysis: larger project + PERT + network graph
uv run python main.py --build --pert --network

Library Usage

You can import and use the library directly in your own scripts.

CPM — Deterministic

from cpm_pert.activity import Activity, CPMProject
from cpm_pert.forward_pass import forward_pass
from cpm_pert.backward_pass import backward_pass
from cpm_pert.critical_path import find_critical_path, print_schedule

# 1. Define activities
project = CPMProject()
project.add_activities(
    Activity("A", "Foundation", 3),
    Activity("B", "Framing", 5, predecessors=["A"]),
    Activity("C", "Roofing", 4, predecessors=["B"]),
    Activity("D", "Electrical", 3, predecessors=["B"]),
    Activity("E", "Finishing", 2, predecessors=["C", "D"]),
)

# 2. Run the CPM pipeline
forward_pass(project)
backward_pass(project)
find_critical_path(project)

# 3. Print results
print_schedule(project)

# 4. Access data programmatically
for act in project.activities.values():
    print(f"{act.id}: ES={act.early_start}, EF={act.early_finish}, "
          f"LS={act.late_start}, LF={act.late_finish}, "
          f"Float={act.total_float}, Critical={act.is_critical}")

critical_ids = [aid for aid, a in project.activities.items() if a.is_critical]
print(f"Critical path: {' → '.join(critical_ids)}")

PERT — Probabilistic

from cpm_pert.activity import Activity, CPMProject, PertEstimate
from cpm_pert.forward_pass import forward_pass
from cpm_pert.backward_pass import backward_pass
from cpm_pert.critical_path import find_critical_path
from cpm_pert.pert import compute_pert_metrics

# 1. Define activities with PERT estimates
project = CPMProject()
project.add_activities(
    Activity("A", "Requirements",
             pert=PertEstimate(optimistic=1, most_likely=2, pessimistic=4)),
    Activity("B", "Development",
             pert=PertEstimate(optimistic=4, most_likely=7, pessimistic=12),
             predecessors=["A"]),
    Activity("C", "Testing",
             pert=PertEstimate(optimistic=1, most_likely=2, pessimistic=3),
             predecessors=["B"]),
)

# 2. Run CPM pipeline
forward_pass(project)
backward_pass(project)
find_critical_path(project)

# 3. Compute PERT metrics
pert = compute_pert_metrics(project)

# 4. Query probabilities
prob_15 = pert.probability_of_completion(15.0)  # P(T ≤ 15 days)
prob_20 = pert.probability_of_completion(20.0)  # P(T ≤ 20 days)

# 5. Days needed for a given confidence
days_90 = pert.days_for_probability(0.90)       # 90% confidence
days_95 = pert.days_for_probability(0.95)       # 95% confidence

print(f"Expected project duration: {pert.critical_path_duration:.2f} days")
print(f"Variance: {pert.critical_path_variance:.4f}")
print(f"P(T ≤ 15 days): {prob_15 * 100:.1f}%")
print(f"P(T ≤ 20 days): {prob_20 * 100:.1f}%")
print(f"90% confidence: {days_90:.2f} days")

Visualizations

Network Diagram

Shows the activity dependency graph. Red nodes are critical activities, blue nodes are non-critical. Arrow direction indicates predecessor → successor.

uv run python main.py --network

What to look for:

Red nodes = critical path (any delay here delays the whole project)
Blue nodes = non-critical (have float/slack)
Numbers below each node show the activity duration

Gantt Chart

Shows each activity as a horizontal bar. The solid bar is the activity duration; the transparent extension shows available float.

uv run python main.py --gantt

What to look for:

Red bars = critical activities (no float)
Blue bars = non-critical activities
Transparent extensions = available float for each activity
Dashed red line = project completion date

Saving to files

uv run python main.py --network --gantt --save ./my_project
# Produces: ./my_project_network.png, ./my_project_gantt.png

Note: On headless servers (no display), charts are saved with the Agg backend automatically. Use --save to persist them.

Running Tests

uv run pytest tests/ -v

All 10 tests cover:

Test	What it verifies
`test_simple_linear`	Forward/backward pass on A→B→C chain
`test_concurrent`	Parallel activities, correct critical path
`test_pert_estimate`	Beta distribution formulas (tₑ, σ²)
`test_pert_project`	Full PERT pipeline with mixed estimates
`test_pert_probability`	Completion probability calculations
`test_pert_ppf`	Normal quantile function (Acklam approximation)
`test_float_precision`	Zero-float tolerance for critical detection
`test_empty_predecessors`	Activities without predecessors start at 0
`test_build_schedule`	Table output produces correct number of rows
`test_pert_invalid_estimates`	O ≤ M ≤ P validation

uv run pytest tests/ -v --tb=short

API Reference

`Activity`

Represents a single activity in the project network.

Field	Type	Default	Description
`id`	`str`	—	Unique identifier (e.g., `"A"`, `"Task1"`)
`description`	`str`	`""`	Human-readable description
`duration`	`float`	`0.0`	Deterministic duration (CPM)
`predecessors`	`list[str]`	`[]`	IDs of activities that must precede this one
`pert`	`PertEstimate \| None`	`None`	PERT probabilistic estimate (overrides `duration`)

Computed fields (populated after forward/backward pass):

Property	Type	Description
`early_start` / `early_finish`	`float`	Forward pass results
`late_start` / `late_finish`	`float`	Backward pass results
`total_float`	`float`	`LS − ES`
`is_critical`	`bool`	`True` if `total_float ≈ 0`
`effective_duration`	`float`	`pert.expected` if PERT is set, else `duration`
`pert_variance`	`float`	PERT variance if applicable

`CPMProject`

Container for a set of activities and the CPM analysis results.

Method	Description
`add_activity(activity)`	Add a single Activity
`add_activities(*activities)`	Add multiple activities at once
`get_activity(id) -> Activity`	Look up an activity by ID
`critical_activities -> list[Activity]`	All critical activities

Field	Type	Description
`activities`	`dict[str, Activity]`	Activity lookup by ID
`project_duration`	`float`	Total project duration (max EF, set by forward_pass)

`PERTProject`

Probabilistic project analysis, built after CPM computation.

Method	Description
`probability_of_completion(target_days) -> float`	P(T ≤ target) using normal CDF
`days_for_probability(probability) -> float`	Inverse: days needed for a given confidence level

Field	Type	Description
`project_cpm`	`CPMProject`	The underlying CPM project
`critical_path_duration`	`float`	Sum of expected durations on critical path
`critical_path_variance`	`float`	Sum of variances on critical path

`PertEstimate`

Immutable container for PERT's three-point estimate.

Field	Type	Constraint
`optimistic`	`float`	≤ `most_likely`
`most_likely`	`float`	≤ `pessimistic`
`pessimistic`	`float`	≥ `most_likely`

Property	Formula	Description
`expected`	`(O + 4M + P) / 6`	Expected duration (beta distribution mean)
`variance`	`((P − O) / 6)²`	Duration variance
`std_dev`	`√variance`	Standard deviation

Core Functions

Function	Input	Output	Description
`forward_pass(project)`	`CPMProject`	`CPMProject` (mutated)	Computes ES/EF for all activities
`backward_pass(project)`	`CPMProject` (post-forward)	`CPMProject` (mutated)	Computes LS/LF/total_float
`find_critical_path(project)`	`CPMProject` (post-backward)	`CPMProject` (mutated)	Marks activities with float ≈ 0 as critical
`print_schedule(project)`	`CPMProject`	stdout	Prints the full schedule as a table
`build_schedule(project)`	`CPMProject`	`list[dict]`	Returns schedule data as a list of dicts
`get_critical_path_ids(project)`	`CPMProject`	`list[str]`	Returns critical path activity IDs in order
`compute_pert_metrics(project)`	`CPMProject`	`PERTProject`	Computes probabilistic metrics from critical path
`plot_network(project, ...)`	`CPMProject`	`plt.Figure`	Draws the dependency graph
`plot_gantt(project, ...)`	`CPMProject`	`plt.Figure`	Draws the Gantt chart

Dependencies

Package	Version	Required?	Purpose
`tabulate`	≥ 0.10.0	✅ Yes	Pretty-printed schedule tables
`matplotlib`	≥ 3.11.0	✅ Yes	Network diagram & Gantt charts
`numpy`	≥ 2.x	🔄 Transitive	Required by matplotlib only
`pytest`	≥ 9.1.1	❌ Dev only	Unit testing

Why no networkx?

The dependency graph is built from scratch using a topological level sorting algorithm — no need for a full graph library for DAG-based project scheduling.

License

Educational project — free to use, modify, and share for academic purposes.

Part of the Operations Research coursework — "Investigación de Operaciones".

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
cpm_pert		cpm_pert
tests		tests
.gitignore		.gitignore
.python-version		.python-version
README.md		README.md
main.py		main.py
pyproject.toml		pyproject.toml
requirements.txt		requirements.txt
uv.lock		uv.lock

Folders and files

Latest commit

History

Repository files navigation

CPM / PERT — Project Scheduling Toolkit

Table of Contents

The Algorithm at a Glance

CPM Pipeline

PERT Extension

Project Structure

Setup

Prerequisites

Installation

Quick Start

Example Output

CLI Usage

Examples

Library Usage

CPM — Deterministic

PERT — Probabilistic

Visualizations

Network Diagram

Gantt Chart

Saving to files

Running Tests

API Reference

Activity

CPMProject

PERTProject

PertEstimate

Core Functions

Dependencies

Why no networkx?

License

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Contributors

Uh oh!

Languages

`Activity`

`CPMProject`

`PERTProject`

`PertEstimate`

Packages