论文部分内容阅读
经典排序论中使误工工件的个数为最少的单台机器排序问题，简称为误工问题，是排序论中最基本的问题之一。著名的Moore—Hodgson算法可以在时间O（n log n）内得到误工问题的最优解。Pinedo在1995年对于Moore—Hodgson算法的最优性给出一个证明。虽然这个证明不严格，许多关键的地方交待不清，但是Pinedo证明的过程表明Moore—Hodgson算法得到解是所有最优解中不误工工件的总的加工时间最短的。这是一个很本质的性质，是其他所有的证明中没有提及的。本文补充和完善了Pinedo的证明