On scheduling multiple two-stage flowshops Academic Article uri icon


  • © 2018 Elsevier B.V. This paper studies the problem of scheduling n two-stage jobs on m multiple two-stage flowshops, with the objective of minimizing the makespan. The problem is NP-hard even when m is a fixed constant, and becomes strongly NP-hard when m is part of the input. A 2.6-approximation algorithm along with its analysis is presented for an arbitrary m≥2. This is the first approximation algorithm for multiple flowshops when the number m of flowshops is part of the input. The fact that m is part of the input and the time complexity O(nlog⁡n) of the algorithm demonstrate that the problem, which plays an important role in the current research in cloud computing and data centers, can be solved efficiently with a reasonable level of satisfaction.

published proceedings

  • Theoretical Computer Science

author list (cited authors)

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

citation count

  • 6

complete list of authors

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

publication date

  • May 2020