On scheduling multiple two-stage flowshops

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 ( n log ⁡ 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.

Authors

• Guangwei Wu
• Jianer Chen
• Jianxin Wang

Keywords

• Scheduling
• Multiple two-stage flowshops
• Approximation algorithm
• Cloud computing