Approximation algorithms for the parallel flow shop problem
| Autor: | Steef van de Velde, Xiandong Zhang |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Mathematical optimization
Information Systems and Management General Computer Science Job shop scheduling Parallel flow Computer science Approximation algorithm Flow shop scheduling Management Science and Operations Research Industrial and Manufacturing Engineering Multi-commodity flow problem Scheduling (computing) Modeling and Simulation Minimum-cost flow problem |
| Zdroj: | European Journal of Operational Research. 216:544-552 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2011.08.007 |
| Popis: | 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 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect