Renumber strategy enhanced particle swarm optimization for cloud computing resource scheduling

摘要

Cloud computing offers unprecedented capacity to execute large-scale workflows in the “era of big data”. In 2014, a cost-minimization and deadline-constrained workflow scheduling (CMDCWS) model is firstly proposed by Rodriguez and Buyya, which is applicable for the business need of cloud computing that a workflow task should be finished by minimizing the execute cost within a deadline constraint. As scheduling cloud computing resources for workflow is an NP-hard problem, Rodriguez and Buyya proposed to use particle swarm optimization (PSO) to solve the CMDCWS problem. In traditional PSO for CMDCWS, each dimension in the particle position stands for each task and the value of the corresponding dimension stands for the index of the cloud resource that executes this task. However, this may have drawback because the value of each dimension does not relate to the resource characteristic but is only a meaningless index number. Therefore the learning behaviors among the particles do not make sense because learning from index number may not lead to better position. In this paper, we present a resource renumber strategy to encode the particle position and design a renumber PSO (RNPSO) for CMDCWS. In RNPSO, all the resources are re-ordered and re-numbered according to their computational ability, i.e., the cost per unit time. By this, the values of particle position can make sense and the positions difference between the well-performed and poorly-performed particles can guide poorly-performed particle to promising region. We conduct experiments on test cases with small, middle, and large scales to compare the performance of PSO and RNPSO. The results show that the resource renumber strategy is promising for enhancing the PSO performance.