TY - JOUR

T1 - An FPTAS for the parallel two-stage flowshop problem

AU - Dong, Jianming

AU - Tong, Weitian

AU - Luo, Taibo

AU - Wang, Xueshi

AU - Hu, Jueliang

AU - Xu, Yinfeng

AU - Lin, Guohui

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2017/1/2

Y1 - 2017/1/2

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Fully polynomial-time approximation scheme

KW - Makespan

KW - Multiprocessor scheduling

KW - Two-stage flowshop scheduling

UR - http://www.scopus.com/inward/record.url?scp=85002531819&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2016.04.046

DO - 10.1016/j.tcs.2016.04.046

M3 - Article

AN - SCOPUS:85002531819

SN - 0304-3975

VL - 657

SP - 64

EP - 72

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -