总延误问题的关键位置法

对于工期递增的工件序列，取最长工时的工件作后移变换，便得到一组总延误值，能使这组总延误值最早达到最小值的那个位置便称为关键位置。在本文中，我们提出了关键位置法如下：在工期递增的工件序列中，将最长工件后移至关键位置，并以此分为二个子问题，然后对一切子问题亦这样做。我们证明了该算法必能得到相邻交换意义下的局部解，并得到了该算法的最坏情形性能性。同时，我们还对该算法给出了计算试验报告及若干讨论。