2012-02-01
Approximation algorithms for the parallel flow shop problem
Publication
Publication
European Journal of Operational Research , Volume 216 - Issue 3 p. 544- 552
We consider the NP-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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1016/j.ejor.2011.08.007, hdl.handle.net/1765/25743 | |
| ERIM Top-Core Articles | |
| European Journal of Operational Research | |
| Organisation | Erasmus Research Institute of Management |
|
Zhang, X., & van de Velde, S. (2012). Approximation algorithms for the parallel flow shop problem. European Journal of Operational Research, 216(3), 544–552. doi:10.1016/j.ejor.2011.08.007 |
|
