An Approximation Algorithm for the Parallel Three-Stage Flowshop Scheduling

The problem that schedules n three-stage jobs on m three-stage flowshops with the objective of minimizing the makespan was studied. When m is fixed, the problem is NP-hard; When m is arbitrary larger than 2, the problem is strongly NP-hard. For this problem, the present work is divided into three situations for discussion: In case 1, we gave an approximate ratio of \dfrac 7 3-\dfrac 13m ; in case 2, we gave an approximate ratio of three; while in case three, there was an approximate ratio of \dfrac 236-\dfrac 13m . Finaly we gave an approximation algorithm with a worst case ratio of \dfrac 236-\dfrac 13m .