关于排序模型1|·|ri≥0|n∑i=1vi的注记

• 作者: 越民义
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 算法 排序
• 年，卷（期）: 2007,（4）
• 页码范围: 1-4
• 页数: 4页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2007.04.001

摘要

设 J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.1978年Kise,Ibaraki,Mine等在条件ri＜rj蕴涵di≤dj(对于任何1≤i,j≤n)下,对于任何给定的J找到算法A.他们在论文[1]中"证明"算法A是最优算法.最近,李杉林给出一个例子说明他们的证明中的一个关键引理是错误的.本文作者在书[2]中也沿用了这个错误的"证明".对于算法A的最优性,本文给出一个新的简单的证明.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	越民义	中国科学院应用数学研究所	5	25	3.0	5.0