摘要
对于一台机器的总延误问题,本文提出了一个近似算法,它具有以下性质:多项式复杂度,给出局部解(相应于后移邻域),有界的性能比。本文侧重给出一个论证方法,以得到该算法性能比的精确值。
An approximation algorithm for the total tardiness problem is presented in this paper, which possesses the following properties: polynomial complexity, a local solution with respect to backward shift neighbourhood and finite performance ratio. Much effort has been put on getting the exact value of the performance ratio of the algorithm.
基金
国家自然科学基金
关键词
动筹学
算法
总延误问题
最佳化
scheduling theory
optimization algorithm
total tardiness problem
local solution
performance ratio
