Single-machine scheduling with times-based and job-dependent learning effect

Absract

Learning effect is a phenomenon in industrial processes that a machine (plant, worker, etc) can improve its productivity continuously with time, that is the actual processing time of a job decreases after the machine (plant, worker, etc) processes other jobs and gains some experiences. We study single machine scheduling problems with sum-of-processing-time based and job-dependent learning effect. The objectives are to minimize the maximum lateness, the number of tardy jobs, and total weighted completion time. By performing reductions from equal cardinality partition problem, we prove that these problems under investigation are all NP-hard. Two special cases that can be solved in polynomial time are also presented.

Keywords:

• Scheduling
• Single machine
• Learning effect
• NP-hardness

Acknowledgements

This work was supported in part by projects of National Natural Science Foundation of China (No. 71171058 and No. 11371103). We are grateful to the anonymous referees for their valuable comments on an earlier version of this paper.