The two-machine flow shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best known approximation algorithms are those of Potts (1985) with a worst-case performance ratio of 5/3 and running time $O(n^3 \log n)$, and a polynomial time approximation scheme of Hall (1995) that can generate solutions arbitrary close to the optimum but with a high time requirement. In this paper, we modify Potts' algorithm so that its worst-case performance ratio is reduced to 3/2, but its running time remains $O(n^3\log n)$.
Citation
Discrete Appl. Math., 114 (2001), 255-271.