Article ID Journal Published Year Pages File Type
4952191 Theoretical Computer Science 2017 10 Pages PDF
Abstract
In this paper we study a flow shop problem F2→D|v=1,c≥1|Cmax with two machines and one transporter: machines A,B and a transporter V which is initially located at machine B. There are a set of jobs needed to be processed on machine A first, then on machine B, and transported to the destination by V finally. Transporter V can carry at most c jobs in one batch where c≥1. The objective is to minimize the completion time when all the jobs are transported to the destination. Problem F2→D|v=1,c=2|Cmax has been proved to be binary NP-hard in EJOR2007 [20] when c=2, we solve the open question in [20] and prove it is strongly NP-hard, i.e., there is no FPTAS for the problem.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , , , ,