A Fully Polynomial Approximation Scheme for the Weighted Earliness–Tardiness Problem
Mikhail Y. Kovalyov, Wieslaw Kubiak
Operations Research · 1999 · Volume 47 · Issue 5
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
Enable JavaScript for citation tools and additional paper interactions.