TY - JOUR
T1 - Corrigendum to “An FPTAS for the parallel two-stage flowshop problem” (Theoretical Computer Science (2017) 657(Part A) (64–72)(S0304397516302250)(10.1016/j.tcs.2016.04.046))
AU - Dong, Jianming
AU - Hu, Jueliang
AU - Kovalyov, Mikhail Y.
AU - Lin, Guohui
AU - Luo, Taibo
AU - Tong, Weitian
AU - Wang, Xueshi
AU - Xu, Yinfeng
N1 - Publisher Copyright:
© 2017
PY - 2017/7/29
Y1 - 2017/7/29
N2 - We, except Mikhail Y. Kovalyov (MYK), considered the NP-hard m-parallel two-stage flow shop problem in [1], abbreviated as the [Formula presented]-PFS problem, where we need to schedule n jobs to m parallel classic two-stage flow shops in order to minimize the makespan, i.e. the maximum completion time of all jobs on the m flow shops. We first presented a pseudo-polynomial time dynamic programming algorithm to solve the [Formula presented]-PFS problem optimally, for any fixed m, based on an earlier idea from [3] for solving the [Formula presented]-PFS problem. Using the dynamic programming algorithm as a subroutine, we designed a fully polynomial-time approximation scheme (FPTAS) for the [Formula presented]-PFS problem. The paper [1] went online on June 8, 2016 and after it formally appeared in Part A of Volume 657, the authors were informed by MYK that a very similar result for a slightly more general problem [4] had published by MYK in Russian in 1985. The authors of [1] regret that the result of MYK [4] was missed by the literature, particularly by the cited works in [1]. The purposes of this corrigendum are • to clarify the relationship between the result in [1] and the result in [4];• to add [4] as a major reference;• to credit MYK as a major contributing author.The work in [1] follows the following research line: • In 1996, He et al. [2] “first” proposed the m parallel identical two-stage flowshop problem [Formula presented]-PFS, motivated by an application from the glass industry. In their work, the [Formula presented]-PFS problem is formulated as a mixed-integer programming and an efficient heuristics is proposed.• In 2000, Vairaktarakis and Elhafsi [3] also studied the [Formula presented]-PFS problem, in order to investigate the hybrid k-stage flowshop problem.• In 2012, Zhang and van de Velde [5] studied the [Formula presented]-PFS problem from the approximation algorithm perspective, (only) for the special case where [Formula presented] or 3. They designed a 3/2-approximation algorithm for the [Formula presented]-PFS problem and a 12/7-approximation algorithm for the [Formula presented]-PFS problem.The main contribution in [1] is to improve Zhang and van de Velde [5]'s work by designing an FPTAS for the [Formula presented]-PFS problem. Unfortunately, all the above line of works are not aware of the result in [4]. Besides, due to the difficulty of accessing the work [4] online, the authors of [1] were not aware of it either. The authors of [1] strongly believe that MYK should be credited for his work [4], and after discussing with MYK we all agreed that the work [1] is an independent re-invention of [4]. We proposed to the editors of Theoretical Computer Science to add [4] back as a major reference in this corrigendum and to include MYK as a contributing author to credit his original contribution [4] to the m-parallel two-stage flow shop problem. All the authors appreciate the editorial team of Theoretical Computer Science, Editors Dr. Jianxin Wang and Dr. Chee K. Yap in particular, for giving us such a chance to clarify this matter.
AB - We, except Mikhail Y. Kovalyov (MYK), considered the NP-hard m-parallel two-stage flow shop problem in [1], abbreviated as the [Formula presented]-PFS problem, where we need to schedule n jobs to m parallel classic two-stage flow shops in order to minimize the makespan, i.e. the maximum completion time of all jobs on the m flow shops. We first presented a pseudo-polynomial time dynamic programming algorithm to solve the [Formula presented]-PFS problem optimally, for any fixed m, based on an earlier idea from [3] for solving the [Formula presented]-PFS problem. Using the dynamic programming algorithm as a subroutine, we designed a fully polynomial-time approximation scheme (FPTAS) for the [Formula presented]-PFS problem. The paper [1] went online on June 8, 2016 and after it formally appeared in Part A of Volume 657, the authors were informed by MYK that a very similar result for a slightly more general problem [4] had published by MYK in Russian in 1985. The authors of [1] regret that the result of MYK [4] was missed by the literature, particularly by the cited works in [1]. The purposes of this corrigendum are • to clarify the relationship between the result in [1] and the result in [4];• to add [4] as a major reference;• to credit MYK as a major contributing author.The work in [1] follows the following research line: • In 1996, He et al. [2] “first” proposed the m parallel identical two-stage flowshop problem [Formula presented]-PFS, motivated by an application from the glass industry. In their work, the [Formula presented]-PFS problem is formulated as a mixed-integer programming and an efficient heuristics is proposed.• In 2000, Vairaktarakis and Elhafsi [3] also studied the [Formula presented]-PFS problem, in order to investigate the hybrid k-stage flowshop problem.• In 2012, Zhang and van de Velde [5] studied the [Formula presented]-PFS problem from the approximation algorithm perspective, (only) for the special case where [Formula presented] or 3. They designed a 3/2-approximation algorithm for the [Formula presented]-PFS problem and a 12/7-approximation algorithm for the [Formula presented]-PFS problem.The main contribution in [1] is to improve Zhang and van de Velde [5]'s work by designing an FPTAS for the [Formula presented]-PFS problem. Unfortunately, all the above line of works are not aware of the result in [4]. Besides, due to the difficulty of accessing the work [4] online, the authors of [1] were not aware of it either. The authors of [1] strongly believe that MYK should be credited for his work [4], and after discussing with MYK we all agreed that the work [1] is an independent re-invention of [4]. We proposed to the editors of Theoretical Computer Science to add [4] back as a major reference in this corrigendum and to include MYK as a contributing author to credit his original contribution [4] to the m-parallel two-stage flow shop problem. All the authors appreciate the editorial team of Theoretical Computer Science, Editors Dr. Jianxin Wang and Dr. Chee K. Yap in particular, for giving us such a chance to clarify this matter.
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=85019773648&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.05.016
DO - 10.1016/j.tcs.2017.05.016
M3 - Commentary
AN - SCOPUS:85019773648
SN - 0304-3975
VL - 687
SP - 93
EP - 94
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -