A fully polynomial approximation scheme for the weighted earliness-tardiness problem
成果类型：
Article
署名作者：
Kovalyov, MY; Kubiak, W
署名单位：
National Academy of Sciences of Belarus (NASB); United Institute of Informatics Problems of the National Academy of Sciences of Belarus; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.5.757
发表日期：
1999
页码：
757-761
关键词：
摘要：
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.