文献类型：期刊文章

作　　者：孙叶平[1] 唐万梅[1] 唐国春[2]

机构地区：[1]重庆师范大学数学与计算机科学学院,重庆400047 [2]上海第二工业大学管理工程研究所,上海200041

出　　处：《重庆师范大学学报（自然科学版）》

基　　金：国家自然科学基金项目(No.10371071No.70618001)

年　　份：2007

卷　　号：24

期　　号：3

起止页码：4-7

语　　种：中文

收录情况：CAB、CAS、DOAJ、IC、JST、RCCSE、WOS、ZGKJHX、ZMATH、ZR、普通刊

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

关 键 词：排序 最优性 算法  

分 类 号：O223]