论文部分内容阅读
排序论中使误工工件的个数为最少的单台机器排序问题，称为误工问题，是排序论中最基本的问题之一。1973年，Sidney研究在工件的一个子集T中的工件必须不误工的条件下，使误工工件的个数为最少的误工排序问题1｜T｜∑Uj，并且给出该问题复杂性为O（n log n）的多项式算法——Sidney算法。本文把Sidney算法改写成比较简洁的算法1，1）步骤1：设E0：T，J-E0={j1，j2，…，jm}j1〈j2〈…〈jm，m=n-｜T｜，令k=1；2）步骤2：若k=m＋1，算法终止，（Em，J-Em）就是最优排