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

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

0.00 Avg rating0 Votes
Article ID: iaor19971848
Country: United States
Volume: 8
Issue: 4
Start Page Number: 376
End Page Number: 382
Publication Date: Oct 1996
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: flowshop
Abstract:

In this paper the authors consider the two-machine flow shop problem with varying machine speeds. They present an algorithm which determines the optimal permutations for all machine speeds in O(nlogn) time, where n is the number 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.