文献类型：期刊文献

中文题名：工件集合上的某种全序及其应用

英文题名：A Total Order on Job Sets and It's Applications

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

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

年份：1991

卷号：5

期号：2

起止页码：66

中文期刊名：应用数学与计算数学学报

外文期刊名：Communication on Applied Mathematics and Computation

基金：国家自然科学基金

语种：中文

中文关键词：全序;延误问题;工件集合;近似算法

摘要：对于由工时与工期所确定的工件的全体,本文定义了一种全序,该全序是SPT序(短工时序)与EDD序(早工期序)的结合,且结合方式依赖于某个时间参数。本文分析了该全序与有关延误的相邻交换条件之联系,从而给出总延误问题的一个近似算法,并证明它可以在多项式时间内得到后移邻域所相应的局部解。
For any job set, of which each job is characterized by a processing time and a due date, a total order with respect to a time paramater is defined as combination of SPT (shortest processing time) order and EDD (earliest due date) order. And relations between the total order and Emmons conditions of the one-machine total tardiness problem are analysed. Then an polynomial algorithm for total tardiness problems is presented. Also it's proved that the algorithm always produces a local solution corresponding neighbourhoods determined by backward shifts on the job sequence.