1.5 算法的经济因素分析

本课题使用有向无环图表征对应的工作流任务，确定任务调度模型中的调度目标和决策变量等，进而设计合理、有效的算法流程实现异构调度算法的各函数功能模块，包括计算向上优先级、优先级排序和分配处理器等。与其他在异构环境下的算法相比，在同等复杂的计算程度上，有效地缩短了最早完成时间，缩短了不同处理器之间的工作间隙，提高了异构系统的整体计算效率。本课题的研究工作为异构环境下多任务调度问题提供了一套行之有效的解决方案，能够有效计算资源的利用率，减少计算成本和能源消耗。

1.6  本文结构安排

本文有四个章节：

第一章，绪论。对目前异构环境下的任务调度问题的研究现状和应用需求进行了介绍和分析，阐述了本课题的任务要点和解决思路，分析了本课题的经济因素和社会影响，说明了本文的主要工作内容和整体文章脉络。

第二章，理论基础。介绍了静态任务调度算法的主要类别。对任务调度问题进行了深入了解，对任务调度时所需的执行成本、通信成本等基础公式进行了阐释，定义了任务调度的目标函数。

第三章，实验核心算法HEFT及具体实现。首先，介绍了HEFT算法设置优先级的图形属性。接着，通过示例图展现了HEFT算法的具体流程。然后，通过一个具体任务流实例证明HEFT算法的可行性和优化性。最后,对HEFT算法的主要思想理念和程序运作给出了全面介绍。

第四章，实验过程。介绍了实验环境、实验配置以及实验所采用的数据。接着，详细描述了随机图生成器的具体参数和详细实现。然后详细介绍了HEFT算法的实验过程和实验结果。

2  相关的理论基础

2.1  静态任务调度算法

静态任务调度算法可以分为两个主要类别，基于启发式算法和有引导的基于随机搜索的算法。前者可以进一步分为三类：列表调度启发式算法，聚类启发式算法和任务复制启发式算法。