Study guide

7.3 Production Sequencing, Dispatching Rules & Johnson's Algorithm

PE Industrial and Systems Exam

Track your progress as you read

Finished sections get a check mark.

1 Exam Overview, Strategy & Systems Foundations

1.1 PE Industrial Exam Format, Official Specification & Reference Handbook Strategy 1.2 System Analysis Tools, Process Definition, Requirements Engineering & QFD 1.3 Performance Measures: Output, Productivity, OEE, Cost & Environmental Sustainability 1.4 Process Types (Discrete, Continuous, Manufacturing, Service) & Value Analysis/Engineering

2 Optimization, Queueing, Simulation, Networks & Markov Chains

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis 2.2 Queueing Theory Models (M/M/1, M/M/s) & Little's Law Applications 2.3 Discrete-Event Simulation, Random Variates & Model Validation 2.4 Graph Theory & Network Models: Shortest Path, Minimal Spanning Tree & Maximum Flow 2.5 Markov Chains: Transition Matrices, Steady-State Probabilities & Absorbing States 2.6 Decision Trees, Expected Value & Bottleneck Analysis (Theory of Constraints)

3 Project Management & Planning

3.1 Project Scheduling with CPM and PERT: Critical Path, Float, Probability & Crashing 3.2 Project Planning & Control: Scope and WBS, Gantt Charts, Critical Chain (CCPM), Risk & Earned Value

4 Facility Layout, Space, Capacity & Material Handling

4.1 Systematic Layout Planning (SLP) & Activity Relationship (REL) Analysis 4.2 Workstation Design, Aisle Sizing & Space Requirements Planning 4.3 Capacity Analysis: Machine Requirements, Scrap Allowances & Personnel Requirements 4.4 Material Handling Equipment Selection, Unit Loads & Handling Principles

5 Site Location, Warehousing & Facility Economics

5.1 Facility Location Models: Center of Gravity & Minisum / Minimax Distance 5.2 Warehousing Systems, Storage Assignment & Order Picking Operations 5.3 Facility Life-Cycle Economics, Replacement Analysis & Rearrangement Costs

6 Demand Forecasting, Production Planning, MRP & JIT

6.1 Demand Forecasting Methods: Moving Averages, Exponential Smoothing & Error Metrics 6.2 Aggregate Planning Strategies & Master Production Scheduling (MPS) 6.3 Material Requirements Planning (MRP), Bill of Materials & Capacity Planning 6.4 Just-in-Time & Lean Production Planning: Pull Systems, Kanban Sizing, Heijunka & SMED

7 Inventory Systems, Scheduling, Logistics & Transportation Modes

7.1 Deterministic Inventory Control: Classical EOQ, EPQ & Quantity Discounts 7.2 Stochastic Inventory Management: Safety Stock, Continuous / Periodic Review & Newsvendor 7.3 Production Sequencing, Dispatching Rules & Johnson's Algorithm 7.4 Supply Chain Logistics, Transportation Simplex & Distribution Network Design 7.5 Transportation Modes, Freight Economics & the Transshipment Model

8 Engineering Economics, Break-Even Analysis & Costing Systems

8.1 Equivalence, Cash Flow Analysis & Discounted Cash Flow Metrics (PW, FW, EAC) 8.2 Rate of Return Analysis (IRR, Incremental IRR) & Benefit-Cost (B/C) Ratios 8.3 Asset Depreciation (MACRS, Straight-Line), Tax Effects & Replacement Decisions 8.4 Break-Even Analysis, Technical Capability Assessment & Costing Systems (Traditional, ABC & Standard Costs)

9 Methods Engineering, Work Measurement, Learning Curves, Line Balancing & Process Planning

9.1 Methods Analysis, Process Charting & Motion Study (Therbligs, 5S) 9.2 Worker–Machine (Man–Machine) Charts, Multiple Activity Analysis & Synchronous Servicing 9.3 Time Study Fundamentals, Performance Rating & Allowance Factors 9.4 Predetermined Motion Time Systems (PMTS, MTM, MOST) & Work Sampling 9.5 Learning Curves: Unit and Cumulative-Average Models, Learning Rates & Applications 9.6 Assembly Line Balancing, Precedence Constraints & Efficiency Heuristics 9.7 Manufacturing & Service Process Planning: Operation Selection, Sequencing, Route Sheets, Fixturing & Mistake Proofing

10 Ergonomics, Human Capacity, Occupational Safety & DART Rates

10.1 Anthropometry, Percentile Design, Workstation Ergonomics & Link Analysis 10.2 Industrial Biomechanics, the NIOSH Lifting Equation & Lifting Aids 10.3 Limits of Human Capacity & Risk-Factor Tools: Work Physiology, Strength, Range of Motion, Vision, RULA & Slip Resistance 10.4 Environmental Ergonomics (Noise, Heat, Illumination), Human-Machine Systems & OSHA Safety 10.5 Safety Codes, Standards & Voluntary Guidelines (OSHA, ANSI, NIOSH, MIL-STD) and DART Rate Calculations

11 Statistical Process Control & Process Capability

11.1 Statistical Process Control for Variables (X-bar/R and X-bar/s Charts) 11.2 Statistical Process Control for Attributes (p, np, c, and u Charts) 11.3 Process Capability Indices (Cp, Cpk, Cpm, Pp, Ppk) & Sigma Levels

12 Design of Experiments, Acceptance Sampling & Quality Systems

12.1 Design of Experiments: 2^k Factorials, ANOVA & Taguchi Robust Design 12.2 Acceptance Sampling: OC Curves, AQL, LTPD, AOQL, Z1.4/MIL-STD-105E & Dodge-Romig 12.3 Quality Systems (Deming, TQM, ISO 9000, Benchmarking), Root Cause Analysis & DMAIC

13 Reliability Engineering & Maintenance Systems

13.1 Reliability Modeling, Failure Rates (lambda) & Life Distributions (Exponential, Weibull) 13.2 System Reliability Architecture: Series, Parallel, k-out-of-n & Redundancy 13.3 Equipment Maintenance Engineering, Availability (A), MTBF/MTTR & RCM

7.3 Production Sequencing, Dispatching Rules & Johnson's Algorithm

Key Takeaways Explain This Topic AI

Single-machine scheduling performance metrics—mean flow time, makespan, mean lateness, and mean tardiness—capture distinct operational objectives; while makespan is fixed for any non-preemptive sequence, flow time and tardiness depend heavily on job dispatch order.

Shortest Processing Time (SPT) mathematically minimizes mean flow time, mean completion time, mean waiting time, and average work-in-process (WIP) level via Little's Law.

Earliest Due Date (EDD) minimizes the maximum lateness (L_{max}) and maximum tardiness (T_{max}) according to Jackson's Theorem, making it the optimal rule when severe contractual penalties apply to late jobs.

Critical Ratio ( CR = Due Date − Current Time Remaining Processing Time \text{CR} = \frac{\text{Due Date} - \text{Current Time}}{\text{Remaining Processing Time}} CR = Remaining Processing Time Due Date − Current Time ​ ) provides a dynamic dispatching index: CR < 1 \text{CR} < 1 CR < 1 signals a job behind schedule, CR = 1 \text{CR} = 1 CR = 1 is exactly on schedule, and CR > 1 \text{CR} > 1 CR > 1 represents positive slack.

Johnson's Rule guarantees the optimal minimum makespan for n jobs across a two-machine flow shop by sequencing jobs with shortest processing time on Machine 1 earliest and Machine 2 latest.

Last updated: October 2026

Production Sequencing, Dispatching Rules & Johnson's Algorithm

Operations scheduling transforms aggregate production plans and master production schedules into actionable, short-interval execution sequences on the factory floor. While aggregate planning operates across monthly buckets, production scheduling allocates specific jobs, tooling, and labor to discrete machines over shift, hourly, or minute-by-minute timeframes.

In manufacturing environments, sequencing determines the exact order in which waiting jobs are processed at a workstation. Because machine capacity is finite, queue dispatching decisions dictate manufacturing lead times, work-in-process (WIP) accumulation, machine utilization, and on-time customer delivery performance.

1. Single-Machine Scheduling Framework & Performance Measures

The fundamental building block of scheduling theory is the single-machine model ( 1 ∣ ∣ γ 1 || \gamma 1∣∣ γ ). In this formulation, n n n distinct jobs are available at time t = 0 t = 0 t = 0 awaiting processing on a single, continuously available processing unit. Preemption is prohibited (once processing begins on a job, it must run to completion without interruption).

Primary Job Attributes

For each job i ∈ { 1 , 2 , … , n } i \in \{1, 2, \dots, n\} i ∈ { 1 , 2 , … , n } :

Processing Time ( p i p_i p i ​ ): The required machine execution time (including setup, run time, and teardown).

Due Date ( d i d_i d i ​ ): The committed contractual completion deadline.

Ready / Release Time ( r i r_i r i ​ ): The earliest time job i i i is physically available for processing ( r i = 0 r_i = 0 r i ​ = 0 for static scheduling).

Mathematical Performance Metrics

Let C i C_i C i ​ denote the completion time of job i i i under a given schedule sequence. The primary operational evaluation metrics are formulated as follows:

Flow Time ( F i F_i F i ​ ): The total elapsed span spent by job i i i in the shop environment: F i = C i − r i = C i ( when r i = 0 ) F_i = C_i - r_i = C_i \quad (\text{when } r_i = 0) F i ​ = C i ​ − r i ​ = C i ​ ( when r i ​ = 0 )

Makespan ( C m a x C_{max} C ma x ​ ): The total completion time of the entire job batch: C m a x = max ⁡ 1 ≤ i ≤ n C i = ∑ i = 1 n p i C_{max} = \max_{1 \le i \le n} C_i = \sum_{i=1}^n p_i C ma x ​ = max 1 ≤ i ≤ n ​ C i ​ = ∑ i = 1 n ​ p i ​ Crucial Property: For any non-preemptive single-machine problem without inserted idle time, makespan is strictly constant , equal to the sum of all processing times regardless of the dispatch sequence.

Mean Flow Time ( F ˉ \bar{F} F ˉ ): The average system residence time across all n n n jobs: F ˉ = 1 n ∑ i = 1 n F i = 1 n ∑ i = 1 n C i \bar{F} = \frac{1}{n} \sum_{i=1}^n F_i = \frac{1}{n} \sum_{i=1}^n C_i F ˉ = n 1 ​ ∑ i = 1 n ​ F i ​ = n 1 ​ ∑ i = 1 n ​ C i ​

Average Work-in-Process ( W I P ‾ \overline{WIP} W I P ): By Little's Law ( L = λ W L = \lambda W L = λW ), the average number of jobs residing in the shop is: W I P ‾ = ∑ i = 1 n F i C m a x = n F ˉ C m a x \overline{WIP} = \frac{\sum_{i=1}^n F_i}{C_{max}} = \frac{n \bar{F}}{C_{max}} W I P = C ma x ​ ∑ i = 1 n ​ F i ​ ​ = C ma x ​ n F ˉ ​ Minimizing mean flow time F ˉ \bar{F} F ˉ directly minimizes factory WIP inventory.

Lateness ( L i L_i L i ​ ): The deviation of completion time from committed due date: L i = C i − d i L_i = C_i - d_i L i ​ = C i ​ − d i ​

L i > 0 L_i > 0 L i ​ > 0 : Job is late (completed after due date).

L i < 0 L_i < 0 L i ​ < 0 : Job is early (completed ahead of due date).

Mean Lateness ( L ˉ \bar{L} L ˉ ): L ˉ = 1 n ∑ i = 1 n L i = F ˉ − d ˉ \bar{L} = \frac{1}{n} \sum_{i=1}^n L_i = \bar{F} - \bar{d} L ˉ = n 1 ​ ∑ i = 1 n ​ L i ​ = F ˉ − d ˉ .

Tardiness ( T i T_i T i ​ ): The non-negative measure of lateness (penalizes tardy jobs while treating early completion as zero penalty): T i = max ⁡ ( 0 , C i − d i ) = max ⁡ ( 0 , L i ) T_i = \max(0, C_i - d_i) = \max(0, L_i) T i ​ = max ( 0 , C i ​ − d i ​ ) = max ( 0 , L i ​ )

Mean Tardiness ( T ˉ \bar{T} T ˉ ): T ˉ = 1 n ∑ i = 1 n T i \bar{T} = \frac{1}{n} \sum_{i=1}^n T_i T ˉ = n 1 ​ ∑ i = 1 n ​ T i ​ .

Maximum Tardiness ( T m a x T_{max} T ma x ​ ): T m a x = max ⁡ 1 ≤ i ≤ n T i T_{max} = \max_{1 \le i \le n} T_i T ma x ​ = max 1 ≤ i ≤ n ​ T i ​ .

Number of Tardy Jobs ( N T N_T N T ​ ): The count of jobs missing their committed due dates: N T = ∑ i = 1 n U i where U i = { 1 if C i > d i 0 if C i ≤ d i N_T = \sum_{i=1}^n U_i \quad \text{where } U_i = \begin{cases} 1 & \text{if } C_i > d_i \\ 0 & \text{if } C_i \le d_i \end{cases} N T ​ = ∑ i = 1 n ​ U i ​ where U i ​ = { 1 0 ​ if C i ​ > d i ​ if C i ​ ≤ d i ​ ​

2. Priority Dispatching Rules & Optimality Theorems

When multiple jobs queue before a machine, dispatching heuristics prioritize the sequence of execution. Dispatching Rule Taxonomy:

  • ├── Static Rules (Calculated once at t = 0)
  • │ ├── FCFS (First-Come, First-Served) -> Baseline fairness, poor inventory efficiency
  • │ ├── SPT (Shortest Processing Time) -> Minimizes mean flow time, completion time & WIP
  • │ ├── WSPT (Weighted SPT / Smith) -> Minimizes weighted flow time sum(w_i * F_i)
  • │ ├── EDD (Earliest Due Date) -> Minimizes maximum lateness L_max & max tardiness T_max
  • │ └── Moore-Hodgson Algorithm -> Minimizes total number of tardy jobs N_T
  • └── Dynamic Rules (Recalculated dynamically as current time t advances)
  • ├── CR (Critical Ratio) -> Sequence ascending CR = (d_i - t) / p_i
  • └── STR (Slack Time Remaining) -> Sequence ascending STR = (d_i - t) - p_i
  • Shortest Processing Time (SPT) Rule

Under SPT, jobs are ordered in ascending order of their processing durations:

p [ 1 ] ≤ p [ 2 ] ≤ ⋯ ≤ p [ n ] p_{[1]} \le p_{[2]} \le \dots \le p_{[n]} p [ 1 ] ​ ≤ p [ 2 ] ​ ≤ ⋯ ≤ p [ n ] ​

Important

Smith's Theorem (1956): The Shortest Processing Time (SPT) sequencing rule mathematically guarantees the minimum mean flow time ( F ˉ \bar{F} F ˉ ) , minimum mean completion time, minimum mean waiting time, and minimum average work-in-process ( W I P ‾ \overline{WIP} W I P ) for any single-machine scheduling problem.

Proof Intuition: Under sequence [ 1 , 2 , … , n ] [1, 2, \dots, n] [ 1 , 2 , … , n ] , completion times accumulate as C 1 = p 1 C_1 = p_1 C 1 ​ = p 1 ​ , C 2 = p 1 + p 2 C_2 = p_1 + p_2 C 2 ​ = p 1 ​ + p 2 ​ , ..., C n = ∑ p i C_n = \sum p_i C n ​ = ∑ p i ​ . Summing completion times yields: ∑ i = 1 n C i = n p [ 1 ] + ( n − 1 ) p [ 2 ] + ( n − 2 ) p [ 3 ] + ⋯ + 1 p [ n ] \sum_{i=1}^n C_i = n p_{[1]} + (n-1) p_{[2]} + (n-2) p_{[3]} + \dots + 1 p_{[n]} ∑ i = 1 n ​ C i ​ = n p [ 1 ] ​ + ( n − 1 ) p [ 2 ] ​ + ( n − 2 ) p [ 3 ] ​ + ⋯ + 1 p [ n ] ​ To minimize this dot product, the largest multiplier coefficients ( n , n − 1 , … n, n-1, \dots n , n − 1 , … ) must pair with the smallest processing times p i p_i p i ​ , proving that sorting p i p_i p i ​ ascending minimizes total flow time.

Weighted Shortest Processing Time (WSPT): If jobs carry different holding or inventory carrying weights w i w_i w i ​ , the WSPT rule (Smith's Rule) minimizes total weighted flow time ∑ i = 1 n w i F i \sum_{i=1}^n w_i F_i ∑ i = 1 n ​ w i ​ F i ​ by sequencing jobs in descending order of the ratio:

w [ 1 ] p [ 1 ] ≥ w [ 2 ] p [ 2 ] ≥ ⋯ ≥ w [ n ] p [ n ] \frac{w_{[1]}}{p_{[1]}} \ge \frac{w_{[2]}}{p_{[2]}} \ge \dots \ge \frac{w_{[n]}}{p_{[n]}} p [ 1 ] ​ w [ 1 ] ​ ​ ≥ p [ 2 ] ​ w [ 2 ] ​ ​ ≥ ⋯ ≥ p [ n ] ​ w [ n ] ​ ​

Earliest Due Date (EDD) Rule

Under EDD, jobs are ordered in ascending order of their committed delivery due dates:

d [ 1 ] ≤ d [ 2 ] ≤ ⋯ ≤ d [ n ] d_{[1]} \le d_{[2]} \le \dots \le d_{[n]} d [ 1 ] ​ ≤ d [ 2 ] ​ ≤ ⋯ ≤ d [ n ] ​

Important

Jackson's Theorem (1955): The Earliest Due Date (EDD) sequencing rule mathematically minimizes the maximum lateness ( L m a x L_{max} L ma x ​ ) and the maximum tardiness ( T m a x T_{max} T ma x ​ ) for any single-machine scheduling problem.

When an industrial facility faces steep contractual penalty clauses for any job delivered exceptionally late, EDD is the provably optimal dispatching policy.

Critical Ratio (CR) Rule

Critical Ratio ( C R CR CR ) is an operational dynamic dispatching heuristic that evaluates the ratio of available slack time to remaining work at the current scheduling decision epoch t t t :

C R i = d i − t p i CR_i = \frac{d_i - t}{p_i} C R i ​ = p i ​ d i ​ − t ​

C R i < 1.0 CR_i < 1.0 C R i ​ < 1.0 (Behind Schedule): Available time until due date is less than remaining processing duration. The job will be late unless expedited. Priority increases as C R CR CR decreases.

C R i = 1.0 CR_i = 1.0 C R i ​ = 1.0 (On Schedule): Job has zero slack; if initiated immediately, it completes precisely on its due date.

C R i > 1.0 CR_i > 1.0 C R i ​ > 1.0 (Ahead of Schedule): Job has positive slack time available.

C R i ≤ 0 CR_i \le 0 C R i ​ ≤ 0 (Already Past Due): Due date has already passed ( t ≥ d i t \ge d_i t ≥ d i ​ ). These jobs require immediate emergency intervention.

Dispatch Logic: Sequence available jobs in ascending order of Critical Ratio (smallest C R CR CR first).

Slack Time Remaining (STR)

Slack Time Remaining computes the absolute surplus margin before a job must commence to meet its deadline:

S T R i = ( d i − t ) − p i STR_i = (d_i - t) - p_i ST R i ​ = ( d i ​ − t ) − p i ​

Dispatching prioritizes jobs with the lowest S T R i STR_i ST R i ​ . A variant for multi-operation routings is Slack Time Remaining per Operation ( S T R / O P STR/OP STR / OP ) :

S T R / O P i = ( d i − t ) − ∑ p i j Number of Remaining Operations STR/OP_i = \frac{(d_i - t) - \sum p_{ij}}{\text{Number of Remaining Operations}} STR / O P i ​ = Number of Remaining Operations ( d i ​ − t ) − ∑ p ij ​ ​

Moore-Hodgson Algorithm (Minimizing N T N_T N T ​ )

To minimize the total number of late jobs ( N T N_T N T ​ ), Moore and Hodgson developed an exact O ( n log ⁡ n ) O(n \log n) O ( n lo g n ) algorithm:

Sequence all n n n jobs according to the EDD rule ( d 1 ≤ d 2 ≤ ⋯ ≤ d n d_1 \le d_2 \le \dots \le d_n d 1 ​ ≤ d 2 ​ ≤ ⋯ ≤ d n ​ ).

Evaluate job completions sequentially. Find the first tardy job in the sequence ( C k > d k C_k > d_k C k ​ > d k ​ ). If no jobs are tardy, the current schedule is optimal.

Identify the job in the current set of scheduled jobs { 1 , 2 , … , k } \{1, 2, \dots, k\} { 1 , 2 , … , k } that has the largest processing time ( p ∗ = max ⁡ 1 ≤ j ≤ k p j p^* = \max_{1 \le j \le k} p_j p ∗ = max 1 ≤ j ≤ k ​ p j ​ ).

Remove that job from the active schedule and assign it to a rejected pool to be processed at the very end of the schedule (in any order).

Recalculate completion times for remaining jobs and repeat steps 2–4 until no scheduled jobs are tardy. The resulting schedule minimizes N T N_T N T ​ .

3. Two-Machine Flow Shop Sequencing: Johnson's Rule

When production expands beyond a single workstation to multiple processing centers in series, scheduling complexity escalates rapidly. The classical Two-Machine Flow Shop Problem ( F 2 ∣ ∣ C m a x F_2 || C_{max} F 2 ​ ∣∣ C ma x ​ ) models n n n jobs processed sequentially across two machines, M 1 M_1 M 1 ​ and M 2 M_2 M 2 ​ . Two-Machine Flow Shop Architecture:

  • [Job Queue] ===> [ Machine 1 (A_i) ] ===> [ Machine 2 (B_i) ] ===> [ Completed ]
  • (All n jobs) First Operation Second Operation Shipment
  • Problem Formulation

Every job i ∈ { 1 , … , n } i \in \{1, \dots, n\} i ∈ { 1 , … , n } must be processed first on Machine 1, and subsequently on Machine 2.

Operation time for job i i i on Machine 1 is A i A_i A i ​ .

Operation time for job i i i on Machine 2 is B i B_i B i ​ .

Machine 2 cannot begin working on job i i i until Machine 1 completes job i i i ( C 2 , i ≥ C 1 , i + B i C_{2, i} \ge C_{1, i} + B_i C 2 , i ​ ≥ C 1 , i ​ + B i ​ ).

Both machines process jobs in identical permutation sequence.

Johnson's Algorithm (1954)

S.M. Johnson proved that a simple sorting heuristic finds the globally optimal sequence that minimizes the total makespan ( C m a x C_{max} C ma x ​ ) across both machines.

Step-by-Step Algorithmic Procedure:

Compile Processing Matrix: Tabulate processing times A i A_i A i ​ (Machine 1) and B i B_i B i ​ (Machine 2) for all unscheduled jobs.

Identify Global Minimum: Scan all remaining processing times across both machines to locate the smallest value: p ∗ = min ⁡ i { A i , B i } p^* = \min_{i} \{A_i, B_i\} p ∗ = min i ​ { A i ​ , B i ​ }

Conditional Assignment:

If the minimum processing time occurs on Machine 1 ( A i A_i A i ​ ): Schedule job i i i in the earliest available unassigned position (toward the beginning of the sequence).

If the minimum processing time occurs on Machine 2 ( B i B_i B i ​ ): Schedule job i i i in the latest available unassigned position (toward the end of the sequence).

Tie-Breaking Protocols:

If a tie occurs between Machine 1 and Machine 2 ( A i = B j A_i = B_j A i ​ = B j ​ ), place job i i i at the beginning and job j j j at the end.

If a tie occurs between two jobs on Machine 1 ( A i = A j A_i = A_j A i ​ = A j ​ ), arbitrarily place either job first.

If a tie occurs between two jobs on Machine 2 ( B i = B j B_i = B_j B i ​ = B j ​ ), arbitrarily place either job last.

Iterate: Remove the assigned job from the candidate list and repeat steps 2–4 until all n n n jobs have been sequenced.

Gantt Chart Construction & Makespan Calculation

Let [ 1 ] , [ 2 ] , … , [ n ] [1], [2], \dots, [n] [ 1 ] , [ 2 ] , … , [ n ] denote the sequence determined by Johnson's algorithm. Tracking completion times recursively:

Machine 1 Completion Times: Machine 1 runs continuously with zero idle time: C 1 , [ 1 ] = A [ 1 ] C_{1, [1]} = A_{[1]} C 1 , [ 1 ] ​ = A [ 1 ] ​ C 1 , [ k ] = C 1 , [ k − 1 ] + A [ k ] ∀ k = 2 , … , n C_{1, [k]} = C_{1, [k-1]} + A_{[k]} \quad \forall k = 2, \dots, n C 1 , [ k ] ​ = C 1 , [ k − 1 ] ​ + A [ k ] ​ ∀ k = 2 , … , n

Machine 2 Completion Times: Machine 2 cannot start job [ k ] [k] [ k ] until Machine 2 finishes job [ k − 1 ] [k-1] [ k − 1 ] AND Machine 1 finishes job [ k ] [k] [ k ] : C 2 , [ 1 ] = A [ 1 ] + B [ 1 ] C_{2, [1]} = A_{[1]} + B_{[1]} C 2 , [ 1 ] ​ = A [ 1 ] ​ + B [ 1 ] ​ C 2 , [ k ] = max ⁡ ( C 2 , [ k − 1 ] , C 1 , [ k ] ) + B [ k ] ∀ k = 2 , … , n C_{2, [k]} = \max(C_{2, [k-1]}, C_{1, [k]}) + B_{[k]} \quad \forall k = 2, \dots, n C 2 , [ k ] ​ = max ( C 2 , [ k − 1 ] ​ , C 1 , [ k ] ​ ) + B [ k ] ​ ∀ k = 2 , … , n

Machine 2 Idle Time: Idle time occurs on Machine 2 whenever C 1 , [ k ] > C 2 , [ k − 1 ] C_{1, [k]} > C_{2, [k-1]} C 1 , [ k ] ​ > C 2 , [ k − 1 ] ​ (Machine 2 is waiting for Machine 1 to finish): I 2 , [ k ] = max ⁡ ( 0 , C 1 , [ k ] − C 2 , [ k − 1 ] ) I_{2, [k]} = \max(0, C_{1, [k]} - C_{2, [k-1]}) I 2 , [ k ] ​ = max ( 0 , C 1 , [ k ] ​ − C 2 , [ k − 1 ] ​ )

Total Makespan ( C m a x C_{max} C ma x ​ ): The completion time of the final job on Machine 2: C m a x = C 2 , [ n ] C_{max} = C_{2, [n]} C ma x ​ = C 2 , [ n ] ​

4. Job Shop Scheduling Complexity and Advanced Heuristics

While flow shops enforce identical, unidirectional routings across all jobs, job shops ( J m ∣ ∣ γ J_m || \gamma J m ​ ∣∣ γ ) feature complex, multi-directional routings. Each job follows an individualized technological route sheet (e.g., Job 1 routes Lathe → \to → Mill → \to → Grind; Job 2 routes Mill → \to → Lathe → \to → Assembly).

Combinatorial Complexity

A general job shop with n n n jobs and m m m machines exhibits extreme combinatorial complexity. The theoretical schedule space contains ( n ! ) m (n!)^m ( n ! ) m active schedules. For a modest shop with 10 jobs and 5 machines:

( 10 ! ) 5 = ( 3,628,800 ) 5 ≈ 6.29 × 10 32 candidate schedules (10!)^5 = (3{,}628{,}800)^5 \approx 6.29 \times 10^{32} \text{ candidate schedules} ( 10 ! ) 5 = ( 3 , 628 , 800 ) 5 ≈ 6.29 × 1 0 32 candidate schedules

General job shop scheduling is proven N P NP NP -hard . Finding guaranteed optimal schedules via exact mathematical programming (mixed-integer linear programming, branch-and-bound) is computationally intractable for industrial scales, forcing reliance on advanced heuristics.

The Shifting Bottleneck Heuristic (SBH)

Developed by Adams, Balas, and Zawack (1988), the Shifting Bottleneck Heuristic is one of the most powerful and widely cited algorithms for job shop scheduling:

Decomposition: The overall job shop problem is decomposed into m m m single-machine subproblems.

Bottleneck Identification: For each unsequenced machine, release dates r i r_i r i ​ and due dates d i d_i d i ​ are derived from preceding and succeeding operations. Each machine is analyzed as a single-machine problem with release dates minimizing maximum lateness ( 1 ∣ r i ∣ L m a x 1 | r_i | L_{max} 1∣ r i ​ ∣ L ma x ​ , solved using Carlier's exact algorithm or Schrage's heuristic).

Bottleneck Selection: The machine exhibiting the largest maximum lateness L m a x L_{max} L ma x ​ is identified as the current critical bottleneck .

Fix Sequence: The sequence of operations on this bottleneck machine is permanently locked into the global schedule.

Shifting / Re-optimization Phase: Every time a new bottleneck machine is sequenced, previously scheduled machines are systematically re-optimized to capture newly created schedule constraints.

Termination: Repeat until all m m m machines have been sequenced.

  • 5. Worked Engineering Examples
  • Example 1: Comparing Dispatching Rules on a Single Machine

Problem Statement: Five jobs are waiting to be processed on a CNC vertical machining center at time t = 0 t = 0 t = 0 . Job processing times and committed due dates are:

  • Job Processing Time ( p i p_i p i ​ , hours) Due Date ( d i d_i d i ​ , hours)
  • J1 5 9
  • J2 3 6
  • J3 8 15
  • J4 2 7
  • J5 6 12

Evaluate the schedule under Shortest Processing Time (SPT) and compute: makespan ( C m a x C_{max} C ma x ​ ), mean flow time ( F ˉ \bar{F} F ˉ ), average WIP ( W I P ‾ \overline{WIP} W I P ), maximum lateness ( L m a x L_{max} L ma x ​ ), and maximum tardiness ( T m a x T_{max} T ma x ​ ).

Solution:

Step 1: Order jobs by SPT ( p i p_i p i ​ ascending): Sequence: J4 (2) → \to → J2 (3) → \to → J1 (5) → \to → J5 (6) → \to → J3 (8)

Step 2: Compute schedule timeline:

Sequence Job p i p_i p i ​ Completion Time ( C i C_i C i ​ ) Due Date ( d i d_i d i ​ ) Lateness ( L i = C i − d i L_i = C_i - d_i L i ​ = C i ​ − d i ​ ) Tardiness ( T i T_i T i ​ )

  • 1 J4 2 2 7 2 − 7 = − 5 2 - 7 = -5 2 − 7 = − 5 0
  • 2 J2 3 2 + 3 = 5 2 + 3 = 5 2 + 3 = 5 6 5 − 6 = − 1 5 - 6 = -1 5 − 6 = − 1 0
  • 3 J1 5 5 + 5 = 10 5 + 5 = 10 5 + 5 = 10 9 10 − 9 = + 1 10 - 9 = +1 10 − 9 = + 1 1
  • 4 J5 6 10 + 6 = 16 10 + 6 = 16 10 + 6 = 16 12 16 − 12 = + 4 16 - 12 = +4 16 − 12 = + 4 4
  • 5 J3 8 16 + 8 = 24 16 + 8 = 24 16 + 8 = 24 15 24 − 15 = + 9 24 - 15 = +9 24 − 15 = + 9 9
  • Total 24 57 14

Step 3: Compute Performance Metrics:

Makespan ( C m a x C_{max} C ma x ​ ): 24 hours 24\text{ hours} 24 hours

Total Flow Time: ∑ C i = 2 + 5 + 10 + 16 + 24 = 57 hours \sum C_i = 2 + 5 + 10 + 16 + 24 = 57\text{ hours} ∑ C i ​ = 2 + 5 + 10 + 16 + 24 = 57 hours

Mean Flow Time ( F ˉ \bar{F} F ˉ ): 57 5 = 11.40 hours \frac{57}{5} = 11.40\text{ hours} 5 57 ​ = 11.40 hours

Average WIP ( W I P ‾ \overline{WIP} W I P ): ∑ F i C m a x = 57 24 = 2.375 jobs \frac{\sum F_i}{C_{max}} = \frac{57}{24} = 2.375\text{ jobs} C ma x ​ ∑ F i ​ ​ = 24 57 ​ = 2.375 jobs

Maximum Lateness ( L m a x L_{max} L ma x ​ ): max ⁡ ( − 5 , − 1 , 1 , 4 , 9 ) = + 9 hours \max(-5, -1, 1, 4, 9) = +9\text{ hours} max ( − 5 , − 1 , 1 , 4 , 9 ) = + 9 hours

Maximum Tardiness ( T m a x T_{max} T ma x ​ ): max ⁡ ( 0 , 0 , 1 , 4 , 9 ) = 9 hours \max(0, 0, 1, 4, 9) = 9\text{ hours} max ( 0 , 0 , 1 , 4 , 9 ) = 9 hours

Number of Tardy Jobs ( N T N_T N T ​ ): 3 jobs (J1, J5, J3)

(Note: Under EDD [J2 → \to → J4 → \to → J1 → \to → J5 → \to → J3] the completion times are 3, 5, 10, 16, and 24 hours, so total flow time rises to 58 hours and F ˉ = 11.6 \bar{F} = 11.6 F ˉ = 11.6 hours. L m a x L_{max} L ma x ​ is still +9 hours with the same three tardy jobs. That is the best possible here: some job must finish at t = 24 t = 24 t = 24 , and the latest due date is 15, so no sequence can have L m a x L_{max} L ma x ​ below 9.)

Example 2: Two-Machine Flow Shop Optimization via Johnson's Rule

Problem Statement: Five structural weldments must be processed sequentially across two dedicated workstations: Fit-up/Tack Welding (Machine 1) and Final Robotic Seam Welding (Machine 2). Processing times (in hours) are:

  • Job Machine 1 ( A i A_i A i ​ ) Machine 2 ( B i B_i B i ​ )
  • J1 4 5
  • J2 8 3
  • J3 2 7
  • J4 6 8
  • J5 7 4

Determine the optimal sequence using Johnson's algorithm and calculate total makespan and idle time on Machine 2.

Solution:

Step 1: Execute Johnson's Algorithm Iterations:

Iteration 1: Smallest processing time overall is 2 hours (Job 3 on Machine 1). Because it is on Machine 1, place J3 in the first available slot .

Current sequence: [ J3, __, __, __, __ ]

Iteration 2: Smallest remaining processing time is 3 hours (Job 2 on Machine 2). Because it is on Machine 2, place J2 in the last available slot .

Current sequence: [ J3, __, __, __, J2 ]

Iteration 3: Smallest remaining processing times are 4 hours (Job 1 on Machine 1, and Job 5 on Machine 2):

Job 1 ( A 1 = 4 A_1 = 4 A 1 ​ = 4 on M1) ⟹ \implies ⟹ place J1 in earliest available slot .

Job 5 ( B 5 = 4 B_5 = 4 B 5 ​ = 4 on M2) ⟹ \implies ⟹ place J5 in latest available slot .

Current sequence: [ J3, J1, __, J5, J2 ]

Iteration 4: Only Job 4 remains. Place J4 in the final remaining middle slot .

Optimal sequence: [ J3 → \to → J1 → \to → J4 → \to → J5 → \to → J2 ]

Step 2: Construct Schedule Timeline:

Sequence Job M 1 M_1 M 1 ​ Start M 1 M_1 M 1 ​ Duration ( A i A_i A i ​ ) M 1 M_1 M 1 ​ End ( C 1 , i C_{1,i} C 1 , i ​ ) M 2 M_2 M 2 ​ Start M 2 M_2 M 2 ​ Duration ( B i B_i B i ​ ) M 2 M_2 M 2 ​ End ( C 2 , i C_{2,i} C 2 , i ​ ) M 2 M_2 M 2 ​ Idle Time

  • 1 J3 0 2 2 2 7 9 2 (from 0 to 2)
  • 2 J1 2 4 6 9 5 14 0
  • 3 J4 6 6 12 14 8 22 0
  • 4 J5 12 7 19 22 4 26 0
  • 5 J2 19 8 27 27 3 30 1 (from 26 to 27)

Step 3: Evaluate Results:

Makespan ( C m a x C_{max} C ma x ​ ): 30 hours 30\text{ hours} 30 hours

Machine 1 Total Runtime: 2 + 4 + 6 + 7 + 8 = 27 hours 2 + 4 + 6 + 7 + 8 = 27\text{ hours} 2 + 4 + 6 + 7 + 8 = 27 hours (finishes at t = 27 t = 27 t = 27 )

Machine 2 Idle Time: 2 hours 2\text{ hours} 2 hours (waiting for J3 to finish on M1) + 1 hour + 1\text{ hour} + 1 hour (waiting from t = 26 t=26 t = 26 to t = 27 t=27 t = 27 for J2 to finish on M1) = 3 hours 3\text{ hours} 3 hours total idle time .

Machine 2 runtime is 7 + 5 + 8 + 4 + 3 = 27 7 + 5 + 8 + 4 + 3 = 27 7 + 5 + 8 + 4 + 3 = 27 hours. Total makespan = 27 runtime + 3 idle = 30 hours 27\text{ runtime} + 3\text{ idle} = 30\text{ hours} 27 runtime + 3 idle = 30 hours .