Flow shop scheduling problems with transportation constraints revisited.

This paper investigates two flow shop scheduling problems with two machines A and B , and a single transporter V. In the first problem, the transporter V is located at machine A initially, each job has to be processed first on A , then transported to B for further processing. While in the second problem, the transporter V is located at machine B initially, each job needs to be processed first on A , then on B , finally transported to the destination. In both problems, the transporter V can carry up to c (where c is a constant and c ≥ 1) jobs at a time and the objective is to minimize the makespan. For the former problem, the best approximation algorithm guarantees a worst-case ratio bound of (5 3 + ε) , while for the latter one, the best approximation algorithm provides a worst-case ratio bound of 2. For each problem, we design a polynomial-time approximation scheme (PTAS). [ABSTRACT FROM AUTHOR]