Building an External Scheduling Engine for D365 Project Operations | Part 5: Dependencies and the Critical Path

Dependencies and the critical path: forward pass, backward pass, float, and what the due date anchors

Part 3 ended with a step it did not explain: “once per affected project, propagate dependencies and recompute the critical path.” Part 4 supplied the working-time arithmetic. This part does the graph.

None of the algorithms here are new. Forward and backward passes over an activity network are fifty years old and every planner reading this learned them on a different tool. What is worth writing down is what changes when the network lives in Dataverse, when the end of the project is a due date rather than “whenever the last task finishes”, and when the planners’ reference model is Primavera P6.

1) The graph

Tasks are nodes. Dependencies are directed edges carrying a link type (FS, SS, FF, SF) and a lag in working time. Before any date arithmetic:

• Reject cycles at write time. A cycle is a data error, not a scheduling problem. Validate the dependency create in the plugin and refuse it with a message naming both tasks. Do not let the engine discover it later and loop.
• Compute a topological order once per run and walk it. The forward pass needs predecessors finished first; the backward pass needs successors first; a topological sort gives you both.
• Decide the scope of a graph. A project is the natural unit. A dependency that crosses into another project is, from this project’s point of view, an external constraint on one node: read the other task’s dates, treat them as fixed, do not try to move them. If you want true cross-project propagation, the unit becomes the program, and everything in Part 6 gets an order of magnitude bigger.
• Manual tasks are fixed nodes. A task the planner has pinned (the manual-scheduling flag from Part 1) keeps its dates; the passes propagate from it but never move it. Report the conflict if its dates violate a predecessor.

2) Forward pass: early start and early finish

Walk the topological order. For each task, early start is the latest of every predecessor-driven date and the task’s own floor:

for task in topologicalOrder:
    floor = max(project.allowedStart, task.startNoEarlierThan)
    for (pred, type, lag) in predecessorsOf(task):
        t = case type:
              FS: addWorkingMinutes(pred.EF, lag)
              SS: addWorkingMinutes(pred.ES, lag)
              FF: subWorkingMinutes(addWorkingMinutes(pred.EF, lag), task.durationMinutes)
              SF: subWorkingMinutes(addWorkingMinutes(pred.ES, lag), task.durationMinutes)
        floor = max(floor, t)
    task.ES = nextWorkingInstant(floor)
    task.EF = addWorkingMinutes(task.ES, task.remainingMinutes)

Two decisions hide in that code and both need writing down:

• Whose calendar is the lag in? Convention: the successor’s. A two-day lag before a task on a 24/7 template is 48 hours; the same lag before a Mon–Fri task can span a weekend. Pick one convention and apply it everywhere, including the Gantt.
• Remaining, not total. For a task in progress, EF is ES plus the remaining work, and ES is the later of the status date and the actual start. This is how Part 3’s status-date sweep and the critical path agree with each other.

3) Backward pass: what the project ends at

Classic CPM anchors the backward pass at the latest early finish in the network: the project ends when its last task ends, and late dates fall out of that. Maintenance work does not behave like that. A work order has a due date, and the question the planner is asking is “how late can each step start and still make it”.

So the anchor is a choice, and it has to be explicit:

The third row is where a business decision leaks into the engine. If the plan is built to finish a percentage of the way through the window, and the backward pass still anchors at the due date, then the schedule tells the planner they can finish on the due date having lost nothing. The buffer exists on paper and not in the float. Whether that buffer is protected time or just a target is not an engineering call; ask, and anchor accordingly.

endTask.LF = anchor                                   # see table
endTask.LS = subWorkingMinutes(endTask.LF, endTask.remainingMinutes)
for task in reverse(topologicalOrder) excluding endTask:
    ceiling = task.mustFinishBy or +infinity
    for (succ, type, lag) in successorsOf(task):
        t = case type:
              FS: subWorkingMinutes(succ.LS, lag)
              SS: addWorkingMinutes(subWorkingMinutes(succ.LS, lag), task.remainingMinutes)
              FF: subWorkingMinutes(succ.LF, lag)
              SF: addWorkingMinutes(subWorkingMinutes(succ.LF, lag), task.remainingMinutes)
        ceiling = min(ceiling, t)
    if task has no successors: ceiling = min(ceiling, anchor)
    task.LF = ceiling
    task.LS = subWorkingMinutes(task.LF, task.remainingMinutes)

Note the last branch: a task with no successors that is not the end task still gets the anchor as its ceiling. Without it, orphan tasks have infinite float and never show as critical, which is technically true and practically useless.

4) Float and criticality

task.totalFloat = workingMinutesBetween(task.ES, task.LS)      # negative when ES > LS
task.freeFloat  = min over successors of (succ.ES - task.EF)   # in working time
task.critical   = task.totalFloat <= criticalThreshold          # usually 0

• Do not clamp negative float to zero. Negative float is the most important number the engine produces: it is how late the plan already is. Truncating it to zero makes a late project look like a tight one.
• Float is in working time. Two tasks with the same calendar-day gap have different float on different templates. Store minutes or hours, display days per the template.
• Critical is a threshold, not a boolean property of the chain. Some planners want “near critical” at a day of float. Make the threshold a setting.

5) Constraints versus dependencies

Constraints are the planner’s overrides. The passes above already honour two of them as floors and ceilings: start no earlier than raises ES, must finish by lowers LF. The one that causes arguments is must start on.

Put a must-start-on constraint on a task whose FS predecessor finishes later than the pinned date, and there are three things an engine can do:

Our recommendation is the first, and it is worth stating why with some force: backward propagation silently rewrites work the planner did not touch. It is the one behaviour in this whole series that we would not build without a written product decision and a way to switch it off. If someone reports “the Gantt is not following the finish-to-start dependency” on a pinned task, the honest answer is that the pin won, as designed, and the fix is to show the violation clearly rather than to move the predecessor.

6) Where the numbers go

Early and late dates, float and the critical flag are all custom columns (Part 1). Two rules for writing them:

• Scheduled dates and early dates are different things. Scheduled start/finish is the plan the planner sees and edits. ES/EF/LS/LF are analysis. Whether an auto-scheduled, unconstrained task’s scheduled dates follow its early dates is a policy; document whichever you pick, and never let the analysis columns overwrite a manual task’s plan.
• One batch, tagged, per project. All CPM values for a project are written together, carrying the engine’s own marker so the task-level trigger recognises them and does not recompute anything (Part 6). Writing them one task at a time from inside that trigger is exactly the deadlock Part 3 described.

7) Full pass, every time

It is tempting to “just update the successors” when one task moves. Don’t. A full forward and backward pass over a few thousand in-memory nodes takes milliseconds; the cost of the critical path is entirely in reading and writing Dataverse, not in the arithmetic. A partial update, by contrast, is a second implementation of the same rules that has to agree with the first one in every edge case, and it will not. Dependency propagation on a single task edit (shifting direct successors by lag) is fine as the immediate, local reaction inside the task’s own pre-operation step. The critical path is always the full pass, afterwards.

8) Validation set

A small project that exercises every rule, kept as a fixture and run on every change to the engine:

1. A chain of three FS tasks: ES/EF cascade, LS/LF cascade, zero float throughout.
2. A diamond (one task fans out to two, both feed a fourth): the shorter branch carries float equal to the difference.
3. An SS with a positive lag and an FF with a negative lag, on different calendars.
4. A must-start-on pin that violates its predecessor: negative float on the predecessor, task unmoved, violation flagged.
5. A manual task in the middle of a chain: unmoved, propagates.
6. An orphan task: takes the anchor as its ceiling, has finite float.
7. A due-date anchor and a target-finish anchor on the same project, and the float difference between them equals the buffer.
8. A dependency create that would form a cycle: rejected with both task names.

Summary

Build the graph, refuse cycles, walk it forward and backward in working time, anchor the end task to whatever the business actually means by “the end”, and keep negative float. Write the result once per project. With that in place the only remaining problem is that writing the result is slow, which is Part 6.

Next in the series: making it fast. Why the per-task plugin cascade deadlocks and times out, and the pending-change buffer and asynchronous persistence pattern that replaced it.