Strong NP-hardness of scheduling problems with learning or aging effect

被引：0
作者：
Adam Janiak
Mikhail Y. Kovalyov
Maciej Lichtenstein
机构：
[1] Wrocław University of Technology,United Institute of Informatics Problems
[2] National Academy of Sciences of Belarus,undefined
来源：
Annals of Operations Research | 2013年 / 206卷
关键词：
Scheduling; Flowshop; Single machine; Learning effect; Aging effect; Computational complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Proofs of strong NP-hardness of single machine and two-machine flowshop scheduling problems with learning or aging effect given in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c; Applied Mathematical Modelling 37:1523–1536, 2013) contain a common mistake that make them incomplete. We reveal the mistake and provide necessary corrections for the problems in Rudek (Computers & Industrial Engineering 61:20–31, 2011; Annals of Operations Research 196(1):491–516, 2012a; Applied Mathematical Modelling 37:1523–1536, 2013). NP-hardness of problems in Rudek (International Journal of Advanced Manufacturing Technology 59:299–309, 2012b; Applied Mathematics and Computations 218:6498–6510, 2012c) remains unknown because of another mistake which we are unable to correct.
引用
收藏
页码：577 / 583
页数：6
相关论文
共 14 条
  • [1] Kuo W.-H.(2012)Single-machine group scheduling with time-dependent learning effect and position-based setup time learning effect Annals of Operations Research 196 349-359
  • [2] Rudek R.(2011)Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect Computers & Industrial Engineering 61 20-31
  • [3] Rudek R.(2012)Scheduling problems with position dependent job processing times: computational complexity results Annals of Operations Research 196 491-516
  • [4] Rudek R.(2012)Some single-machine scheduling problems with the extended sum-of-processing-time-based aging effect International Journal of Advanced Manufacturing Technology 59 299-309
  • [5] Rudek R.(2012)The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect Applied Mathematics and Computing 218 6498-6510
  • [6] Rudek R.(2013)On single processor scheduling problems with learning dependent on the number of processed jobs Applied Mathematical Modelling 37 1523-1536
  • [7] Wang J.-B.(2011)Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects Annals of Operations Research 191 155-169
  • [8] Wang M.-Z.(2009)Single-machine scheduling with both deterioration and learning effects Annals of Operations Research 172 315-327
  • [9] Yang D.-L.(2011)Single-machine scheduling problems with time and position dependent processing times Annals of Operations Research 186 345-356
  • [10] Kuo W.-H.(undefined)undefined undefined undefined undefined-undefined
12