模糊云资源调度问题的RIOPSO算法

doi:10.3778/j.issn.1673-9418.2006045

摘要/Abstract

摘要：

针对时间-成本约束下的云资源调度问题，使用三角模糊数表示不确定的任务执行时间，建立了模糊云资源调度模型，调度的目标是降低任务总的执行时间和总的成本消耗，决策变量是任务和虚拟机的映射关系。使用混合粒子群优化算法（RIOPSO）对模糊云资源调度进行求解。该算法使用了正交初始化粒子群的方法，提升粒子初始探索最优调度方案的质量，在粒子搜索过程中使用重新随机化控制粒子的搜索范围，使用实时更新惯性权重的方式控制粒子在搜索中的速度，从而得到最优的调度方案。在Cloudsim仿真平台上使用随机生成的仿真数据，对提出的问题模型和优化算法进行验证，证明了模型的可靠性，实验结果表明使用提出的优化算法，可以达到使云资源调度中总执行时间和总执行成本降低的目的，并且在收敛速度、求解能力方面具有良好的性能。

关键词: 云资源调度, 粒子群算法（PSO）, 正交初始化, 重新随机化, 更新惯性权重

Abstract:

To solve the cloud resource scheduling problem under time-cost constraints, a triangular fuzzy number is used to represent the uncertain task execution time, and a fuzzy cloud resource scheduling model is established. The objective function of scheduling model is to reduce the total execution time and total cost consumption of the task, and the decision variables are the mapping relationship between tasks and virtual machines. The re-randomization inertia weight orthogonal initialization particle swarm optimization algorithm (RIOPSO) is proposed to solve the fuzzy cloud resource scheduling. This algorithm uses the method of orthogonal initialization particle swarm optimiza-tion to improve the quality of the initial exploration of the optimal scheduling scheme. In the process of particle search, re-randomization is used to control the search range of particles, and real-time updating of inertia weight is used to control the speed of particles, and to obtain the optimal scheduling scheme. The randomly generated simula-tion data on the Cloudsim simulation platform are used to verify the problem model and optimization algorithm proposed in this paper, which proves the reliability of the model. The experimental results show that RIOPSO algorithm can reduce the total execution time and cost in cloud resource scheduling, and it has good performance in convergence speed and solving ability.

Key words: cloud resource scheduling, particle swarm optimization (PSO), orthogonal initialization, re-randomization, update inertia weight

李成严, 宋月, 马金涛. 模糊云资源调度问题的RIOPSO算法[J]. 计算机科学与探索, 2021, 15(8): 1534-1545.

LI Chengyan, SONG Yue, MA Jintao. RIOPSO Algorithm for Fuzzy Cloud Resource Scheduling Problem[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(8): 1534-1545.

参考文献

[1] ABDULLAHI M, NGADI M A, ABDULHAMID S M. Sym-biotic organism search optimization based task scheduling in cloud computing environment[J]. Future Generation Com-puter Systems-The International Journal of Escience, 2016, 56: 640-650.
[2] ZHANG Y, SUN J. Novel efficient particle swarm optimiza-tion algorithms for solving QoS-demanded bag-of-tasks scheduling problems with profit maximization on hybrid clouds[J]. Concurrency and Computation-Practice & Expe-rience, 2017, 29(21): e4249.
[3] JUAREZ F, EJARQUE J, BADIA R M. Dynamic energy-aware scheduling for parallel task-based application in cloud computing[J]. Future Generation Computer Systems, 2016, 78: 257-271.
[4] EPHZIBAH E P. Time complexity analysis of genetic-fuzzy system for disease diagnosis[J]. Advanced Computing: An International Journal, 2011, 2(4): 23-31.
[5] VENKATESA K V, DINESH K. Job scheduling using fuzzy neural network algorithm in cloud environment[J]. Bonfring International Journal of Man Machine Interface, 2012, 2(1): 1-6.
[6] LI C Y, CAO K H, FENG S X, et al. Resource scheduling with uncertain execution time in cloud computing[J]. Journal of Harbin University of Science and Technology, 2019, 24(1): 85-91.
李成严, 曹克翰, 冯世祥, 等. 不确定执行时间的云计算资源调度[J]. 哈尔滨理工大学学报, 2019, 24(1): 85-91.
[7] MA Y, WANG Y. Grid task scheduling based on chaotic ant colony optimization algorithm[C]//Proceedings of the 2012 International Conference on Computer Science and Network Technology, Changchun, Dec 29-31, 2012. Piscataway: IEEE, 2013: 469-472.
[8] HASSAN M A, KACEM I, MARTIN S, et al. Genetic algo-rithms for job scheduling in cloud computing[J]. Studies in Informatics & Control, 2015, 24(4): 387-399.
[9] SADHASIVAM N, THANGARAJ P. Design of an improved PSO algorithm for workflow scheduling in cloud computing environment[J]. Intelligent Automation & Soft Computing, 2016, 31(8): 493-500.
[10] HU X X, ZHOU X W. Improved ant colony algorithm on scheduling optimization of cloud computing resources[J]. Applied Mechanics & Materials, 2014, 678: 75-78.
[11] LEUNG Y W, WANG Y. An orthogonal genetic algorithm with quantization for global numerical optimization[J]. IEEE Transactions on Evolutionary Computation, 2001, 5(1): 41-53.
[12] JIANG Z Y, CAI Z X, WANG Y. Hybrid self-adaptive orthogonal genetic algorithm for solving global optimization problems[J]. Journal of Software, 2010, 21(6): 1296-1307.
江中央, 蔡自兴, 王勇. 求解全局优化问题的混合自适应正交遗传算法[J]. 软件学报, 2010, 21(6): 1296-1307.
[13] MAO H Y, WANG W D. Particle swarm optimization based on adaptive inertia weight model with membership function[J]. Computer Applications and Software, 2020, 37(1): 277-283.
毛焕宇, 王文东. 融合隶属度函数的自适应惯性权重模式的粒子群优化算法[J]. 计算机应用与软件, 2020, 37(1): 277-283.
[14] RAQUEL C, YAO X. Dynamic multi-objective optimization: a survey of the state-of-the-art[J]. Evolutionary Computation for Dynamic Optimization Problems, 2013, 490: 85-106.
[15] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength pareto evolutionary algorithm for multiobjective optimization: TIK-Report 103[R]. Zurich: Swiss Federal In-stitute of Technology, 2002.
[16] PURSHOUSE R C, FLEMING P J. Evolutionary many-objective optimization: an exploratory analysis[C]//Procee-dings of the 2003 IEEE Evolutionary Computation, Can-berra, Dec 8-12, 2003. Piscataway: IEEE, 2003: 2066-2073.
[17] ZITZLER E, KUNZLI S. Indicator-based selection in evolu-tionary multiobjective optimization algorithm based on the desirability index[J]. Journal of Multi-Criteria Decision Ana-lysis, 2013, 20(5/6): 319-337.
[18] BADER J, ZITZLER E. HypE: an algorithm for fast hyper-volume-based many-objective optimization[J]. IEEE Transac-tions on Evolutionary Computation, 2011, 19(1): 45-76.
[19] LI K, FIALHO A, KWONG S, et al. Adaptive operator selec-tion with bandits for a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolu-tionary Computation, 2014, 18(1): 114-130.
[20] ZHANG Q F, LI H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[21] ZHENG J H, SHI Z Z, XIE Y. A fast multi-objective genetic algorithm based on clustering[J]. Journal of Computer Re-search and Development, 2004, 41(7): 44-50.
郑金华, 史忠植, 谢勇. 基于聚类的快速多目标遗传算法[J]. 计算机研究与发展, 2004, 41(7): 44-50.
[22] SAHMOUD S, TOPCUOGLU H R. Sensor-based change detection schemes for dynamic multi-objective optimization problems[C]//Proceedings of the 2016 IEEE Symposium Series on Computational Intelligence. Piscataway: IEEE, 2016: 1-8.
[23] MIRIAM A J, SAMINATHAN R, CHAKARAVARTHI S. Non-dominated sorting genetic algorithm (NSGA-III) for effective resource allocation in cloud[J]. Evolutionary Intelli-gence, 2021, 14: 759-765.
[24] LI H, ZHANG Q F. MOEA/D: a multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[25] SIERRA M R, COELLO C C A. Improving PSO-based multi-objective optimization using crowding, mutation and ∈-dominance[C]//Proceedings of the 2005 International Con-ference on Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg: Springer, 2005: 505-519.
[26] SCHüTZE O, HERNáNDEZ V A S, TRAUTMANN H, et al. The hypervolume based directed search method for multi-objective optimization problems[J]. Journal of Heuristics, 2016, 22(3): 1-28.
[27] LIU R C, LI J X, LIU J, et al. A survey on dynamic multi-objective optimization[J]. Chinese Journal of Computers, 2020, 43(7): 1246-1278.
刘若辰, 李建霞, 刘静, 等. 动态多目标优化研究综述[J]. 计算机学报, 2020, 43(7): 1246-1278.
[28] YANG X L, QIAN C, ZHU F X. Evaluation method of big data service resources based on cloud computing[J]. Com-puter Science, 2018, 45(5): 295-299.
阳小兰, 钱程, 朱福喜. 基于云计算的大数据服务资源评价方法[J]. 计算机科学, 2018, 45(5): 295-299.
[29] BALIN S. Non-identical parallel machine scheduling with fuzzy processing times using genetic algorithm and simula-tion[J]. International Journal of Advanced Manufacturing Technology, 2012, 61(9-12): 1115-1127.
[30] CALHEIROS R N, RANJAN R, BELOGLAZOV A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provi-sioning algorithms[J]. Software Practice & Experience, 2010, 41(1): 23-50.
[31] AL-SHAIKHI A A, KHAN A H, AL-AWAMI A T, et al. A hybrid particle swarm optimization technique for adaptive equalization[J]. Arabian Journal for Science and Engineering, 2019(3): 2177-2184.
[32] KRUSIENSKI D J, JENKINS W K. A modified particle swarm optimization algorithm for adaptive filtering[C]//Proceedings of the 2006 IEEE International Symposium on Circuits & Systems, Island of Kos, May 21-24, 2006. Pis-cataway: IEEE, 2006: 137-140.
[33] QIN Q D, CHENG S, ZHANG Q Y, et al. Multiple stra-tegies based orthogonal design particle swarm optimizer for numerical optimization[J]. Computers & Operations Research, 2015, 60: 91-110.