A Note on a Fully Polynomial-Time Approximation Scheme for Minimizing Makespan of Deteriorating Jobs. (11th September 2013)

• Record Type: Journal Article
• Authors: Wan, Long
• Other Names: Yin Yunqiang Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2013(2013)
• Publication Date: 2013-09-11
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2013/957494
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : In (1998), Kovalyov and Kubiak studied the problem of scheduling n deteriorating jobs on a single machine to minimize makespan. They presented a fully polynomial-time approximation scheme which is based on a dynamic programming. Unfortunately, their dynamic programming is incorrect. So the fully polynomial-time approximation scheme is also invalid. In this paper, we construct an instance to show how their dynamic programming does not work and provide a correct dynamic programming, based on which a new fully polynomial-time approximation scheme is derived.