{"ID":2832708,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.06119","arxiv_id":"2512.06119","title":"Revisiting Johnson's rule for minimizing makespan in the Two-Machine Flow Shop scheduling problem","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.","short_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 ana...","url_abs":"https://arxiv.org/abs/2512.06119","url_pdf":"https://arxiv.org/pdf/2512.06119v4","authors":"[\"Federico Della Croce\",\"Quentin Schau\"]","published":"2025-12-05T19:55:27Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}