Revisiting Johnson’s rule for minimizing makespan in the two-machine flow shop scheduling problem

Operations Research Letters 2026 Open access

Read full text
Authors: Federico Della Croce, Quentin Schau
DOI: 10.1016/j.orl.2026.107514
Cited by: 0
References: 18

Abstract

We consider Johnson’s rule for minimizing the makespan in the two-machine flow shop problem. 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.

Fields of Study & Subjects

Scheduling and Optimization Algorithms Optimization and Search Problems Optimization and Packing Problems

Publication details

Journal / source
Operations Research Letters
Publisher
Elsevier BV
Volume
69
Pages
107514–107514
Publication date
13 August 2026
Language
EN