一类资源负荷均衡问题的双最小平衡调度算法

Double Minimum-balance Scheduling Algorithms for a Class of Workload Balance Problems

针对一类n个独立任务在m个不完全同等的处理机上处理 ,使处理机的最大负荷为最小的非抢先调度问题 ,在最小平衡算法的基础上提出了双最小平衡算法 ,并分析了它的时间复杂性。在此基础上 ,提出了基于遗传的双最小平衡算法 。

In view of a class of nonpreemptively scheduling n independent tasks on m non identical multiprocessors to minimize the maximum workload, an algorithm called error minimum(EM) algorithm which is based on the double minimum balance algorithm is put forward and its time complexity is analyzed. Based on this, the genetics based EM algorithm is presented and the examples prove that its results is prior to those of genetics based double minimum balance algorithm.