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

abstract

• 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.

authors

• Chen, Jianer

published proceedings

• THEORETICAL COMPUTER SCIENCE

author list (cited authors)

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

citation count

• 3

complete list of authors

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

publication date

• February 2020

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Approximation Algorithm
• Flowshops
• Makespan
• Scheduling

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2019.08.028

start page

• 509

end page

• 515

volume

• 806

URL

• http://dx.doi.org/10.1016/j.tcs.2019.08.028