Moore-Hodgson算法的最优性  

The Optimality of Moore-Hodgson Algorithm

作　　者：陈小林[1] 苏文玉[1] 唐国春[1] 

机构地区：[1]重庆师范大学数学与计算机科学学院,重庆400047

出　　处：《上海第二工业大学学报》2008年第1期25-28,共4页Journal of Shanghai Polytechnic University

基　　金：国家自然科学基金项目(No.10371071和No.70731160015);上海市教委资助项目"若干现代排序模型的研究"(No.07zz178);运筹学与系统工程重庆市市级重点实验室资助项目

摘　　要：经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一。著名的Moore-Hodgson算法可以在时间O(n log n)内得到误工问题的最优解。Pinedo在1995年对于Moore-Hodgson算法的最优性给出一个证明。虽然这个证明不严格,许多关键的地方交待不清,但是Pinedo证明的过程表明Moore-Hodgson算法得到解是所有最优解中不误工工件的总的加工时间最短的。这是一个很本质的性质,是其他所有的证明中没有提及的。本文补充和完善了Pinedo的证明。此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,是否也有类似的性质?这是非常有意义的进一步研究方向。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 could get the problem＇s optimal solution in O（n log n）, A proof was given by Pinedo in 1995. The process of the proof indicates that the solution finding by Moore-Hodgson algorithm has the shortest total processing time among all optimality solutions, which is a property of the essence, although this proof isn＇t strict and not clear at some crucial points. A precise and complete proof is presented in this paper.. In addition, it＇s a promising topic in further researches to study the similar property 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 one of agreeability of ready times with due dates, or the one of reverse agreeability of processing times with weights, et al.

关 键 词：排序 最优性 算法 

分 类 号：O223[理学—运筹学与控制论] O157.5[理学—数学]