Improved approximation algorithms for two-stage flowshops scheduling problem

作     者：Wu, Guangwei Chen, Jianer Wang, Jianxin 

作者机构：Cent South Univ Sch Comp Sci & Engn Changsha 410083 Hunan Peoples R China Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha 410004 Hunan Peoples R China Guangzhou Univ Sch Comp Sci & Educ Software Guangzhou 510006 Guangdong Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2020年第806卷

页      面：509-515页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [61420106009, 61672536, 61872450, 61872097] 111 Project [B18059] Hunan Provincial Science and Technology Program [2018wk4001] 

主　　题：Scheduling Flowshops Approximation algorithm MAKESPAN 

摘      要：This paper considers the problem of scheduling n two-stage jobs on m two-stage flowshops so as to minimize the makespan. By studying the relationship between the problem and the classical MAKESPAN problem, we prove that if there is an alpha-approximation algorithm for the MAKESPAN problem, then for the general case of the problem, we can construct a 2 alpha-approximation algorithm, and for two restricted cases which are of practical importance, we can construct an (alpha + 1/2)-approximation algorithm. As a result, by employing the polynomial-time approximation scheme for the MAKESPAN problem, we get a (2 + epsilon-approximation algorithm for the general case and a (1.5 + epsilon)-approximation algorithm for the two restricted cases, which significantly improve the previous approximation ratios 2.6 and 11/6 respectively. (C) 2019 Elsevier B.V. All rights reserved.