一种独立任务的同型机调度快速算法

被引：4

作者：

李小平

徐晓飞

战德臣

机构：

[1] 哈尔滨工业大学计算机科学与工程系

[2] 哈尔滨工业大学计算机科学与工程系黑龙江哈尔滨

[3] 黑龙江哈尔滨

[4] 黑龙江哈尔滨

来源：

软件学报 | 2002年 / 04期

关键词：

同型机调度; 装箱; LPT算法; MULTIFIT算法; 任务机器比;

D O I：

10.13328/j.cnki.jos.2002.04.049

中图分类号：

TP316 [操作系统];

学科分类号：

摘要：

如何将n个独立任务调度到m台同型机上加工,使总完成时间最短,是一个复杂问题.通过分析Bound Fit预备算法的性质,结合MULTIFIT和Bound Fit提出QUICKFIT算法;对相同机器数和任务数,QUICKFIT能用比MULTIFIT和Bound Fit都少的迭代次数得到相同的总完成时间.实验结果表明,任务机器比越大,QUICKFIT算法的性能就越优于MULTIFIT和Bound Fit.绝大多数情况下,总完成时间等于MULTIFIT和Bound Fit中的最小者.该算法适用于大规模同型机调度.

引用

页码：812 / 817

页数：6