Deadline-constrained workflow scheduling using imperialist competitive algorithm on infrastructure as a service clouds

摘要

Cloud computing is internet based computing paradigm that opens new opportunities for researchers to investigate its benefits and disadvantages on executing scientific applications such as workflows. Workflow scheduling on distributed systems has been widely studied over the years. Most of the proposed scheduling algorithms attempt to minimize the execution time without considering the cost of accessing resources and mostly target environments similar or equal to community Grids. But, in case of Cloud computing, usually, faster resources are more expensive than the slower one such that execution time as well as cost incurred by using a set of heterogeneous resources over cloud should be minimized. The proposed approach in this paper is based on Imperialist Competitive Algorithm (ICA). The ICA is a new evolutionary algorithm which is inspired by human's socio-political evolution. Generally this algorithm mathematically models the imperialism as a level of human's social evolution and uses this model for optimization Problems. In this paper, we develop a static cost-minimization, deadline-constrained heuristic for scheduling a scientific workflow application in a Cloud environment. Our approach considers fundamental features of IaaS providers such as on-demand resource provisioning and unlimited computing resources. The results show that our approach performs better than the PSO algorithm in terms of cost minimization and percent of meeting deadline.