A transfer team can improve one route and still move no more material through the factory. The reason may lie several steps away, where a group of limited links caps the network despite spare capacity on individual lanes.

Maximum flow finds the largest feasible flow from a source to a destination. Minimum cut identifies a set of links whose combined capacity proves that no larger flow is possible. Used together, they turn a vague bottleneck claim into a calculation that an operations team can inspect.

This guide builds an original apparel transfer example in standard totes per hour. It verifies the optimum, tests proposed upgrades and explains reverse residual links. It also shows where the model stops being suitable, including shared handling resources, distinct product routes and delivery deadlines.

Define the flow unit and the physical boundary

The example concerns totes of cut bundles moving from release point S to destination staging T. A and B are intermediate transfer zones, while C and D are downstream consolidation zones. The letters identify locations, not successive garment-making operations.

Every tote in this teaching model has the same handling requirements and can use either eligible branch. No tote disappears, changes size or becomes a different product in transit. There is enough released material and enough demand at T to use the available throughput.

Each directed link has a capacity in totes per hour, describing the available transfer rate under a fixed staffing arrangement. All stated rates must be available simultaneously. A single worker is not secretly assigned at full capacity to several links. We also assume no net accumulation at intermediate zones over the period represented.

These boundaries matter. A fabric roll entering cutting and a garment leaving sewing do not have the same physical unit. A standard flow balance cannot equate their counts. A model with conversion, scrap or rework needs explicit conversion rules and may no longer be a plain maximum-flow problem.

Google's OR-Tools maximum-flow guide defines capacity-limited arcs and conservation at intermediate nodes. For factory use, first agree what crosses each arc and what one unit means. A valid algorithm cannot repair an inconsistent unit definition.

Assemble the directed capacity table

The network contains the following eight links. A missing link is unavailable; it is not an unrecorded route with unlimited capacity. The direction matters because permission to move from A to C does not imply a physical return route from C to A.

From

To

Capacity, totes/hour

S

A

8

S

B

7

A

C

6

A

D

2

B

C

1

B

D

4

C

T

5

D

T

6

All inputs are illustrative; a real route estimate might use available handling minutes and a complete trip cycle. Suppose one dedicated resource has 50 usable minutes per clock hour. A round trip, including loading and return, takes 6.25 minutes and carries one tote. Its planned rate is eight totes per hour.

route capacity = 50 minutes/hour ÷ 6.25 minutes/tote = 8 totes/hour

The return journey belongs in that cycle if the resource must return before the next loaded trip. Do not measure only the outward journey and then treat the saved minutes as real capacity. Also distinguish a measured typical rate from a dependable limit under the conditions being planned.

Keep the source of each capacity next to the input table. Useful fields include the observation date, shift, staffing level, tote type and exclusions. A rate derived during a quiet trial may not hold when the aisle is shared with other traffic.

Write the model without counting the same tote three times

Let x(i,j) be the nonnegative transfer rate on link i to j, and let c(i,j) be that link's capacity. Each x must remain at or below its corresponding c. At each intermediate node, incoming flow equals outgoing flow.

0 ≤ x(i,j) ≤ c(i,j)

incoming flow at v = outgoing flow at v, for v in {A, B, C, D}

The objective is net flow leaving S, which equals net flow arriving at T. In this network there are no links into S or out of T, so either sum is simple.

maximize F = x(S,A) + x(S,B) = x(C,T) + x(D,T)

Do not maximize the sum of all eight link flows. A tote passes through three links here, so that sum counts its movement three times. In a network with cycles, maximizing all link flows can even reward useless circulation.

For example, conservation at A requires x(S,A) to equal x(A,C) plus x(A,D). Conservation at C requires x(A,C) plus x(B,C) to equal x(C,T). These equations prevent the solver from creating extra totes at a merge point.

NetworkX defines maximum-flow value as net outflow from the source. That definition remains sound when a more general network contains cycles or arcs returning toward the source.

Construct an eleven-tote feasible routing

Start with five totes per hour on S–A–C–T. Then send two on S–A–D–T. Finally send four on S–B–D–T. The total reaching T is eleven.

Link

Planned flow

Capacity

Unused capacity

S to A

7

8

1

S to B

4

7

3

A to C

5

6

1

A to D

2

2

0

B to C

0

1

1

B to D

4

4

0

C to T

5

5

0

D to T

6

6

0

Every value is in totes per hour. At A, seven arrive and five plus two leave. At B, four arrive and four leave; C receives five and sends five. D receives two plus four and sends six. All link limits are respected.

This proves that eleven is achievable within the model, but it does not yet prove that twelve is impossible. A feasible plan is a lower bound on the optimum, so we need a matching upper bound to close the argument.

The unused capacity on S to B is not a contradiction. More material can enter B only if it can continue to T. Capacity cannot be added across disconnected or incompatible parts of a route to create throughput.

Use a cut to prove the maximum

A source-to-sink cut partitions all nodes into two sets. S belongs to the source side and T belongs to the other side. The cut capacity is the sum of capacities on arcs pointing from the source side to the other side.

Place S, A, B, C and D on the source side. Only C to T and D to T leave that set. Their capacities sum to five plus six, or eleven totes per hour. Every tote reaching T must cross this boundary. No feasible flow can exceed eleven.

cut capacity = c(C,T) + c(D,T) = 5 + 6 = 11

We already have a feasible flow of eleven. The lower and upper bounds match, so the routing is optimal. There is no need to trust a solver status without understanding its evidence.

The max-flow/min-cut theorem in Bertsekas's Network Optimization, Section 3.1, gives the general result. With the usual nonnegative capacities and zero lower bounds, the largest source-to-sink flow equals the smallest cut capacity.

A cut is a partition of nodes, which need not appear as a straight line on a floor plan. Nor is it the single smallest-capacity link. B to C has capacity one, yet the network can carry eleven by using other paths. The relevant restriction is the combined capacity across an entire separating boundary.

Recognize that there can be more than one minimum cut

Now place only S, A, B and C on the source side. The outgoing boundary links are A to D, B to D and C to T. Their capacities are two, four and five, so this cut also totals eleven.

second cut capacity = 2 + 4 + 5 = 11

The two minimum cuts explain why increasing D to T alone does not help. Even if that link rises from six to eight, the second cut remains eleven. D can still receive only six from its upstream links, leaving its new outbound space without extra material to carry.

The worked network has four intermediate nodes. Each can be placed on either side, so there are sixteen possible source-to-sink partitions. All sixteen were enumerated as a verification check. Exactly the two cuts described here attain the original value of eleven.

NetworkX's minimum-cut interface returns a cut value and a node partition. One returned partition need not list every minimum cut. When an investment depends on a particular bottleneck claim, test the proposed change and inspect the new limiting cut.

Understand residual capacity and the right to reroute

An augmenting-path method improves a flow through a residual network. A forward residual link represents unused capacity, while a reverse residual link represents flow that can be cancelled and assigned elsewhere. It does not create permission to move physical totes backward.

Consider a separate four-node example. Each of S to U, S to V, U to V, U to T and V to T has capacity one. A first choice sends one unit along S–U–V–T. That fills S to U and V to T.

A search that permits only unused forward links now appears stuck. Yet two units are possible: one on S–U–T and one on S–V–T. The first choice used U to V unnecessarily and needs to be revised.

The residual path S–V–U–T does this. Its V-to-U step cancels the existing unit on U to V. The other steps add one on S to V and U to T. The final physical plan has zero flow on U to V and one unit on each direct branch to T.

Cornell's flow tutorial explains this residual interpretation. Keeping reverse residual links is essential for a correct augmenting-path algorithm. A spreadsheet that merely fills convenient paths and never revisits them can stop at a feasible but inferior answer.

Test upgrades against the whole network

The capacity scenarios below were solved independently. Each row changes only the stated links from the base network, except where the row explicitly starts from an upgraded case.

Scenario

Maximum flow, totes/hour

Change from base

Original capacities

11

0

A to C increased from 6 to 8

11

0

D to T increased from 6 to 8

11

0

C to T increased from 5 to 6

12

1

C to T increased from 5 to 7

13

2

C to T = 7 and B to D = 5

13

2

C to T = 7 and D to T = 7

13

2

C to T = 7, B to D = 5 and D to T = 7

14

3

After C to T rises to seven, one feasible routing uses all six on A to C, two on A to D, one on B to C and four on B to D. S supplies eight to A and five to B. C sends seven to T and D sends six. Total throughput is thirteen.

At that point, increasing only B to D leaves the two final links capped at thirteen. Increasing only D to T leaves the middle transfer links capped at thirteen, whereas increasing both permits fourteen. The upgrades complement one another.

This is why a saturated link is not automatically a good isolated investment. A link can belong to one minimum cut while another unchanged cut blocks the benefit. The relevant evidence is the new achievable flow after the complete proposed change.

maximum flow minimum cut factory network

Reproduce the basic calculation in Python

The following code uses the node order S, A, B, C, D, T. Capacities form a square directed matrix. Zero means that the corresponding link is unavailable in this example.

import numpy as np

from scipy.sparse import csr_matrix

from scipy.sparse.csgraph import maximum_flow

capacity = np.array([

[0, 8, 7, 0, 0, 0],

[0, 0, 0, 6, 2, 0],

[0, 0, 0, 1, 4, 0],

[0, 0, 0, 0, 0, 5],

[0, 0, 0, 0, 0, 6],

[0, 0, 0, 0, 0, 0]

], dtype=np.int64)

result = maximum_flow(

csr_matrix(capacity), 0, 5, method="dinic"

)

print(result.flow_value) # 11

This calculation was executed with SciPy 1.17.0. Its result was also checked with Edmonds–Karp, a separate linear program and exhaustive cut enumeration. All methods agreed for the nine tested cases, including an outage scenario discussed below.

SciPy's maximum-flow documentation specifies integer capacities in a sparse directed matrix. Its returned flow matrix includes a signed reverse representation. Read physical flow from the original directed arcs; do not interpret every negative matrix entry as a requested backward move.

Different algorithms may return different optimal routings, and the route table above is one feasible optimum. Agreement on the maximum value, capacity limits, conservation and a matching cut is more meaningful than identical tie choices on every arc.

Check the certificate independently

For each returned physical arc, check that flow is nonnegative and does not exceed capacity. Then calculate inflow minus outflow at every intermediate node. Each balance should be zero within the tolerance appropriate to the numeric representation.

Calculate net outflow at S and net inflow at T separately. They should agree with the reported value. Finally, add the capacities of the forward arcs crossing the reported cut. A cut equal to the feasible flow proves optimality for the model.

Count only arcs leaving the source-side set when calculating cut capacity. If a physical arc points back into that set, adding its capacity would inflate the bound. For a general feasible flow, net flow across the cut is forward flow minus backward flow.

With integer data, an integer optimum exists for the ordinary single-commodity problem. Dalhousie's integral-flow notes explain why augmentations preserve integer values. This does not mean that every possible optimal solution is integral, or that arbitrary added constraints preserve the property.

Add node capacity without counting it once per route

Suppose consolidation zone C can handle only four totes per hour in total. Setting every inbound link to four would permit up to eight to enter C. Setting each outbound link to four can cause a similar error if there are several exits.

Represent C as two nodes: C-in and C-out. Direct every original inbound link to C-in. Direct every original outbound link from C-out. Connect C-in to C-out with one arc of capacity four. All flow through C must cross that arc exactly once.

All routes through the split node now share one capacity, rather than each receiving a separate allowance. Bertsekas's node-throughput exercise, Exercise 1.18, describes the splitting approach. It is useful for a staging checkpoint or a handling station whose total load is limited.

The same trick cannot represent every shared resource. If one mobile team serves several unrelated routes, its time use may depend on distance and trip type. A sum of route-specific labor minutes may be needed. Do not create a common node that accidentally lets material switch to a route it could not physically reach.

Treat multiple supplies and destinations explicitly

A super-source can connect several release points, with each connecting arc limiting the amount available at its release point. A super-sink can collect flow from several destinations, with connecting capacities that represent their acceptance limits.

However, a destination cap is not a guaranteed allocation. If two lines can each accept six totes, a maximum total flow may send six to one and less to the other. That is acceptable only when the objective truly concerns interchangeable total volume.

A requirement to send at least a stated amount to each line needs lower bounds, a feasibility transformation or a richer optimization model. A source cap should also reflect released material. Unlimited source supply can make a route expansion look valuable when no additional material is available.

If garments for one buyer cannot replace garments for another, preserve those identities throughout the network model. Aggregating them into a single flow can hide a shortage on one order behind excess on another. Separate commodities with shared capacities generally require a multicommodity model. The plain maximum-flow certificate does not prove that all order-specific requirements are met.

Keep throughput separate from cost and timing

Maximum flow answers how much can move under the stated capacity system. It does not choose the cheapest routing among equal-throughput plans. Two optimal plans may require different labor, handling or external transfer cost.

After finding a required throughput, a minimum-cost flow model can allocate that amount using route costs. Google's minimum-cost flow guide includes arc capacities, unit costs and node supplies or demands. ApparelDiary's fabric transportation model addresses a related cost-allocation task. The present article uses cuts to establish a capacity limit.

A rate model also does not prove that eleven totes will reach T during the first hour after an empty start. Travel and handling take time. Some material may still be inside the network at the cutoff. Multiplying a sustained rate by a short horizon can overstate completed transfers.

When deadlines or time-varying capacities matter, use time-indexed states or a scheduling or simulation model. A time-expanded network distinguishes a location now from the same location later. It can represent travel time and permitted waiting, but it requires more data and a clear time step.

Use disruptions as scenarios, not unexplained averages

Suppose C to T is completely unavailable. The original network can then deliver only through D. Its maximum falls to six totes per hour. This result was verified with the same capacity and conservation checks as the base case.

That does not mean the expected output is the average of eleven and six. Such an average needs probabilities and a time interpretation. An outage lasting ten minutes, an outage lasting a full shift and a route with randomly varying speed have distinct capacity and timing consequences.

For an operational review, state the scenario directly: which link is lost, how the remaining capacities change, and whether rerouting is available in time. A mathematically feasible substitute route may require a driver, gate access or a transfer approval that is not immediately available.

Also test whether the network remains usable under the demand mix that matters. A redundant path for a small tote may be unsuitable for a large roll. Connectivity on a diagram is not enough to establish practical interchangeability.

Turn the model into a capacity decision

Begin with the current graph, a feasible routing and a matching cut. Ask the operating team to confirm that each link can work at its stated rate at the same time as the others. Review any shared labor or aisle assumptions before discussing upgrades.

For each candidate change, update the affected capacities and solve again. Record the new throughput, the new limiting cut and the physical route changes. A proposal that adds two units of link capacity but no system capacity still may have resilience value. That is a separate benefit and should be stated as such.

Compare the extra useful throughput with the actual need. If demand is twelve totes per hour, moving from eleven to thirteen gives one unit above that requirement. It does not automatically create demand for the thirteenth tote. A cap on demand can be included at the destination when appropriate.

Keep the capacity version with the result. A later shift change may invalidate an earlier cut. The model is a calculation for a particular operating arrangement, not a permanent label that one department is always the bottleneck.

Common mistakes and practical repairs

Missing capacities can be dangerous in software. NetworkX treats a missing capacity attribute as infinite. Validate every physical arc before solving. A blank spreadsheet cell should trigger review rather than silently become a very large number.

Parallel routes need care too. Two separate links between the same nodes may share a resource or have different eligibility rules. Add their capacities only when simultaneous use is valid and the routes are interchangeable for the modeled flow. Otherwise preserve their separate identity in a suitable representation.

Another mistake is claiming that a higher capacity must increase flow. It cannot reduce the optimum when all else is unchanged, but the gain can be zero. The tested A-to-C and D-to-T upgrades demonstrate that distinction.

Finally, check rounding. Scaling fractional rates to integers can support an integer-capacity solver, but choose the scale explicitly. Rounding each route upward creates capacity that was not available. For whole-tote decisions in a short period, use a period model whose units match indivisible transfers.

A zero result deserves a graph check before a capacity purchase. Trace whether any directed path connects S to T. Reversed labels, an omitted handoff or a capacity entered as zero can disconnect the model. With zero lower bounds, the all-zero flow is feasible, so a solver can correctly report an optimal value of zero. That status does not prove a positive operating target is achievable. Compare the optimum with the required transfer rate and explain any gap separately.

Frequently asked questions

Is the minimum cut always the busiest machine?

No. A cut may contain several links at different locations. This model concerns transfer routes, and a high observed utilization by itself is not a minimum-cut proof. The complete capacity network determines the bound.

Can the maximum flow have more than one routing?

Yes. Different route assignments can attain the same total. If cost, congestion preference or workload balance matters, add a suitable second decision criterion. Do not assume the first optimum returned by software is uniquely best operationally.

Another unchanged cut may still cap the system. D to T is full in the base routing, yet its isolated expansion gives no gain. Its inbound routes can still supply only six totes per hour.

Does reverse residual flow mean moving goods backward?

No. It revises an earlier mathematical assignment. Only the final nonnegative flows on physical arcs describe the transfer plan. A reverse route must exist in the original data before it can carry physical goods.

Conclusion

Maximum flow provides a feasible transfer plan, while minimum cut supplies a matching capacity bound. In the example, eleven totes per hour are achievable and optimal. Two different minimum cuts explain why some apparently useful upgrades add no throughput.

The strongest use of the method is a transparent decision record: common units, verified capacities, balanced flows, a cut certificate and explicit upgrade scenarios. Extend the model when product identity, shared labor, timing or cost changes the question. The certificate remains powerful because its meaning is precise.

Bottleneck methods connect to other flow analysis, so see fabric allocation with a transportation model, linear programming, value stream mapping and machine capacity planning.

References

1. Google OR-Tools: Maximum Flows. Arc capacities, conservation and solver setup.

2. NetworkX: maximum_flow. Net source flow and residual conventions.

3. Bertsekas: Network Optimization. Section 3.1 on cuts; Exercise 1.18 on node throughput; Exercise 1.24 on time-indexed transfers.

4. NetworkX: minimum_cut. Cut value and partition output.

5. Cornell: More on Graphs, Flows and Matchings. Residual graphs and cancellation of previous flow.

6. SciPy: maximum_flow. Sparse integer-capacity implementation.

7. Dalhousie: Existence of Integral Flows. Integral flow property.

8. Google OR-Tools: Minimum Cost Flows. Costs, supplies, demands and capacity constraints.