Eleven software tasks depend on each other. EyeProlog computes the earliest start and finish of every task, the project’s finish date, and the chain of tasks that leaves no slack. That chain is the critical path, and any delay on it delays the whole project.
Run it in the playground · Source
A task can start only when all of its predecessors have finished. So its earliest start is the latest finish among its predecessors, and its finish is that start plus its own duration.
The project ends when its last task ends. The critical tasks are the ones you reach by walking back from that last task, each time to the predecessor that finished last.
task(requirements, 2).
task(architecture, 3).
task(api_design, 2).
task(database, 4).
task(backend, 6).
depends(architecture, requirements).
depends(api_design, requirements).
depends(database, architecture).
depends(backend, api_design).
depends(backend, database).
task(Name, Duration) gives a duration in project time units, and
depends(Task, Predecessor) is one edge of the network. The full file has
eleven tasks and fourteen edges, ending in launch.
earliest_start(Task, 0) :-
task(Task, _duration),
\+ depends(Task, _pred).
earliest_start(Task, Start) :-
depends(Task, _pred),
aggregate_max(Finish, Pred,
(depends(Task, Pred), finish_time(Pred, Finish)),
Start, _criticalpred).
finish_time(Task, Finish) :-
task(Task, Duration),
earliest_start(Task, Start),
(Finish is Start + Duration).
A task with no predecessors starts at 0. Any other task starts at the maximum
predecessor finish, which aggregate_max/5 computes. earliest_start/2 and
finish_time/2 are declared with :- table, so each task’s times are computed
once and reused by every query that needs them.
eyeprolog examples/critical-path-schedule.pl
critical_path_answer(project_finish, 23).
critical_path_answer(critical_task, launch).
critical_path_answer(critical_task, security_review).
critical_path_answer(critical_task, integration).
critical_path_answer(critical_task, backend).
critical_path_answer(critical_task, database).
critical_path_answer(critical_task, architecture).
critical_path_answer(critical_task, requirements).
critical_path_answer(schedule, task(requirements, 0, 2)).
critical_path_answer(schedule, task(architecture, 2, 5)).
The project takes 23 units. Seven tasks are critical. The other eleven answers
give each task’s start and finish (two are shown here). frontend, auth,
api_design, and load_test have slack: they can slip a little without moving
the finish date.
step(project_finish(23),
rule(32),
['Finish' = 23],
[aggregate_max(Key, Value, finish_time(Value, Key), 23, launch)]).
step(earliest_start(backend, 9),
rule(29),
['Task' = backend, 'Start' = 9],
[depends(backend, api_design),
aggregate_max(Key, Value, (depends(backend, Value), finish_time(Value, Key)), 9, database)]).
The project finishes at 23 because the largest finish time belongs to
launch. The backend starts at 9 because, of its two predecessors, database
finishes last, at 9. That is why database lies on the critical path and
api_design does not.
condition('C1', resolution, ok, 105).
condition('C5', re_decision, ok, 11).
condition('C6', boundary_consistency, ok, 1).
obligation(builtin, theory_scoped, aggregate_max(A, B, finish_time(B, A), 23, launch)).
obligation(absent, theory_scoped, \+ depends(requirements, A)).
steps(128).
trusted(12).
verdict(checked_with_obligations).
The checker replays 105 rule and fact steps and recomputes 11 arithmetic steps.
Twelve steps are obligations: the eleven maxima and the claim that
requirements has no predecessor. A maximum over the program’s own
finish_time/2 cannot be recomputed without running the program, so the
verdict is checked_with_obligations. The proof is valid provided those
twelve conclusions hold, and the file lists every one of them.
frontend take 9 units instead of 5. Does the critical path change,
and what is the new finish date?depends(launch, frontend). Which answers change, and why not the finish
date?--goal 'critical_task(T)'.Learn more in The Art of EyeProlog, Chapter 8 (collecting and choosing answers) and Chapter 13 (tabling).