An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
Presents an algorithm which determines the optimal permutations for all machine speeds in O(n log n) time where the algorithm n is the number of jobs. Description of the two-machine flow shop problem; Use of the algorithm as an elementary dominance relation; Description of the algorithm; Correctness of the algorithm.
van Hoesel, C.P.M., Wagelmans, A.P.M., & van Vliet, M.. (1996). An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds. I N F O R M S Journal on Computing: charting new directions in OR and CS, 376–382. Retrieved from http://hdl.handle.net/1765/2304