A note on the time complexity of machine scheduling with DeJong's learning effect. (October 2017)

• Record Type: Journal Article
• Authors: Zhao, Chuanli; Fang, Ji; Cheng, T.C.E.; Ji, Min
• Is Part Of: Computers & industrial engineering. Volume 112(2017)
• Page Start: 447
• Page End: 449
• Publication Date: 2017-10
• Subjects: Scheduling -- DeJong's learning effect -- FPTAS -- Time complexity; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.08.010
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: This note improves time complexity of two FPTASes provided in two papers published in CAIE . Further general comments are also proposed in the last. Abstract: 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.