随着互联网技术的发展，云用户的规模在不断地增加，大量的任务集中在云端导致任务等待时间过长和云计算系统性能下降，而造成该现象的主要原因是任务调度的不合理，因此对任务调度算法的研究具有重要意义。

蚁群优化算法（Ant Colony Optimization，ACO）在寻找最优路径方面具有良好的表现，常被用于解决云环境下的任务调度问题，但在求解的过程中存在容易陷入局部极值和收敛速度较慢的问题。针对以上问题，本文（1）对传统蚁群算法的启发函数和信息素浓度进行改进，解决算法容易陷入局部极值的问题。首先在启发函数中引入负载均衡因子，对任务分配过于集中在计算能力较强资源的分配概率进行调整；其次引入信息素修正系数，来及时更新资源上累积的信息素浓度，更好地实现蚁群的正反馈机制；（2）设计一种混合蚁群算法（QACO），解决算法初期收敛速度较慢的问题。首先对任务进行优先级的设置，其次通过引入Q-learning算法，对蚁群的初始信息素进行改进，用来增强信息素浓度对蚂蚁选择资源的指导作用，最后结合改进的蚁群算法来实现云环境下的任务调度。

通过使用云仿真平台CloudSim模拟工作流任务的调度，分别对QACO算法、ACO算法、基于资源状态的自适应蚁群优化算法（MACO）以及经典仿生算法粒子群优化（PSO）算法进行实验对比。实验结果表明，在对Montage工作流任务实现大规模任务调度时，在任务执行时间方面，QACO算法较ACO算法、MACO算法和PSO算法分别提高了14.98%、4.90%和17.26%；在资源利用率方面，QACO算法的资源利用率最佳；QACO算法求解目标函数值的精度较ACO算法、MACO算法和PSO算法分别提高了24.36%、12.48%和18.68%，同时算法的收敛速度也显著增加。为验证QACO算法的有效性，分别对工作流任务LIGO和CyberShake进行调度，调度结果同样优于其他三种算法。

With the development of Internet technology, the scale of cloud users is constantly increasing. A large number of tasks are concentrated in the cloud, which leads to a long waiting time for tasks and a decline in the performance of cloud computing system. The main reason for this phenomenon is the unreasonable task scheduling, so it is of great significance to study the task scheduling algorithm.

Ant Colony Optimization (ACO) algorithm has a good performance in finding the optimal path, and is often used to solve the task scheduling problem in cloud environment. However, it is easy to fall into local extreme value and slow convergence speed in the process of solving. In view of the above problems, this paper (1) improves the heuristic function and pheromone concentration of traditional ant colony algorithm to solve the problem that the algorithm is easy to fall into local extremum. Firstly, a load balancing factor is introduced into the heuristic function to adjust the assignment probability of resources with strong computing power. Secondly, pheromone correction coefficient is introduced to update the accumulation of pheromone concentration in resources in time, and the positive feedback mechanism of ant colony was better realized. (2) Design a hybrid ant colony algorithm (QACO) to solve the problem of slow convergence in the initial stage of the algorithm. Firstly, the task priority was set. Secondly, the initial pheromone of ant colony is improved by introducing q-learning algorithm to enhance the guiding effect of pheromone concentration on ant resource selection. Finally, the improved ant colony algorithm is combined to realize the task scheduling in cloud environment.

By using cloud simulation platform CloudSim to simulate workflow task scheduling, the QACO algorithm, ACO algorithm, resource state-based adaptive ant colony optimization (MACO) algorithm and the classical bionic algorithm particle swarm optimization (PSO) algorithm are compared. Experimental results show that the QACO algorithm improves the execution time of Montage tasks by 14.98%, 4.90% and 17.26% compared with ACO algorithm, MACO algorithm and PSO algorithm, respectively. In terms of resource utilization, QACO algorithm has the best resource utilization. Compared with ACO algorithm, MACO algorithm and PSO algorithm, the accuracy of QACO algorithm to solve the objective function value is improved by 24.36%, 12.48% and 18.68%, respectively, and the convergence speed of the algorithm is also significantly increased. In order to verify the effectiveness of QACO algorithm, the scheduling results of workflow tasks LIGO and CyberShake are also better than the other three algorithms.

[1]Xu J, Zhang Z, Hu Z, et al. A many-objective optimized task allocation scheduling model in cloud computing[J]. Applied Intelligence, 2021, 51(6): 3293-3310.

[2]夏靖波, 韦泽鲲, 付凯, 等. 云计算中Hadoop技术研究与应用综述[J]. 计算机科学, 2016, 43(11): 6-11.

[3]田倬璟, 黄震春, 张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11.

[4]Kumar M, Sharma S C, Goel A, et al. A comprehensive survey for scheduling techniques in cloud computing[J]. Journal of Network and Computer Applications, 2019, 143: 1-33.

[5]马小晋, 饶国宾, 许华虎. 云计算中任务调度研究的调查[J]. 计算机科学, 2019, 46 (3): 1-8.

[6]Elaziz M A , Attiya I . An improved Henry gas solubility optimization algorithm for task scheduling in cloud computing[J]. Artificial Intelligence Review, 2020:1-39.

[7]Abd Elaziz M, Xiong S, Jayasena K P N, et al. Task scheduling in cloud computing based on hybrid moth search algorithm and differential evolution[J]. Knowledge-Based Systems, 2019, 169: 39-52.

[8]付学良, 孙扬, 王海芳, 等. 改进遗传算法在云任务调度中的应用研究[J]. 内蒙古农业大学学报(自然科学版), 2020, 41(4): 64-69.

[9]王俊英, 颜芬芬, 陈鹏, 等. 基于概率自适应蚁群算法的云任务调度方法[J]. 郑州大学学报(工学版), 2017, 38(4): 51-56.

[10]李佳, 夏云霓. 云计算资源调度问题求解的布谷鸟搜索算法[J]. 控制工程, 2019, 26(1): 170-174.

[11]Padmavathi M, Basha S M. Dynamic and elasticity ACO load balancing algorithm for cloud computing[C]//2017 International Conference on Intelligent Computing and Control Systems. ICICCS 2017. Madurai, India: Institute of Electrical and Electronics Engineers Inc, 2017: 77-81.

[12]Fang Y, Li X. Task scheduling strategy for cloud computing based on the improvement of ant colony algorithm[C]//2017 International Conference on Computer Technology. Electronics and Communication. ICCTEC 2017. Dalian, China: Institute of Electrical and Electronics Engineers Inc, 2017: 571-574.

[13]魏勇, 赵开新, 张松青, 等. 基于改进蚁群算法的云计算任务调度研究[J]. 火力与指挥控制, 2017, 42(5): 130-133.

[14]聂清彬, 潘峰, 吴嘉诚, 等. 基于改进蚁群算法的自适应云资源调度模型研究[J]. 激光与光电子学进展, 2020, 57(1): 90-96.

[15]Gupta A, Garg R. Load balancing based task scheduling with ACO in cloud computing[C]//2017 International Conference on Computer and Applications. ICCA 2017. Doha, United arab emirates: Institute of Electrical and Electronics Engineers Inc. 2017: 174-179

[16]Elsedimy E, Algarni F. MOTS‐ACO: An improved ant colony optimiser for multi‐objective task scheduling optimisation problem in cloud data centres[J]. IET Networks, 2022, 11(2): 43-57.

[17]Agarwal M, Srivastava G M S. A PSO algorithm based task scheduling in cloud computing[J]. International Journal of Applied Metaheuristic Computing (IJAMC), 2019, 10(4): 1-17.

[18]Loheswaran K. An upgraded fruit fly optimisation algorithm for solving task scheduling and resource management problem in cloud infrastructure[J]. IET Networks, 2021, 10(1): 24-33.

[19]钟志峰, 张田田, 张, 等. 基于云环境的高效任务调度算法[J]. 计算机科学, 2018, 45(7): 90-94.

[20]Zhou Z, Li F, Zhu H, et al. An improved genetic algorithm using greedy strategy toward task scheduling optimization in cloud environments[J]. Neural Computing and Applications, 2020, 32(6): 1531-1541.

[21]Shafahi Z, Yari A. An efficient task scheduling in cloud computing based on ACO algorithm[C]//12th International Conference on Information and Knowledge Technology. IKT 2021. Babol, Iran: Institute of Electrical and Electronics Engineers Inc. 2021:72-77.

[22]Bindu G B, Ramani K, Bindu C S. Optimized resource scheduling using the meta heuristic algorithm in cloud computing[J]. IAENG International Journal of Computer Science, 2020, 47(3): 360-366.

[23]Chen X, Long D. Task scheduling of cloud computing using integrated particle swarm algorithm and ant colony algorithm[J]. Cluster Computing, 2019, 22(2): 2761-2769.

[24]Senthil Kumar A M, Venkatesan M. Multi-objective task scheduling using hybrid genetic-ant colony optimization algorithm in cloud environment[J]. Wireless Personal Communications, 2019, 107(4): 1835-1848.

[25]Rajakumari K, Kumar M V, Verma G, et al. Fuzzy based ant colony optimization scheduling in cloud computing[J]. Computer Systems Science and Engineering, 2022, 40(2): 581-592.

[26]Jethava A N, Desai M R. Optimizing multi objective based dynamic workflow using aco and black hole algorithm in cloud computing[C]//3rd International Conference on Computing Methodologies and Communication. ICCMC 2019. Erode, India: Institute of Electrical and Electronics Engineers Inc. 2019: 1144-1147.

[27]Tang L, Zhang X, Li Z, et al. A New Hybrid Task Scheduling Algorithm Designed Based on ACO and GA[J]. J. Inf. Hiding Multim. Signal Process., 2018, 9(6): 1585-1594.

[28]Rugwiro U, Gu C, Ding W. Task scheduling and resource allocation based on ant-colony optimization and deep reinforcement learning[J]. Journal of Internet Technology, 2019, 20(5): 1463-1475.

[29]Dong T, Xue F, Xiao C, et al. Workflow scheduling based on deep reinforcement learning in the cloud environment[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12(12): 10823-10835.

[30]Hajoui Y, Bouattane O, Youssfi M, et al. Q-learning and ACO hybridisation for real-time scheduling on heterogeneous distributed architectures[J]. International Journal of Computational Science and Engineering, 2019, 20(2): 225-239.

[31]Li N, Gao B, Xie Z, et al. Q-learning Based Intelligent Ant Colony Scheduling Algorithm in Heterogeneous System[C]//4th IEEE International Conference on Electronics Technology. ICET 2021. Chengdu, China: Institute of Electrical and Electronics Engineers Inc. 2021: 1020-1025.

[32]Nalini J, Khilar P M. Reinforced Ant Colony Optimization for Fault Tolerant Task Allocation in Cloud Environments[J]. Wireless Personal Communications, 2021, 121(4): 2441-2459.

[33]Peng Z, Cui D, Zuo J, et al. Random task scheduling scheme based on reinforcement learning in cloud computing[J]. Cluster computing, 2015, 18(4): 1595-1607.

[34]Wu Q, Wu Z, Zhuang Y, et al. Adaptive DAG tasks scheduling with deep reinforcement learning[C]//International Conference on Algorithms and Architectures for Parallel Processing. Cham : Springer International Publishing. 2018: 477-490.

[35]Islam M T, Karunasekera S, Buyya R. Performance and Cost-Efficient Spark Job Scheduling Based on Deep Reinforcement Learning in Cloud Computing Environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 33(7): 1695-1710.

[36]Swarup S , Shakshuki E M , Yasar A . Task Scheduling in Cloud Using Deep Reinforcement Learning[J]. Procedia Computer Science, 2021, 184(2): 42-51.

[37]Rjoub G, Bentahar J, Abdel Wahab O, et al. Deep and reinforcement learning for automated task scheduling in large‐scale cloud computing systems[J]. Concurrency and Computation: Practice and Experience, 2021, 33(23): 5913-5919.

[38]刘鹏. 云计算[M]. 北京: 电子工业出版社, 2015: 16.

[39]Prem Jacob T, Pradeep K. A multi-objective optimal task scheduling in cloud environment using cuckoo particle swarm optimization[J]. Wireless Personal Communications, 2019, 109(1): 315-331.

[40]肖明清, 杨召, 薛辉辉, 等. 云计算及其在测试领域的应用探索[J]. 空军工程大学学报(自然科学版), 2015, 16(1): 50-55.

[41]张秋霞, 何留杰, 张来顺. 基于联盟博弈的云任务调度及Shapley值法的收益分配模型[J]. 计算机应用与软件, 2020, 37(5): 275-280.

[42]甘娜, 黄裕锋, 陆晓梅. 云计算中基于M/Geom/C/∞排队系统的任务调度模型研究[J]. 计算机测量与控制, 2018, 26(3): 176-179.

[43]孙长亚, 王向文. 基于MGA-PSO的云计算多目标任务调度[J]. 计算机应用与软件, 2021, 38(6): 212-218.

[44]张扬, 马飞. 云环境中一种多阶段式工作流任务调度算法[J]. 计算机应用与软件, 2020, 37(11): 178-184.

[45]Loheswaran K. An upgraded fruit fly optimisation algorithm for solving task scheduling and resource management problem in cloud infrastructure[J]. IET Networks, 2021, 10(1): 24-33.

[46]林诗洁, 董晨, 陈明志, 等. 新型群智能优化算法综述[J]. 计算机工程与应用, 2018, 54(12): 1-9.

[47]郑娟毅, 程秀琦, 付姣姣. 改进蚁群算法在TSP中的应用研究[J]. 计算机仿真, 2021, 38(5): 126-130

[48]张硕航, 郭改枝, 张朋. K-Means聚类下的改进蚁群算法优化TSP问题[J]. 内蒙古大学学报(自然科学版), 2021, 52(6): 609-616.

[49]姚晓通, 李致远, 程晓. 基于改进蚁群算法的机器人路径规划研究[J]. 计算机仿真, 2021, 38(11): 379-383.

[50]张子然, 黄卫华, 陈阳, 等. 基于双向搜索的改进蚁群路径规划算法[J]. 计算机工程与应用, 2021, 57(21): 270-277.

[51]刘辉, 代学武, 崔东亮, 等. 基于参数自适应蚁群算法的高速列车行车调度优化[J].控制与决策, 2021, 36(7): 1581-1591.

[52]张晓莉, 杨亚新, 谢永成. 改进的蚁群算法在机器人路径规划上的应用[J]. 计算机工程与应用, 2020, 56(2): 29-34.

[53]李成严, 孙巍, 唐立民. 一种权重自适应的强化学习云资源调度算法[J]. 哈尔滨理工大学学报, 2021, 26(2): 17-25.

[54]龙浩, 张书奎, 张力. 基于马尔科夫决策过程的高能效任务调度算法[J]. 计算机应用与软件, 2020, 37(1): 242-246.

[55]姜力争, 裴云曼, 赵建涛. 基于蚁群优化算法的云任务分配策略研究[J]. 计算机应用与软件, 2021, 38(6): 284-287.

[56]薛凡. DAG分割模型下的云工作流调度策略[J]. 计算机应用研究, 2019, 36(12): 3725-3728.

[57]Jiahao W, Zhiping P, Delong C, et al. A multi-object optimization cloud workflow scheduling algorithm based on reinforcement learning[C]//14th International Conference on Intelligent Computing. ICIC 2018. Wuhan, China: Springer Verlag. 2018: 550-559.

[58]王丽娟, 吴锋. 基于CSA和PSO的多目标优化任务调度算法[J]. 西南师范大学学报(自然科学版), 2021, 46(3): 27-32.