The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard

•We analyse the single machine total weighted completion time scheduling with learning and aging effects.•The job processing times depend on the sum of the normal job processing times.•The considered problem with the learning effect is proved to be strongly NP-hard.•The considered problem with the aging effect is proved to be strongly NP-hard.•A parallel branch and bound algorithm is constructed for the general version of the problem.

Although the single machine scheduling problem to minimize the total weighted completion times with the sum-of-processing time based learning or aging effects have been known for a decade, it is still an open question whether these problems are strongly NP-hard. We resolve this issue and prove them to be strongly NP-hard with the learning effect as well as with the aging effect. Furthermore, we construct an exact parallel branch and bound algorithm for the problem with general sum-of-processing time based models, which can solve optimally moderate problem instances in reasonable time.