Single-machine scheduling with a sum-of-actual-processing-time-based learning effect

Abstract

In this paper we consider the single-machine scheduling problems with a sum-of-actual-processing-time-based learning effect. By the sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by a function of the sum of the actual processing time of the already processed jobs. We show that even with the introduction of the sum-of-actual-processing-time-based learning effect to job processing times, the makespan minimization problem, the total completion time minimization problem, the total completion time square minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable, respectively.

Keywords:

• scheduling
• single machine
• learning effect

Acknowledgements

We are grateful to two anonymous referees for their helpful comments on earlier version of this paper. This research was supported by the Science Research Foundation of the Educational Department of Liaoning Province, China, under grant number 20060662, and the National Natural Science Foundation of China.