机器带准备时间的平行机排序问题的并行阈值算法

摘要：

针对带准备时间的最小机器完工时间最大化排序问题,结合原始阈值算法、对偶阈值算法并加以修正,提出并行层次阈值算法,证明了三台机器情况下当参数ε＝1/4时,此线性时间算法的最坏情况界为3/4.这是到目前为止最坏情况界最小且时间复杂性为线性时间的算法.进一步通过计算实验,表明并行阈值算法对于3台至50台机器、5至50 000个工件数量的规模下,具备很高效率.

关键词：排序、阈值算法、最坏情况界、机器准备时间、线性时间

所属期刊栏目：8

分类号：O223(运筹学)

资助基金：上海市高校优秀青年教师后备人选科研项目LX306002;上海市教委研创新基金08ZY78;07ZZ178;国家自然科学基金70731160015;10371071

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

页数：共6页

页码：1649-1654