平行机在线(半在线)排序问题近似算法研究

摘要：

主要研究三台平行机三种不同类型的半在线排序问题.通过最优情况分析或数值方法评价其性能.得到第一种第二种情况的最坏性能都不超过预期的5/3,第三种情况依罚值与工件长度的固定比值的不同而有不同的算法,当α小于(√3)/3时将拒绝所有的工件,否则接受所有的工件并按照LS法将工件进行排序.进一步证明其竞争比为α的分段函数.

关键词：半在线排序、平行机、可拒绝、最坏性能比、近似算法

所属期刊栏目：18

分类号：O22(运筹学)

在线出版日期：2006-09-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：202-205