No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem
证明了无等待流水车间调度问题（最小化最大完工时间）与不对称旅行商问题在近似难度上等价，从而首次得到该问题的APX-难结果。
In this paper, we study the classical no-wait flowshop scheduling problem with makespan objective (F|no-wait|C max in the standard three-field notation). This problem is well known to be a special case of the asymmetric traveling salesman problem (ATSP) and as such has an approximation algorithm with logarithmic performance guarantee. In this work, we show a reverse connection, we show that any polynomial time α-approximation algorithm for the no-wait flowshop scheduling problem with makespan objective implies the existence of a polynomial time α(1 + ɛ)-approximation algorithm for the ATSP for any ɛ > 0. This, in turn, implies that all nonapproximability results for the ATSP (current or future) will carry over to its special case. In particular, it follows that the no-wait flowshop problem is APX-hard, which is the first nonapproximability result for this problem.