KIM算法的最优性

The Optimality of the KIM Algorithm

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

We address the scheduling problem for the case of agreeability of release times with due dates to minimize the number of late jobs. In 1978 Kise, Ibaraki and Mine et.al. proposed an algorithm （abbreviated to the KIM algorithm） for the problem and proved that it could get the optimal solution. Recently, using a counter-example, Li Shanlin, Chen Zhilong and Tang Guochun et.al. pointed out that the Lemma 2 was wrong when Kise, Ibaraki and Mine et.al. proved the optimality of the algorithm. Yue Minyi also gave a simple proof to it. In this paper we analyze and point out the error of the Lemma 2 and give a revised Lemma 2＇. Therefore, we should revise the KIM algorithm, also. Fortunately, at last, we prove that the KIM algorithm still gets the optimal solution.