¹Nanjing University of Information Science & Technology, School of Computer and Software, Nanjing, China
²Nanjing University of Information Science & Technology, Jiangsu Engineering Center of Network Monitoring, Nanjing, China

---

Abstract—Partly dependent tasks (PDTs) scheduling with multi-objective optimization in cloud computing is an NP-hard problem. Taking the quality of service (QoS) requirements of users that use cloud computing into account, we set the cost and time requirements of handling the PDTs as the multiple objectives and present an improved algorithm based on the non-dominated sorting genetic algorithm-II (NSGA-II) to find the Pareto optimal set of the PDTs scheduling. In this paper, the similar task order crossover (STOX) operator is applied to make the evolution more efficient while the shift mutation operator is applied in the process of evolution to avoid the premature convergence. In addition, we present a new method named self-adapting crowding distance (SCD) operator, which can improve the diversity of individuals in the Pareto-optimal front. The simulation results and analysis show that the proposed algorithm performs better than NSGA-II in maintaining the diversity and the distribution of the Pareto-optimal solutions in the cloud PDTs scheduling.

Index Terms—PDTs, multi-objective optimization, cloud computing, STOX, SCD, improved NSGA-II

[PDF]

Cite: Shengjun Xue, Fei Liu, Xiaolong Xu, "An Improved Algorithm Based on NSGA-II for Cloud PDTs Scheduling," Journal of Software vol. 9, no. 2, pp. 443-450, 2014.