Machine scheduling with DeJong’s learning effect

• We consider a new scheduling model with DeJong’s learning effect.
• The objectives are to minimize makespan and the total completion time.
• For single machine, both objectives are showed to be polynomially solvable.
• For parallel machines, an FPTAS is proposed for minimizing makespan.
• Minimizing the total completion time is still polynomially solvable on parallel machines.

We consider a relatively new learning model in scheduling based on DeJong’s learning effect. Compared with the classical learning model for scheduling, this model is more general and realistic. The objectives are to minimize makespan and total completion time. For the single-machine case, we show that both of the objectives are polynomially solvable. For the parallel-machine case, we show that minimizing total completion time is still polynomially solvable, while minimizing makespan is NP-hard, for which we provide a fully polynomial-time approximation scheme (FPTAS).