On scheduling multiple two-stage flowshops - Texas A&M University (TAMU) Scholar

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 m2. 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(nlogn) 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.

On scheduling multiple two-stage flowshops Academic Article