KIM算法的最优性

研究工件的就绪时间可以不相同、但是与交货期有＂一致性＂关系的误工问题.1978年Kise,Ibaraki,Mine提出算法（简称为KIM算法）,证明他们提出的KIM算法可以得到这个误工问题的最优解.最近李杉林、陈志龙、唐国春用反例指出Kise,Ibaraki,Mine证明最优性时提出的引理2是错误的,并用新的方法证明KIM算法的最优性.越民义则给出一个非常简洁的证明.本文分析引理2的错误所在,给出修改后的引理2’,由此似乎应该相应修改KIM算法,然而我们证明原来的KIM算法仍然可以得到最优解.