KIM算法的最优性
研究工件的就绪时间可以不相同、但是与交货期有"一致性"关系的误工问题.1978年Kise,Ibaraki,Mine提出算法(简称为KIM算法),证明他们提出的KIM算法可以得到这个误工问题的最优解.最近李杉林、陈志龙、唐国春用反例指出Kise,Ibaraki,Mine 证明最优性时提出的引理2是错误的,并用新的方法证明KIM算法的最优性.越民义则给出一个非常简洁的证明.本文分析引理2的错误所在,给出修改后的引理2',由此似乎应该相应修改KIM算法,然而我们证明原来的KIM算法仍然可以得到最优解.
作 者： 孙叶平 唐国春 Sun Yeping Tang Guochun 作者单位： 孙叶平,Sun Yeping(重庆师范大学数学与计算机科学学院,重庆,400047)唐国春,Tang Guochun(上海第二工业大学管理工程研究所,上海,200041)
刊 名： 运筹学学报 ISTIC PKU 英文刊名： OPERATIONS RESEARCH TRANSACTIONS 年，卷(期)： 2007 11(4) 分类号： O22 关键词： 运筹学 排序 最优性 算法