کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952326 | 1364440 | 2017 | 9 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 64-72