On scheduling multiple two-stage flowshops Academic Article uri icon

abstract

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

author list (cited authors)

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

citation count

  • 5

publication date

  • May 2020