|
个人信息Personal Information
教授
博士生导师
硕士生导师
主要任职：Professor
性别：男
毕业院校：日本京都大学
学位：博士
所在单位：软件学院、国际信息与软件学院
学科：计算机软件与理论. 运筹学与控制论
联系方式：hanxin@dlut.edu.cn
Flowshop problem F2 -> D broken vertical bar nu = c >= 1 vertical bar C-max revisited
点击次数：
论文类型：期刊论文
发表时间：2017-03-29
发表刊物：THEORETICAL COMPUTER SCIENCE
收录刊物：SCIE
卷号：670
页面范围：79-85
ISSN号：0304-3975
关键字：Flow shop problems; NP-hard; Complexity
摘要：In this paper we study a flow shop problem F2 -> D vertical bar v =1, c >= I vertical bar C-max 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 vertical bar v = 1, c = 2 vertical bar C-max has been proved to be binary NP-hard in EJ0R2007 [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. (C) 2017 Elsevier B.V. All rights reserved.