文件名称：Moore-Hodgson算法最优性的新证明* (2007年)
文件大小：745KB
文件格式：PDF
更新时间：2024-05-14 03:09:37
自然科学 论文
经典排序论中使误工工件的个数为最少的单台机器排序问题，简称为误工问题，是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O（nlog n）内得到误工问题的最优解。虽然经过改进，然而Moore-Hodgson算法最优性的证明仍然非常复杂。本文给出Moore-Hodgson算法最优性的一个非常简洁的新的证明。由于误工问题在排序论里的重要性，本文给出的新的证明在理论上是有重要意义的，是可以为排序论的专著和教材所采纳的。此外，对于推广的误工问题，例如，某些工件必须不误工的排序问题，或者工件