基于优先级和优化完成时间的网格调度算法

Scheduling algorithm based on the priority and improved completion-time in grid

网格由大量的异构资源组成,具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源,提高网格处理应用程序的能力。M in-m in算法是一个简单、快速、有效的调度算法,但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析,计算并优化M in-m in算法的任务完成时间,再根据任务需求赋予任务优先级,通过优先级安排任务调度,提高算法负载平衡能力,最后在上述分析基础上提出POTE M in-m in(Priorityand Overlap Transm ission and Execution M in-m in)调度算法。

Grid system consists of a wide variety of geographically distributed resources and these resources are heterogeneous, geographically distributed and dynamically available. High efficient scheduling algorithm would be able to increase throughput, maximize system utilization, and fulfill economical system and user constraints. Min-min algorithm is a simple and fast algorithm, and able to deliver good performance, but with the drawback of limitation of load balance. In this paper the transmission and execution of jobs were analyzed first. Then the completion time of the Min-min algorithm was computed and improved based on the schedule model. Furthermore, in order to improve the load balance of the Min-min algorithm, priority was assigned to the jobs according to different schedule limitations, and jobs were scheduled based on these priorities. Finally the POTE Min-min （Priority and Overlap Transmission and Execution Min-min） algorithm was proposed based on the analysis.