A 3/2-approximation algorithm for two-machine flow-shop sequencing subjectto release dates

The two-machine flow-shop sequencing problem with arbitrary release dates o f jobs and the minimum makespan criterion is considered. The problem is kno wn to be NP-hard, and the best-known approximation algorithms are those of Potts (Math. Oper. Res. 10 (1985) 576) 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 (Proceedings of the 36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. press, Los Alamitos, 1995, pp. 82-91.) 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 wor st-case performance ratio is reduced to 3/2, but its running time remains O (n(3) log n). (C) 2001 Elsevier Science B.V. All rights reserved.