- 相关推荐
关于排序模型1-·-ri≥0-n∑i=1vi的注记
设 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的最优性,本文给出一个新的简单的证明.
作 者: 越民义 Yue Minyi 作者单位: 中国科学院应用数学研究所,北京,100080 刊 名: 运筹学学报 ISTIC PKU 英文刊名: OPERATIONS RESEARCH TRANSACTIONS 年,卷(期): 2007 11(4) 分类号: O22 关键词: 运筹学 算法 排序 Operations research algorithm scheduling【排序模型1-·-ri≥0-n∑i=1vi的注记】相关文章:
CCR模型中决策单元的区间效率值及其排序04-27
关于LCM方程的李-曹猜想的注记04-26
基于禁忌搜索的点状注记研究04-26
关于Shannon采样定理的一点注记04-26
次可加测度压的一个注记04-26
1-羟基-2-(1-甲基咪唑-2-基)乙烷-1,1-双膦酸的合成04-27
模型昆虫翼作非定常i运动时的气动力特性04-27
实习1-厌恶教案!04-25
关于变截面杆自由振动精确解的注记04-26