No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem

• 成果类型: Article
• 署名作者: Mucha, Marcin; Sviridenko, Maxim
• 署名单位: University of Warsaw; Yahoo! Inc; University of Warwick
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2015.0725
• 发表日期: 2016
• 页码: 247-254
• 关键词: algorithms; machine; tsp

摘要

In this paper, we study the classical no-wait flowshop scheduling problem with makespan objective (F vertical bar no-wait vertical bar 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 alpha-approximation algorithm for the no-wait flowshop scheduling problem with makespan objective implies the existence of a polynomial time alpha(1+epsilon)-approximation algorithm for the ATSP for any epsilon > 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.