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.