Approximation algorithms for the parallel flow shop problem

We consider the $\mathcal{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 $\frac{3}{2}$ ‐approximation algorithm, and for m =3, we present a $\frac{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.