 A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shopsJianming Dong, Ruyan Jin, Taibo Luo and Weitian Tong European Journal of Operational Research, 2020, vol. 281, issue 1, 16-24 Abstract: 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. Keywords: Scheduling; Parallel two-stage flow-shops; Makespan; Mixed integer program; Polynomial-time approximation scheme (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:281:y:2020:i:1:p:16-24 DOI: 10.1016/j.ejor.2019.08.019 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.