Network Flow and Assignment Problems in WFM

Network Flow and Assignment Problems in WFM applies graph-based optimization to workforce management problems where resources (agents) must be allocated to tasks (shifts, skills, sites) through a network structure. Transportation problems, min-cost flow, maximum matching, and the Hungarian algorithm provide exact solutions to assignment problems that are often solved by heuristic rules in practice. When a WFM team assigns agents to skills, optimizes cross-training investments, or balances workload across sites, they are solving network flow problems — usually without knowing it.

Overview

Bipartite agent-skill assignment as network flow

Many WFM problems have a natural network structure:

• Skill-agent assignment: Agents on one side, skills on the other, edges represent competencies. Finding the best assignment of agents to call types is a bipartite matching problem.
• Cross-training optimization: Agents, skills, and training costs form a network. Deciding which agents to train on which skills to minimize total training cost while meeting coverage requirements is a min-cost flow problem.
• Multi-site load balancing: Sites are nodes, call routing paths are edges, capacity constraints are flow limits. Distributing workload across sites to minimize total cost is a network flow problem.
• Channel allocation: Channels (phone, chat, email) are nodes with capacity constraints. Allocating agents across channels to meet demand is a transportation problem.

Network flow theory provides algorithms that solve these problems optimally in polynomial time — fast enough for operational use.

Mathematical Foundation

The Transportation Problem

The transportation problem is the simplest network flow model: move goods (agents, hours, calls) from supply nodes to demand nodes at minimum cost.

Formulation:

• m supply nodes (sources of capacity: agent groups, sites, shifts)
• n demand nodes (consumers of capacity: intervals, skills, queues)
• $c_{ij}$ = cost of routing one unit from supply i to demand j
• $s_i$ = supply at node i
• $d_j$ = demand at node j

$\min \sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}$

subject to:

$\sum _{j=1}^n{x}_{ij}=s_i\mathrm{\forall }i\text{(supply exhausted)}$

$\sum _{i=1}^m{x}_{ij}=d_j\mathrm{\forall }j\text{(demand met)}$

$x_{ij}\ge 0\mathrm{\forall }i,j$

This is a linear program with special structure that allows it to be solved much faster than general LP.

Min-Cost Network Flow

The min-cost flow problem generalizes the transportation problem to arbitrary networks:

• Nodes: Each has supply $b_i$ (positive = source, negative = sink, zero = transshipment)
• Arcs: Each has capacity $u_{ij}$, lower bound $l_{ij}$, and cost per unit $c_{ij}$
• Decision: Flow $x_{ij}$ on each arc

$\min \sum _{(i,j)\in E}{c}_{ij}{x}_{ij}$

subject to:

$\sum _{j:(i,j)\in E}{x}_{ij}-\sum _{j:(j,i)\in E}{x}_{ji}=b_i\mathrm{\forall }i\text{(flow conservation)}$

$l_{ij}\le x_{ij}\le u_{ij}\mathrm{\forall }(i,j)\in E$

Algorithms (network simplex, successive shortest paths) solve this in O(nm log n) time — practical for networks with thousands of nodes.

Maximum Flow

The maximum flow problem asks: what is the maximum total flow from a source to a sink through a capacitated network?

The max-flow min-cut theorem (Ford and Fulkerson, 1956): the maximum flow equals the minimum cut — the smallest total capacity of edges whose removal disconnects source from sink.

WFM interpretation: The maximum throughput of a multi-skill routing network equals the capacity of its bottleneck skill group. If the min-cut runs through the "Spanish-speaking technical support" edges, that's the constraint limiting total throughput.

Bipartite Matching and the Assignment Problem

The assignment problem: Given n agents and n tasks with cost $c_{ij}$ for assigning agent i to task j, find the one-to-one assignment that minimizes total cost.

This is a special case of the transportation problem (all supplies and demands equal 1) but its importance in WFM merits separate treatment.

The Hungarian Algorithm

The Hungarian algorithm (Kuhn, 1955) solves the assignment problem optimally in O(n³) time. It works by:

1. Subtract the minimum value in each row from all entries in that row.
2. Subtract the minimum value in each column from all entries in that column.
3. Cover all zeros with a minimum number of lines. If n lines suffice, an optimal assignment through zeros exists.
4. If fewer than n lines suffice, adjust the matrix and repeat.

Why this matters for WFM: Any time you need to assign agents to tasks, calls to agents, or shifts to people in a one-to-one manner, the Hungarian algorithm finds the optimal assignment. It's fast enough to run in real time for routing decisions with dozens of agents.

WFM Applications

Skill-Agent Assignment as Bipartite Matching

Problem: 100 agents have various skill combinations. 8 call types require different skill sets. For a given interval, 80 calls are waiting and 100 agents are available. Which agent handles which call type?

Network model: Construct a bipartite graph. Left nodes: agents. Right nodes: call types. An edge connects agent i to call type j if agent i has the required skill. Edge cost: expected handle time for agent i on call type j (or a composite score incorporating quality, handle time, and customer value).

Objective: Find the minimum-cost matching that assigns calls to agents, respecting skill constraints and maximizing the quality-weighted throughput.

This is exactly the weighted bipartite matching problem, solvable via the Hungarian algorithm or network flow methods.

Real-world complication: Calls arrive dynamically, not in batches. The assignment changes every few seconds. But the mathematical structure is the same — and fast algorithms make real-time re-optimization feasible.

See: Skill-Based Routing, Next Generation Routing

Cross-Training Optimization as Min-Cost Flow

Problem: A center has 150 agents and 10 skills. Current skill coverage is uneven — the "billing" skill has 120 qualified agents while "technical escalation" has only 25. Management wants to cross-train agents to improve coverage resilience. Each training course costs time and money. Which agents should learn which skills to minimize total training cost while meeting minimum coverage targets?

Network model:

• Source: A super-source with supply = total training capacity (e.g., 40 training slots this quarter).
• Agent nodes: One per agent. Flow into an agent node = number of new skills they learn.
• Skill nodes: One per skill. Flow out of a skill node = number of newly trained agents for that skill.
• Agent → Skill arcs: Cost = training cost for agent i to learn skill j. Capacity = 1 (either train or don't). Only feasible arcs included (some agents cannot learn certain skills due to language requirements, etc.).
• Skill sink constraints: Each skill node has a minimum flow requirement (minimum coverage target).
• Agent capacity: Each agent can learn at most 2 new skills per quarter.

Solve as min-cost flow: find the flow that moves 40 "training units" from source through agents to skills at minimum total cost, subject to skill minimums and agent maximums.

Result: An optimal cross-training plan. Agent 47 learns "technical escalation" (cost $800) and "Spanish support" (cost $600). Agent 23 learns "billing" (cost $400) — but the model says: don't bother, billing already has 120 agents. The network flow formulation automatically identifies where cross-training investment has the highest marginal value.

Multi-Site Load Balancing as Network Design

Problem: A company operates contact centers in Manila, Hyderabad, and Phoenix. Each site has capacity limits, different labor costs, and overlapping hours. How should incoming calls be distributed across sites to minimize total cost while meeting service level at each site?

Network model:

• Source nodes: Call pools by type and time zone.
• Site nodes: Each site has capacity (agents available) and cost per call (labor rate × AHT).
• Arcs: Connect call pools to sites. Arc costs = per-call labor cost + penalty for cross-time-zone routing. Arc capacities = site capacity limits.
• Sink: All served calls flow to a common sink.

This is a min-cost flow problem. Solve it per interval to determine optimal call routing.

Extension — Network Design: If the company is deciding whether to open a fourth site, the problem becomes a network design problem: which node to add to the network to minimize total long-run cost. This combines flow optimization with location/capacity decisions.

Channel Allocation as Transportation Problem

Problem: 200 agents are multi-skilled across phone, chat, and email. Phone requires 100 agents, chat requires 60 (with 3:1 concurrency, so 20 agents), email requires 30 agents. Some agents are faster on certain channels. Minimize total cost while meeting all channel demands.

Transportation model:

• Supply: Agent groups (grouped by skill combination). Group A: phone + chat (50 agents). Group B: phone + email (40 agents). Group C: all three (60 agents). Group D: phone only (50 agents).
• Demand: Phone = 100, Chat = 20, Email = 30.
• Costs: Based on efficiency. Group C agents on email cost $12/hr (fast). Group B agents on email cost $14/hr (slower). Group D on email: infeasible.

Solve the transportation problem to optimally allocate agent groups to channels.

Worked Example: Optimal Agent-to-Shift Assignment

Setup: 6 agents, 6 shifts. Each agent has a cost for each shift based on overtime premiums, preferences (converted to cost penalties), and skill match quality.

Cost matrix ($/shift):

	Shift 1 (6A–2P)	Shift 2 (7A–3P)	Shift 3 (8A–4P)	Shift 4 (10A–6P)	Shift 5 (2P–10P)	Shift 6 (4P–12A)
Agent A	120	130	140	160	180	200
Agent B	150	120	130	140	160	170
Agent C	200	180	140	120	130	150
Agent D	170	160	150	130	120	140
Agent E	130	140	160	170	150	120
Agent F	160	150	130	150	140	130

Hungarian algorithm — Step 1 (row reduction): Subtract row minimum from each row.

	S1	S2	S3	S4	S5	S6
A	0	10	20	40	60	80
B	30	0	10	20	40	50
C	80	60	20	0	10	30
D	50	40	30	10	0	20
E	10	20	40	50	30	0
F	30	20	0	20	10	0

Step 2 (column reduction): Subtract column minimum from each column. Column minimums are all 0 (already have zeros in every column), so matrix is unchanged.

Step 3: Find maximum matching through zero entries: A→S1, B→S2, C→S4, D→S5, E→S6, F→S3.

This is a complete matching through zeros — the algorithm terminates.

Optimal assignment:

Agent	Assigned Shift	Cost
A	Shift 1 (6A–2P)	$120
B	Shift 2 (7A–3P)	$120
C	Shift 4 (10A–6P)	$120
D	Shift 5 (2P–10P)	$120
E	Shift 6 (4P–12A)	$120
F	Shift 3 (8A–4P)	$130

Total cost: $730. Every agent except F gets their cheapest shift. A greedy approach (assign each agent to cheapest available shift) might produce a worse total by creating conflicts.

Maturity Model Position

Network flow and assignment methods map to the WFM Labs Maturity Model:

• Level 1 (Reactive): Manual skill-agent assignment. Rule-of-thumb load balancing.
• Level 2 (Established): Basic skill routing with priority rules. Manual cross-training decisions.
• Level 3 (Advanced): Optimization-based agent-to-shift assignment. Data-driven cross-training plans. Multi-site routing optimization.
• Level 4 (Optimized): Network flow models for cross-training portfolio optimization. Real-time bipartite matching for routing. Channel allocation optimization.
• Level 5 (Autonomous): Dynamic network re-optimization. Automated skill gap detection with network flow-prescribed training. Continuous multi-site load balancing as capacities and costs change.

See Also

• Operations Research in Workforce Management
• Schedule Optimization
• Skill-Based Routing
• Next Generation Routing
• Cross-Training and Skill Mix Strategy
• Multi-Channel and Blended Operations
• Multi-Skill Scheduling
• WFM Labs Maturity Model

References

• Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993. — The definitive text on network flow theory and algorithms.
• Kuhn, H.W. "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2, 1955.
• Ford, L.R. and Fulkerson, D.R. Flows in Networks. Princeton University Press, 1962. — Origin of max-flow min-cut theorem.
• Hillier, F.S. and Lieberman, G.J. Introduction to Operations Research, 11th ed. McGraw-Hill, 2021. — Chapters on network optimization and transportation problems.
• Koole, G. Call Center Optimization. MG Books, 2013. — Multi-skill routing and agent assignment.