Customizing Ford-Fulkerson for shift scheduling

This algorithm grew out of a much bigger shift management problem in Trakkup. The scheduling feature already had a lot of configuration: role requirements, qualification checks, availability windows, shift timing rules, and booking-driven demand changes. Once those rules were all in place, it became clear that we had enough structure to do more than assist scheduling. We could automatically manage schedules as bookings changed and as operating parameters were updated.

That is where this write-up starts. I needed an algorithm that could continuously re-balance assignments and still respect the real-world constraints of the system. The shift scheduler started with a straightforward idea: model assignment as flow in a directed graph. In practice, each edge represented time intervals, not a single number, so I had to customize Ford-Fulkerson to reason about assignable date ranges.

From configuration to automation

At first, these rules were mostly guardrails around manual operations. Over time, they became the input data for an automatic decision engine:

  • Bookings go up or down.
  • Demand bands and role requirements change.
  • Worker availability and qualification combinations vary.

Instead of hand-adjusting schedules each time, the goal became: recompute assignments automatically and safely. That goal is what made a flow-based approach so attractive.

Why Ford-Fulkerson

Before writing custom logic, I spent time looking at different algorithm families for assignment and routing. I eventually landed on Ford-Fulkerson because the core idea matched the problem shape: push as much valid "flow" as possible through a constrained network.

At a high level, Ford-Fulkerson is a maximum-flow algorithm for directed graphs. It repeatedly finds an augmenting path from a source node to a sink node and pushes flow along that path until no more valid paths exist. It is typically used for things like network throughput, resource allocation, bipartite matching, and capacity-constrained routing.

That maps well to shift scheduling:

  • A shift role behaves like capacity that needs to be filled.
  • A worker behaves like a constrained receiver with limited availability.
  • Qualification and rule checks become graph edges that either exist or do not.

Once I viewed scheduling as a max-flow problem, the remaining work became adapting the edge capacity model from scalar values to time intervals.

Why flow was a good fit

In my graph:

  • Source connects to shift nodes with full shift intervals.
  • Shift nodes connect to user nodes when the role and qualifications match.
  • User nodes connect to sink with each user's availability.

Running max-flow gives a good baseline: route as much valid time as possible from source to sink. The complication is that interval arithmetic can break assumptions that plain numeric capacities depend on. So the core problem shifted from "find any max flow" to "find max flow that remains valid in time."

The key customization: capacities as date intervals

Each edge capacity uses DatesRange values ([startISO, endISO][]) instead of integers. That means augmentation is no longer capacity -= bottleneck; I have to:

  • Subtract intervals from the chosen edge in the main graph.
  • Add intervals to the reverse edge in the residual graph.
  • Merge or split adjacent ranges when needed.
  • Reject overlap-invalid transitions for user assignments.

This is handled by interval utilities like addInterval(), subInterval(), canAddInterval(), and canSubInterval(). Those helpers let me preserve the Ford-Fulkerson shape while swapping in time-aware operations. In other words, I kept the algorithmic skeleton, but replaced scalar capacity math with interval operations that match scheduling reality.

Augmenting path checks for scheduling constraints

A plain path existence check is not enough for shift scheduling. The path also has to satisfy interval feasibility:

  • The requested interval must be contained in available capacity.
  • Newly assigned shift windows must not overlap a user's already assigned shifts.
  • Some "swap" paths require removing conflicting assignments first, then rechecking feasibility.

This is why my implementation has layered traversals (dfs, bfs, and a deeper dfsDepth2) and uses net-change checks before accepting deeper augmenting paths. Those extra checks are what allow the scheduler to react to booking changes without producing invalid overlap-heavy schedules.

What I changed from textbook Ford-Fulkerson

The most important differences in this implementation:

  1. Inverted adjacency setup to align traversal direction with assignment operations.
  2. Custom residual updates using interval arithmetic rather than scalar updates.
  3. Depth-2 augmenting exploration for shift-swapping behavior when a simple path fails.
  4. Bonus removals logic to detect and clear overlapping assignments that block higher-value solutions.
  5. Flow objective tracked in minutes using differenceInMinutes and interval sums.

The end result is still recognizably Ford-Fulkerson, but adapted for temporal constraints and realistic scheduling conflict rules. This ended up becoming the core engine behind automatic shift reallocation in response to operational changes.

Trade-offs and lessons learned

I intentionally optimized for correctness and debuggability first. That decision made this version practical for moderate scheduling sizes, even with a heavy worst-case complexity.

Main takeaways:

  • Interval operations are where most hidden bugs live.
  • Residual updates become business logic, not just graph theory.
  • A small amount of visualization makes the algorithm much easier to trust and explain.

I plan to keep improving this by extracting interval math into smaller pure functions, tightening invariants around graph updates, and adding targeted tests around path-swap edge cases.