Single-machine scheduling problems with actual time-dependent and job-dependent learning effect

In this study, we introduce an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. We show that the complexity results of the makespan minimization problem and the sum of weighted completion time minimization problem are all NP-hard. The complexity result of the maximum lateness minimization problem is NP-hard in the strong sense. We also provide three special cases which can be solved by polynomial time algorithms.

Highlight► A new learning effect is introduced into single machine scheduling problems. ► The actual time-dependent and job-dependent model is a more general one. ► The complexity result of the makespan minimization problem is NP-hard. ► The sum of weighted completion time minimization problem is NP-hard. ► The maximum lateness minimization problem is NP-hard in the strong sense.