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.