Machine scheduling with deteriorating jobs and DeJong’s learning effect

•We consider parallel-machine scheduling with deteriorating jobs and DeJong’s learning effect.•We provide an FPTAS for minimizing the makespan.•We show that the total completion time minimization problem is polynomially solvable.

We consider parallel-machine scheduling with deteriorating jobs and DeJong’s learning effect. We focus on the problems to minimize the total completion time and the makespan. We show that the former is polynomially solvable, while the latter is NP-hard, for which we provide a fully polynomial-time approximation scheme.