Improved approximation algorithms for two-stage flowshops scheduling problem

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

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

Keywords

• Scheduling
• Flowshops
• Approximation algorithm
• makespan