کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480606 | 1446087 | 2012 | 9 صفحه PDF | دانلود رایگان |
We consider the NPNP-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 32-approximation algorithm, and for m = 3, we present a 127-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.
► We consider the problem of scheduling n jobs in m two-stage parallel flow shops.
► For m = 2, we present a 3/2-approximation algorithm so as to minimize the makespan.
► 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 guarantees.
Journal: European Journal of Operational Research - Volume 216, Issue 3, 1 February 2012, Pages 544–552