A FULLY POLYNOMIAL-APPROXIMATION SCHEME FOR SCHEDULING A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED LATE WORK

被引：57

作者：

KOVALYOV, MY

POTTS, CN

VANWASSENHOVE, LN

机构：

[1] INSEAD, FONTAINEBLEAU, FRANCE

[2] UNIV SOUTHAMPTON, FAC MATH STUDIES, SOUTHAMPTON SO9 5NH, HANTS, ENGLAND

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 1994年 / 19卷 / 01期

关键词：

SCHEDULING; SINGLE MACHINE; APPROXIMATION SCHEME; DYNAMIC PROGRAMMING;

D O I：

10.1287/moor.19.1.86

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：86 / 93

页数：8

共 4 条

[1]

HARRIS AMA, 1994, IN PRESS ORSA J COMP

[2] OPTIMAL SEQUENCING OF A SINGLE MACHINE SUBJECT TO PRECEDENCE CONSTRAINTS [J].