Dev_Min-Min:一种基于最小偏差的网格调度算法

Dev_Min-Min: a grid scheduling algorithm based on minimal deviation

针对独立任务调度的负载均衡和高吞吐率原则,提出基于Min-Min算法的最小完成时间偏差调度算法(Dev_Min-Min),算法构造了调度完成时间的偏差矩阵,根据任务的偏差调度任务.Dev_Min-Min算法克服了Min-Min算法追求局部最优的贪心算法思想的局限性.实验数据表明,与被作为评测基准的Min-Min算法相比,Dev_Min-Min算法能在各种网格环境中有效降低调度跨度、提高负载均衡度,在异构环境中调度性能提高更加明显.

Aiming at the independent job scheduling of loading balance and high throughput in heterogeneous computing environment, a new algorithm named Deviation Min-Min （Dev_Min- Min） based on Min-Min algorithm is presented, in which the deviation matrix of the job execution time is constructed and the job is scheduled according to the deviation. Dev_Min-Min overcomes the defect that Min-Min pursues the local optimization based on the thinking of greedy algorithm. The experimental data show that Dev_Min-Min in various grid environments reduces the scheduling span, and improves the loading balance effectively. The scheduling performance is more obvious in heterogeneous computing environment.