Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time

作     者：Wei, Hongjun Yuan, Jinjiang 

作者机构：Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2019年第47卷第1期

页      面：41-46页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：Natural Science Foundation of China 

主　　题：Scheduling Flow shop Total weighted completion time NP-hard Approximation algorithm 

摘      要：We consider the classical two-machine flow-shop scheduling for minimizing the total weighted completion time. For this problem, the computational complexity of a version in which the jobs have a common processing time on the second machine, has not been addressed. We show that the problem is unary NP-hard, answering an open problem posed in Zhu et al. (2016). Then we present an approximation algorithm for the problem with worst-case performance ratio at most 2. (C) 2018 Elsevier B.V. All rights reserved.