An FPTAS for the parallel two-stage flowshop problem

作     者：Jianming Dong Weitian Tong Taibo Luo Xueshi Wang Jueliang Hu Yinfeng Xu Guohui Lin 

作者机构：Department of Mathematics Zhejiang Sci-Tech University Hangzhou Zhejiang 310018 China Department of Computing Science University of Alberta Edmonton Alberta T6G 2E8 Canada Department of Computer Sciences Georgia Southern University Statesboro GA 30458 USA Business School Sichuan University Chengdu Sichuan 610065 China State Key Lab for Manufacturing Systems Engineering Xi'an Shaanxi 710049 China 

出 版 物：《Theoretical Computer Science》 (理论计算机科学)

年 卷 期：2017年第657卷第PartA期

页      面：64-72页

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

主　　题：Two-stage flowshop scheduling Multiprocessor scheduling Makespan Dynamic programming Fully polynomial-time approximation scheme 

摘      要：We consider the NP-hard m - parallel two-stage flowshop problem, abbreviated as the ( m , 2 ) -PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m flowshops. The ( m , 2 ) -PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the ( m , 2 ) -PFS problem optimally, for any fixed m , based on an earlier idea for solving the ( 2 , 2 ) -PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the ( m , 2 ) -PFS problem.