A note on the time complexity of machine scheduling with DeJong's learning effect

作者：Zhao, Chuanli; Fang, Ji; Cheng, T. C. E.; Ji, Min^*

来源：Computers & Industrial Engineering, 2017, 112: 447-449.

DOI：10.1016/j.cie.2017.08.010

• Scheduling
• DeJong's learning effect
• FPTAS
• Time complexity

In a recent paper (Ji et al., 2015), the authors provided a fully polynomial-time approximation scheme (FPTAS) for the considered NP-hard problem. Extending this research, the authors in another paper (Ji et al., 2016) gave an FPTAS for a related NP-hard problem. In this note we show that the time complexity of the two FPTASes can be improved.

• 出版日期2017-10
• 单位沈阳师范大学; 浙江工商大学; 香港理工大学