An O(n log n) algorithm for the two-machine flow shop problem with controllable machine speeds

An O(n log n) algorithm for the two-machine flow shop problem with controllable machine speeds

0.00 Avg rating0 Votes
Article ID: iaor19982701
Country: United States
Volume: 8
Issue: 4
Start Page Number: 376
End Page Number: 382
Publication Date: Sep 1996
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: flowshop
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.

Reviews

Required fields are marked *. Your email address will not be published.