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))

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.