Chen Zong-Gan, Zhan Zhi-Hui, Lin Ying, Gong Yue-Jiao, Gu Tian-Long, Zhao Feng, Yuan Hua-Qiang, Chen Xiaofeng, Li Qing, Zhang Jun
IEEE Trans Cybern. 2019 Aug;49(8):2912-2926. doi: 10.1109/TCYB.2018.2832640. Epub 2018 May 18.
Cloud workflow scheduling is significantly challenging due to not only the large scale of workflow but also the elasticity and heterogeneity of cloud resources. Moreover, the pricing model of clouds makes the execution time and execution cost two critical issues in the scheduling. This paper models the cloud workflow scheduling as a multiobjective optimization problem that optimizes both execution time and execution cost. A novel multiobjective ant colony system based on a co-evolutionary multiple populations for multiple objectives framework is proposed, which adopts two colonies to deal with these two objectives, respectively. Moreover, the proposed approach incorporates with the following three novel designs to efficiently deal with the multiobjective challenges: 1) a new pheromone update rule based on a set of nondominated solutions from a global archive to guide each colony to search its optimization objective sufficiently; 2) a complementary heuristic strategy to avoid a colony only focusing on its corresponding single optimization objective, cooperating with the pheromone update rule to balance the search of both objectives; and 3) an elite study strategy to improve the solution quality of the global archive to help further approach the global Pareto front. Experimental simulations are conducted on five types of real-world scientific workflows and consider the properties of Amazon EC2 cloud platform. The experimental results show that the proposed algorithm performs better than both some state-of-the-art multiobjective optimization approaches and the constrained optimization approaches.
由于工作流规模庞大，以及云资源的弹性和异构性，云工作流调度面临着巨大的挑战。此外，云的定价模型使得执行时间和执行成本成为调度中的两个关键问题。本文将云工作流调度建模为一个多目标优化问题，同时优化执行时间和执行成本。提出了一种基于多目标框架的协同进化多个种群的新型多目标蚁群系统，该系统采用两个蚁群分别处理这两个目标。此外，所提出的方法还结合了以下三种新颖的设计，以有效应对多目标挑战：1）一种基于全局存档中的一组非支配解的新的信息素更新规则，以指导每个蚁群充分搜索其优化目标；2）一种互补启发式策略，以避免蚁群只专注于其相应的单一优化目标，与信息素更新规则协作以平衡两个目标的搜索；3）一种精英学习策略，以提高全局存档的解质量，帮助进一步逼近全局帕累托前沿。在五种类型的实际科学工作流上进行了实验模拟，并考虑了亚马逊EC2云平台的特性。实验结果表明，所提出的算法比一些现有的多目标优化方法和约束优化方法表现更好。
