Every project has tasks that depend on each other: you can’t test before you build, or deploy before you test. Project scheduling optimization answers two questions a manager asks every week: what’s the shortest time this can take, and which tasks can’t slip without delaying everything? This lesson answers both in MATLAB with the critical path method.
Playing loads the video from YouTube. Watch on YouTube
The code uses base MATLAB only, no toolboxes, and also runs in GNU Octave. Where an example uses random numbers, your figures may differ slightly from the ones shown, because random number generators differ between versions.
The project as data
Each task has a duration and a list of tasks that must finish before it starts, its predecessors. For a small software project:
- Design: 5 days, no predecessors.
- Backend: 10 days, after Design.
- Frontend: 7 days, after Design.
- Testing: 4 days, after both Backend and Frontend.
- Deploy: 2 days, after Testing.
In MATLAB, durations go in a vector and predecessors in a cell array, one entry per task, with tasks listed so that every task comes after its predecessors:
names = {'Design', 'Backend', 'Frontend', 'Testing', 'Deploy'};
dur = [5 10 7 4 2];
pred = {[], 1, 1, [2 3], 4};
n = numel(dur);The forward pass: earliest start and finish
A task can start as soon as all its predecessors have finished, so its earliest start (ES) is the latest earliest finish (EF) among them. Walking forward through the list fills in every ES and EF, and the largest EF is the project’s length:
ES = zeros(1, n); EF = zeros(1, n);
for i = 1:n
if ~isempty(pred{i}), ES(i) = max(EF(pred{i})); end
EF(i) = ES(i) + dur(i);
end
total = max(EF);The backward pass: latest start and finish
Now walk backwards from the end. A task must finish by the time its earliest successor has to start, so its latest finish (LF) is the smallest latest start (LS) among its successors. The difference between latest and earliest start is the task’s slack: how many days it can slip without delaying the project.
LF = total * ones(1, n); LS = zeros(1, n);
for i = n:-1:1
succ = find(cellfun(@(p) any(p == i), pred));
if ~isempty(succ), LF(i) = min(LS(succ)); end
LS(i) = LF(i) - dur(i);
end
slack = LS - ES;Worked example: the schedule and its critical path
Print the table and pick out the tasks with zero slack. Those form the critical path:
fprintf('%-9s %3s %3s %3s %3s %5s\n', 'Task', 'ES', 'EF', 'LS', 'LF', 'Slack');
for i = 1:n
fprintf('%-9s %3d %3d %3d %3d %5d\n', names{i}, ES(i), EF(i), LS(i), LF(i), slack(i));
end
fprintf('Project length: %d days\n', total);
fprintf('Critical path: %s\n', strjoin(names(slack == 0), ' -> '));Task ES EF LS LF Slack
Design 0 5 0 5 0
Backend 5 15 5 15 0
Frontend 5 12 8 15 3
Testing 15 19 15 19 0
Deploy 19 21 19 21 0
Project length: 21 days
Critical path: Design -> Backend -> Testing -> DeployThe project takes 21 days, and only Frontend has room to move: it can start up to 3 days late, or take up to 3 days longer, without moving the finish date. Every other task is critical. That changes where a manager should spend effort. Adding a developer to Frontend won’t finish the project sooner; shortening Backend will, until Frontend becomes critical too.
From scheduling to optimization
The critical path tells you the shortest schedule for fixed durations. The optimization question comes next: if you can shorten some tasks at a cost, by adding people or paying for overtime, which ones should you shorten to hit a deadline for the least money? That’s a linear program, and MATLAB’s linprog (Optimization Toolbox) solves it directly. The critical path is still the starting point, because only critical tasks are worth paying to shorten.
Mistakes to avoid
- Listing a task before its predecessors: the forward pass then uses finish times that haven’t been computed yet. Sort the tasks first.
- Forgetting that more than one critical path can exist. Shorten one and another may take over.
- Treating durations as certain. Real projects add a buffer, or simulate durations, as the next lessons on forecasting do.
Try it yourself
- Shorten Backend from 10 to 7 days. What is the new project length, and which tasks are now critical?
- Add a task, Documentation, taking 6 days after Design and finishing before Deploy. Does the critical path change?
- Give each task an optimistic and a pessimistic duration, draw durations at random 1,000 times and record the project length. How often does the project finish within 21 days?
Key points
- The forward pass gives each task’s earliest start; the backward pass gives its latest start.
- Slack is the difference: how far a task can slip without delaying the project.
- Tasks with zero slack form the critical path, and only they are worth paying to shorten.
Want to go further?
I teach professionals one to one, and I build these systems for businesses. See Python AI mentoring or see what I build.