科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider the N/P-hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops; and scheduling the jobs assigned to the same flow shop by use of Johnson's rule. For m = 2, we present a 3/2-approximation algorithm, and for m = 3, we present a 12/7-approximation algorithm. Both these algorithms run in O(n log n) time. These are the first approximation algorithms with fixed worst-case performance guarantees for the parallel flow shop problem.
- 出版日期2012-2-1
- 单位复旦大学
