The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model

In this paper, we analyse the single processor total weighted completion time scheduling problem with the learning effect, where the processing time of each job is a non-increasing function dependent on the sum of the normal processing times of preceding jobs. We prove that the considered problem is at least NP-hard. Moreover, a pseudopolynomial time dynamic programming algorithm that optimally solves the problem with a step learning function (curve) is constructed. Furthermore, fast approximation algorithms for the general version of the problem, where job processing times are described by arbitrary functions dependent on the sum of the normal job processing times, are provided. Their efficiency is verified numerically and for Weighted Shortest Processing Times algorithm a worst case analysis is also performed.

► The total weighted completion time scheduling problem with the processing time based learning effect is NP-hard.
► An exact pseudopolynomial time dynamic programming algorithm is constructed.
► Fast heuristics and metaheuristics for the problem with the general processing time based learning model are provided.
► A survey on scheduling problems with processing time based learning models is presented.