Network Optimization and Project Management

Introduction

Operations managers frequently make decisions in which activities, facilities, jobs, and transportation links are connected by a network. Examples include routing products through a distribution system, selecting communication links, assigning flows through a pipeline, and coordinating interdependent project activities. Network optimization provides a unified language for these problems, while project-management techniques convert activity relationships and duration estimates into schedules, completion forecasts, and resource decisions.

This chapter develops four fundamental network models—shortest path, minimum spanning tree, maximum flow, and minimum-cost flow—and then applies critical path method (CPM) and program evaluation and review technique (PERT) to project scheduling. The emphasis is not merely on computation but on modelling assumptions, managerial interpretation, sensitivity, and limitations.

Learning Objectives

After studying this chapter, you should be able to:

1. Represent operational systems as directed or undirected networks.
2. Formulate and solve shortest-path, minimum-spanning-tree, maximum-flow, and minimum-cost-flow problems.
3. Explain the logic of Dijkstra’s, Kruskal’s, Ford–Fulkerson, and related algorithms.
4. Construct CPM schedules and identify critical activities and total project float.
5. Use PERT to estimate expected completion times and uncertainty.
6. Evaluate project crashing, resource trade-offs, and schedule risk.
7. Recognize modelling assumptions, implementation risks, and ethical implications of network decisions.

1. Network Foundations

A network consists of nodes (also called vertices) and arcs or edges. A node may represent a plant, customer, event, junction, or project milestone. An arc represents a connection or activity. A directed arc has a specified direction; an undirected edge permits movement in either direction.

A network may be represented graphically, by an adjacency list, or by an adjacency matrix. Arc attributes commonly include distance, time, cost, capacity, reliability, or activity duration. A path is a sequence of connected arcs. A cycle is a path that returns to its starting node. A connected network permits a path between every relevant pair of nodes.

A useful modelling discipline is to distinguish:

• Physical feasibility: whether a connection actually exists.
• Operational feasibility: whether capacity, time windows, regulations, or resources permit its use.
• Objective value: the cost, time, risk, or benefit assigned to a feasible connection.

Many network models are special cases of linear programming. For example, if x_ij indicates whether arc (i,j) is selected, binary restrictions may be required. If f_ij denotes flow, it is generally continuous unless indivisible units must be represented.

2. Shortest-Path Models

2.1 Definition and formulation

The shortest-path problem seeks a minimum-weight route from an origin node s to a destination node t. Arc weights may represent distance, travel time, or cost. Let c_ij be the non-negative weight of arc (i,j), and let x_ij equal 1 if the arc is used and 0 otherwise. A flow-balance formulation is:

subject to one unit of flow leaving the origin, one unit entering the destination, and conservation at intermediate nodes:

where b_s=1, b_t=-1, and b_i=0 for all other nodes. For a simple network, x_ij is binary; with non-negative arc weights, an optimal linear-programming solution is integral under standard network-flow conditions.

2.2 Algorithms

Dijkstra’s algorithm repeatedly labels the unsettled node with the smallest tentative distance and permanently fixes its label. It is efficient and widely used, but requires all arc weights to be non-negative. It is invalid when negative arc weights are present.

Bellman–Ford can accommodate negative arc weights and can detect negative cycles, although it is generally slower. A negative cycle makes a shortest-path problem ill-defined if it can be reached from the origin and can reach the destination, because the path cost can be reduced indefinitely.

2.3 Worked example

Suppose the following directed arcs have travel times in minutes:

Routes from A to E include A–B–E (14), A–C–D–E (12), and A–C–B–D–E (10). Therefore the shortest route is A–C–B–D–E, with total time:

The result is meaningful only if the times are additive and independent of congestion, departure time, and route choice. If congestion changes with flow, a static shortest-path model may be inadequate.

3. Minimum-Spanning-Tree Models

A spanning tree connects every node without cycles. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight. It is appropriate for designing a least-cost connected infrastructure—for example, connecting offices with communication cables—when every site must be connected but no particular origin-to-destination route is required.

For an undirected graph with node set V and edge set E, an MST contains exactly |V|-1 edges. It does not necessarily provide the shortest route between any two nodes, and it does not include redundant connections unless reliability requirements are added.

3.1 Kruskal’s and Prim’s algorithms

Kruskal’s algorithm sorts edges from smallest to largest and adds an edge if it does not create a cycle. The process ends after |V|-1 edges have been selected.

Prim’s algorithm starts with one node and repeatedly adds the least-cost edge joining the current tree to an unconnected node. Both algorithms produce an MST when the graph is connected and edge weights are defined. Ties can lead to more than one MST with the same total cost.

3.2 Worked example

Consider five sites and the following undirected connection costs:

Kruskal’s method selects B–C (1), A–B (2), D–E (2), and B–D (4). The edge C–D is rejected because it would create a cycle after the first, second, and fourth selections; C–E and B–E are unnecessary. The total MST cost is:

The design connects all sites at minimum total installation cost. A manager should still test whether the resulting network has sufficient resilience; an MST has no spare link and may be vulnerable to a single failure.

4. Maximum-Flow Models

A maximum-flow problem determines the greatest amount that can move from a source s to a sink t through capacitated arcs. Let u_ij be the capacity and f_ij the flow on arc (i,j). The formulation is:

subject to:

where v is the source-to-sink flow, with net outflow v at the source and net inflow v at the sink. Flow conservation assumes no intermediate production, storage, or loss.

The Ford–Fulkerson algorithm repeatedly finds an augmenting path in the residual network and sends as much additional flow as possible along it. The Edmonds–Karp version uses breadth-first search and has a well-defined polynomial bound for capacitated networks. The maximum-flow/minimum-cut theorem states that the maximum feasible flow equals the capacity of the smallest source–sink cut.

Worked example

Suppose source S connects to A and B with capacities 8 and 6. A connects to B and T with capacities 3 and 5. B connects to T with capacity 7. One feasible flow is S–A–T = 5, S–B–T = 6, and S–A–B–T = 3, giving 14 units. The source capacity is 14, and the total capacity entering T is 12 only if the stated arcs are interpreted as A–T = 5 and B–T = 7; hence the maximum cannot exceed 12. The flow must therefore be revised to respect the sink-side cut: at most 12 units can reach T. A valid maximum flow is S–A–T = 5, S–A–B–T = 3, and S–B–T = 4, totalling 12. The cut consisting of arcs A–T and B–T has capacity 12, proving optimality.

This example illustrates why local capacity reasoning can be misleading: the total capacity leaving the source is not sufficient to establish the maximum flow unless all downstream constraints are considered.

5. Minimum-Cost-Flow Models

Minimum-cost flow combines capacity, supply, demand, and cost. It is useful for transportation, production-distribution systems, and shipment consolidation. Let f_ij be flow and c_ij its unit cost. The objective is:

subject to:

and

Here b_i is supply when positive, demand when negative, and zero for a transshipment node. Feasibility requires total supply to equal total demand, unless a dummy source or sink is introduced. Costs must use consistent units, such as dollars per pallet.

Algorithms include the network simplex, successive shortest path, and cost-scaling methods. In a successive-shortest-path method, the algorithm sends flow along the least reduced-cost route in the residual network until all supplies and demands are satisfied. Negative residual costs may arise, so reduced-cost methods or suitable shortest-path procedures are needed.

A key managerial insight is that the cheapest direct arc is not necessarily part of the cheapest complete supply plan. Capacity and conservation constraints create system-wide trade-offs.

6. Project Networks and Scheduling Logic

A project network represents precedence relationships among activities. In an activity-on-node (AON) network, each node is an activity and arcs show precedence. In an activity-on-arrow (AOA) network, arrows represent activities and nodes represent events. AON is common in contemporary project software because it handles precedence relationships directly.

Important terms include:

• Predecessor: an activity that must occur before another activity.
• Successor: an activity dependent on a preceding activity.
• Earliest start (ES): earliest feasible start time.
• Earliest finish (EF): earliest completion time.
• Latest start (LS): latest start that does not delay the project.
• Latest finish (LF): latest allowable completion time.
• Float or slack: scheduling flexibility without delaying the project.
• Critical path: a longest-duration path through the precedence network; activities on it normally have zero total float.

6.1 Critical Path Method

CPM assumes deterministic activity durations. For activity i with duration d_i, the forward pass is:

For an activity with predecessors, its earliest start is:

The project duration is the largest final activity finish time. Beginning at the project completion time, the backward pass is:

For an activity with successors:

Total float is:

These equations assume finish-to-start precedence, no resource constraints, and durations measured in a common unit such as days. Alternative relationships—start-to-start, finish-to-finish, lags, calendars, and resource limits—require an expanded scheduling model.

6.2 CPM worked example

Consider the following project:

Forward pass:

The project duration is 13 days. The two principal paths are A–B–D–F = 11 days and A–C–E–F = 13 days, so A–C–E–F is critical.

Backward pass from day 13 gives F: LS = 11, LF = 13; D: LF = 11, LS = 9; E: LF = 11, LS = 8; B: LF = 9, LS = 5; C: LF = 8, LS = 3; and A: LF = 3, LS = 0. Thus B and D each have 2 days of float, while A, C, E, and F have zero float. Delaying a critical activity by one day normally delays the project by one day, unless corrective action or network changes are introduced.

7. PERT and Schedule Uncertainty

PERT is designed for activities whose durations are uncertain. For each activity, the planner estimates:

• optimistic time a: favourable conditions;
• most likely time m: normal conditions;
• pessimistic time b: unfavourable conditions.

The traditional beta-based PERT expected duration is:

The approximate activity variance is:

and the standard deviation is σ_i = (b-a)/6. These formulas assume the three-point estimates reasonably represent a unimodal beta-like distribution and that activity durations are measured on the same scale.

For a selected critical path, expected project duration is:

If activity durations are treated as independent, path variance is:

The approximate probability of completing by deadline D is:

where Φ is the standard normal cumulative distribution function. This approximation becomes less reliable when paths merge, activity durations are correlated, or the critical path changes under uncertainty.

PERT example

An activity has estimates a=2, m=5, and b=8 days. Its expected duration is:

Its variance is:

For a path of three independent activities with expected durations 5, 4, and 6 days and variances 1, 0.25, and 0.444, the expected path duration is 15 days and the variance is 1.694 days². Thus σ_T≈1.30 days. For a 17-day deadline, the standard score is approximately (17−15)/1.30=1.54, giving a normal-approximation completion probability of about 0.94. This should be reported as an approximation, not a guarantee.

8. Crashing and Resource Trade-offs

Crashing shortens activity duration by allocating additional resources, using overtime, subcontracting, improved technology, or alternative methods. Each activity may have a normal time and cost and a crash time and cost. The cost slope is:

The slope has units of currency per day saved. Crashing should begin with the least-cost activity on the current critical path, but only if shortening that activity actually shortens the project. When multiple critical paths exist, an activity common to all critical paths may be valuable, or several activities may need to be crashed simultaneously.

Crashing example

Suppose a critical path contains three activities:

Cost slopes are A: 300 per day, B: 300 per day, and C: 300 per day. Each day saved costs the same, but managerial feasibility may differ. If the project must be reduced by two days, any combination within activity crash limits saves two days at an additional direct cost of 600. The choice should then consider resource availability, quality, safety, overtime fatigue, and effects on other paths.

Crashing is not the same as fast-tracking. Crashing adds resources; fast-tracking changes precedence by performing activities in parallel and generally increases rework and coordination risk.

9. Resource-Constrained Project Management

Classical CPM assumes unlimited resources. In practice, two activities may require the same specialist, machine, or work area. Resource-constrained scheduling may increase project duration even when the precedence network has float.

Common heuristics include scheduling activities by minimum slack, earliest finish, or priority weighting. More rigorous approaches use integer programming, constraint programming, or metaheuristics. A resource-feasible schedule must respect both precedence and capacity constraints. A useful managerial procedure is:

1. identify scarce resources;
2. calculate demand by time period;
3. resolve over-allocation using activity priorities;
4. recalculate the critical path and floats;
5. communicate the effect on cost, risk, and completion date.

Resource levelling avoids peaks by moving activities, often extending the schedule. Resource smoothing uses available float to reduce variation while preserving the target completion date where possible.

10. Illustrative Case: Regional Medical-Device Distribution Project

Background. A medical-device company plans a regional distribution centre. The project includes site approval, facility design, equipment procurement, installation, regulatory validation, and staff training. Delays would postpone market entry and may affect hospitals relying on the new supply point.

Problem. Management must connect six locations in a secure data-and-voice network, determine shipment routes from the plant to hospitals, and schedule the facility project under uncertain validation times.

Analysis. The IT team uses an MST model to identify a low-cost initial physical connection among all offices, then adds a redundant link because the MST alone has no protection against single-link failure. Shipment routing is modelled as a minimum-cost flow with plant supply, hospital demand, vehicle capacities, and lane costs. A maximum-flow analysis checks whether the distribution system can deliver the required peak daily volume. Shortest paths are used for emergency deliveries, but travel-time variability is recorded rather than hidden.

For the project, CPM identifies site approval–design–installation–validation–opening as the principal critical chain. PERT estimates show that validation has the largest variance. Rather than crashing every activity, management invests in an additional validation team and pre-submits documentation. The intervention reduces validation uncertainty and cost less than accelerating low-risk procurement activities.

Outcome. The integrated analysis produces a low-cost connected infrastructure, confirms that normal capacity is adequate but peak demand requires a contingency carrier, and raises the estimated probability of opening by the contractual date. The project manager maintains a risk register for regulatory changes, supplier delays, and resource conflicts.

Learning points. A network objective must match the decision: MST minimizes connection cost, shortest path minimizes a route measure, maximum flow tests throughput, and minimum-cost flow allocates quantities. Similarly, CPM identifies schedule logic, PERT represents uncertainty, and crashing evaluates time–cost trade-offs. No single model answers all questions.

11. Technology, Governance, and Contemporary Practice

Enterprise project-management systems integrate precedence networks, calendars, resource profiles, cost data, and progress updates. Geographic information systems support location-based shortest-path and network-flow analyses. Digital twins can connect live capacity and asset-condition data to network models. Machine-learning models may improve travel-time or activity-duration forecasts, but they do not replace conservation laws, precedence logic, or managerial accountability.

Good governance requires version control, documented assumptions, data lineage, and validation against actual performance. Automated routing can create unfair service outcomes if demand or accessibility data are biased. Emergency logistics models should explicitly include vulnerable populations and service-priority rules. In infrastructure design, a mathematically cheapest network may be unacceptable if it creates safety, privacy, environmental, or resilience risks.

Important limitations include:

• deterministic arc costs may ignore congestion and time dependence;
• estimated capacities may be optimistic;
• PERT’s normal approximation can understate tail risk;
• critical paths can change as durations change;
• correlations among activities violate simple variance addition;
• resource constraints can invalidate classical CPM results;
• optimization outputs are only as credible as the data and model assumptions.

Best practice is therefore to perform sensitivity analysis, scenario analysis, and post-project comparison of predicted and actual times, costs, flows, and failures. Managers should distinguish an optimal solution under a model from a robust solution under uncertainty.

Chapter Summary

Network optimization models connected systems using nodes, arcs, costs, capacities, and flow-balance relationships. Shortest-path models select a least-weight route; Dijkstra’s algorithm is appropriate for non-negative weights. Minimum-spanning-tree models connect all nodes at minimum total edge cost but do not provide redundancy or necessarily minimize point-to-point travel. Maximum-flow models determine system throughput under capacity constraints, and the maximum-flow/minimum-cut theorem provides an important optimality interpretation. Minimum-cost-flow models allocate quantities through capacitated networks at minimum total cost.

CPM uses deterministic durations and forward and backward passes to calculate earliest and latest times, float, project duration, and critical paths. PERT uses optimistic, most likely, and pessimistic estimates to approximate expected durations and uncertainty. Crashing evaluates the marginal cost of reducing durations, while resource-constrained scheduling recognizes that limited people, equipment, and facilities can alter the schedule. Effective professional practice combines optimization with sensitivity analysis, governance, resilience, ethics, and informed managerial judgement.

Key Terms

Network: A set of nodes connected by arcs or edges.

Node: A point representing a location, event, or state.

Arc: A directed connection between two nodes.

Path: A sequence of connected arcs.

Shortest path: A minimum-weight route between specified nodes.

Minimum spanning tree: A least-cost tree connecting every node in an undirected connected graph.

Capacity: The maximum permissible flow on an arc.

Maximum flow: The greatest feasible flow from a source to a sink.

Cut: A partition separating a source from a sink.

Minimum-cost flow: A flow satisfying supplies, demands, and capacities at minimum total cost.

Flow conservation: Equality of inflow and outflow at a transshipment node.

CPM: A deterministic project-scheduling method based on precedence and durations.

PERT: A project-scheduling method using three-point duration estimates.

Critical path: The longest-duration precedence path controlling project completion.

Float: Time by which an activity can be delayed without delaying the project.

Crashing: Reducing activity duration by adding resources or incurring extra cost.

Fast-tracking: Performing formerly sequential work in parallel.

Resource levelling: Rescheduling to reduce resource peaks, possibly extending duration.

Residual network: A network showing remaining and reversible flow possibilities.

Review Questions

5 Short Answer Questions

1. What is the difference between a path and a spanning tree?
2. Why can Dijkstra’s algorithm fail when an arc has a negative weight?
3. State the maximum-flow/minimum-cut theorem.
4. How is total float calculated in CPM?
5. What three estimates are required for traditional PERT?

5 Long Answer Questions

1. Explain the formulation, assumptions, and managerial uses of shortest-path and minimum-cost-flow models.
2. Compare Kruskal’s and Prim’s algorithms, including their suitability for infrastructure design.
3. Describe the forward-pass and backward-pass procedures in CPM and explain how critical activities are identified.
4. Derive the PERT expected-time and variance calculations and discuss the limitations of the normal approximation.
5. Explain how crashing, fast-tracking, resource levelling, and resource smoothing differ.

3 Analytical / Application Questions

1. A distribution network has excess source capacity but inadequate hospital-delivery capacity. Explain how a minimum-cut analysis would identify the bottleneck and recommend two managerial responses.
2. A project has two nearly equal paths, and activity-duration estimates are correlated because both depend on the same supplier. Explain why a simple PERT variance calculation may be misleading and propose a better analysis.
3. Design a modelling approach for a disaster-relief network that must minimize cost while meeting demands, respecting vehicle capacities, and guaranteeing service to priority hospitals. Identify the data, decision variables, constraints, objective, and ethical risks.

Multiple Choice Questions with Answers

Question 1

Which model is most appropriate for connecting every site at minimum total installation cost without requiring a particular origin-to-destination route?

A. Shortest path

B. Minimum spanning tree

C. Maximum flow

D. PERT

Correct Answer: B. Minimum spanning tree

Question 2

Dijkstra’s algorithm requires arc weights to be:

A. All equal

B. Non-negative

C. Strictly negative

D. Integer only

Correct Answer: B. Non-negative

Question 3

In a maximum-flow model, what does an arc capacity represent?

A. The minimum route cost

B. The maximum permissible flow on the arc

C. The number of nodes in a cut

D. The project float

Correct Answer: B. The maximum permissible flow on the arc

Question 4

If an activity has optimistic time 2 days, most likely time 5 days, and pessimistic time 8 days, its PERT expected time is:

A. 4 days

B. 5 days

C. 6 days

D. 8 days

Correct Answer: B. 5 days

Question 5

For an activity with ES = 7 and EF = 11, what is its duration?

A. 3 days

B. 4 days

C. 7 days

D. 18 days

Correct Answer: B. 4 days

Question 6

Which statement about a critical-path activity is generally correct in classical CPM?

A. It has the highest direct cost

B. It has zero total float

C. It can always be delayed without consequence

D. It must be the shortest activity

Correct Answer: B. It has zero total float

Question 7

The cost slope for crashing an activity is calculated as:

A. Normal cost ÷ normal time

B. Crash cost ÷ crash time

C. (Crash cost − normal cost) ÷ (normal time − crash time)

D. (Normal cost − crash cost) ÷ (crash time − normal time)

Correct Answer: C. (Crash cost − normal cost) ÷ (normal time − crash time)

Question 8

If independent activities on a PERT path have variances 1, 0.25, and 0.49 days², the path variance is:

A. 0.58 days²

B. 1.25 days²

C. 1.74 days²

D. 2.49 days²

Correct Answer: C. 1.74 days²

Question 9

Which condition is required for a balanced minimum-cost-flow model without dummy nodes?

A. Total supply equals total demand

B. Every arc has the same cost

C. There is only one customer

D. All capacities are unlimited

Correct Answer: A. Total supply equals total demand

Question 10

What is the principal difference between crashing and fast-tracking?

A. Crashing changes costs; fast-tracking changes network sequencing

B. Crashing reduces quality automatically; fast-tracking eliminates resources

C. Crashing applies only to transportation; fast-tracking applies only to trees

D. There is no difference

Correct Answer: A. Crashing changes costs; fast-tracking changes network sequencing