基于正交自适应鲸鱼优化的云计算任务调度

张金泉，徐寿伟，李信诚，王重洋，徐景芝

（1.山东科技大学 计算机科学与工程学院， 山东 青岛 266590； 2.山东科技大学 科技产业管理处， 山东 青岛 266590）（∗通信作者电子邮箱skd306@163.com）

基于正交自适应鲸鱼优化的云计算任务调度

张金泉1，徐寿伟1，李信诚1，王重洋1，徐景芝2*

（1.山东科技大学 计算机科学与工程学院， 山东 青岛 266590； 2.山东科技大学 科技产业管理处， 山东 青岛 266590）（∗通信作者电子邮箱skd306@163.com）

针对任务调度中存在的任务完成时间长、系统执行任务成本高且系统负载不均衡等问题，提出了一种基于正交自适应鲸鱼优化算法（OAWOA）的云计算任务调度方法。首先，将正交试验设计（OED）应用于种群初始化和全局搜索阶段，以提升和维持种群的多样性，避免算法过早陷入局部收敛状态；然后，利用自适应指数递减因子和双向搜索机制，来进一步加强算法的全局搜索能力；最后，对适应度函数进行优化，从而使算法实现多目标优化。通过仿真实验将所提的算法与鲸鱼优化算法（WOA）、粒子群优化（PSO）算法、蝙蝠算法（BA）以及其他两种改进的WOA进行比较。实验结果表明，在任务规模为50和500时所提算法都取得了更好的收敛效果，并且得到的系统执行任务的总时间和总成本均低于其他几种算法，同时负载均衡度仅低于BA。可见，所提算法在降低系统执行任务的总时间和总成本以及提高系统负载均衡方面均表现出了显著的优势。

云计算；任务调度；鲸鱼优化算法；正交试验设计；多目标优化

0 引言

云计算是互联网技术、计算机技术以及分布式技术等多种技术相互融合和发展产生的一种新兴技术。云计算凭借其超大规模、可伸缩、虚拟化、按需服务、高可靠性、高性价比的特点给个人的生活、学习和工作都带来了极大的便利［1］，其中虚拟化技术的应用，使得云系统中的资源可以打破传统物理资源的使用限制，使资源配置可以更加灵活地进行［2］。但是，由于云资源本身的异构性和动态性，以及用户任务请求的复杂性、多样性以及不确定性等特点［3］，云计算任务调度问题已经成为一种多项式复杂程度的非确定性问题（即NP（Nondeterministic Polynomially）完全问题）［4］。

如何更好地解决云计算任务调度问题，是当前云计算发展亟需解决的问题，现有的一些可用于求解云计算任务调度问题的算法大致可以分为启发式算法、元启发式算法以及混合式算法三大类［5］。在这三类算法中，元启发式算法和混合式算法是现在研究和应用最为广泛的两类方法，其中，元启发式算法主要包括：遗传算法（Genetic Algorithm， GA）［6］、粒子群优化（Particle Swarm Optimization， PSO）算法［7］、蚁群优化（Ant Colony Optimization， ACO）算法［8］等。但是，通常情况下，元启发式算法都存在或多或少的缺陷，单纯地采用一种元启发式算法往往难以取得令人满意的结果。在这种情况下，混合式算法越来越受到人们的关注，混合式算法即将多种方法和算法结合到一起而产生的新算法，如混沌松鼠搜索算法（Chaotic Squirrel Search Algorithm， CSSA）［9］、基于遗传算法的混合电子搜索（Hybrid Electro Search with Genetic Algorithm， HESGA）算法［10］以及基于性能代价的灰狼优化（Performance Cost Grey Wolf Optimization， PCGWO）算法［11］等，往往能取得比单一元启发式算法更好的优化效果。

鲸鱼优化算法（Whale Optimization Algorithm， WOA）是由Mirjalili等［12］提出的一种新的基于群体智能的元启发式优化算法，与其他已有的一些元启发式算法相比，WOA拥有寻优策略简单、收敛较快的特点，但同时也不可避免地存在全局搜索能力较弱、搜索精度较低且容易陷入局部收敛状态的缺陷。为了更充分地发挥WOA的优势，克服WOA原有的一些缺陷，更好地解决云计算任务调度问题，本文结合正交试验设计（Orthogonal Experimental Design， OED）［13］、自适应指数递减因子以及双向搜索机制，提出了一种新的正交自适应鲸鱼优化算法（Orthogonal Adaptive Whale Optimization Algorithm， OAWOA），并将其应用于求解云计算任务调度问题。

1 云计算任务调度与鲸鱼优化算法

1.1 云计算任务调度

在云系统中，任务调度就是云计算中心在接收到用户提交的任务请求之后，为用户的任务请求合理地分配云资源，并且实现系统执行任务的时间最小化和系统执行任务的成本最小化以及系统的平均负载率最大化等目标的过程。

常用的云计算任务调度模型可以划分为4个阶段，即用户提交任务请求、系统为任务请求分配资源（虚拟机）、将虚拟机分配给物理服务器以及云系统向用户返回计算结果。在这4个阶段中，第2个阶段，即系统为任务请求分配资源（虚拟机）阶段又被称为“任务调度”阶段，这也是本文要研究的内容。

设用户提交的n个任务的集合为：

云系统中m个虚拟机的集合为：

则任务调度的结果为：

根据云计算任务调度的目标，一个任务调度结果的优劣取决于该任务调度结果在云系统中执行时所需的执行时间的长短、成本的大小以及资源利用率和负载均衡程度的高低，同时，如何能够更好地对这些指标进行优化也是当前云计算任务调度所面临的重要问题。为了能够得到更好的任务调度结果，更有效地实现降低系统执行任务的时间和成本以及提高系统的平均负载率等目标，本文利用改进的鲸鱼优化算法即OAWOA对任务调度问题进行求解，并取得了显著的效果。

1.2 鲸鱼优化算法

鲸鱼优化算法［12］是受自然界中鲸鱼的捕食行为启发而提出的一种优化算法，它通过人工模拟鲸鱼捕食行为来寻求最优解。

鲸鱼优化算法主要包括：包围猎物、泡泡网攻击猎物（开发阶段）和搜寻猎物（探索阶段）这3个阶段，具体过程描述如下。

1）包围猎物。

WOA假设当前最佳候选解是目标猎物，而座头鲸可以识别猎物的位置并包围它们。在确定目标猎物之后，其他座头鲸将因此尝试向处于目标猎物位置的座头鲸方向更新它们的位置，在此阶段，鲸鱼的位置更新方式如式（1）～（2）所示：

2）泡泡网攻击猎物（开发阶段）。

在该阶段，鲸鱼利用气泡网向猎物发起攻击，并逐渐收缩包围圈。为了实现这一过程，需要包围猎物过程和螺旋更新位置机制协同进行，实现方式如式（7）所示：

3）搜寻猎物（探索阶段）。

为了增强算法的全局搜索能力，扩大鲸鱼的搜索范围，在该阶段，WOA根据随机选择的搜索个体来更新搜索代理在探索阶段的位置，而不是根据找到的最佳搜索个体，本阶段的鲸鱼位置更新方式如式（8）所示：

2 本文方法

在云计算资源调度问题中，系统执行任务的时间、系统执行任务的成本以及系统的平均负载率等是检验云计算系统服务能力的重要指标，WOA在解决这类问题中有显著的优势［14-15］，但是由于WOA本身存在的一些缺陷，在解决云计算任务调度问题时仍存在许多局限性。为克服WOA的局限性，实现云计算任务调度问题的多目标优化，本文对WOA的种群初始化、扩展搜索机制以及适应度函数的设计进行了优化。

2.1 正交自适应鲸鱼优化算法

为克服WOA在处理云计算任务调度问题时存在的全局搜索能力弱且易陷入局部最优的缺陷，本文提出了一种新的正交自适应鲸鱼优化算法（OAWOA）。在OAWOA中，首先利用正交试验设计对WOA的鲸鱼种群位置初始化以及全局搜索机制进行了优化，提出了一种正交扩展搜索机制；其次，本文对WOA的关键参数向量和进行了优化，进一步提高算法的寻优能力和寻优精度，具体过程如下。

2.1.1 基于正交试验设计的种群初始化和正交扩展搜索机制

针对WOA全局搜索能力较差且易陷入局部最优的缺陷，本文使用正交试验设计对算法的种群初始化和全局搜索机制进行优化，增强算法全局搜索和避免陷入局部最优的能力。

正交试验设计（OED），简称正交设计（Orthogonal Design， OD），是研究多因素多水平的一种试验设计方法，它根据正交性从全面试验中挑选出部分具备均匀分散、齐整可比特点的点。现在正交设计已经应用于遗传算法、差分进化算法来提高算法的性能［16］。在进行正交设计过程中，正交表是一个必不可少的部分，本文使用的是正交表（如表1所示），即一个由7个因素（每个因素2种水平）、共计8次实验组成的正交序列。由于在云计算任务调度问题中，可行方案的维度一般要比正交试验的因素数大很多，因此需要对任务调度的可行方案进行进一步处理，具体任务调度问题的正交设计过程具体如下。

表1 正交表Tab. 1 orthogonal table

表1 正交表Tab. 1 orthogonal table

试验号12345671111111121112222312211224122221152121212621221217221122182212112

1）随机将种群平均分为两组，记为X、Y。

2）分别从X、Y中随机选择一个鲸鱼位置，记为和，其中为一个鲸鱼位置向量的维度。

4）将3）分解产生的两组子向量，根据表1中的正交表进行正交试验，产生8组正交试验的结果。

6）重复过程2）～5），直到所有原始种群的各个位置向量均参与过正交试验。

7）返回产生的新种群的位置向量集合。

为充分发挥正交设计的优势，本文首先将正交设计应用于种群初始化过程，增强种群多样性，使得种群能够更加均匀地分布于解空间中，提高算法的搜索精度；其次，由于在每次WOA迭代完成之后，种群的多样性都会有所下降，当种群多样性过低时，算法容易陷入局部收敛状态，因此，本文在每次迭代完成之后增加一次正交扩展搜索过程，使用正交设计来维持种群的多样性，增强算法的全局搜索和避免陷入局部收敛的能力，并且正交试验过程中会保留当前最优解，因此不会影响算法的收敛速度。

使用正交设计进行鲸鱼种群位置初始化时，首先采用纯随机策略产生特定个数的初始位置，然后对产生的初始位置进行正交试验，直至所有的初始位置均完成正交试验，将新产生的鲸鱼位置向量集合作为种群初始化的结果返回，并应用于WOA的迭代过程。基于正交试验设计的鲸鱼种群位置初始化算法流程如算法1所示。

算法1 利用OD初始化种群位置向量集合。

8） end for

将正交设计用于正交扩展搜索的算法流程与算法1相似，区别在于在进行初始化时，需要采用纯随机策略先产生一组随机解，而在正交扩展搜索阶段，直接使用每次算法迭代完产生的位置向量集进行正交试验，正交扩展搜索的具体算法流程如算法2所示。

算法2 正交扩展搜索。

7） end for

2.1.2 基于自适应指数递减因子的位置更新机制

2.1.3 双向搜索机制

2.2 适应度函数设计

适应度函数是对具体问题的抽象表述，用一个数学模型来对具体问题进行表示，它是各种优化算法的优化目标。适应度函数设计是否合理，决定了一个具体问题经过算法求解之后能否得到需要的解决方案。由于本文需要对云计算任务调度问题的总执行时间、总成本以及平均负载率进行多目标优化，因此在设计适应度函数时要综合考虑系统执行任务的总时间、总成本以及平均负载率等多个指标，具体的适应度函数设计过程如下所述。

1）系统执行任务的总时间。

系统执行任务的总时间即每个虚拟机（Virtual Machine， VM）执行任务所需的时间之和，计算式如式（17）所示：

2）系统执行任务的总成本。

系统执行任务的总成本即每个虚拟机执行任务所耗费的成本之和，其计算式如式（20）所示：

3）系统平均负载率。

系统平均负载率是描述当前系统工作状态的重要指标，在云系统中，系统的平均负载越高，表明系统中的资源利用得越充分，系统的综合执行效率越高。本文中系统平均负载率是各个虚拟机负载率的均值，计算式如式（22）所示：

4）多目标适应度函数。

为了实现对系统执行任务的总时间、总成本和平均负载率的多目标优化，本文采用线性加权法将多目标优化问题转换成单目标优化问题，为了能够更好地将系统执行任务的总时间、总成本和平均负载率使用线性加权法转化成单目标问题，需要对系统执行任务的总时间、总成本和平均负载率进行归一化处理。对系统执行任务的总时间和总成本进行归一化处理的过程如式（25）～（26）所示：

由于对系统执行任务的总时间和总成本的优化目标是尽可能地获得它们的最小值，而对于系统平均负载率而言，则是需要尽可能地取其最大值，因此，为了能够将系统平均负载率与系统执行任务的总时间和总成本一起进行优化，本文先对系统平均负载取其倒数，然后再进行归一化处理，过程如式（27）～（28）所示：

由此可以得到本文的适应度函数如式（29）所示：

基于此得到本文的优化目标如式（30）所示：

2.3 基于正交自适应鲸鱼优化的云计算任务调度

为了更好地解决云计算中的任务调度问题，提高云系统的服务水平和服务能力，本文将正交自适应鲸鱼优化算法用于求解云计算任务调度问题，具体过程描述如下。

2.3.1 云计算任务调度问题的编码

为将OAWOA应用于求解云计算任务调度问题，首先需要对云计算任务调度问题进行编码，使云计算任务调度问题可以输入到OAWOA中进行求解。

本文对云计算任务调度问题的编码过程如式（31）～（32）所示：

即将云计算任务调度问题编码为一个由虚拟机编号组成且维数为任务数的位置向量，其中位置向量每一维的索引号为任务编号，表示1～m的一个随机数，表示一个鲸鱼的位置向量，为鲸鱼种群中每个鲸鱼的位置向量的集合。

2.3.2 基于OAWOA的云计算任务调度过程

基于OAWOA的云计算任务调度流程如图1所示，具体过程如下：

步骤1 构建鲸鱼的位置向量：将云系统中的任务和虚拟机按式（31）～（32）进行编码。

图1 基于OAWOA的云计算任务调度流程Fig. 1 Flow chart of cloud computing task scheduling based on OAWOA

步骤4 包围猎物：该阶段鲸鱼位置向量的更新方式与WOA的包围猎物阶段位置更新策略一致。

步骤5 泡泡网攻击猎物：该阶段鲸鱼位置向量的更新方式与WOA的泡泡网攻击猎物阶段位置更新策略一致。

步骤6 搜寻猎物：该阶段鲸鱼位置向量的更新方式与WOA的搜寻猎物阶段位置更新策略一致。

步骤7 更新最优位置向量：计算经过步骤6更新后的鲸鱼种群的位置向量的适应度，记录适应度函数值最小的鲸鱼的位置向量及其适应度函数值，若当前的最优解比当前全局最优位置向量更好，则更新当前全局最优位置向量。

步骤8 正交扩展搜索：将经过步骤6更新后的鲸鱼种群的位置向量，进行正交扩展搜索，增强种群的多样性，避免陷入局部最优状态，该阶段的具体过程如算法2所述。

步骤9 判断算法是否达到终止条件：若是则终止算法，并返回最优解作为云计算任务调度问题的解决方案；否则返回步骤3进入下一次迭代过程。

3 仿真实验与结果分析

为验证正交自适应鲸鱼优化算法在解决云计算任务调度问题中的性能，将本文提出的OAWOA与传统鲸鱼优化算法（WOA）［12］、粒子群优化（PSO）算法［7］、蝙蝠算法（Bat Algorithm， BA）［18］以及其他两种改进的鲸鱼优化算法：改进互利共生鲸鱼优化算法（Whale Optimization Algorithm with a modified Mutualism， WOAmM）［19］和改进的鲸鱼优化算法（Improved Whale Optimization Algorithm， IWOA）［20］进行了对比。

3.1 实验设计

3.1.1 实验环境设置

为验证OAWOA在解决云计算任务调度问题中的可靠性和有效性，本文使用Python 3.9作为编程语言，实验环境为PyCharm Community 2021.1，操作系统为Windows 10，CPU型号为Intel Core i5-7400 CPU @ 3.00 GHz，内存为8 GB。云系统中虚拟机分为低性能组、中性能租和高性能组这3个组，每组5个虚拟机，共计15个虚拟机，每组虚拟机的编号、执行速度和单位定价如表2所示。

表2 虚拟机信息Tab. 2 Virtual machine information

云系统中任务规模共分为两组，分别为50个任务和500个任务，用来模拟任务量较小和任务量较大两种情况，其中每一个任务的大小都在［1 000，100 000］随机产生。

3.1.2 算法及适应度函数参数设置

在实验过程中，WOA、PSO算法、BA、WOAmM、IWOA以及OAWOA的种群规模均设置为50，算法的迭代次数均为100，对于其他参数，WOA、PSO算法、BA、WOAmM以及IWOA分别参照文献［12］、文献［7］、文献［18］、文献［19］以及文献［20］设置。同时，为综合考虑系统执行任务的总时间、总成本和系统平均负载率这3个指标，本文取，即：

3.2 结果分析

在实验过程中，由于任务是随机产生的，因此为消除随机性对于实验结果的影响，本文在每种任务规模条件下均进行20次实验，然后取其平均值进行分析。各算法在不同任务规模下的实验结果如表3所示。

表3 任务规模为50和500时适应度函数的最优值Tab. 3 Optimal values of fitness function when task scale is 50 and 500

图2～3给出了当任务规模为50时的实验结果。

图2为任务规模为50时的算法收敛过程，从图2中可以得出，WOA、PSO算法、WOAmM、IWOA在算法前期都保持着较快的收敛，而BA的收敛则相对较慢；在对局部收敛状态处理中，WOA、PSO算法、WOAmM、IWOA以及BA都没有取得较好的效果。OAWOA不仅在算法前期保持着与WOA、PSO算法、WOAmM以及IWOA相似的较快收敛，而且在其他算法都逐渐陷入局部收敛状态时，OAWOA仍凭借正交扩展搜索机制、自适应指数递减因子以及双向搜索机制，不断地尝试对适应度函数进行优化，并且在避免陷入局部收敛状态，以及对云计算任务调度问题解决方案的优化中取得了更好的效果。

图2 任务规模为50时不同算法的收敛情况Fig. 2 Convergence of different algorithms when task scale is 50

图3为任务规模为50时各算法对于系统执行任务的总时间、总成本以及系统平均负载率等指标的优化效果。从图3中可以看出，当任务规模为50时，BA虽然取得了较高的平均负载率，但却在成本和时间方面付出了较大的代价，并且从表3中也可以看出，BA在解决问题中取得的综合指标（适应度函数值）并不是太好，因此在此处不再与BA进行具体对比。对于除BA之外的其他几种算法，从图3中可以看出，当任务规模为50时，相较于WOA、PSO算法、WOAmM、IWOA，OAWOA都取得了更好的效果。由此可见，当任务规模较小时，在对于云计算任务调度的多目标优化问题的求解中，OAWOA取得了较为显著的优势。

图4～5给出了当任务规模为500时的实验结果。

图4为任务规模为500时的算法收敛过程，从图4中可以看出，当任务规模较大时，BA已经难以取得较好的效果，而其他几种算法仍保持着较快的收敛，并且取得了较好的优化效果。相较于其他几种算法，本文的OAWOA不仅在算法前期依旧保持着较快的收敛，并且在后期处理局部收敛问题时，依旧取得了相较其他算法更好的效果。

图4 任务规模为500时不同算法的收敛情况Fig. 4 Convergence of different algorithms when task scale is 500

图3 任务规模为50时各个指标的优化情况Fig. 3 Optimization of each index when task scale is 50

图5为任务规模为500时各算法对于系统执行任务的总时间、总成本以及系统平均负载率等指标的优化效果。从图5可以看出，当任务规模为500时，BA同样存在与任务规模为50时相同的情况，因此在此处也不再与BA进行对比。对于除BA外的其他几种算法，当任务规模为500时，WOA、WOAmM、IWOA和本文的OAWOA都取得了较好的结果，并且OAWOA在执行任务的总时间、总成本以及系统平均负载率等方面均取得了比WOA、PSO算法、WOAmM和IWOA更好的效果。

图5 任务规模为500时各个指标的优化情况Fig. 5 Optimization of each index when task scale is 500

综上，无论任务规模较小时，还是任务规模较大时，本文提出的OAWOA在处理云计算任务调度问题时都可以取得比较显著的优化效果。

4 结语

本文基于正交设计的种群初始化机制、正交扩展搜索机制、自适应指数递减因子和双向搜索机制提出了一种新的正交自适应鲸鱼优化算法（OAWOA），并将其应用于求解云计算任务调度问题。为验证OAWOA的有效性，本文将OAWOA与WOA等五种其他的算法进行了对比，通过在任务规模小和任务规模大两种情况下的实验结果表明，本文所提的OAWOA在求解云计算任务调度问题时，在降低任务执行总时间和总成本与提高系统平均负载率的多目标优化方面都取得了更为显著的优势。在下一步的研究中，我们将考虑在更为复杂的情况下（如考虑内存、带宽等因素的影响）如何更好地解决云计算任务调度问题，提高云系统的服务性能。

[1] 王冠宇，王庆生，赵腾.混合蛙跳算法在云计算资源调度的策略改进［J］.科学技术与工程，2018，18（4）：297-303.（WANG G Y， WANG Q S，ZHAO T. The improved strategy of shuffled frog leaping algorithm in the resource scheduling of cloud computing ［J］. Science Technology and Engineering， 2018， 18（4）： 297-303.）

[2] ALDOSSARY M. A review of dynamic resource management in cloud computing environments ［J］. Computer Systems Science and Engineering，2021， 36（3）： 461-476.

[3] 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.

[4] HU H Y， LI Z J， HU H， et al. Multi-objective scheduling for scientific workflow in multicloud environment ［J］. Journal of Network and Computer Applications， 2018， 114： 108-122.

[5] ZHANG G H， ODBAL， ABNOOSIAN K. Scheduling mechanisms in the cloud environment： a methodological analysis ［J］. Kybernetes， 2020，49（12）： 2977-2992.

[6] ARORA M， KUMAR V， DAVE M. Task scheduling in cloud infrastructure using optimization technique genetic algorithm ［C］// Proceedings of the 2020 4th World Conference on Smart Trends in Systems， Security and Sustainability. Piscataway：IEEE， 2020： 788-793.

[7] KENNEDY J， EBERHART R. Particle swarm optimization ［C］// Proceedings of the 1995 International Conference on Neural Networks. Piscataway： IEEE， 1995：1942-1948.

[8] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents ［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996，26（1）： 29-41.

[9] SANAJ M S， JOE PRATHAP P M. Nature inspired Chaotic Squirrel Search Algorithm （CSSA） for multi objective task scheduling in an IAAS cloud computing atmosphere ［J］. Engineering Science and Technology， an International Journal， 2020， 23（4）： 891-902.

[10] VELLIANGIRI S， KARTHIKEYAN P， ARUL XAVIER V M， et al. Hybrid electro search with genetic algorithm for task scheduling in cloud computing ［J］. Ain Shams Engineering Journal， 2021， 12（1）： 631-639.

[11] NATESAN G， CHOKKALINGAM A. An improved grey wolf optimization algorithm based task scheduling in cloud computing environment ［J］. The International Arab Journal of Information Technology，2020， 17（1）： 73-81.

[12] MIRJALILI S， LEWIS A. The whale optimization algorithm ［J］. Advances in Engineering Software， 2016， 95： 51-67.

[13] XU Z Z， HU Z Y， HEIDARI A A， et al. Orthogonally-designed adapted grasshopper optimization： a comprehensive analysis ［J］. Expert Systems with Applications， 2020， 150： Article No.113282.

[14] SREENU K， SREELATHA M. W-Scheduler： whale optimization for task scheduling in cloud computing ［J］. Cluster Computing， 2019， 22（S1）： 1087-1098.

[15] CHEN X， CHENG L， LIU C， et al. A WOA-based optimization approach for task scheduling in cloud computing systems ［J］. IEEE Systems Journal， 2020， 14（3）： 3117-3128.

[16] 閤大海，李元香，祝婕.基于正交设计的反向学习差分进化算法［J］.华中科技大学学报（自然科学版），2017，45（5）：23-27，44.（XIA D H， LI Y X， ZHU J. Differential evolution algorithm using orthogonal design opposition-based learning ［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2017， 45（5）： 23-27， 44.）

[17] 郝晓弘，宋吉祥，周强，等.混合策略改进的鲸鱼优化算法［J］.计算机应用研究，2020，37（12）：3622-3626，3655.（HAO X H， SONG J X， ZHOU Q， et al. Improved whale optimization algorithm based on hybrid strategy ［J］. Application Research of Computers， 2020， 37（12）： 3622-3626， 3655.）

[18] YANG X S， HOSSEIN GANDOMI A. Bat algorithm： a novel approach for global engineering optimization ［J］. Engineering Computations， 2012，29（5）： 464-483.

[19] CHAKRABORTY S， SAHA A K， SHARMA S， et al. A novel enhanced whale optimization algorithm for global optimization ［J］. Computers and Industrial Engineering， 2021， 153： Article No.107086.

[20] 武泽权，牟永敏.一种改进的鲸鱼优化算法［J］.计算机应用研究，2020，37（12）：3618-3621.（WU Z Q， MU Y M. Improved whale optimization algorithm ［J］. Application Research of Computers， 2020， 37（12）： 3618-3621.）

Cloud computing task scheduling based on orthogonal adaptive whale optimization

ZHANG Jinquan1， XU Shouwei1， LI Xincheng1， WANG Chongyang1， XU Jingzhi2*

（1.College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao Shandong266590，China；2.Science and Technology Industry Management Office，Shandong University of Science and Technology，Qingdao Shandong266590，China）

Aiming at the problems such as long task completion time， high task execution cost and unbalanced system load in task scheduling， a new cloud computing task scheduling method based on Orthogonal Adaptive Whale Optimization Algorithm （OAWOA）was proposed. Firstly， the Orthogonal Experimental Design （OED） was applied to the population initialization and global search stages to improve and maintain the population diversity， avoid the algorithm from falling into local convergence too early. Then， the adaptive exponential decline factor and bidirectional search mechanism were used to further strengthen the global search ability of the algorithm. Finally， the fitness function was optimized to enable the algorithm to achieve multi-objective optimization. Through the simulation experiments， the proposed algorithm was compared with Whale Optimization Algorithm （WOA）， Particle Swarm Optimization （PSO） algorithm， Bat Algorithm （BA）and two other improved WOAs. Experimental results show that， when the task scale is 50 and 500， the proposed algorithm achieves better convergence effect，has the total time and total cost of the obtained system executing tasks lower than those of other algorithms， and has the load balancing degree only lower than that of BA. In conclusion， the proposed algorithm shows significant advantages in reducing the total time and cost of system executing tasks and improving the system load balancing.

cloud computing; task scheduling; Whale Optimization Algorithm (WOA); Orthogonal Experimental Design (OED); multi-objective optimization

TP399

A

1001-9081（2022）05-1516-08

10.11772/j.issn.1001-9081.2021050806

2021⁃05⁃17；

2021⁃09⁃15；

2021⁃09⁃16。

教育部人文社科基金资助项目（20YJAZH078， 20YJAZH127）；同济大学嵌入式系统与服务计算教育部重点实验室开放课题（ESSCKF 2019‑06，ESSCKF 2019‑08）。

张金泉（1972—），男，四川南充人，副教授，博士，CCF会员，主要研究方向：云计算、大数据分析与处理、隐私保护； 徐寿伟（1996—），男，山东烟台人，硕士研究生，CCF会员，主要研究方向：云计算、边缘计算、任务调度； 李信诚（1997—），男，山东泰安人，硕士研究生，CCF会员，主要研究方向：云计算、边缘计算、任务调度； 王重洋（1996—），男，山东潍坊人，硕士研究生，CCF会员，主要研究方向：云计算、隐私保护； 徐景芝（1973—），女，山东济南人，讲师，硕士，主要研究方向：云计算、大数据分析与处理。

This work is partially supported by Humanity and Social Science Fund of Ministry of Education （20YJAZH078， 20YJAZH127）， Open Project of Key Laboratory of Embedded System and Service Computing， Ministry of Education （Tongji University） （ESSCKF 2019-06， ESSCKF 2019-08）.

ZHANG Jinquan， born in 1972， Ph. D.， associate professor. His research interests include cloud computing， big data analysis and processing， privacy protection.

XU Shouwei， born in 1996， M. S. candidate. His research interests include cloud computing， edge computing， task scheduling.

LI Xincheng， born in 1997， M. S. candidate. His research interests include cloud computing， edge computing， task scheduling.

WANG Chongyang， born in 1996， M. S. candidate. His research interests include cloud computing， privacy protection.

XU Jingzhi， born in 1973， M. S.， lecturer. Her research interests include cloud computing， big data analysis and processing.