Network, Scheduling and Allocation Models

Introduction

Business decisions often involve movement, connection, sequencing, timing, or assignment. A logistics manager may need to find the least-cost route between warehouses; a project manager must determine which activities control completion time; and a human-resources manager may assign employees to jobs while minimizing cost. These decisions can be represented by mathematical models based on graphs and networks.

Network models are particularly valuable because they convert complex relationships into a structured representation of nodes, arcs, and weights. Scheduling models extend this logic to precedence and time. Transportation and assignment models address the allocation of scarce resources to destinations or tasks.

This chapter develops the principal models used in business analytics: shortest path, minimum spanning tree, maximum flow, transportation, assignment, CPM, and PERT. The emphasis is on formulation, solution logic, interpretation, and managerial limitations.

Learning Objectives

After studying this chapter, you should be able to:

1. Represent business systems using nodes, arcs, directed graphs, and weighted networks.
2. Solve shortest-path and minimum-spanning-tree problems.
3. Formulate transportation and assignment models and interpret their solutions.
4. Apply CPM to identify critical activities, project duration, and slack.
5. Apply PERT to incorporate uncertain activity times.
6. Diagnose bottlenecks, resource constraints, and limitations of network models.

1. Network Model Foundations

A graph consists of a set of vertices and edges. In business applications, vertices are usually locations, events, departments, or tasks, while edges represent roads, communication links, feasible transfers, or precedence relationships.

A network is a graph in which numerical values, called weights, are attached to arcs or nodes. A weight may represent distance, cost, time, capacity, risk, or energy consumption.

A mathematical network can be written as G = (N,A), where N is the set of nodes and A is the set of arcs. A network model is useful only when its assumptions reflect the actual decision environment.

Common assumptions include known costs, feasible connections, additive path values, and independence of activities where required. If travel times vary by congestion or costs depend on volume, a simple fixed-weight network may be inadequate.

2. Shortest-Path Models

The shortest-path problem seeks a route from an origin node to a destination node that minimizes total weight. The weight may be distance, travel time, or cost.

For a path P, its total weight is:

Here, w_ij is the weight of arc from node i to node j. The formula assumes that path weights are additive and that arc weights are known. Dijkstra’s algorithm applies when all arc weights are nonnegative. If negative weights exist, another method, such as Bellman–Ford, is required.

Dijkstra’s Algorithm

1. Label the origin with permanent distance 0; label every other node with infinity.
2. Select the unvisited node with the smallest temporary distance.
3. Make its label permanent.
4. For each adjacent unvisited node, calculate the possible new distance through the selected node.
5. Replace a temporary label if the new distance is smaller.
6. Continue until the destination is permanent.
7. Trace predecessor labels backward to obtain the route.

Worked Example: Delivery Route

Suppose the directed network has the following travel times:

Find the fastest route from A to E. Initial labels are A = 0, B = ∞, C = ∞, D = ∞, E = ∞.

From A: B = 4 and C = 2. Make C permanent next. Through C, B becomes 3 and D becomes 10. Make B permanent. Through B, D becomes 8. Make D permanent; through D, E becomes 10. Therefore, the shortest route is A → C → B → D → E, with total time:

The route A → B → D → E also takes 11 units, so it is inferior. In practice, the model should be rerun when travel conditions, tolls, vehicle restrictions, or customer priorities change.

3. Minimum-Spanning-Tree Models

A spanning tree connects every node without creating a cycle. A minimum spanning tree (MST) is the spanning tree with the smallest possible total edge weight. It is useful when a firm needs to connect all sites at minimum installation cost—for example, through fiber-optic cable, pipelines, or electricity lines.

An MST containing n nodes has exactly n − 1 edges. It connects all nodes but does not necessarily provide the shortest route between any two specific nodes.

Kruskal’s Algorithm

1. List edges from smallest to largest weight.
2. Select the next smallest edge if it does not form a cycle.
3. Reject an edge that creates a cycle.
4. Stop after n − 1 edges have been selected.

Worked Example

For nodes A, B, C, and D, suppose the undirected edges are AB = 1, BC = 2, AC = 3, BD = 4, CD = 5, and AD = 6. Kruskal’s method selects AB, BC, and BD. These edges connect all four nodes without a cycle, with total cost:

The MST is not a route from A to D; it is a least-cost infrastructure design. This distinction is essential in managerial interpretation.

4. Maximum-Flow Models

A maximum-flow model determines the greatest quantity that can pass from a source to a sink through capacity-constrained arcs. Applications include pipeline distribution, data networks, production systems, and emergency supply chains.

For each node other than source and sink, flow conservation requires:

For every arc (i,j), flow x_ij must satisfy:

where u_ij is arc capacity. The maximum-flow value equals the flow leaving the source and entering the sink. The max-flow/min-cut theorem states that maximum feasible flow equals the capacity of the minimum cut separating source and sink. A bottleneck is an arc or cut whose capacity limits total flow.

5. Transportation Models

A transportation problem allocates shipments from sources to destinations at minimum cost. Let:

• x_ij = quantity shipped from source i to destination j;
• c_ij = unit shipping cost;
• s_i = supply at source i;
• d_j = demand at destination j.

The objective is:

subject to:

In a balanced transportation problem, total supply equals total demand, so inequalities are commonly written as equalities. If totals differ, a dummy source or destination can balance the table. A dummy cost must reflect the economic meaning of unused supply or unmet demand.

Illustrative Transportation Calculation

A firm has two plants and three markets. The cost table is:

A feasible plan is P1→M1 = 10, P1→M2 = 20, P2→M2 = 5, and P2→M3 = 15. Its cost is:

This is a feasible solution, not automatically an optimal one. Methods such as the northwest-corner method, least-cost method, Vogel’s approximation method, and the transportation simplex or MODI method can be used to obtain and test optimality. Software is appropriate for large models, but managers must still validate capacity, demand, and cost assumptions.

6. Assignment Models

An assignment problem allocates each person, machine, or employee to exactly one task, with each task receiving exactly one resource. Let x_ij be 1 if resource i is assigned to task j and 0 otherwise. The cost-minimization model is:

subject to:

The model assumes equal numbers of resources and tasks. Dummy rows or columns handle unequal numbers. The Hungarian algorithm solves the balanced assignment problem efficiently by row and column reductions followed by selection of independent zeros.

For example, if a cost matrix is:

The assignment E1→T2, E2→T1, E3→T3 has total cost 2 + 6 + 1 = 9. Assignment models should not use cost alone when fairness, qualification, safety, or workload balance is material.

7. Project Scheduling: CPM

The Critical Path Method (CPM) schedules projects when activity durations are treated as known. An activity-on-node network represents activities as nodes and precedence relationships as directed arcs.

For activity i, define:

• ES: earliest start;
• EF: earliest finish;
• LS: latest start without delaying the project;
• LF: latest finish without delaying the project;
• duration t_i.

Forward pass:

For an activity with predecessors, its earliest start is:

Backward pass:

For an activity with successors, its latest finish is:

Total slack is:

These equations assume a precedence network with fixed durations and unlimited availability of required resources unless resource constraints are modeled separately. Activities with zero total slack form at least one critical path. Delaying a critical activity delays project completion unless corrective action is taken.

CPM Example

Consider the following activities:

Forward pass gives A: ES 0, EF 3; B: ES 3, EF 7; C: ES 3, EF 5; D: ES 7, EF 12; E: ES 5, EF 8; F: ES 12, EF 14. Project duration is 14 time units.

Backward pass gives F: LF 14, LS 12; D: LF 12, LS 7; E: LF 12, LS 9; B: LF 7, LS 3; C: LF 9, LS 7; A: LF 3, LS 0. Thus A, B, D, and F have zero slack and constitute the critical path A–B–D–F. Activity C has slack 4, and E has slack 4.

8. PERT and Uncertain Duration

PERT addresses uncertainty in activity durations using three estimates:

• optimistic time a;
• most likely time m;
• pessimistic time b.

The beta-weighted expected time is:

The activity variance is:

The standard deviation is σ_i = √σ_i². These formulas assume the three-point beta approximation is reasonable and that activity estimates are meaningful.

For a critical path, expected project duration is the sum of expected activity times:

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

To estimate the probability of completing by deadline [[MATH,D]], use:

The corresponding standard normal cumulative probability is an approximation, not a guarantee. Correlated delays, changing critical paths, and resource constraints can make the estimate unreliable.

PERT Example

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

Its variance is:

If a three-activity critical path has expected durations 5, 4, and 6, and variances 1, 0.25, and 2.25, then μ_T = 15 and σ_T² = 3.5, so σ_T ≈ 1.871. For a deadline of 17, Z ≈ 1.07. The completion probability is approximately 0.86 under the stated assumptions.

9. Resource Planning and Bottleneck Analysis

A precedence-feasible schedule may still be impossible if the same employee, machine, or facility is required by simultaneous activities. Resource leveling shifts activities to reduce demand peaks, while resource-constrained scheduling explicitly includes resource limits in the optimization model.

A bottleneck is a resource or process stage whose effective capacity restricts total output. Little’s Law provides a useful operational relationship:

where L is average work-in-process, λ is average throughput rate, and W is average time in the system. Units must be consistent, such as jobs, jobs per day, and days. Increasing upstream production does not improve throughput if the bottleneck remains unchanged.

Common responses include reallocating staff, changing sequence, outsourcing, adding capacity, reducing setup time, and redesigning the process. Expediting a noncritical activity may have no effect on completion time.

10. Integrated Illustrative Case: Regional Distribution Upgrade

Background. A fictional retailer is opening three regional fulfillment centers and connecting them to stores. Management must select communication links, allocate shipments, and complete the installation before a promotional season.

Problem. The firm faces three decisions: (1) connect all centers at minimum infrastructure cost; (2) route daily shipments at minimum transport cost; and (3) schedule installation activities under uncertain durations.

Analysis and approach. The network engineer uses an MST to select links connecting all centers without redundant construction. The logistics analyst formulates a transportation model with plant capacities and store demands. The project manager constructs a CPM network for permitting, equipment delivery, installation, testing, and training. PERT estimates are used for activities affected by regulatory uncertainty. A shared technician creates a resource conflict between testing and installation, so the schedule is leveled.

Outcome. The MST reduces fixed connection cost, while the transportation model identifies the least-cost shipment pattern. CPM reveals that permitting and equipment delivery lie on the critical path. PERT shows that the launch probability is lower than the deterministic CPM schedule suggests. Management therefore expedites permits rather than training, because training has slack and does not control the launch date.

Learning points. Different models answer different questions. MST minimizes connection cost, shortest path minimizes one route, transportation allocates quantities, assignment matches one resource to one task, and CPM/PERT analyze project timing. Combining models improves decisions, but only when data definitions and assumptions remain consistent.

11. Limitations, Governance, and Best Practice

Network models can create false precision. Costs may be outdated, demand may be forecast rather than observed, and activity estimates may reflect optimism. A model can also encode unfair priorities—for example, an assignment model that minimizes labor cost by repeatedly allocating undesirable shifts to a vulnerable group.

Best practice includes:

1. Define the decision, objective, units, and constraints before collecting data.
2. Distinguish hard constraints from preferences and penalties.
3. Validate network structure with operational experts.
4. Test sensitivity to costs, capacities, demand, and durations.
5. Report alternative feasible solutions, not only one optimum.
6. Monitor actual performance and update the model.
7. Protect personal, location, and operational data.
8. Document assumptions, overrides, and model version history.

Modern optimization software, geographic information systems, and AI forecasting can improve inputs and computation. However, AI-generated recommendations require human review, especially where safety, labor rights, service equity, or regulatory compliance is involved. Explainability, auditability, and cybersecurity are essential when network decisions are automated.

Chapter Summary

Network models represent business systems through nodes, arcs, weights, capacities, and precedence relationships. Shortest-path methods identify least-cost routes; minimum-spanning-tree methods connect all nodes at minimum infrastructure cost; and maximum-flow models identify capacity-limited throughput. Transportation models allocate quantities from sources to destinations, while assignment models match individual resources with individual tasks.

CPM uses forward and backward passes to calculate project duration, critical paths, and slack. PERT incorporates optimistic, most likely, and pessimistic estimates to approximate expected duration and uncertainty. Resource leveling and bottleneck analysis extend scheduling beyond precedence alone. Effective practice requires valid data, explicit assumptions, sensitivity analysis, ethical governance, and continuing comparison between model results and operational reality.

Key Terms

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

Arc: A connection between two nodes.

Path: A sequence of connected arcs.

Weight: A numerical value such as cost, time, or distance.

Shortest path: The minimum-weight route between two nodes.

Spanning tree: A cycle-free structure connecting all nodes.

Minimum spanning tree: The least-cost spanning tree.

Capacity: Maximum allowable flow through an arc or resource.

Bottleneck: A capacity constraint limiting total system output.

Transportation model: A model allocating supply to demand at minimum cost.

Assignment model: A one-to-one resource-to-task allocation model.

CPM: A deterministic project scheduling method.

PERT: A project scheduling method using three time estimates.

Critical path: A path of activities with zero total slack.

Slack: Permissible delay without delaying project completion.

Forward pass: Calculation of earliest activity times.

Backward pass: Calculation of latest allowable activity times.

Resource leveling: Adjusting timing to reduce resource-demand peaks.

Flow conservation: Equality of inflow and outflow at an intermediate node.

Sensitivity analysis: Testing how results change when assumptions vary.

Review Questions

Short Answer Questions

1. What is the difference between a shortest path and a minimum spanning tree?
2. State the flow-conservation condition at an intermediate node.
3. What does zero total slack indicate in CPM?
4. Why might a dummy destination be added to a transportation table?
5. What three estimates are used in PERT?

Long Answer Questions

1. Explain Dijkstra’s algorithm and its applicability conditions.
2. Formulate a transportation model and explain each class of constraint.
3. Describe the forward-pass and backward-pass procedures in CPM.
4. Compare CPM and PERT in terms of duration assumptions and uncertainty.
5. Discuss ethical and governance risks in automated assignment models.

Analytical / Application Questions

1. A company must connect five offices at minimum installation cost. Explain how you would formulate and solve the problem, and why a shortest-path solution would not be appropriate.
2. A project has a nominal critical path, but two activities require the same specialist at the same time. Explain how you would revise the schedule and assess the effect on completion time.
3. A distribution network has sufficient total production but cannot meet store demand. Explain how a transportation or maximum-flow model could identify the cause and recommend an intervention.

Multiple Choice Questions with Answers

Question 1

Which algorithm is appropriate for a shortest-path network when all arc weights are nonnegative?

A. Dijkstra’s algorithm

B. Hungarian algorithm

C. Kruskal’s algorithm

D. Backward-pass algorithm

Correct Answer: A. Dijkstra’s algorithm

Question 2

A minimum spanning tree for a connected graph with n nodes contains how many edges?

A. n

B. n − 1

C. n + 1

D. 2n

Correct Answer: B. n − 1

Question 3

In a transportation model, what does xᵢⱼ usually represent?

A. The fixed cost of opening source i

B. The quantity shipped from source i to destination j

C. The demand at source i

D. The number of destinations

Correct Answer: B. The quantity shipped from source i to destination j

Question 4

If an activity has ES = 7 and duration = 5, what is its earliest finish?

A. 2

B. 7

C. 12

D. 35

Correct Answer: C. 12

Question 5

An activity with zero total slack is normally part of the:

A. Dummy route

B. Critical path

C. Minimum cut only

D. Transportation surplus

Correct Answer: B. Critical path

Question 6

For PERT estimates a = 2, m = 5, and b = 8, what is the expected activity time?

A. 4

B. 5

C. 6

D. 8

Correct Answer: B. 5

Question 7

Which constraint applies to an intermediate node in a maximum-flow model?

A. Inflow must equal outflow

B. Inflow must always be zero

C. Outflow must exceed capacity

D. Demand must equal fixed cost

Correct Answer: A. Inflow must equal outflow

Question 8

Which method is specifically designed for balanced one-to-one assignment problems?

A. Hungarian algorithm

B. Dijkstra’s algorithm

C. PERT

D. Kruskal’s algorithm

Correct Answer: A. Hungarian algorithm

Question 9

If a path has activity variances 1, 0.25, and 2.25, what is its total variance under independence?

A. 1.5

B. 2.5

C. 3.5

D. 6.0

Correct Answer: C. 3.5

Question 10

In Little’s Law, what does W represent in L = λW?

A. Average work-in-process

B. Average throughput rate

C. Average time in the system

D. Maximum capacity

Correct Answer: C. Average time in the system