Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952191 | Theoretical Computer Science | 2017 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yan Lan, Xin Han, Yinling Wang, Min Ge, He Guo, Xin Chen,