Flow Shop Scheduling Calculator

Calculate optimal schedules using Johnson's Rule, NEH Heuristic, and other algorithms

Flow Shop Scheduling

Flow shop scheduling involves sequencing jobs through a series of machines where each job must follow the same machine order. The goal is typically to minimize the makespan (total completion time).

Makespan = max(C_i) where C_i is completion time of job i

Key algorithms:

  • Johnson's Rule: Optimal for 2-machine flow shops
  • NEH Heuristic: Effective heuristic for m-machine problems
  • CDS Heuristic: Extension of Johnson's rule to m machines
  • Palmer Heuristic: Uses slope indices to prioritize jobs

Select Algorithm

Choose the appropriate algorithm for your problem:

Johnson's Rule (2 machines)
NEH Heuristic
CDS Heuristic
Palmer Heuristic

Johnson's Rule (2-Machine Flow Shop)

Optimal algorithm for minimizing makespan in 2-machine flow shops. Jobs are sequenced based on processing times on the two machines.

NEH Heuristic (Nawaz-Enscore-Ham)

Effective heuristic for m-machine flow shops. Jobs are ordered by total processing time, then inserted to minimize makespan.

CDS Heuristic (Campbell-Dudek-Smith)

Extension of Johnson's rule to m machines by creating m-1 artificial 2-machine problems.

Palmer Heuristic

Uses slope indices to prioritize jobs based on processing times across machines.

Scheduling Results

Makespan

Total completion time

Average Utilization

Machine busy time

Total Idle Time

Across all machines

Gantt chart will appear here after calculation

Optimal Sequence

Position Job ID Processing Times

Machine Completion Times

Practical Examples

Example 1: Johnson's Rule

Jobs: [{"id":"A","times":[3,6]},{"id":"B","times":[5,2]},{"id":"C","times":[1,8]}]

Optimal Sequence: C → A → B | Makespan: 13

Example 2: NEH Heuristic

Jobs: [{"id":"X","times":[5,4,3]},{"id":"Y","times":[2,3,4]},{"id":"Z","times":[4,1,2]}]

NEH Sequence: X → Z → Y | Makespan: 14

Example 3: CDS Heuristic

Jobs: [{"id":"J1","times":[3,4,6]},{"id":"J2","times":[5,2,4]},{"id":"J3","times":[2,3,1]}]

CDS Sequence: J3 → J1 → J2 | Makespan: 15

Algorithm Comparison

Algorithm Machines Optimality Complexity Best For
Johnson's Rule 2 Optimal O(n log n) Simple 2-machine problems
NEH Heuristic m ≥ 2 Heuristic O(n³) General flow shops
CDS Heuristic m ≥ 2 Heuristic O(mn log n) When Johnson-like results desired
Palmer Heuristic m ≥ 2 Heuristic O(mn) Quick approximation