关键词: 异构计算系统, 综合性启发式算法, 关键路径, 任务复制

Abstract: The list-scheduling algorithm driven by priority chooses tasks to schedule only by one attribute. But in the case of that different tasks should have the same priority, it can not work well. Therefore, a new synthesized heuristic algorithm called HCPFS was proposed. There were three levels of priority in the algorithm to choose task. First, the tasks in critical path have the highest priority. Secondly, the tasks with longer path to exit task should be selected, and then the tasks with more successors were chosen to schedule. The algorithm took duplication method and insertion method in the process of scheduling task. The experimental results in randomly generated graphs and sets of task graphs show that HCPFS performs well compared with HEFT and HCNF in heterogeneous environment.

Key words: heterogeneous computing system, synthesized heuristic algorithm, critical path, task duplication