Exact and parallel metaheuristic algorithms for the single processor total weighted completion time scheduling problem with the sum-of-processing-time based models

In this paper, the single processor scheduling problem to minimize the total weighted completion times is analysed, where the processing times of jobs are described by functions dependent on the sum of the normal processing times of previously processed jobs, which can model learning or aging (deteriorating) effects. We construct the exact pseudopolynomial time algorithm based on the dynamic programming, which solves the problem, where the processing time of each job is described by an arbitrary stepwise function. Moreover, the parallel metaheuristic algorithms are provided for the general version of the problem with arbitrary sum-of-processing time based models. The efficiency of the proposed algorithms is evaluated during numerical analysis.