期刊论文

The Optimality of the KIM Algorithm

中文

运筹学学报

OPERATIONS RESEARCH TRANSACTIONS

1007-6093

2007

11

4

116-120

10.3969/j.issn.1007-6093.2007.04.016

国家自然科学基金项目(No．10371071,70731160015)； 运筹学与系统工程重庆市市级重点实验室资助项目．；

本校为其他机构

研究工件的就绪时间可以不相同、但是与交货期有"一致性"关系的误工问题.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 ...