Johnson's algorithm, developed for two-machine flow shop sequencing to minimize makespan, can be extended to three-machine problems when specific conditions on processing times are satisfied. When these conditions are not met, branch-and-bound algorithms provide optimal solutions through implicit enumeration, using lower bounds based on machine workloads to prune the solution space. Table of Contents: • Johnson's extension conditions: maximum processing time on middle machine ≤ minimum on first or last machine • Equivalent two-machine transformation when conditions hold • Lower bound computation: machine workload sums and job-specific bounds • Branch-and-bound algorithm: node creation, lower bound evaluation, node fathoming by feasibility or bound • Implicit enumeration: explores n! permutations implicitly without exhaustive evaluation • Dominant solution property: maintains sequence feasibility across all machines
Johnson's algorithm, developed for two-machine flow shop sequencing to minimize makespan, can be extended to three-machine problems when specific conditions on processing times are satisfied. When th…