Multiobjective Cloud Workflow Scheduling: A Multiple Populations Ant Colony System Approach

• Published in: IEEE transactions on cybernetics 2019-08, Vol.49 (8), p.2912-2926
• Main Authors: 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
• Format: Article
• Language: English
• Subjects: Algorithms; Archives & records; Cloud computing; Computational modeling; Computer simulation; Elasticity; evolutionary approach; multiobjective optimization; Multiple objective analysis; Objectives; Optimization; Populations; Processor scheduling; Scheduling; Search problems; Task analysis; Workflow; workflow scheduling
• ISSN: 2168-2267; 2168-2275
• DOI: 10.1109/TCYB.2018.2832640

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.