Indexed by:
Abstract:
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 fiowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m fiowshops. 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. (C) 2016 Elsevier B.V. All rights reserved.
Keyword:
Reprint Author's Address:
Email:
Source :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
Year: 2017
Volume: 657
Page: 64-72
0 . 7 7 2
JCR@2017
0 . 8 2 7
JCR@2020
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:135
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 17
SCOPUS Cited Count: 22
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: