An FPTAS for the parallel two-stage flowshop problem

详细信息    查看全文

• 作者：Jianming Dong^a ; ¹ ; Weitian Tong^b ; ^c ; ¹ ; Taibo Luo^d ; ^b ; ¹ ; Xueshi Wang^a ; Jueliang Hu^a ; Yinfeng Xu^d ; ^e ; Guohui Lin^a ; ^b ; ^{guohui@ualberta.ca}
• 关键词：Two-stage flowshop scheduling ; Multiprocessor scheduling ; Makespan ; Dynamic programming ; Fully polynomial-time approximation scheme
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：2 January 2017
• 年：2017
• 卷：657
• 期：part_PA
• 页码：64-72
• 全文大小：430 K
• 卷排序：657

文摘

We consider the NP-hard m-parallel two-stage flowshop   problem, abbreviated as the (m,2)(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)(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)(m,2)-PFS problem optimally, for any fixed m  , based on an earlier idea for solving the (2,2)(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)(m,2)-PFS problem.