文献类型：期刊文献

中文题名：总延误问题的关键位置法

英文题名：Key-Position Method for the Total Tardiness Problem

作者：俞文(鱼此)[1];于明晶[1]

机构：[1]上海华东理工大学应用数学研究所,上海200237

年份：1995

卷号：14

期号：1

起止页码：8

中文期刊名：运筹学杂志

收录：CSCD:【CSCD2011_2012】；

基金：国家自然科学基金资助项目

语种：中文

中文关键词：时间表问题;总延误问题;排序;关键位置法

外文关键词：Scheduling Problem;;Total Tardiness Problem;;Decomposition Theorem;;Approximation Method;;Local Solution;;Computational Complexity;;Performance Ratio.

摘要：对于工期递增的工件序列,取最长工时的工件作后移交换,便得到一组总延误值,能使这组总延误值最早达到最小值的那个位置便称为关键位置.在本文中,我们提出了关键位置法如下:在工期递增的工件序列中,将最长工件后移至关键位置,并以此分为二个子问题,然后对一切子问题亦这样做.我们证明了该算法必能得到相邻交换意义下的局部解,并得到了该算法的最坏情形性能比.同时,我们还对该算法给出了计算试验报告及若干讨论.
For a one-machine total tardiness problem,while making backward-shifts of the longest job to all possible positions in the EDD sequence of all jobs (in the order of nondecreasing due dates),key position is defined as the earliest position such that the corresponding total tardiness takes minimum.In this paper,key position method is proposed as follows:begin with the EDD job sequence,move the longest job to the key position,get two subproblems with jobs left to and right to the key position,and treat these subproblems in the same manner,it is proved that the key position method results always a local solution in the meaning of neighboring interchange.Also,the computational complexity and the performance ratio of the method are obtained.Additionally computational tests are described.