非同起点加工的多机调度合成算法

摘要：

针对调度n个独立任务到初始时刻并非都空闲的m台机器上加工,使得机器最长加工时间(makespan)最短的问题,改进MLPT算法以减少运行时间,改进MULTIFIT算法以减少迭代次数,提出以改进的MLPT算法结果为改进的MULTIFIT算法的初始上界的合成算法--CMM,从理论上对MLPT,MULTIFIT和CMM等算法的时间复杂度和调度结果进行了分析和比较. 实验结果表明:改进的MULTIFIT比MULTIFIT的平均迭代次数少;CMM在平均迭代次数方面甚至比改进的MULTIFIT还少得多且调度结果不次于MULTIFIT和MLPT的优者.

关键词：非同起点多机调度、合成算法、MULTIFIT、同型机

所属期刊栏目：25

分类号：TP301(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划863-511-944-001

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

页数：共6页

页码：817-822