Moore-Hodgson算法最优性的新证明

A New Proof of the Optimality of Moore-Hodgson Algorithm

经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O(nlogn)内得到误工问题的最优解。虽然经过改进,然而Moore-Hodgson算法最优性的证明仍然非常复杂。本文给出Moore-Hodgson算法最优性的一个非常简洁的新的证明。由于误工问题在排序论里的重要性,本文给出的新的证明在理论上是有重要意义的,是可以为排序论的专著和教材所采纳的。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,也可能有简洁的证明。

The single machine scheduling problem to minimize the number of tardy jobs is one of the most basic scheduling problems in scheduling theory. The famous Moore-Hodgson algorithm can get the problem＇s optimal solution in O（ nlog n）. Though there is improvment, the proof of the optimality of Moore-Hodgson algorithm is still very complicated. Owing to the importance of the problem, the simplified proof in our paper is meaningful in terms of theory and should be adopted in acheduling books. In addition, for the generalized scheduling problems to minimize the number of tardy jobs, such as： the case in which some jobs must be on-time, or the case of agreeability of ready times with due dates, or the case of reverse agreeability of processing times with weights, etc. their optimalities could be simplified to prove, too.