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

Radosław Rudek


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
Author Radosław Rudek (MISaF / IBI / DIT)
Radosław Rudek,,
- Department of Information Technologies
Journal seriesApplied Mathematical Modelling, ISSN 0307-904X, (A 35 pkt)
Issue year2017
Publication size in sheets0.9
Keywords in Englishscheduling, learning effect, aging effect computational complexity, strongly NP-hard, parallel branch and bound
ASJC Classification2604 Applied Mathematics; 2611 Modelling and Simulation
Languageen angielski
Rudek_The_ single_ machine_ total_ weighted2017.pdf 778,54 KB
Score (nominal)35
Score sourcejournalList
Publication indicators Scopus Citations = 2; Scopus SNIP (Source Normalised Impact per Paper): 2017 = 1.469; WoS Impact Factor: 2017 = 2.617 (2) - 2017=2.94 (5)
Citation count*5 (2020-09-19)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.