Network Optimization

Network optimization problems are modelled as graphs, with nodes and weighted edges representing flow, cost, or distance.

Flow Problems

LP formulations of these models are covered in linear programming.

• Transportation problem
  Minimizes the cost of shipping goods from a set of supply nodes to a set of demand nodes.
• Transshipment problem
  Generalizes the transportation problem by allowing goods to pass through intermediate nodes.
• Assignment problem
  Minimizes the cost of assigning $n$ agents to $n$ tasks, 1 agent per task.

Network Algorithms

• Minimum connector problem
  Finds a minimum weight tree connecting all nodes, solved by algorithms such as Kruskal or Prim.
• Maximum flow problem
  Finds the maximum flow from a source node to a sink node subject to edge capacities.
• Shortest and longest path algorithms
  Finds the minimum or maximum weight path between 2 nodes.

Engineering Project Management

Critical Path Analysis

Finds the longest path through a project’s task network, determining minimum project duration.

• Forward pass
  Computes each task’s earliest start and earliest finish from project start.
• Backward pass
  Computes each task’s latest start and latest finish from project end.
• Float
  Latest start minus earliest start. The amount a task can slip without delaying the project.
• Critical path
  The chain of tasks with 0 float. Its total duration is the minimum project duration.

PERT Model

Estimates task durations probabilistically using optimistic, pessimistic, and most likely estimates.

Here:

• $o$: optimistic estimate
• $m$: most likely estimate
• $p$: pessimistic estimate
• $t_e$: expected task duration

Schedule Adjustment

• Project crashing
  Reduces project duration by allocating extra resources to critical tasks at extra cost.
• Resource smoothing
  Reschedules tasks within their float to balance resource usage, without extending project duration.
• Resource leveling
  Reschedules tasks to keep resource usage under a fixed limit, extending project duration if necessary.