A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem

Mikhail Y. Kovalyov and Wieslaw Kubiak
Additional contact information
Mikhail Y. Kovalyov: Institute of Engineering Cybernetics, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus
Wieslaw Kubiak: École Nationale Supérieure de Génie Industriel, Laboratoire GILCO, and Université Joseph Fourier, Laboratoire Leibniz, Grenoble, France

Operations Research, 1999, vol. 47, issue 5, 757-761

Abstract: A fully polynomial approximation scheme for the problem of scheduling n jobs on a single machine to minimize total weighted earliness and tardiness is presented. A new technique is used to develop the scheme. The main feature of this technique is that it recursively computes lower and upper bounds on the value of partial optimal solutions. Therefore, the scheme does not require any prior knowledge of lower and upper bounds on the value of a complete optimal solution. This distinguishes it from all the existing approximation schemes.

Keywords: analysis of algorithms; suboptimal algorithms; fully polynomial approximation scheme; production/scheduling; approximations/heuristic; single machine; weighted earliness–tardiness (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.5.757 (application/pdf)

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:inm:oropre:v:47:y:1999:i:5:p:757-761

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().