A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
Document Type
Article
Publication Date
2020
Department/School
Computer Science
Publication Title
European Journal of Operational Research
Abstract
© 2019 Elsevier B.V. We investigate the approximability of the m parallel two-stage flow-shop (mP2FS) problem, where a set of jobs is scheduled on the multiple identical two-stage flow-shops to minimize the makespan, i.e., the finishing time of the last job. Each job needs to be processed non-preemptively on one flow-shop without switching to the other flow-shops. This problem is a hybrid of the classic parallel machine scheduling and two-stage flow-shop scheduling problems. Its strong NP-hardness follows from the parallel machine scheduling problem when the number of machines is part of the input. Our main contribution is a polynomial-time approximation scheme (PTAS) for the mP2FS problem when the number of shops is part of the input, which improves the previous best approximation algorithm of a ratio (2+ϵ). Owing to the strong NP-hardness, our PTAS achieves the best possible approximation ratio.
Link to Published Version
Recommended Citation
Dong, J., Jin, R., Luo, T., & Tong, W. (2020). A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops. European Journal of Operational Research, 281(1), 16–24. https://doi.org/10.1016/j.ejor.2019.08.019