Some single‐machine scheduling problems with a truncation learning effect

Scheduling with learning effects has received growing attention nowadays. A well‐known learning model is called ‘sum‐of processing‐times‐based learning’ in which the actual processing time of a job is a non‐increasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Motivated by this observation, we propose a truncation learning model where the actual job processing time is a function which depends not only on the processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. Under the proposed learning model, we show that some single‐machine scheduling problems can be solved in polynomial time. In addition, we further provide the worst‐case error bounds for the problems to minimize the maximum lateness and total weighted completion time.