An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
Published Online:1 Nov 1996https://doi.org/10.1287/ijoc.8.4.376
Abstract
In this paper we consider the two-machine flow shop problem with varying machine speeds. We present an algorithm which determines the optimal permutations for all machine speeds in O(n log n) time, where n is the number of jobs. To achieve this bound on the running time, the algorithm employs an elementary dominance relation.
