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

Radosław Rudek

Abstract

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
Vol50
Pages314-332
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
DOIDOI:10.1016/j.apm.2017.05.034
URL https://doi.org/10.1016/j.apm.2017.05.034
Languageen angielski
File
Rudek_The_ single_ machine_ total_ weighted2017.pdf 778,54 KB
Score (nominal)35
ScoreMinisterial score = 35.0, 20-08-2019, ArticleFromJournal
Publication indicators Scopus Citations = 2; Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.748; WoS Impact Factor: 2017 = 2.617 (2) - 2017=2.94 (5)
Citation count*3 (2019-12-10)
Cite
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.
Back