Improved approximation algorithms for two-stage flowshops scheduling problem Academic Article uri icon


  • © 2019 Elsevier B.V. This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical MAKESPAN problem, we prove that if there is an α-approximation algorithm for the MAKESPAN problem, then for the general case of the problem, we can construct a 2α-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an (α+1/2)-approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the MAKESPAN problem, we get a (2+ϵ)-approximation algorithm for the general case and a (1.5+ϵ)-approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6 respectively.

published proceedings

  • Theoretical Computer Science

author list (cited authors)

  • Wu, G., Chen, J., & Wang, J.

citation count

  • 2

complete list of authors

  • Wu, Guangwei||Chen, Jianer||Wang, Jianxin

publication date

  • February 2020