Revisiting Johnson's rule for minimizing makespan in the Two-Machine Flow Shop scheduling problem

We consider Johnson's rule for minimizing the makespan in the two-machine flow shop problem. Although its worst-case time complexity is O(n log n), we show that it is possible to detect in linear time whether a full sorting of jobs can be avoided and an optimal solution can be computed in O(n) time. A probabilistic analysis indicates that linear time complexity holds with high probability under uniformly distributed processing times, a result further supported by extensive computational experimentation.