摘要
对于由工时与工期所确定的工件的全体,本文定义了一种全序,该全序是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.
出处
《应用数学与计算数学学报》
1991年第2期66-71,共6页
Communication on Applied Mathematics and Computation
基金
国家自然科学基金
