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

2025/12/05 by Della Croce, Federico, Schau, Quentin
Computer Science · Engineering · #90 #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms

paper · doi:10.48550/arxiv.2512.06119

openalex publication_date 2025/12/05 · openalex created_date 2025/12/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Two-stage flow shop scheduling with dedicated machines
• On the variable common due date, minimal tardy jobs bicriteria\n two-machine flow shop problem with ordered machines
• A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines
• Flowshop Machine Scheduling: Markov Modeling, Optimal Schedules and Heuristics
• Universality of Makespan in Flowshop Scheduling Problem