Publication Date:
2019
Description:
〈p〉Publication date: Available online 12 August 2019〈/p〉
〈p〉〈b〉Source:〈/b〉 European Journal of Operational Research〈/p〉
〈p〉Author(s): Jianming Dong, Ruyan Jin, Taibo Luo, Weitian Tong〈/p〉
〈h5〉Abstract〈/h5〉
〈div〉〈p〉We investigate the approximability of the 〈em〉m〈/em〉 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 〈em〉makespan〈/em〉, 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 〈math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si6.svg"〉〈mrow〉〈mo〉(〈/mo〉〈mn〉2〈/mn〉〈mo linebreak="goodbreak"〉+〈/mo〉〈mi〉ϵ〈/mi〉〈mo〉)〈/mo〉〈/mrow〉〈/math〉. Owing to the strong NP-hardness, our PTAS achieves the best possible approximation ratio.〈/p〉〈/div〉
Print ISSN:
0377-2217
Electronic ISSN:
1872-6860
Topics:
Mathematics
,
Economics
