A Note on a Fully Polynomial-Time Approximation Scheme for Minimizing Makespan of Deteriorating Jobs

Abstract EN

In (1998), Kovalyov and Kubiak 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.