On scheduling multiple two-stage flowshops
Academic Article
-
- Overview
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
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(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.
published proceedings
-
Theoretical Computer Science
author list (cited authors)
-
Wu, G., Chen, J., & Wang, J
citation count
complete list of authors
-
Wu, Guangwei||Chen, Jianer||Wang, Jianxin
publication date
publisher
published in
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume