12.21 Scheduling Applications

Scheduling problems often look different from flow problems.

algorithmsgraphsnetwork-flow

12.21 Scheduling Applications

Problem

Scheduling problems often look different from flow problems.

You may need to assign:

  • Workers to shifts
  • Jobs to machines
  • Students to exams
  • Nurses to hospital wards
  • Deliveries to time windows
  • Courses to rooms
  • Tasks to processors

Each assignment must respect constraints: availability, capacity, minimum coverage, maximum workload, skill requirements, time windows, and sometimes fairness rules.

The challenge is to recognize when a scheduling problem is really a flow problem in disguise.

Solution

Model scheduling as movement through layers.

A typical scheduling flow network has this shape:

source
  -> resources
  -> time slots or jobs
  -> sink

Capacities enforce how much each resource can provide and how much each time slot or job can consume.

Costs can encode preferences, penalties, overtime, distance, or priority.

Lower bounds can encode minimum coverage requirements.

Basic Worker-Shift Model

Suppose workers must be assigned to shifts.

Workers:

Alice
Bob
Carol

Shifts:

Morning
Evening
Night

Availability:

Worker Available Shifts
Alice Morning, Evening
Bob Evening, Night
Carol Morning, Night

Each worker can work at most one shift.

Each shift needs one worker.

Construct:

source -> workers -> shifts -> sink

Capacities:

source -> worker = 1
worker -> shift = 1 if available
shift -> sink = demand

A max flow that saturates all shift demands gives a feasible schedule.

Example

Edges:

s -> Alice  capacity 1
s -> Bob    capacity 1
s -> Carol  capacity 1

Alice -> Morning capacity 1
Alice -> Evening capacity 1

Bob -> Evening capacity 1
Bob -> Night capacity 1

Carol -> Morning capacity 1
Carol -> Night capacity 1

Morning -> t capacity 1
Evening -> t capacity 1
Night -> t capacity 1

One feasible flow:

Alice -> Evening
Bob -> Night
Carol -> Morning

This corresponds directly to a schedule.

Shift Demands Greater Than One

If a shift requires multiple workers, increase the capacity into the sink.

Example:

Shift Required Workers
Morning 2
Evening 1
Night 1

Use:

Morning -> t capacity 2
Evening -> t capacity 1
Night -> t capacity 1

A feasible schedule exists only if the maximum flow equals:

2 + 1 + 1 = 4

Worker Capacity

If a worker can work up to k shifts, set:

s -> worker capacity = k

Example:

s -> Alice capacity 3

means Alice can be assigned to at most three shifts.

If a worker must work at least l shifts, use a lower bound:

s -> Alice lower = l capacity = k

Then apply the lower-bound transformation.

Skill Requirements

Suppose some shifts require special skills.

Example:

Shift Skill
ICU Night ICU
ER Evening ER

Only workers with the required skill receive edges to those shifts.

worker -> shift

exists only if:

worker has required skill
and worker is available

This is usually the cleanest way to encode eligibility.

Time Windows

For jobs with time windows, create one node per time slot or per job-time option.

Example:

Job A can run at 9:00, 10:00, or 11:00

Add edges:

Job A -> 9:00
Job A -> 10:00
Job A -> 11:00

or reverse the direction depending on the model.

Capacity on a time slot limits how many jobs can be scheduled then.

Machine Scheduling

Suppose jobs must be assigned to machines.

Machines have capacities:

Machine Capacity
M1 3
M2 2

Jobs require one machine each.

Use:

source -> jobs -> machines -> sink

Edges:

job -> machine

exist when that machine can process that job.

Capacities:

source -> job = 1
machine -> sink = machine capacity

If all job edges out of the source are saturated, every job is scheduled.

Minimum Coverage

Some scheduling models require minimum coverage.

Example:

Night shift needs at least 2 workers and at most 4.

Use a lower-bounded edge:

Night -> sink
lower = 2
capacity = 4

Then solve the resulting circulation or lower-bounded flow problem.

This avoids adding custom feasibility logic.

Preferences and Costs

If assignments have different desirability, use minimum-cost flow.

Example:

Worker Shift Cost
Alice Morning 1
Alice Night 8
Bob Morning 4
Bob Night 2

Add costs to worker-shift edges.

Then compute minimum-cost maximum-flow.

The result is a feasible schedule with minimum total penalty.

Overtime

Overtime is often modeled with parallel capacity tiers.

Example:

Alice can work:

  • first 5 shifts at normal cost
  • next 2 shifts at overtime cost

Model this using two worker nodes or two edges:

s -> AliceNormal   capacity 5 cost 0
s -> AliceOvertime capacity 2 cost overtimePenalty

Both connect to eligible shifts.

The optimizer uses normal capacity before overtime if costs are nonnegative.

Fairness Constraints

Simple fairness constraints can be modeled with lower and upper bounds.

Example:

Each worker must receive between 2 and 4 shifts.

Use:

source -> worker
lower = 2
capacity = 4

For more complex fairness, such as minimizing the maximum workload difference, you may need binary search around a flow feasibility check or a more general integer programming model.

Multi-Day Scheduling

For repeated days, create layered nodes.

Example:

worker -> day -> shift

or:

worker-day -> shift-day

This lets you encode daily limits separately from weekly limits.

Weekly capacity:

source -> worker capacity = weeklyLimit

Daily capacity:

worker -> workerDay capacity = dailyLimit

Shift assignment:

workerDay -> shiftDay

only when available.

Rest Constraints

Rules like:

cannot work night shift followed by morning shift

are harder.

Some limited cases can be modeled by expanding the state:

worker-day-lastShift

But the graph may grow quickly.

For rich sequencing constraints, use dynamic programming, min-cost flow on a time-expanded network, or integer programming.

Time-Expanded Networks

A time-expanded network represents the same resource across multiple times.

For example:

machine at time 0
machine at time 1
machine at time 2

Edges represent:

  • staying idle
  • starting a job
  • completing a job
  • moving between locations

This is useful for transportation, delivery routing, and machine scheduling with time.

Feasibility Check

For a pure coverage schedule:

  1. Build the flow network.
  2. Compute max flow.
  3. Compare flow value with total demand.

If:

max flow = total demand

a feasible schedule exists.

If not, inspect the minimum cut.

The cut often identifies the bottleneck: insufficient workers, missing skills, impossible availability, or excessive demand in a time block.

Diagnosing Infeasibility

Minimum cuts are useful for explaining scheduling failures.

Example:

Night shifts require 12 assignments
available qualified workers can cover only 9

A cut around the night-shift nodes exposes this limit.

This is often more useful than simply reporting:

no feasible schedule

Implementation Pattern

For worker-shift scheduling:

add source
add sink

for each worker:
    addEdge(source, worker, maxShifts)

for each shift:
    addEdge(shift, sink, demand)

for each worker, shift:
    if worker is available and qualified:
        addEdge(worker, shift, 1)

Run max flow.

Recover assignments from edges:

worker -> shift

with flow 1.

Complexity

Let:

  • W = workers
  • S = shifts
  • A = availability edges

The graph has:

V = W + S + 2
E = W + S + A

This is usually sparse.

Dinic or Hopcroft-Karp-style algorithms are effective for large instances.

Minimum-cost variants are slower but still practical for many scheduling systems.

Common Mistakes

Modeling Ineligible Assignments

Do not add edges for unavailable or unqualified worker-shift pairs.

Forgetting Total Demand

The max-flow value must equal total required coverage, not merely be positive.

Ignoring Lower Bounds

Minimum coverage, minimum workload, and fairness floors require lower bounds.

Overusing Flow for Sequencing

Flow is excellent for capacity and assignment. Complex temporal logic may require state expansion or a different model.

Losing Assignment Edges

Keep track of which graph edges correspond to real assignments so the final schedule can be recovered.

Discussion

Scheduling is one of the most common places where flow modeling pays off. The modeling pattern is simple: supply enters from one side, demand exits on the other, and eligibility is represented by edges in between.

As constraints become richer, the graph becomes more layered. Availability, skills, daily limits, weekly limits, overtime, and preferences can often be represented by capacities, lower bounds, and costs.

The key is to distinguish assignment constraints from sequencing constraints. Flow handles assignment and capacity naturally. Sequencing usually requires either a time-expanded graph or another optimization method.

Takeaway

Scheduling problems often reduce to flow by treating workers, machines, rooms, or other resources as supply nodes and shifts, jobs, or time slots as demand nodes. Capacities encode limits, lower bounds encode minimum requirements, and costs encode preferences.

When the max-flow value equals total demand, the schedule is feasible. When it does not, the minimum cut provides a structured explanation of the bottleneck.