A project has 50-300 activities with given durations and precedence. Which chain is the longest (critical path, drives the project)? Which activities can slip without delaying the project (slack)? Under uncertain durations, what is the probability of finishing by the target date? CPM (Kelley-Walker 1959) gives the deterministic answer; PERT (Malcolm-Roseboom-Clark-Fazar 1959) the probabilistic one — the engine inside every project management tool.
In plain words
Sound familiar?
- We manage 50-300 activity construction projects (residential, mall, motorway, small factory); the planner draws a Gantt chart and says 'the project takes 18 months', but which chain is critical and which activities have slack tolerance is not numerical — it is intuition.
- The tender spec says 'CPM/PERT mandatory' and we hand in a Gantt; but we do not report early-start, late-start, total-slack, free-slack for every activity — we hand in only a total duration.
- An activity slipped; will the project slip a week or not — we do not know whether it is on the critical path, the planner says 'let me compute' and returns 2 hours later.
- A supplier reported a 3-week slip on one item; what is its impact on the project completion date, which downstream activities slip, what is the contingency plan — we cannot see this numerically.
- On a public-works tender the daily delay penalty is 0.5-1.0% of the contract; we must manage this penalty numerically, but probabilistic analysis (PERT) is not done — an 'optimistic schedule' is handed in, and it slips.
- On an industrial plant erection (factory build-out, power plant, refinery unit) there are 200+ activities, multiple parallel crews, the critical path races across multiple chains — manual tracking is not enough.
- A software or corporate-IT investment project (ERP migration, data-centre move) is 80-150 activities; durations are estimated optimistically, the schedule risk of missing the target date is not numerical — the board sees an intuition-based 'we are on plan' report.
Why it matters
How it's solved
Technical depth
How it's solved
Technical depthIn one sentence: Enter the activity list + precedence relationships, run a forward pass to compute each activity’s earliest finish, run a backward pass to compute its latest finish; activities with zero slack form the critical path — to shorten the project, you must invest only in activities on that path.
In the Operations Research (the discipline that uses math and computers to solve business decisions) literature this problem is studied as two paired classical techniques: Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT). CPM was developed in 1959 for chemical-plant maintenance planning, PERT in the same year for a missile programme; together they became the backbone of modern project management. CPM is resource-unconstrained — only durations + precedence; PERT makes this probabilistic (durations as random variables). #007 RCPSP layers resource constraints on top; #066 Stochastic RCPSP produces a policy under uncertainty. CPM/PERT is the foundation of the chain — the core engine under every project management tool. Three stages:
1. Modelling. Input data: (a) Activity list — 50-300 activities (e.g. a residential block project: excavation, foundation concrete, columns, floor slabs, roof, façade, MEP — mechanical/electrical/plumbing, finishing, landscaping). For each activity: name, deterministic duration (CPM) or three-time estimate a-m-b (PERT), required resources (crew, machine — under CPM these are recorded but not constrained). (b) Precedence relations — which activity must follow which; classical ‘finish-to-start’ (predecessor finishes, successor starts), extended ‘start-to-start’, ‘finish-to-finish’, ‘start-to-finish’ with lag/lead times; relations modelled as a directed acyclic graph (DAG). (c) Activity graph representation — two standards: activity-on-arrow (AoA) — activities as arrows, events as nodes; activity-on-node (AoN) — activities as nodes, precedence as arrows; modern software uses AoN, more flexible. (d) Probabilistic estimates (for PERT) — for each activity an optimistic a, most-likely m, pessimistic b; beta-distribution approximation: expected duration (a + 4m + b) / 6, variance ((b - a) / 6) squared. (e) Time-cost trade-off data (for crashing) — for each activity a normal-duration/normal-cost and a crash-duration/crash-cost pair; how much does shortening the activity by one day cost.
2. Solution method. (a) CPM forward pass — starting from project start (Earliest Start = 0), in topological order, compute each activity’s earliest start (ES) and earliest finish (EF): ES = maximum EF over predecessors; EF = ES + duration. At the end, project completion = last activity’s EF = project duration. (b) CPM backward pass — starting from the project end (Latest Finish = project duration), in reverse, compute each activity’s latest finish (LF) and latest start (LS): LF = minimum LS over successors; LS = LF - duration. (c) Slack computation — for each activity, total slack TS = LS - ES = LF - EF (delay tolerated without slipping the project), free slack FS = min ES over successors minus this activity’s EF (delay tolerated without slipping the next activity). Critical activity: TS = 0. Critical path: the chain of critical activities running from project start to end (multiple paths possible). The algorithm is polynomial on the activity graph — O(n + m) for n activities and m precedence relations, in seconds. (d) PERT analysis — compute each activity’s expected duration (a + 4m + b) / 6, run the CPM forward/backward pass on expected durations; critical path variance = sum of variances of activities on it; by the central limit theorem project completion time is approximately normal, expected duration = critical path length, standard deviation = square root of critical path variance; probability of finishing by target date = Phi((target - expected) / standard deviation). Caveat: in projects with many parallel near-critical paths the analytical formula understates the true variance, Monte Carlo simulation is preferred (sample each activity duration N times, run CPM on each sample, P10/P50/P90 completion dates emerge from the distribution). (e) Time-cost trade-off (crashing) — to shorten the project at a cost, accelerate critical-path activities; linear programming (LP) formulation by Kelley and Walker 1959 classical extension. (f) Critical chain (Critical Chain Project Management, Goldratt 1997) — addresses CPM’s failure to account for resource conflicts; recomputes the critical path under resource constraints (resource-constrained critical path), places a shared project buffer and feeding buffers between activities. The bridge to RCPSP (#007).
3. Field integration. Output is four-layered: (a) Activity table — for each activity ES, EF, LS, LF, TS, FS; critical activities (TS = 0) and critical path(s) flagged. If PERT is enabled, expected duration and standard deviation per activity; project-level P10/P50/P90 completion. (b) Gantt chart — activities on the time axis, critical path coloured, slack bars visible; the planner sees at a glance which activity is real risk. (c) Downstream propagation report — if activity X slips by d days, what the project impact is and which downstream activities shift; the numerical tool of risk management. (d) Crashing table — for each candidate activity, the cost per day shortened, and the maximum reduction achievable per budget. End-to-end flow: project management software runs the CPM/PERT engine, ERP work-item and supplier-date updates feed it, output is the planner’s screen + field mobile app; on a delay report the recomputation is 5-15 seconds, new critical path and impact report automatic. Quarterly project committee: did the critical path change (new critical activities emerge), slack consumption rate, target-date hit-rate trend.
Alternatives
Manual + planner + spreadsheet
FreeZero licence
Who it fits: Small project (30-80 activities), single project, experienced planner
- + Zero software cost
- + Planner experience stays in front
- + Flexible — site changes handled quickly
- + Training overhead low
- − Running the forward/backward pass manually on 100+ activities produces errors
- − Slack analysis in a spreadsheet is fragile — the critical path can be mis-flagged
- − PERT probabilistic analysis not practical by hand
- − Propagation chain not visualised
- − A tender audit asking for a 'CPM report' cannot easily be answered
Local project management software
Enterprise$1,500-10,000 licence + $700-3,000/year maintenance (regional SMB)
Who it fits: Mid project (80-200 activities), 3-10 parallel projects, stable planner team
- + Local-language UI and support
- + Progress billing + cost integrated
- + A classical CPM engine usually present
- − PERT probabilistic module usually absent or shallow
- − Crashing (time-cost trade-off) LP module absent
- − Critical-chain approach (resource-constrained critical path + buffer placement) support weak
- − Monte Carlo simulation limited
International project management software
Enterprise$5,000-30,000/licence/year or $30K-200K enterprise
Who it fits: Large contractor (200+ activity complex projects), public works + industrial plant
- + Mature CPM engine, forward/backward pass + slack analysis standard
- + PERT + Monte Carlo simulation module
- + Critical-chain module (resource-constrained critical path + project buffer + feeding buffers)
- + Crashing (LP-based time-cost) module
- + Earned Value Management integration
- + Multi-project critical-path visibility
- − High licence + long (3-6 month) rollout
- − Local-language support limited, steep learning curve
- − Customising to local tender specs extends the project
Open-source solver + custom CPM/PERT module
Open SourceLicence free; in-house build 8-16 weeks or $10K-30K consulting
Who it fits: Contractor with a tech team, ERP integration desired, repeating project type
- + No licence cost
- + CPM forward/backward pass algorithm is easy on open-source solvers
- + PERT Monte Carlo simulation with open-source statistical libraries
- + Fully customisable (work-item structure, reporting)
- − In-house OR specialist + project management experience required
- − User-interface development load
- − Academic prototype to field system: 6-12 months
- − Maintenance burden in-house
Recommendation
Ask in the meeting
- Does the CPM engine under the software apply a classical forward/backward pass + slack computation, or only Gantt visualisation? In a demo, walk through the algorithm steps on a 200-activity example.
- Is PERT probabilistic analysis supported — three-time estimate (a-m-b) per activity, beta-distribution approximation, project completion P10/P50/P90 distribution? Demonstrate these outputs on a sample project.
- Is Monte Carlo simulation supported — how many scenarios, which distribution types (beta, triangular, normal, lognormal), is the criticality index (probability of each activity being on the critical path) computed?
- Are total slack and free slack reported separately per activity? Is the downstream propagation matrix (if an activity slips X days, the project impact and which successors shift) a numerical output?
- Is a crashing (time-cost trade-off) module available — cost per activity shortened, maximum reduction per budget; is it solved with a systematic linear-programming formulation, or with a heuristic?
- Is the critical-chain approach supported — resource-constrained critical-path recomputation, project buffer and feeding buffer placement?
- When a supplier or the field reports an activity slip, how fast does the system recompute and present the new critical path + propagation effect to the operations centre? Is bidirectional ERP/MES integration available?
- If the contract ends, in which standard format (XER, MPP, CSV, XML, JSON) can we export the activity list, precedence relations, CPM/PERT analysis history, propagation matrices and crashing decisions?
Technical details
Editor’s note
In plain speech this problem is called the “work schedule”, “Gantt plan” or “project calendar”. In the academic literature it carries two paired foundational names: the deterministic decision is the Critical Path Method (CPM), the probabilistic extension is the Program Evaluation and Review Technique (PERT). CPM was developed by Kelley and Walker (1959) for DuPont chemical-plant maintenance planning; PERT by Malcolm, Roseboom, Clark and Fazar (1959) for the US Navy Polaris fleet ballistic missile program — the same year, the birth date of modern project management.
Distinction from #007 RCPSP and #066 Stochastic RCPSP: CPM (#098) is resource-unconstrained — only activity durations + precedence, critical path = longest-duration path; the algorithm is polynomial (seconds). RCPSP (#007) layers resource constraints on top — some activities share a crew / machine / crane and cannot overlap; the problem is NP-hard, MIP/CP/metaheuristic solvers required. Stochastic RCPSP (#066) under duration uncertainty produces a policy instead of a schedule — a “given this state, start this activity” mapping. CPM is the foundation stone; the other two are built on it. In a software-vendor demo, “we support CPM” is not enough — does the engine still work when resource constraints are added (RCPSP), and does it produce a policy under uncertainty (Stochastic RCPSP) are separate questions.
The most-skipped point in the sector: early-start vs late-start + free-slack vs total-slack distinction. In daily practice only the “critical path length” and the “project end date” are usually discussed, but every activity has four core numbers: early-start (ES) — earliest it can start; late-start (LS) — latest it must start without slipping the project; total slack (TS) — how much it can slip without slipping the project = LS - ES; free slack (FS) — how much it can slip without slipping the next activity. Without reporting all four per activity, risk management is shallow — if an activity slips, total slack 5 days means the project is fine, but free slack 0 means the successor crew sits idle. Second skipped point: PERT’s analytical formula understates true variance. The classical PERT formula (a + 4m + b) / 6 and ((b - a) / 6) squared sums the activities on a fixed critical path; in real projects there are parallel near-critical paths and one of them may turn out to be critical in the realised execution — the “critical path” is not a fixed line, it is a probabilistic property. Monte Carlo simulation (sample every activity N times, run CPM each time, the criticality index = frequency of being on the critical path) addresses this. Third skipped point: crashing decisions depend on the critical path. Shortening an activity (extra shift, more workers, parallelisation) only shortens the project if that activity is on the critical path; shortening a non-critical activity is money wasted. Crashing decisions made without running the CPM engine misallocate 30-50% of the rush budget.
A step-by-step path for an SMB
Stage 1 — Measure first, plan later. At least 2-3 completed similar projects: for each activity planned vs actual duration (for the three-time PERT estimate — optimistic-actual, most-likely-actual, pessimistic-actual), reason for slippage (weather, supplier, permit, crew shortage, scope change), which activities turned out to be critical (in actual execution), which were free. This knowledge capital without it, PERT three-time estimates stay intuitive.
Stage 2 — Activity list and precedence map. A typical residential block is 80-150 activities, a mall 150-300, a motorway 300-500, factory build-out 200-400, ERP migration 80-150, data-centre move 50-100. For each activity: name, deterministic estimate (for CPM) or three-time estimate a-m-b (for PERT), required resources (informational, not a constraint), predecessor list (precedence). Review the precedence map: some links are ‘real’ (no slab formwork before the columns are poured), some are ‘resource’ (the same crew does two activities) — resource links are modelled in RCPSP (#007), not in CPM.
Stage 3 — Pilot. 8-12 weeks. On a single mid-size project (80-200 activities) run CPM forward/backward pass + slack analysis + PERT Monte Carlo (1,000 scenarios); in parallel with the existing intuition-based plan. Success criterion written down beforehand: did the critical path change (in execution), slack consumption rate per activity, target-date error (PERT P50 vs actual), criticality-index accuracy. During the pilot, document how the CPM/PERT report changed the planner’s decision.
Stage 4 — Rollout. Over 6-12 months CPM becomes the standard across all active projects; PERT probabilistic analysis is mandatory on high-penalty projects (public works, industrial plant), optional on mid-penalty projects. The crashing module is engaged at tender stage or when a critical activity signals risk. Quarterly project committee: critical-path-change report, slack-consumption trend, PERT P50/P90 vs actual comparison, criticality index vs actual-critical comparison.
Risks — what can go wrong
Activity duration estimate bias. In practice activity durations are estimated optimistically (tender-winning pressure, planner optimism); the PERT formula (a + 4m + b) / 6 weights the ‘most likely’ estimate, but if the ‘most likely’ itself is optimistically placed the result is skewed. Fix: diversify the estimate source (planner + site supervisor + supplier separate estimates), keep the ‘pessimistic’ tail honest (look at past project actual pessimistic).
Missing precedence definitions. Some dependencies are not in the documents but exist on site (e.g. statutory inspection approval — legal precedence; rainy season — calendar precedence). Missing precedence makes the CPM output misleading — the critical path looks short on paper but is long on site. Fix: review the precedence map with the site supervisor + inspection authority + primary supplier in the same room; model calendar dependencies separately.
Real-time update latency. If site status (activity complete, percent progress) reaches the system late, the CPM engine runs on stale data — the critical path looks fine on paper but has shifted in reality. Fix: mandatory daily progress reporting via a mobile site app, automatic recomputation in 5-15 seconds on a slip, impact report pushed to the operations centre + affected field crew.
Single-supplier project-software lock-in. Without a contract clause stating “annual export in standard formats (XER, MPP, CSV, XML, JSON) of the activity list, precedence relations, CPM/PERT analysis history, slack and criticality index values, crashing decisions”, leaving the system means losing the firm’s project-management memory. The contract should explicitly list the activity library + precedence templates + historical CPM/PERT analyses as exportable in open format.
Solution method — technical view
| Approach | Typical scale | Solve time | Guaranteed optimum? |
|---|---|---|---|
| Manual + spreadsheet CPM | Small project, 30-80 activities | minutes (manual) | Yes in principle; error-prone in practice |
| Classical CPM engine (forward/backward pass) | Mid-large project, 50-500 activities | seconds | Yes (resource-unconstrained) |
| PERT analytical (beta + CLT) | 50-300 activities, duration uncertainty | seconds | Approximate (drifts on parallel paths) |
| PERT Monte Carlo simulation | 100-500 activities, multiple parallel paths | minutes-hours | Probabilistic, accurate |
| Crashing LP (time-cost) | Crashing on the critical path | seconds-minutes | Yes (LP polynomial) |
| Critical chain (Goldratt 1997) | Resource-conflicted mid project | minutes | Heuristic, sensitive to buffer placement |
| RCPSP MIP (resource-constrained, #007) | 30-100 activities + resources | minutes-hours | Yes (within bound) |
Objective function choice:
- Objective 1 — Minimise project duration (makespan): Classical CPM — critical-path length.
- Objective 2 — Minimise expected delay penalty: PERT + Monte Carlo + penalty function; risk-adjusted schedule.
- Objective 3 — Minimise total project cost: Including crashing; activity-shortening cost + delay penalty.
- Objective 4 — Maximise probability of finishing by target date: PERT P50/P90 + crashing — hitting the contractual window.
CPM/PERT variants — pick by the field:
- Classical CPM (Kelley-Walker 1959): Deterministic durations, resource-unconstrained; the core of every project management tool.
- PERT (Malcolm-Roseboom-Clark-Fazar 1959): Three-time duration estimate, beta distribution, project completion probability.
- PERT Monte Carlo: Overcomes the analytical formula’s limitation; real variance under multiple parallel paths, criticality index.
- Critical chain (CCPM, Goldratt 1997): Resource conflicts + project buffer + feeding buffers; the bridge to RCPSP.
- Time-cost trade-off (Kelley-Walker LP): Crashing critical-path activities, cost-optimal acceleration.
- Resource-constrained CPM (RCPSP, #007): Recompute the critical path under resource constraints; MIP/CP required.
Academic references
Listed in the page frontmatter under sources. Kelley-Walker (1959) and Malcolm-Roseboom-Clark-Fazar (1959) foundational; Goldratt (1997) the critical chain extension; Hillier-Lieberman (2014) modern OR textbook CPM chapter; Kerzner (2017) industrial reference. Operations Research, Management Science and the Project Management Journal publish current research; INFORMS Interfaces and PMI publications carry field deployment cases.
Sources
- Kelley Jr., J. E. and Walker, M. R. (1959). Critical-path planning and scheduling. Proceedings of the Eastern Joint Computer Conference, 160-173. Foundational CPM paper — developed for DuPont chemical-plant maintenance planning.
- Malcolm, D. G., Roseboom, J. H., Clark, C. E. and Fazar, W. (1959). Application of a technique for research and development program evaluation. Operations Research, 7(5), 646-669. Foundational PERT paper — built for the US Navy Polaris fleet ballistic missile program.
- Goldratt, E. M. (1997). Critical Chain. North River Press. Buffer-based Critical Chain Project Management (CCPM) extension.
- Kerzner, H. (2017). Project Management: A Systems Approach to Planning, Scheduling, and Controlling (12th ed.). Wiley. Industrial project management reference, CPM/PERT chapter.
- Hillier, F. S. and Lieberman, G. J. (2014). Introduction to Operations Research (10th ed.). McGraw-Hill. OR textbook CPM chapter, modern computational approaches.
- YÖK Thesis Center — keyword: ‘kritik yol’ or ‘CPM’ or ‘PERT’ or ‘proje çizelgeleme’ — 30+ theses from TR academia. tez.yok.gov.tr
Glossary
- Critical Path Method
- Foundational deterministic project-network technique: given activities with fixed durations and precedence, compute earliest and latest start/finish times and identify the longest path that drives project duration.
- Program Evaluation and Review Technique
- Probabilistic extension of CPM developed in 1958 for the US Navy Polaris program: each activity duration is a random variable from optimistic, most-likely and pessimistic estimates, yielding an expected project-completion distribution.
- Critical Path
- The longest chain of dependent tasks running from project start to finish — the chain that drives the delivery date.
- RCPSP
- Sequencing hundreds of project tasks, sizing durations, and assigning crews under precedence and resource constraints.