AnO(nlogn) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
C. P. M. van Hoesel, A. P. M. Wagelmans, M. van Vliet
INFORMS Journal on Computing · 1996 · Volume 8 · Issue 4
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.
Keywords
scheduling, flow shop, algorithm analysis, controllable machine speeds
Enable JavaScript for citation tools and additional paper interactions.