77  Scheduling, Loading and Sequencing

77.1 What are Scheduling, Loading and Sequencing?

Once capacity and materials are planned, operations needs to decide when each job gets done, which machine handles it, and in what order. The three closely-related functions:

TipThree Operations Functions
Function Question it answers
Loading Which work-centre / machine handles each job?
Sequencing In what order should the jobs be done?
Scheduling When (start, finish) should each job be done?

Heizer and Render frame scheduling as “the assignment of jobs to specific times in the operations plan” (heizerrender2020?).

77.2 Forward vs Backward Scheduling

TipForward vs Backward Scheduling
Type What it does Use
Forward scheduling Start work as soon as the order is received; finish as early as possible Jobs without firm due dates
Backward scheduling Start with the due date and work backward to when each task must begin Jobs with firm due dates

77.3 Loading Methods

TipTwo Loading Approaches
Approach Description
Infinite loading Assume infinite capacity; check feasibility later
Finite loading Schedule no job that exceeds capacity in any period

The classical visual tools:

TipThree Visual Tools for Loading
Tool What it shows
Gantt load chart Current load on each work-centre
Gantt schedule chart Time-phased plan for each job
Assignment method (Hungarian) Optimal one-to-one assignment of jobs to machines / workers

The Hungarian assignment method (Harold Kuhn, 1955) is the textbook algorithm for the special case where each job must be assigned to one machine and each machine to one job, minimising total cost.

77.4 Sequencing Rules

When several jobs await processing on the same machine, which job goes first? Common priority rules:

TipCommon Priority Sequencing Rules
Rule What it does
FCFS (First-Come-First-Served) Process in order of arrival
SPT (Shortest Processing Time) Shortest jobs first
LPT (Longest Processing Time) Longest jobs first
EDD (Earliest Due Date) Jobs nearest due date first
CR (Critical Ratio) (Time remaining ÷ Work remaining); lowest first
Slack per Operation Slack ÷ remaining operations
TipPerformance of Priority Rules
Rule Best for
SPT Average flow time, average lateness, average WIP
EDD Maximum tardiness, minimising lateness
FCFS Fairness; simplicity

SPT minimises average flow time is one of the most-tested rules.

77.5 Johnson’s Rule for Two-Machine Sequencing

S.M. Johnson’s algorithm (1954) finds the optimal sequence for n jobs on two machines in series, minimising total processing time (makespan) (johnson1954?):

TipJohnson’s Rule — Two Machines
Step Action
1 List the jobs and their times on Machine 1 and Machine 2
2 Find the smallest time across all jobs and machines
3 If on Machine 1 → schedule that job first (earliest available slot)
4 If on Machine 2 → schedule that job last (latest available slot)
5 Cross out the scheduled job and repeat

The result is the optimal sequence — minimum makespan and idle time on Machine 2.

77.6 Network Scheduling — PERT and CPM

For projects with many activities and dependencies, use network methods. Two classical:

TipPERT vs CPM
Method Origin What it captures
PERT (Program Evaluation and Review Technique) US Navy Polaris (1958) Probabilistic activity times — uses three time estimates (optimistic, most likely, pessimistic)
CPM (Critical Path Method) DuPont (1957) Deterministic activity times — focuses on the critical path
TipKey Network-Scheduling Concepts
Concept Definition
Activity Task that consumes time and resources
Event Start or end of an activity (a node)
Critical path Longest path through the network — determines minimum project duration
Slack / Float Time an activity can be delayed without delaying the project
Forward pass Compute Earliest Start (ES) and Earliest Finish (EF)
Backward pass Compute Latest Start (LS) and Latest Finish (LF)
Crashing Reduce activity time at additional cost

PERT’s expected time (Beta distribution):

\[T_e = \frac{a + 4m + b}{6}, \quad \sigma^2 = \left(\frac{b - a}{6}\right)^2\]

where \(a\) = optimistic, \(m\) = most likely, \(b\) = pessimistic.

flowchart LR
  A[Start] --> B[Activity 1<br/>Days 0-3]
  A --> C[Activity 2<br/>Days 0-5]
  B --> D[Activity 3<br/>Days 3-8]
  C --> E[Activity 4<br/>Days 5-9]
  D --> F[End]
  E --> F
  style A fill:#E3F2FD,stroke:#1565C0
  style F fill:#E8F5E9,stroke:#2E7D32

77.7 Theory of Constraints (TOC) — Drum-Buffer-Rope

Eliyahu Goldratt’s Theory of Constraints (goldratt1984?) focuses on the bottleneck — the constraint that limits throughput. The drum-buffer-rope scheduling approach:

  • Drum — the bottleneck sets the pace.
  • Buffer — protective inventory before the bottleneck.
  • Rope — pull signal that releases work into the system.

77.8 Practice Questions

Q 01 Functions Easy

Choosing the order in which jobs are processed is:

  • ALoading
  • BSequencing
  • CScheduling
  • DCapacity planning
View solution
Correct Option: B
Sequencing = order of jobs. Loading = which machine; Scheduling = when (start/finish).
Q 02 SPT Medium

The Shortest Processing Time (SPT) rule minimises:

  • AMaximum tardiness
  • BAverage flow time and average WIP
  • CTotal cost of inventory
  • DSetup time only
View solution
Correct Option: B
SPT minimises average flow time, average lateness, and average WIP. EDD minimises maximum tardiness.
Q 03 Johnson Medium

Johnson's rule applies to sequencing:

  • An jobs on two machines in series
  • BOne job on n machines
  • Cn jobs on one machine
  • DProject networks
View solution
Correct Option: A
Johnson's rule (1954) — optimal sequence for n jobs on two machines in series, minimising makespan.
Q 04 PERT Medium

In PERT, the expected activity time is computed as:

  • A(a + b) ÷ 2
  • B(a + 4m + b) ÷ 6
  • C(a + m + b) ÷ 3
  • Dm alone
View solution
Correct Option: B
T_e = (a + 4m + b) ÷ 6 — Beta-distribution weighted average of optimistic, most likely, pessimistic.
Q 05 Critical Path Medium

The "critical path" of a project is:

  • AThe shortest path through the network
  • BThe longest path — determines minimum project duration
  • CThe path through the most expensive activities
  • DThe path through optional activities
View solution
Correct Option: B
Critical path = longest path = minimum project duration. Activities on it have zero slack.
Q 06 PERT vs CPM Medium

PERT differs from CPM in that:

  • APERT is deterministic; CPM is probabilistic
  • BPERT is probabilistic (three time estimates); CPM is deterministic
  • CBoth are identical
  • DPERT is for cost; CPM is for time
View solution
Correct Option: B
PERT (US Navy, 1958) — three time estimates (a, m, b), probabilistic. CPM (DuPont, 1957) — single estimate, deterministic.
Q 07 Hungarian Medium

The Hungarian method is used for:

  • AOptimal one-to-one assignment of jobs to machines / workers
  • BProject scheduling
  • CEOQ calculations
  • DQuality control
View solution
Correct Option: A
Hungarian assignment method (Kuhn, 1955) — minimises total cost in one-to-one assignment problems.
Q 08 TOC Medium

Goldratt's "Drum-Buffer-Rope" scheduling approach within Theory of Constraints uses the bottleneck as the:

  • ADrum (sets the pace)
  • BRope (signal)
  • CBuffer (inventory)
  • DAll three
View solution
Correct Option: A
The Drum = the bottleneck setting the pace. Buffer = protective inventory; Rope = release signal.
ImportantQuick recall
  • Three functions: Loading (which machine) · Sequencing (in what order) · Scheduling (when).
  • Forward vs Backward scheduling. Infinite vs finite loading.
  • Visual tools: Gantt charts; Hungarian assignment (Kuhn 1955).
  • Sequencing rules: FCFS, SPT (best for avg flow time), LPT, EDD (best for max tardiness), CR.
  • Johnson’s rule (1954) — optimal sequence for n jobs on two machines.
  • PERT (probabilistic, 1958, Polaris) vs CPM (deterministic, 1957, DuPont). T_e = (a + 4m + b) / 6.
  • Critical path = longest path = min project duration; activities on it have zero slack.
  • TOC (Goldratt) — drum-buffer-rope, bottleneck-driven scheduling.