Modelling the backend of a construction scheduling engine
I spent the last nine months building a construction project management software. The biggest challenge I faced so far was not building the app. It was the scheduling engine.
This is a long post. It is the modelling decisions behind that engine and what each one cost.
What construction scheduling actually is
A construction project is a list of things that have to happen in a specific sequence.
excavate foundations -> pour blinding ->fix reinforcement -> pour slab -> strike the formwork
Some of those can happen at the same time. Most cannot. You cannot pour a slab into a hole that has not been dug.
A schedule, or programme, is that list plus every "this must come before that" rule between the items, turned into dates. This matters because of one question a contractor gets asked frequently, 'We are three days late on pouring the slab, does the handover date move?'
Sometimes the answer is no and it costs nothing. Sometimes it is yes and it costs a month. Those two situations look identical on a gantt chart, and telling them apart is the entire job of the engine.
Getting it wrong is expensive in a specific way. Construction contracts carry liquidated damages, a fixed sum per day late. A schedule that quietly under-reports a delay does not just mislead, it costs money per day of being wrong.
And the schedule is never left alone. Rain stops earthworks. A concrete pour cannot happen in a downpour. Tasks spill into the following week, and some of that spill reaches the handover date while some of it disappears into slack that was already there.
Which of those two happened is not obvious from looking at the gantt chart, and the difference is commercial. Weather delay on a task with room in it is absorbed. Weather delay on a task with no room is a claim for an extension of time, and if it is not identified and argued for, the contractor eats the damages instead.
So the backend engine is not calculating a plan once. It is answering the same question every time reality moves. Given what just happened, does the end date move, and which tasks caused it.
The vocabulary
A few terms I will use throughout. These are the construction ones. I am assuming the computer science ones.
Task. One item of work. 'Excavate foundations'. It has a duration and a place in a numbered hierarchy called the WBS, the Work Breakdown Structure, which is why tasks are labelled 1.1, 1.2, 1.2.1 and so on.
Dependency. A rule saying one task must come before another. Not a suggestion or a preference. In my schema it is a row in its own table, not a column on a task, and I will explain why below.
Predecessor and successor. The two ends of a dependency. If excavation must come before pouring, excavation is the predecessor and pouring is the successor. The relationship is one-way and the direction carries the meaning. Reverse it and you have told the crew to pour concrete into ground that has not been dug.
Lag. Delay built into the dependency itself, separate from either task's duration. Pour concrete, then wait seven days before striking the formwork so it can cure. Nobody is on site working during those seven days. It is not a task. It is a property of the link between two tasks, which is why it lives on the dependency row.
A negative lag is legal and is called lead. It means the successor starts before the predecessor finishes, overlapping them deliberately.
Lag unit and Edays. Lag needs a unit, and this is the detail I would not have got right without talking to someone who has run a site.
Concrete cures on Saturday. It cures on a public holiday. A seven-day cure is seven actual days, no matter what the calendar says about work. I call that unit EDAYS, elapsed days, and it is raw calendar math.
Waiting for an inspector is also written as seven days. But inspectors do not work weekends, so that one is seven working days. I call that DAYS, and it routes through the calendar service that skips weekends and holidays.
Same phrase in the contract. Different math in the code. Get it wrong on a cure period and you lose two days per weekend crossed, compounding across every pour on the project.
Forward pass. Runs from the project start to the end and establishes each task's earliest start and finish. In my engine those dates are already resolved when a task's dates are set, so this pass reads them rather than deriving them.
Backward pass. Runs from the project end date backwards and computes the latest each task can finish without pushing the end date out. Every successor has to be computed before the task that feeds it, which is why the ordering matters.
Float, also called slack. How many working days a task can slip before the project end date moves. A task with ten days of float slipping three days costs nothing. A task with zero float slipping one day costs a day off the handover.
Critical path. The chain of zero-float tasks. If anything on it slips, the project end date moves. Everything else has room.
Baseline. The plan, locked. Without it, "behind schedule" has no referent, because if the plan moves every time something slips then nothing is ever late.
Dependency type. I assumed for too long that a dependency just meant "after." It does not. There are four:
Type |Full name |Meaning |Site example
FS |Finish to Start |successor starts after predecessor finishes |Excavate, then pour
SS |Start to Start |successor starts after predecessor starts |Start trenching, then start laying pipe behind the trenching crew
FF |Finish to Finish |successor finishes after predecessor finishes |Two crews on one pour who must stop together
SF |Start to Finish |successor finishes after predecessor starts |Rare. Shift handovers, mostly FS is the common one. SS is the one people forget, and it is the one that breaks a naive model, because SS work runs in parallel rather than in sequence.
1. Dependencies are not a column on the task
The obvious schema is a blocked_by column on the task row.
That breaks the first time a task has two predecessors. Pouring a slab waits on the reinforcement being fixed and on the formwork being up. One column cannot hold both.
It breaks harder once you notice the relationship carries its own data. A dependency has a type and a lag. Those belong to neither task. They belong to the link.
So dependencies are their own table. predecessor_id, successor_id, type, lag, lag_unit
The cost is that reading a schedule is now two queries and an in-memory join. Nearly every operation in my calculator starts by building a predecessor map and a successor map before it can do anything useful.
2. Four dependency types means four formulas everywhere
Supporting SS, FF and SF is not a matter of storing an enum and moving on.
Every place the engine reasons about dates has to branch on the type. My backward pass computes, for each dependency, what that edge implies about the predecessor's latest finish. FS and SS read the successor's latest start. FF and SF read its latest finish. The two start-anchored types then add the predecessor's duration back on.
Four formulas, and each one is a place a sign error can hide without crashing anything.
The cost is test surface. A single formula needs a handful of cases. Four formulas with positive lag, zero lag and negative lag is twelve, before you add weekends.
3. Two lag units means two code paths
Lag routes to different date math depending on its unit. Working days go through the calendar service. Elapsed days are raw calendar addition.
The cost is that every lag calculation has a branch in it, and the branch is invisible in the output. Both paths return a valid-looking date. The only way to know which one was correct is to know what the seven days represented on site.
I have not solved the interface side of that. The person entering a dependency has to pick the unit, and there is nothing in the data that lets me infer it for them.
4. The dependency graph has to be acyclic
Tasks and dependencies are already a directed graph, whether or not anything draws one. Directed because predecessor to successor is one-way, and the direction is the entire meaning.
It also has to be acyclic, meaning you cannot follow the arrows and arrive back where you started.
Here is a cycle, taken from one of my test fixtures.
Alpha -> Beta -> Gamma -> Alpha
Read it as constraints. Alpha before Beta. Beta before Gamma. Gamma before Alpha. Therefore Alpha before Alpha.
That is not a tight schedule or a late schedule. There is no set of dates that satisfies it.
This matters structurally. My backward pass computes each task's latest finish from its successors' dates, so it has to visit every successor before it touches that successor's predecessors. Otherwise it reads values that have not been computed yet.
An ordering with that property is a topological sort, and it exists if and only if the graph is acyclic.
No acyclicity, no valid order, no critical path.
5. Two cycle algorithms, because they answer different questions
I use Kahn's algorithm for the ordering. Track in-degree per task, which is just a countdown of unmet preconditions. Seed a queue with every task at zero. Pop one, emit it, decrement its successors, and any successor that hits zero joins the queue.
I picked it over the depth-first search because the intermediate state means something here. The queue at any moment holds exactly the tasks that are currently unblocked, which is a real thing a site manager wants to see.
I use Kahn's algorithm for the ordering. Track in-degree per task, which is just a countdown of unmet preconditions. Seed a queue with every task at zero. Pop one, emit it, decrement its successors, and any successor that hits zero joins the queue.
I picked it over the depth-first version because the intermediate state means something here. The queue at any moment holds exactly the tasks that are currently unblocked, which is a real thing a site manager wants to see.
Kahn's detects cycles for free. Tasks inside a loop never reach in-degree zero, so the queue starves and you finish with fewer sorted tasks than you started with.
But that only tells me a cycle exists. It cannot tell me which tasks form it, and the starved set includes everything downstream of the loop as well as the loop itself.
"Your schedule contains a circular dependency somewhere among four thousand tasks" is not an error message anyone can act on.
So imports run a second algorithm. A depth-first walk with three states per task. White for not yet visited. Black for fully explored. Gray for the tasks currently on the path from where I started down to where I am standing.
An edge to a gray task is an edge back to an ancestor. That is a cycle. And because I am already tracking the current path, the loop is the slice of that path from the gray task onward.
The import rejects with the actual loop listed by WBS code and task name. The user fixes it in a minute.
Two algorithms for what looks like one job, because "is there a cycle" and "which cycle" are different questions.
6. I have three different cycle policies
Layer |Policy on a cycle
Import |reject, return the loop path, write nothing
Critical path engine |append the unsorted remainder and continue
Cascade |bound the worklist by a step count, log a warning, stop The reasoning is that the import is the gate, so the engine should never see a cyclic graph.
But the engine currently degrades silently rather than throwing. If anything ever reaches it that did not come through the gate, I get wrong dates instead of an error.
I think it should throw. Then the invariant is enforced rather than assumed.
7. Working days are per project
Skipping Saturday and Sunday is not enough. Public holidays move dates, and they are not the same set in any two countries, so the holiday list cannot be hardcoded anywhere in the engine. Different projects also run different working weeks. A road contract working six days is not the same calendar as a commercial fit-out working five.
So there is one calendar service, holidays arrive as a set of date keys rather than being baked in, and the project’s schedule row carries a calendar_id. Adding a country is adding a calendar, not touching the engine. Where those dates come from is a data problem, and there are public holiday APIs that resolve them per country, which is exactly why it belongs at the boundary rather than in the calculator.
The cost is that date math stops being a pure utility function. It becomes a service with a dependency, which makes the parts of the engine that use it harder to test in isolation.
8. Late needs something to be late against
If you measure progress against the current plan, and the plan shifts every time something slips, nothing is ever late. The chart looks healthy permanently.
So the plan gets locked, and the locked version is the baseline. Separate columns on the task, plus a history table because projects do get re-baselined when a variation is agreed.
The cost is duplicating every planned date column on every task row.
9. Not all lateness moves the end date
This is the question the whole engine exists to answer.
Twenty late tasks can cost nothing. One late task can cost a month. The difference is float, and only zero-float tasks move the handover date.
I persist float and the critical flag on the task rather than computing them on read, because the read path is a chart that loads constantly and recomputing a few thousand tasks per load was not viable.
The cost is staleness. Anything that changes dates has to trigger a recalculation, or the flags quietly describe a plan that no longer exists.
There is a version of this where float is derived on read and cached properly.
Conclusion
That is nine months of decisions compressed into one post. It’s been hella crazy learning and implementing this feature btw I have zero construction knowledge when I got started. I learned by getting it wrong first and talking to construction managers.
I am happy to go deeper in any of it in the comments.
Thanks for reading this far.