78  Scheduling, Loading and Sequencing

78.1 Concept

Scheduling = the assignment of jobs to specific time slots and resources. Loading = assignment of work to workstations. Sequencing = order in which jobs are processed. These three together turn the Master Production Schedule (MPS) into executable shop-floor instructions.

78.2 Loading

TipLoading approaches
  • Finite loading — capacity not exceeded; jobs delayed if needed.
  • Infinite loading — assume infinite capacity, then adjust.
  • Forward scheduling — start ASAP from current date.
  • Backward scheduling — start from due date and work backwards.
  • Mixed scheduling — combine forward and backward.

78.3 Gantt Chart

Henry L. Gantt (early 1900s) — visual bar chart showing schedule. Still the most widely used tool in PM.

78.4 Sequencing Rules (Priority Rules)

TipCommon priority rules
Rule Description
FCFS First Come, First Served
SPT Shortest Processing Time
LPT Longest Processing Time
EDD Earliest Due Date
CR Critical Ratio = (due date − today) / processing time
S/O Slack per Operation
Random Random selection

78.5 Performance Measures

TipScheduling performance measures
  • Makespan — total time to complete all jobs.
  • Mean Flow Time — average time in system.
  • Average Lateness / Tardiness.
  • Number of Tardy Jobs.
  • Average WIP.
  • Utilisation.
  • Throughput.

78.6 Single-Machine Sequencing

TipSingle-machine results
  • SPT minimises average flow time and average lateness (proven optimal).
  • EDD minimises maximum lateness.
  • Moore’s Algorithm — minimise number of tardy jobs.

78.7 Two-Machine Sequencing — Johnson’s Rule (1954)

Johnson’s Rule (S.M. Johnson 1954) — optimal sequence for n jobs on 2 machines to minimise makespan.

TipJohnson’s rule steps
  1. List all jobs with times on Machine 1 (M1) and Machine 2 (M2).
  2. Find shortest processing time.
  3. If on M1, schedule as early as possible.
  4. If on M2, schedule as late as possible.
  5. Remove the job and repeat.

Johnson’s Rule extended for n-job, 3-machine problems under specific conditions.

78.8 Job Shop Scheduling (n × m)

For n jobs on m machines — NP-hard. Solved by heuristics, branch-and-bound, simulation, or AI / GA / Reinforcement Learning.

78.9 Network Scheduling — CPM and PERT

TipProject scheduling
  • CPM (Critical Path Method) — DuPont 1957 — deterministic times.
  • PERT (Program Evaluation and Review Technique) — US Navy 1958, Polaris — probabilistic times.
  • PERT time estimates: t = (o + 4m + p) / 6.
  • Variance = ((p − o)/6)².
  • Critical path — longest sequence, zero slack.
  • Float / Slack: Total · Free · Independent.
  • Crashing — reducing duration by adding resources.
  • Resource levelling.
  • Gantt charts for visualisation.

78.10 Manufacturing Scheduling Systems

TipManufacturing scheduling systems
  • MRP / ERP — central planning.
  • Drum-Buffer-Rope (Goldratt TOC).
  • Kanban / Pull (Toyota).
  • Conwip — Constant WIP.
  • Heijunka — Level loading.
  • Theory of Constraints.
  • Advanced Planning and Scheduling (APS) — SAP APO, Kinaxis, o9.
  • Finite Capacity Scheduling (FCS).
  • Manufacturing Execution System (MES).

78.11 Service Scheduling

TipService-sector scheduling
  • Appointment scheduling — hospitals, clinics.
  • Reservation systems — hotels, airlines.
  • Cyclic / staff scheduling.
  • Yield management.
  • Call centres — Erlang C formula.

78.13 Practice Questions

Q 01GanttEasy

Gantt chart was developed in early 1900s by:

  • AHenry L. Gantt
  • BTaylor
  • CGilbreth
  • DFord
View solution
Correct Option: A
Henry L. Gantt (~1910).
Q 02SPTMedium

SPT rule minimises:

  • AAverage flow time
  • BMaximum tardiness
  • CMakespan
  • DSetup cost
View solution
Correct Option: A
SPT — Shortest Processing Time → minimises average flow time.
Q 03JohnsonHard

Johnson's Rule (1954) is for:

  • An jobs, 2 machines
  • B1 job, n machines
  • Cn jobs, n machines
  • DPERT
View solution
Correct Option: A
2-machine optimal sequence.
Q 04CPMMedium

CPM (1957) was developed by:

  • ADuPont
  • BUS Navy
  • CGM
  • DIBM
View solution
Correct Option: A
DuPont, Remington Rand 1957.
Q 05PERTMedium

PERT (1958) was developed for:

  • AUS Navy Polaris missile
  • BNASA Apollo
  • CDuPont chemicals
  • DToyota
View solution
Correct Option: A
Polaris submarine program.
Q 06EDDMedium

EDD priority rule minimises:

  • AMaximum lateness
  • BAverage flow
  • CSetup time
  • DWIP
View solution
Correct Option: A
Earliest Due Date — max lateness.
Q 07PERT formulaHard

PERT expected time:

  • A(o + 4m + p)/6
  • B(o + m + p)/3
  • Co + p
  • Dm × 6
View solution
Correct Option: A
Beta distribution mean.
Q 08Critical PathMedium

Critical path is the:

  • ALongest path with zero slack
  • BShortest path
  • CMost expensive path
  • DLast activity
View solution
Correct Option: A
Longest sequence; any delay delays project.
Q 09DBRHard

Drum-Buffer-Rope is from:

  • ATheory of Constraints (Goldratt)
  • BTPS
  • CSix Sigma
  • DJIT
View solution
Correct Option: A
Eli Goldratt — TOC scheduling.
Q 10KanbanMedium

Kanban is a:

  • APull-signal card
  • BPush system
  • CMRP module
  • DPERT chart
View solution
Correct Option: A
Toyota pull system.
Q 11ForwardMedium

Forward scheduling means:

  • AStart as soon as possible
  • BStart from due date
  • CRandom
  • DIdle time
View solution
Correct Option: A
From today forward.
Q 12MooreHard

Moore's algorithm minimises:

  • ANumber of tardy jobs
  • BMakespan
  • CIdle time
  • DSetup
View solution
Correct Option: A
Number of late jobs minimised.
Q 13APSHard

APS stands for:

  • AAdvanced Planning and Scheduling
  • BAggregate Production Sequencing
  • CAnnual Production Spread
  • DAutomated Process Solution
View solution
Correct Option: A
SAP APO, Kinaxis, o9 etc.
Q 14ErlangHard

Erlang C formula is used in:

  • ACall centres / queuing
  • BInventory
  • CNetwork
  • DSampling
View solution
Correct Option: A
Staff sizing in call centres.
Q 15NP-hardHard

General job-shop scheduling is:

  • ANP-hard
  • BPolynomial time
  • CTrivial
  • DConstant time
View solution
Correct Option: A
No known polynomial-time algorithm.

78.13.1 Advanced Format Questions

AR 1Assertion-ReasonHard

A: Johnson's rule is optimal for n jobs on 2 machines.
R: It minimises makespan.

  • ABoth true; R explains A
  • BBoth true; R does not explain A
  • CA true, R false
  • DA false, R true
View solution
Correct Option: A
S 1Statement-basedMedium

Sequencing rules: (i) FCFS. (ii) SPT. (iii) EDD. (iv) CR.

  • AAll four
  • B(i) and (ii) only
  • C(iii) and (iv) only
  • D(i) only
View solution
Correct Option: A
N 1NumericalHard

PERT: o = 4, m = 6, p = 14 days. Expected time:

  • A7
  • B6
  • C8
  • D10
View solution
Correct Option: A
(4 + 4×6 + 14)/6 = 42/6 = 7.
N 2NumericalHard

PERT variance for above activity = ((p−o)/6)²:

  • A2.78
  • B10
  • C1.67
  • D5
View solution
Correct Option: A
((14−4)/6)² = (10/6)² ≈ 2.78.

78.14 Quick Recall

ImportantQuick recall
  • Loading: Finite/Infinite; Forward / Backward / Mixed scheduling.
  • Sequencing rules: FCFS · SPT (min avg flow) · LPT · EDD (min max lateness) · CR · S/O · Random.
  • Moore’s algorithm — min number of tardy jobs.
  • Performance: Makespan · Flow time · Lateness · Tardiness · WIP · Utilisation · Throughput.
  • Johnson’s Rule (1954) — n jobs, 2 machines, min makespan.
  • Job shop n×m — NP-hard.
  • Project scheduling: CPM (DuPont 1957) deterministic · PERT (US Navy 1958, Polaris) probabilistic; t=(o+4m+p)/6; Variance=((p−o)/6)².
  • Slack / Float; Crashing; Resource levelling; Gantt (Henry Gantt, c.1910).
  • Mfg scheduling systems: MRP/ERP · Drum-Buffer-Rope (Goldratt TOC) · Kanban · Conwip · Heijunka · APS · MES.
  • Service: appointments · reservations · cyclic staff · yield management · Erlang C for call centres.
  • Modern: AI/ML · GA · simulated annealing · real-time/dynamic · Digital Twin · predictive · cloud APS (o9, Kinaxis, Anaplan) · AGV · last-mile · quantum-inspired.