Improved approximation algorithms for two-stage flowshops scheduling problem
- Additional Document Info
- View All
© 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.
Theoretical Computer Science
author list (cited authors)
Wu, G., Chen, J., & Wang, J.
complete list of authors
Wu, Guangwei||Chen, Jianer||Wang, Jianxin