Single-machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect

We study single machine scheduling problems with general truncated sum-of-actual-processing-time-based learning effect. In the general truncated learning model, the actual processing time of a job is affected by the sum of actual processing times of previous jobs and by a job-dependent truncation parameter. We show that the single machine problems to minimize makespan and to minimize the sum of weighted completion times are both at least ordinary NP-hard and the single machine problem to minimize maximum lateness is strongly NP-hard. We then show polynomial solvable cases and approximation algorithms for these problems. Computational experiments are also conducted to show the effectiveness of our approximation algorithms.