大规模云计算服务器优化调度问题的最优二元交换算法研究

王万良，臧泽林，陈国棋，屠杭垚，王宇乐，陆琳彦

（1. 浙江工业大学计算机科学与技术学院，浙江 杭州 310027；2. 伦敦大学国王学院工程科学学院，英国 伦敦 WC2R 2LS）

1 引言

云计算是分布式计算（distributed computing）、网络存储（network storage technology）、负载均衡（load balance）等传统计算机和通信技术发展融合的产物，由于云计算技术的通用性和高可靠性，该技术得到了广泛的发展[1]。随着云计算规模的逐步扩大，谷歌、阿里巴巴、百度等大型互联网企业纷纷搭建了自己的云服务平台。它们建立的平台可容纳超过万台的服务器，为超过百万的用户进行服务。大规模云服务平台的建立，使云服务的调度系统变得更加重要[2]。在庞大的云服务平台基数下，云服务平台的性能即使有1%的提高也会带来巨大的收益[3]。

目前，云计算调度分为云服务请求实时调度和基于历史数据的云服务优化调度。

云服务请求实时调度以调度系统的快速性、稳定性为出发点，研究如何实时地将云计算任务指派给一台或几台宿主机服务器实现负载均衡。在这类研究中，传统的方法有Max-Min方法[4]、RR算法[5]、FCFS算法、FIFO算法[6]等。另外，一系列的商业软件如 Google的 Borg调度系统[7-8]、阿里巴巴的Sigma调度系统[9]和MapReduce等开源软件都做出了相应的学术贡献。但是上述研究存在以下2个尚待解决的问题：1)上述方法只能应用于过程迭代和异构任务类型，无法执行递归或复杂的业务流；2)上述方法会出现占用特定的虚拟机 I/O，造成其他作业“饥饿”的情况。

在基于历史数据的云服务优化调度领域，同样出现了大量的研究成果。其中，Tsai等[10]阐述了实时的云计算的生命周期问题，并在此基础上提出了一种面向云计算实时调度的框架，该框架能够有效地解决云计算实时调度的一般问题。在此基础上，Zhu等[11]提出了一种用于虚拟化云中实时任务调度的新型滚动调度架构，然后提出并分析了面向任务的能耗模型。另外，Zhu等[11]开发了一种新的能量感知调度算法（EARH, energy awar），并通过实验证明了该算法能够在可调度性和节能之间做出良好的权衡。王吉等[12]在考虑调度快速性和有效性的背景下，又考虑了调度的容错性，提出了一种在虚拟云平台中的容错调度算法（FSVC, fault-tolerant scheduling algorithm in virtualized cloud），通过主副版本方法实现对物理主机的容错控制，采用副版本重叠技术与虚拟机迁移技术提高算法的调度性能。郭平等[13]将云平台的调度问题简化为本地化的调度问题，并且结合主导资源公平调度策略 DRF和Delay调度约束机制，提出了一种满足本地化计算的集群资源调度策略（DDRF, delay-dominant resource fairness），并讨论了本地化计算时延对作业执行效率的影响。另外，对于提供 GPU服务的云平台，Peng等[14]提出了一种高效的、动态的深度学习资源调度方法—— Optimus，该方法使用在线训练来拟合训练模型，并建立性能模型以准确地估计每个作业的训练速度。就工作完成时间而言，Optimus的调度性能有63%的提高。

基于历史数据的云服务优化调度将同一云计算请求源产生的计算请求看成是可预测的时间序列。调度算法以该时间序列为基础对宿主机服务器的分配进行调度[15]。很多经典的优化方法和优化理论可以引入调度框架[16]中，如遗传算法（GA, genetic algorithm）[17]、群智能算法、局部搜索（LS, local search）算法[18]等。同时，有部分学者提出了专门面向服务器的调度算法。例如，林伟伟等[19]通过对约束满足问题对异构的云数据中心的能耗优化资源调度问题建模，并且在此基础上提出了能耗优化的资源分配算法（DY, dynamic power）。Li等[20]提出了一种协调调度算法来解决过度生成虚拟机（VM, virtual machine）实例的问题，并使用实际生产中的数据验证了该方法的有效性。Dong等[21]将云服务器调度问题建模为混合整数规划（MIP, mixed integer programming）问题，将目标函数设置为使数据中心服务器消耗的能量最小，并提出了一个有效的服务器优先任务调度方案。

为了克服分支定界算法解决大规模问题时间消耗庞大的问题，本文将LS算法[22]的框架融入分枝定界算法，设计了最优二元交换算法（OTECA,optimal two element exchange algorithm）。OTECA并不是使用分支定界法一次性解决全部问题，而是每次只解决其中的部分子问题。然后使用LS的思想不断地选择子问题进行解决。因此，OTECA可以通过求解多个子问题获得原问题的解。上述求解策略可以快速有效地求解大规模的服务器调度问题。实验证明，OTECA优于LS、GA等算法。

2 云计算服务器调度模型

本节建立一个MIP模型，对云计算服务器调度问题进行描述。模型框架如图1所示。

图1显示了云计算调度资源、调度方案、目标函数、约束条件与运算请求间的相互关系。本节将用数学方式对上述单元以建模的方式进行描述。

2.1 云计算服务器的资源表示与数据描述

在整个调度过程中，需要处理的资源被抽象为5个集合：服务器集合M、应用集合A、实例集合S、亲和约束集合Q与反亲和约束集合F。

每个宿主机服务器mj都可以提供多种类型的计算资源，服务器集合M可描述为

图1 云计算服务调度模型框架

其中，n为服务器的数量，mj为第j台服务器所能提供的资源，即

应用集合A描述了请求服务器资源的应用与其对服务器提供资源的消耗，即

其中，p为应用的总量，ar为第r个应用需求的资源，即

其中，CPU、DISK与MEM的每日资源消耗按照时间曲线给出，NET-IO、DISK-IO的每日资源消耗以常数的形式给出。为元素个数为N的列向量，其中k为时间维度的检索句柄，满足k∈{1,2,3,…,N}。

相互独立的运算请求被称为实例。实例集合S包含调度过程中应用产生的所有实例，即

其中，q为实例的总量，实例si为

亲和约束与反亲和约束描述了调度场景中的约束关系，主要分为2种情况：应用与应用之间的亲和/反亲和关系，应用与服务器之间的亲和/反亲和关系。

亲和/反亲和关系可以描述为2个应用之间（或者应用与宿主机服务器之间）存在相互依赖或者相互排斥的关系。具体的亲和/反亲和关系描述如表 1所示。

表1 亲和/反亲和关系描述

亲和/反亲和的关系使用 0-1矩阵Haa、Ham、Faa、与Fam描述。应用与应用间的亲和关系Haa的结构描述为

Faa的结构与Haa的结构相同，其矩阵内元素为，当时，r1应用与r2应用不存在反亲和关系，反之存在。Ham的结构描述为

其中，Ham描述应用与机器间的亲和关系。

Fam的结构与Ham的结构相同，其矩阵内元素为当时，r应用与j机器不存在反亲和关系，反之存在。

2.2 云计算服务器调度的决策变量与目标函数

云计算服务器的调度问题乃至大部分的资源调度问题都可以转化为一个多维度的背包问题。调度的目的是为每一个计算请求（实例si）寻找一个合适的宿主机服务器mj，减少系统的运行成本。因此以0-1整数的形式，定义二维决策变量V描述实例到机器的分配关系，即

其中，vi,j为0-1决策变量，vi,j=1代表实例s1被调度到机器mj中执行，反之没有。

为了方便对亲和/反亲和约束描述，另外，设定辅助决策变量W来描述应用到机器的分配关系，即

其中，wi,j为0-1决策变量，wi,j=1代表应用ai被调度在机器mj中执行，反之没有。V与W之间存在的约束关系为

其中，R(i)为一个从实例Si到其对应的应用的映射。优化调度的目标描述为：在一定调度时间段内，寻找一种使用服务器数量最少、负载均衡的服务器调度方案。为了避免由于模型不精确带来的资源使用溢出风险，本文通过惩罚的形式定义目标函数为

其中，k为时间索引，满足k∈{1,2,3,…,N}；C为时间采样频率；Fj为宿主机服务器mj获得的分数值，其可以描述为

其中，β为惩罚阈值，当宿主机服务器的CPU使用率大于惩罚阈值时，开始引入额外平方项对调度方案进行惩罚；α为惩罚增量系数，描述进行惩罚时的惩罚力度；xj,k为机器mj在k时刻的CPU使用率，计算式为

单一机器 CPU使用率与目标分数关系如图 2所示。由图2可知，当机器在所有的时间内保持CPU使用率为0时，目标分数为0；当机器的CPU使用率大于0且小于惩罚阈值β时，目标分数为1；但当CPU使用率大于惩罚阈值时，目标分数从1开始以二次幂形式上升。

图2 单一机器CPU使用率与目标分数关系

2.3 云计算服务器调度的约束条件

实际的云计算服务器调度环境中存在大量由硬件条件和应用功能导致的限制。模型将这些限制转化为模型约束、资源约束、亲和/反亲和约束和优先级约束进行处理。

模型约束描述了调度模型的基本约束，包括每个实例都应被安排到一个宿主机服务器上，且只能被安排到一台宿主机服务器上，即

资源约束是一种由于资源限制造成的约束，每个宿主机服务器上配置的不同类型的资源是有容量上限的。

CPU资源约束为

DISK资源约束为

MEM资源约束为

NET-IO资源约束为

DISK-IO资源约束为

亲和/反亲和约束可以分为以下4种情况。

1) 应用与应用的亲和约束

2) 应用与应用的反亲和约束

3) 应用与机器的亲和约束

4) 应用与机器的反亲和约束

约束决策变量不能同时为1。

3 大规模云计算二元交换分析论证

将式(13)写成max函数形式，定义评分函数为

其中，x为宿主机服务器某一时刻的CPU使用率，机器j的CPU使用率为xj。

引理1在所有对2台机器进行的CPU使用率(x1,x2)的重新分配(x1*,x2*)中，至少存在一个使评价分最小的最优分配，且该最优分配可由计算式和求得，其中，c为2台机器的CPU容量的比例，即

证明将式(14)代入Ot(x1,x2)=f(x1)+f(x2)可得

由于实例的重新分配不改变其 CPU使用率绝对值之和，因此有

因此，可以表示成l(·)，即，将其代入式(26)，可得变量为x1*的方程为

对式(28)进行分段讨论后再对x1*求导可得

引理2定义机器j的特征计算式为xj为机器j的平均CPU使用率。在2台机器的平均CPU占比为(x1,x2)的情况下，最优分配(x1*,x2*)所带来的评分之和的下降量Od(x1,x2,c)=Ot(x1,x2)-Ot(x1*,x2*,c)与 2台机器的特征计算式的差的平方(g1-g2)2呈正相关。

证明对特征公式的差的平方(g1-g2)2进行展开，有

构造函数

对于所有的自由变量，使用链式法则进行展开，可得

其中

由于α、β与c皆大于或等于 0，Od对于特征计算式p的导数恒大于0，即D(x1,x2,c)＞0，因此2个方程呈正相关。证毕。

4 算法设计

混合整数规划问题是一个NP完全问题，即求解该问题的最优解的时间复杂度与问题的规模呈指数关系。随着数据量的增长，分支定界法不能在有效时间内得到理想的解，基于此，本文设计了OTECA，寻找一个时间花费与求解精度的平衡点，快速有效地解决云计算服务器调度问题。

4.1 可行解生成方法

可行解生成方法负责生成占用尽量少的服务器资源且满足约束要求的初始解。求解的流程如算法1所示。

算法1可行解生成方法（GSSM, good solution generation method）

输入服务器集合M，应用集合A，实例集合S

输出调度初始可行解V，状态矩阵E

1) 初始化可行解V，使用服务器数下限Nml=0，使用服务器数上限Nmh=p

2) whileNml!=Nmhdo

3) 机器指示m=0

4) for 实例索引s=0,s≤q,s++

5) if 实例s可装入机器mthen

6)V,E=put(s,m) %将s放入m中，并更新状态

7) else

8)m=m+1,s=s-1

9) end if

10) ifm==Nmhthen %机器数选取过少

17) end if

18) end for

19) end while

20) returnV,E

算法通过二分法的形式对使用服务器数量的上限和下限不断更新，从而不断地拉近使用服务器的上下限的差距，最终在上下限相等时停止程序，完成对最合适的可行解的生成。步骤5)验证机器m装入实例s后，是否仍然满足模型约束。步骤 10)与步骤 15)判断当前的机器数量上限Nmh能否得到可行解，如果可以得到可行解，则进一步减少机器数量，如果无法得到可行解，则增加机器的数量，直至上下限相等则退出方法。

在时间复杂度方面，由于每次进入步骤 11)、步骤12)与步骤16)判断都会造成Nmh与Nml的差减少一半，因此外部循环的复杂度为log(p)。步骤4)～步骤18)的内部循环的次数受到实例数p与机器数n的影响，在最坏的情况下将进行n+p次循环，因此整个算法的时间复杂度为(n+p)log(p)。

4.2 最优二元交换算法

分支定界法求解大规模MIP问题消耗的时间常常是不能接受的，但是求解较小规模的MIP问题却有很高的效率。该算法将通过求解一系列小规模的 MIP子问题，去逼近整个大规模的 MIP问题。

可以证明，在所有的实例都满足约束被分配进入宿主机服务器的情况下，将其中2台机器中的实例以 BBM 方法重新分配到原来的宿主机服务器中，不会造成调度目标值的上升（如引理1所示），且这2台机器的特征计算式gj差距越大，其获得更高分数下降的可能性也就越大（如引理2所示）。

OTECA流程如图3所示。

图3 OTECA流程

最优二元交换算法伪代码如算法2所示。

算法2OTECA

输入服务器集合M，应用集合A，实例集合S，惩罚系数α和β，集合选择系数γ，小规模MIP子问题求解次数Ns

输出服务器调度结果Vbest

1)V=GSSM(M,A,S) %生成可行解

2)M,ScoreList=Score(E,M) %按照式(14)对当前可行状态中每个服务器进行打分，并按照分数进行排序

3) for loop=0, loop＜Naim, loop++

4)M=SMWS(M, ScoreList) %按照分数调整顺序

5)Smh,Sml=CMSet(Mc,A,S,α,β,γ) %选取高分服务器集合与低分服务器集合

6)Mh,Ml=ChoMach(Smh,Sml) %分别在2台服务器集合中选取一台待交换机器

7)VMIP,E=BBM(Mh,Ml,A,α,β)%分支定界法求解该小规模MIP问题，得到新的分配方案与机器状态

8) end for

9) returnVbest

最优二元优化部分是算法的核心部分，该部分为寻找一个优秀的大规模服务器调度方案，其主要循环中包括高分机器集合与低分机器集合的维护、MIP子问题选择、MIP子问题求解等步骤。

步骤 4)和步骤 5)生成一个高分机器集合与低分机器集合，其中特征分数概念由目标函数中目标分数的概念变化而来。该特征分数综合考虑了机器当前负载与机器的容量这2个特性，可以表现机器未来的负载能力，如引理 2所示。步骤 5)中，使用最高分sh与最低分sl生成高分集合与低分集合，生成的标准为

其中，γ为集合选择系数，一个较大的值可以使高分机器集合和低分机器集合随循环次数的选择增长得更快；Smh为高分机器集合，Sml为低分机器集合。

步骤7)中设定当机器得分不变的前提下，实例负载尽量装入容量较大的服务器，从而尽量减少服务器的使用。步骤 4)～步骤 7)不断解决子问题优化调度结果。

每个循环子问题由高分机器、低分机器与机器中的实例组成。子问题的最优解一定是上述实例在上述机器上的重新组合。可以证明，新解的目标分数之和一定优于原解（如引理 1所示）。另外，高分机器与低分机器的分差越高，重新组合后分数的优化越显著（如引理 2所示）。上述引理是算法挑选高分集合和低分集合进行混合的原因。因此，最优二元优化算法比传统的基于随机或启发的算法有更强的目的性，在前期拥有更高的收敛速度，在后期拥有更强的调度精确度。

算法初始阶段将快速地消除高负载机器，造成低负载机器分数上升、高负载机器分数下降，这时高分机器集合和低分机器集合将出现一定重叠。随着这种重叠现象的逐步加深，算法的子问题选择将逐渐退化为对机器的随机优化，从而对机器中实例进行整理，并减小宿主机服务器的数量。最后该算法将返回从实例到宿主机服务器的优化分配。

在时间复杂度方面，4.1节已经论证了算法 2步骤1)的复杂度为(n+p) log(p)，步骤2)作为一个排序的工作，复杂度为nlog(n)。因为步骤3)～步骤7)在最坏情况下复杂度为Naim2x，其中x为子问题中实例的数量，这并不意味着该步骤是十分耗时的，因为在子问题中，x受到机器容量的约束。在实际的应用环境中，步骤7)均可以在可接受的时间（秒级）范围内得到响应，则算法2总的时间复杂度为(n+p)log(p)+nlog(n)。

5 仿真与验证

5.1 实验硬件架构描述与数据集描述

为了保证改进算法得到充分稳定的测试，本文使用不同规模的调度测试数据与阿里云计算中心公开的实际数据集（ALISS）进行仿真实验。数据中心拥有10 000台不同配置的宿主机服务器。实验仿真硬件平台为：曙光天阔W580-G20服务器，CPU E5-2620 v4 2.1 GHz；软件环境为：ubuntu 18 LTS，Python3.6。

实验的硬件架构如图4所示。硬件架构按照功能由4种节点组成，分别为资源节点、管理节点、调度节点和服务节点。其中，服务节点负责收集云计算请求，并以集合A、S的形式提交给调度节点。管理节点负责监控资源节点的资源使用和工作情况，并以集合M的形式提交给调度节点。调度节点综合整个云计算服务平台的情况进行调度工作，将运算请求调度到资源节点中。

ALISS数据集中每一组数据由4张表格组成，分别是机器信息列表、应用信息列表、实例信息列表、亲和与反亲和信息列表。其中，机器信息列表中含有M-id、M-c、M-m、M-d，M-id为机器的ID，M-c、M-m、M-d分别对应机器集合的miCPU、miDISK、miMEM。应用信息列表中含有 A-id、A-c、A-m、A-d，A-id为应用的 ID，A-c、A-m、A-d分别对应集合中的。时变数据 CPU-use、MEM-use的采样周期为15 min，即C=96。

图4 实验的硬件架构

5.2 OTECA在ALISS上的求解结果

本节使用OTECA求解ALISS-2数据集中的调度问题。为了保证服务器运行的稳定性与资源分配的合理性，设置模型参数为α=10，β=0.5，选取OTECA参数为择优选取集合选择系数γ=1.5，子问题求解次数Ns=300，并对问题进行求解。求解过程如图5～图7所示。

图5 ALISS-2问题宿主机服务器数、目标函数与循环次数关系

图6 ALISS-2问题高低分机器数与循环次数关系变化

图7 ALISS-2宿主机服务器使用率与循环次数关系变化

优化开始时，宿主机服务器平均 CPU使用率仅在45%左右，这证明优化开始时服务器组的负载并不均衡。随着算法迭代循环次数的增加，算法将得分较高的机器中的实例与得分较低的机器中的实例使用整数规划的方法进行最优的重新组合，重新分配到原来的机器中，并将负载进行有效的重组。由图5可知，随着优化的进行，得分在快速地下降。在最理想的情况下，算法将所有的机器的负载都调整到从下方逼近β的情况。由图6可知，由于优化开始时机器分数差异较大，以最高分和最低分划定的高分机器集合和低分机器集合中元素较少。随着优化的进行，机器的负载逐步平均，分数的分布逐步集中，高分机器集合和低分机器集合逐渐包含同一部分机器。

当loop＞100时，由于机器的负载已经达到了平均水平，机器数与得分的差距基本不再变化，此时分数的下降主要来自机器数的削减。当某台机器不执行任何程序时，其得分为 0。因此在交换无法使负载更加均衡的情况下，OTECA的同样的交换操作将尽量清除多余的宿主机服务器。由图7可知，随着循环次数的上升，CPU的平均使用率逐渐接近β，达到接近最优解的状态。

5.3 不同规模服务器调度问题上算法性能对比

本文在不同规模的调度问题中进行算法性能的比较。实验算法包括 OTECA、分离化差分进化算法（C-MSDE, cost modified separation differential evolution）[23]、成本时间进化算法（CT-DE, cost time differential evolution）[24]、GA[17]和 LS[18]。

择优选取 OTECA 中参数γ=1.5，Ns=300；C-MSDE中选择变异因子为 1，交叉因子为 0.5；CT-DE中Ptime=Pcost=0.5；GA中选择概率为0.2，交叉概率为0.2，变异概率为0.2；LS中搜索范围为3；C-MSDE、CT-DE、GA的种群数为300。测试使用的服务器规格数据与云计算要求数据皆从阿里巴巴公司公布的Alibaba Cluster Data V2018中抽取，测试结果如表2所示。

表2 不同规模服务器调度问题上5种算法性能对比

表 2中显示了不同规模（SSP1～SSP6）的调度问题，其中SSP1～SSP3是规模与实例数较小的服务器调度问题，SSP4～SSP6是规模与实例数较大的服务器调度问题。其中，Nm代表算法调度结果使用的宿主机服务器数量，Score代表算法所得目标分数，CPU代表调度结果平均CPU使用率，目标为50%。处理小规模问题时，进行比较的算法拥有相似的性能表现，但是OTECA、CT-DE与LS拥有较好的表现，目标分数的平均值相比其他算法优秀 1%。处理较大规模问题时，OTECA展现出比较突出的性能优势，目标分数的平均值比其他算法中最优秀的LS优秀3%。综合上述2种情况，OTECA表现更好。

5.4 5种算法在ALISS数据集上性能对比

设置算法参数与5.3节相同，以实例在宿主机服务器中的转移次数为横坐标，以分数为纵坐标，得到5种算法求解ALISS-1问题如图8所示。

图8 5种算法求解ALISS-1问题

图8中最下方的虚线为该问题的最优解。在算法的初始阶段，OTECA与C-MSDE的效率较高。随着优化的进行，目标值快速下降，GA、LS与CT-DE因优化策略原因效率较低。在优化的中后阶段，OTECA表现出了较强的调度能力与精确性，通过解决子问题，有目的地将组合不合理的机器挑选出来并进行重新组合，该操作在效果上优于基于随机迁移的GA、LS、C-MSDE等其他算法，OTECA得到的调度结果能够跳出局部最优解。

算法对服务器组负载的均衡能力是衡量算法优劣程度的重要指标，本文对于ALISS-1的求解过程绘制机器负载量直方图，如图9所示。

图9 机器CPU使用率标准差直方图

由图9可知，当实例交换次数为0时，5种算法以相同的基础进行优化。随着实例交换次数的增加，5种优化方法都能起到有效的负载均衡效果。当实例的交换次数为20 000次时，OTECA的效果最为显著，其对应的机器 CPU使用率的标准差最小，相比初始值变化的幅度是GA的2倍。随着优化的继续进行，其他算法的标准差几乎没有发生改变，而OTECA的标准差有少量提升。这是因为随着交换的进行，OTECA能够有效地减少使用宿主机服务器的数量，从而提高了仍在工作的宿主机服务器使用率的标准差。5种算法求解ALISS数据集的结果对比如表3所示。

表3中评价了5种算法在数据集上的5个指标，分别是目标分数（Score）、平均机器 CPU 使用率（CPU）、平均机器内存使用率（DISK）、平均机器硬盘使用率（MEM）、机器 CPU使用率标准差（STD）。在 7个测试数据中，OTECA表现最佳，目标分数的平均分为 6 665.70，比第二优秀的C-MSDE优秀4%。

数据问题的差异性会引起算法表现的差异，但是OTECA综合性能占有一定优势。对于ALISS-3与ALISS-4这类实例粒度较小（单个实例占用的资源较小）的问题，5种算法的表现相似。但是对于实例粒度较大的问题，GA、LS、C-MSDE与CT-DE等算法表现稍逊于 OTECA，原因是不满足约束的情况会降低上述算法的搜索效率。综合考虑上述情况，OTECA具有更加优秀的性能。

表3显示，C-MSDE、CT-DE、GA与LS这4种算法在解决有相对严格约束的服务器调度问题时没有明显优势，这是因为4种算法的解集更新具有随机性，新生成的解很容易不满足问题的约束。因此，检查新解是否满足约束与丢弃不满足约束的解花费大量的运算时间，从而大大降低了算法性能。OTECA不需要维护多个解的集合，也从不产生可能不满足约束的解。OTECA只通过求解 MIP子问题不断地对解集进行更新，因此拥有较高的效率与性能。

6 结束语

本文针对大规模云服务器调度问题进行研究。在对大规模云服务器调度问题进行MIP建模的基础上，为了解决传统方法很难及时地求解出最优调度方案的问题，本文提出了 OTECA。OTECA首先通过可行解生成算法求出可行解，然后通过在循环中不断选取与解决MIP子问题的方式优化可行解，从而得到全局调度方案。结果表明，OTECA可以快速优化大规模服务器调度方案，在测试数据集ALISS上较传统的GA、LS、C-MSDE与CT-DE算法有较大的优势。在完成相同任务的情况下，OTECA使云计算中心的资源消耗减少4%以上。

表3 5种算法求解ALISS数据集的结果对比