A note on a fully polynomial-time approximation scheme for minimizing makespan of deteriorating jobs (Q474321)

Summary: \textit{M. Y. Kovalyov} and \textit{W. Kubiak} [J. Heuristics 3, No. 4, 287--297 (1998; Zbl 0903.90100)] studied the problem of scheduling \(n\) deteriorating jobs on a single machine to minimize makespan. They presented a fully polynomial-time approximation scheme which is based on a dynamic programming. Unfortunately, their dynamic programming is incorrect. So the fully polynomial-time approximation scheme is also invalid. In this paper, we construct an instance to show how their dynamic programming does not work and provide a correct dynamic programming, based on which a new fully polynomial-time approximation scheme is derived.