A FULLY POLYNOMIAL-APPROXIMATION SCHEME FOR SCHEDULING A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED LATE WORK
成果类型：
Article
署名作者：
KOVALYOV, MY; POTTS, CN; VANWASSENHOVE, LN
署名单位：
INSEAD Business School; University of Southampton
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.19.1.86
发表日期：
1994
页码：
86-93
关键词：
摘要：
This paper studies approximation algorithms for the problem of nonpreemptively scheduling n jobs on a single machine to minimize total weighted late work, where the late work for a job is the amount of processing of this job that is performed after its due date. A family of approximation algorithms {DP(epsilon)} is derived. For any epsilon > 0, DP(epsilon) delivers a schedule having total weighted late work which does not exceed (1 + epsilon) times that of an optimal schedule. Since DP(epsilon) requires O(n3 log n + n3/epsilon) time, the family {DP(epsilon)} is a fully polynomial approximation scheme.