文献类型：期刊文献

中文题名：总延误问题的一个近似算法及其分析

英文题名：An Approximation Algorithm for the Total Tardiness Problem and its Analysis

作者：俞文(鱼此)[1]

机构：[1]华东化工学院应用数学研究所

年份：1992

卷号：18

期号：5

起止页码：671

中文期刊名：华东化工学院学报

收录：Scopus;CSCD:【CSCD2011_2012】；

基金：国家自然科学基金

语种：中文

中文关键词：动筹学;算法;总延误问题;最佳化

外文关键词：scheduling theory; optimization algorithm; total tardiness problem; local solution; performance ratio

摘要：对于一台机器的总延误问题,本文提出了一个近似算法,它具有以下性质:多项式复杂度,给出局部解(相应于后移邻域),有界的性能比。本文侧重给出一个论证方法,以得到该算法性能比的精确值。
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.