公有云环境向用户提供了大量可租用的资源,例如不同性能的虚拟机、不同带宽的网络和不同的存储容量。科学工作流是由一系列计算任务组成,来完成一些科学计算目标的任务集合。科学工作流已经被广泛应用在天文学、物理学、地球科学、神经科学等领域。公有云环境下工作流调度问题是研究如何将工作流中的任务合理分配到租用的虚拟机上。这个问题通常被建模成一个优化问题。现在已经提出了许多单目标或多目标优化算法来解决工作流调度问题。但是根据我们对现有研究的总结,优化目标之间的冲突度还没有被研究。在本文中,我们使用皮尔森相关系数来对优化目标之间的冲突度进行度量。然后提出了一个基于非支配排序遗传算法(NSGAII)和正交实验设计方法(OD)的多目标优化算法ONSGAII来解决工作流调度问题。基于上述背景和问题,首先,本文对从2007年云计算概念提出至今所有有关公有云计算环境下科学工作流调度的文章进行了综述,并总结出六个优化目标,分别为执行时间、总花费、虚拟机数量、资源利用率、计算花费、数据传输花费。文中列出了部分文章,其中9篇单目标优化文章,10篇多目标优化文章。之后,本文对科学工作流调度问题进行数学建模。具体来说,分别对工作流、云计算环境和六个优化目标进行了建模。在对六个优化目标建模前,本文介绍了云资源共享的概念,并举例说明了资源共享的规则。对于六个优化目标,本文给出了各自的计算公式和部分计算伪代码。其次,本文在解空间上通过计算皮尔森相关系数分析了六个优化目标之间的冲突度。分析过程中使用正交实验设计方法降低了解空间的规模。我们将结果用灰度图进行表示,图中颜色越深表明两个优化目标之间冲突度越大,反之,冲突度越小。我们在11个现实科学工作流上进行了分析,结果表明执行时间和总花费之间冲突度最大。最后,本文提出了一个解决公有云环境下科学工作流调度问题的算法ONSGAII。在选择优化目标时,考虑到执行时间和总花费之间冲突度最大,并且现有研究主要优化这两个目标,我们选择执行时间和总花费作为优化目标。本算法基于传统的NSGAII算法和正交实验设计方法,在NSGAII算法基础上改进了初始化种群过程和交叉算子。在初始化过程中,为了避免解的分布太集中,我们使用正交实验设计的方法构造初始种群,使得初始种群能够具有均匀广泛的分布性。在改进交叉算子时,我们提出了一个基于距离的模拟二进制交叉算子。为了验证算法的性能,我们将ONSGAII算法与三个启发式算法(NSGAII、GA、PSO)、两个构造型算法(HEFT、Min-min)进行比较。首先我们分析了四个启发式算法的收敛性,结果表明本算法能快速产生最优解集。其次,我们分析了六个算法的最优解分布,结果表明本算法产生的最优解集优于其他五个算法。11个现实科学工作流上的实验结果都表明了本算法能够快速产生出较优的最优解集。
