Approximation algorithms for two-stage flexible flow shop scheduling (Q2292124)

This paper deals with a two-stage flexible flow shop problem with a single machine at the first stage and \(m\) identical parallel machines at the second stage. The optimization criterion is the minimization of the makespan. First, a \((2 + \epsilon)\)-approximation algorithm is given. Then a 3-approximation and an \((2.5 + \epsilon)\)-approximation algorithm are given for the case when contiguous addresses are required at the second stage. In addition, the special cases with two and three identical parallel machines are considered, and approximation algorithms with a ratio of 2.5 and 2.67, respectively, are given which can be applied both to the contiguous and noncontiguous cases. The paper concludes with a new lower bound on the optimal function value.