Single-machine sequencing determines the optimal job processing order to minimize a chosen performance metric, with optimal solutions depending on whether minimizing average completion time, total weighted completion time, or maximum lateness. Johnson's algorithm is a polynomial-time optimal solution method for the two-machine flow shop problem, based on the principle that jobs should be ordered to minimize idle time on the second machine by processing short-duration jobs early on the bottleneck machine. The algorithm provides exact optimality guarantees and establishes the theoretical foundation for understanding flow shop scheduling complexity. Table of Contents: • Single machine scheduling problem formulation and solution space • Scheduling rules and their optimality conditions for different objectives • Shortest processing time (SPT) rule for minimizing total completion time • Weighted completion time and job prioritization • Johnson's algorithm for two-machine flow shop problems • Algorithm logic: separation into two groups based on processing times • Optimal solution structure and non-preemptive scheduling • Makespan (total completion time) optimization in flow shops • Idle time relationships between consecutive machines • Computational efficiency: polynomial-time algorithm properties • Proof of optimality and worst-case performance bounds
Single-machine sequencing determines the optimal job processing order to minimize a chosen performance metric, with optimal solutions depending on whether minimizing average completion time, total we…