A Note on a Fully Polynomial-Time Approximation Scheme for Minimizing Makespan of Deteriorating Jobs

Long Wan

Mathematical Problems in Engineering, 2013, vol. 2013, 1-7

Abstract:

In (1998), Kovalyov and Kubiak studied the problem of scheduling 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.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/957494.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/957494.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:957494

DOI: 10.1155/2013/957494

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().