The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard
AbstractAlthough 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
|Journal series||Applied Mathematical Modelling, ISSN 0307-904X, (A 35 pkt)|
|Publication size in sheets||0.9|
|Keywords in English||scheduling, learning effect, aging effect computational complexity, strongly NP-hard, parallel branch and bound|
|Publication indicators||= 2; : 2017 = 1.469; : 2017 = 2.617 (2) - 2017=2.94 (5)|
|Citation count*||5 (2020-09-19)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.