面向行政管理系统的任务调度算法研究

唐月霞

（上海市奉贤区中心医院信息管理和统计处 上海201499）

面向行政管理系统的任务调度算法研究

唐月霞

（上海市奉贤区中心医院信息管理和统计处 上海201499）

为了更好地解决云计算在行政管理系统任务调度交互数据量大的问题，本研究在综合遗传算法与退火算法的优点基础上提出了一种遗传退火混合算法。该算法针对行政管理系统中的任务调度数据关系特点，在云计算环境下对执行任务进行整数编码，通过遗传算法的适应度函数对任务数据进行全局最优解的搜索，任务数据的编码交叉重组过程中，利用退火算法调整适应函数的方式加快系统虚拟机对任务调度的完成时间。实验表明，该任务调度算法适应度值高于传统遗传算法且具有较强的搜索能力和收敛性。

任务调度；行政管理；遗传算法；退火算法

目前大部分部门的电子行政管理系统对信息化的交流仅利用基础平台的发布，封闭的系统结构使得信息资源难以高效的共享[1]。行政管理系统的任务调度利用数据在系统中的业务传输为电子行政发展带来了契机[2]。由于目前已有的行政系统偏重于工作流程的建模，让用户群体容易忽略任务调度的重要性[3]。调度策略的优先级关系到电子行政系统的整体业务工作，将有限的信息资源进行整合与挖掘对提高工作流程效率起到至关作用[4]。本研究在简要分析行政管理系统环境的基础上，将数据资源与任务相结合、遗传算法与退火算法相结合，提出了一种面向行政管理系统的任务调度算法。该算法依据任务调度数据特点进行整数编码完成动态规划模型，通过遗传算法的适应度函数对任务数据进行全局最优解搜索，并结合退火算法调整适应函数以降低时间复杂度。

1 行政管理系统任务调度

1.1 行政管理云任务

在行政管理系统的环境下进行任务的调度，其任务的实质就是将相互之间存在关联的Z个任务在R个资源上进行平行高效的处理与执行[5]，在任务调用的同时还需要满足占用带宽、数据可靠性、实际投入经费、任务调度所分配时间的约束[6]。在行政管理系统中进行任务调度可具体描述如下：当可用资源数量为R时，其所对应的集合为Q={q1，q2，…，qr}；在进行任务调度的过程中，系统操作者提交任务的数量为G，其所对应的集合为N={N1，N2，…，Ng}；同时将G个任务划分为Z个分区任务，其所对应的集合为Y={Y1，Y2，…，Yz}，换而言之即第Ng个任务将会被配分为Ynum（Ng）个任务，则G个任务经过划分之后所对应的任务总数为：

1.2 算法操作

本研究在行政管理体系的任务调度过程中引入了模拟退火算法以及遗传算法，通过将两者的结合，使得模拟退火算法的优点充分的发挥出来，同时将推进任务调度的进程并且提高整体协作的效率。所谓的模拟退火算法即在初始温度较高的条件下，当环境的温度参数缓慢下降时，出于概率突跳的特性，算法将在求解的空间内随机寻求目标函数的最优解的过程[7]。而遗传模拟算法的初始条件产生于一组随机的初始解，通过选择、交叉、变异等一系列的遗传程序产生新的个体，并针对产生的每个新的个体来模拟退火过程，通过这样的过程将结果遗传给下一代群体中的个体，从而实现目标函数最优解的求解过程[8]。在本文中将模拟退火算法和遗传算法相结合，其具体的步骤如下：

步骤1：当初始温度为tk时，对进行过选择、交叉、变异等一系列的遗传程序的种群个体分别测算其适应度值。

步骤2：针对测算出的亲代染色体的适应度值进行比较，同时参照Metropolis准则对遗传程序后得到的个体进行接受选择。

步骤 3：设 tk+1=αtk，其中t表示温度衰减函数，α表示其中的参数，同时还需要对迭代次数进行更新。

步骤4：由于控制参数的衰减量将会影响到迭代次数的选取，因此在此步骤需要先确定衰减函数。

步骤5：为了使得控制参数的每个取值在行政管理系统中保持相对的稳定，设定的迭代次数不宜取太小的值。

步骤6：针对当期啊种群的每个个体计算其适应度值，直至满足终止条件。

2 遗传-退火算法

2.1 编码与解码

在行政管理系统中进行任务调度时引入的模拟退火算法以及遗传算法，通过对种群的规模选取实现对遗传算法收敛性的影响。种群规模出于太小或是太大的状态下都会对整体的算法运行性能产生影响。根据前人研究经验[9]，本文将种群的规模设定在20～175之间。随机设定染色体长度为m，基因在[1，n]的区间内随机取值。同时假设行政管理系统的环境中存在5个虚拟机，18个任务，即R=5，G=18，赋予每个基因个体一项任务，基因值与赋予的任务虚拟机编号相对应，其通过遗传程序所产生的染色体为：P0=[1，3，5，1，2，4，2，1，2，5，1，2，4，2，5，1]。为了得到虚拟机的排列，需要对上述的染色体进行解码，具体排列如下:

通过利用ETC矩阵[10]以及染色体解码后的序列测算出计算出每个任务Ng在被调用时的占用带宽、数据可靠性以及实际投入经费、任务调度所分配时间等。系统的操作人员对任务操作时间的需求可具体划分为完成时间、起始时间、最终完成时间等。本文将选取任务的总体完成时间作为行政管理系统下任务调度的时间需求评判标准，每项任务Ng的总完成时间为：

即直到任务Ng中的最后一项分项调用完成时间所需要的总的时间，tETC（i，j）表示在第i个任务的时间节点上处理调用第j个任务完成所需要的时间。总的任务完成时间为：

2.2 适应度选择

遗传算法主要通过以适应度函数为工具对下一代的进化选择来寻求最优解从而解决问题。遗传算法调用任务的收敛速度以及求得的最优质量如何将与适应度函数的选择息息相关[11]。调度任务还需要满足系统操作人员对服务质量的多样化要求，这也导致了过去的遗传算法适应度函数目标单一，因此将不再适合行政管理系统的环境下的任务调度[12]。在行政管理系统的环境中，系统操作人员用服务质量QoS的评价标准来对服务的满意程度进行评价[13]。在适应度函数指标选取方面，文中选取带宽、数据可靠性、实际投入费用、任务总完成时间等不同的目标来衡量满意程度，行政管理系统任务调度的适应度函数表述如下：

其中，wi（i=1，2，3，4）表示由不同指标构成的需求偏好函数的权重函数，其主要用来对行政管理系统的操作人员对行政管理系统操作的满意程度。WTime表示任务的总体完成时间的用户满意度函数，WBW表示任务调用过程的实际投入费用用户满意度函数，WCost表示任务调用的占用带宽用户满意度函数，WSucc表示数据的可靠性的用户满意度函数。Ag表示任务Ng的实际资源消耗量，Eg表示系统操作人员预期资源消耗量，因此任务Ng的操作人员满意度函数表述为：

一般情况下当实际资源消耗同系统操作人员的资源消耗量预期差距越小时，系统操作人员的满意度则越高，即适应度函数的值趋向于0。实际资源消耗量大于系统操作人员的资源消耗预期，则Wi＞0，实际资源消耗量大于系统操作人员的资源消耗预期，则Wi＜0[14]。利用texpt表示的系统操作人员预期的任务Ng完成时间，Bwm表示行政管理系统环境下的资源带宽，Buser表示系统操作人员指定项目Ng的预期带宽，Bi表示任务Ng所划分的任务Yg的带宽。任务调用后的数据可靠性选取任务的完成率表示[15]。假设行政管理系统环境下的资源出现故障的概率为P，而系统操作人员的任务完成率为Psucc。则任务Ng的总完成时间系统操作人员满意度函数、任务调用占用带宽和任务可靠性的系统操作人员满意度函数如下：

实际投入的费用是服务质量QoS最流行的约束之一，在行政管理系统环境下系统操作人员根据去要的服务进行付费。对于任务Ti的总费用，利用Cuser表明系统操作人员的费用预期，实际投入费用的操作人员满意度函数Wcost可根据自然界优胜劣汰的法则从新的个体中选择适应度最高的进行遗传操作，对于适应度为fi的种群中的染色体个体进行选择概率Qi计算，具体的表达式如下：

其中，Pg（g=1，2，3，4）为各项资源的数量，Ccpu表示CPU的价格、Cmem表示内存的价格、Cstor表示存储器的价格、CBW表示带宽资源的价格。

2.3 交叉与变异

遗传算法中的交叉操作实际上是在模仿自然界的基因繁殖重组的过程，这样的编码交叉重组过程与染色体的交叉重组类似，在这样的过程中容易产生优良基因的染色体。在这样繁衍的过程中对两个子代个体的约束进行检验，当这样的约束条件无法满足时将其舍弃，而对两个亲代个体进行重新的交叉操作，这样的过程持续到交叉产生出两个子代个体满足约束条件为止。变异和交叉的自适应调整概率函数公式如下：

在上式的表达中，fmax表示种群中的适应度的最大值，favg表示种群的平均适应度，f*表示交叉个体中适应度较大的值，f表示未变异个体的适应度的值，Pc1，Pc2，Pm1和 Pm2表示非 0的自然数。 按照顺序交叉法的进行遗传交叉操作，假设两个父代个 体 ：P1=[2，3，3，4，2，3，4，3，4，2，1，1，3，2，1，4]和P2=[1，2，3，4，3，2，3，4，2，4，2，1，3，4，1，2]。

假设通过随机投点的方式投到第3个基因，则P1基因串为 tP1=[4，2，1，1]，P2的基因串为 tP2= [2，3，1，4]。通过在P1中依据顺序查找tP2中的各基因值并向前移位取得新个体，nP1= [2，3，1，4，2，1，1，4，2，3，4，1，2，3，4，1]。同理，通过在P2中依据顺序查找tP1中的各基因值并向前移位取得新个体，nP2=[4，2，1，1，2，3，1，4，2，3，1，4，1，1，3]。

遗传算法中的变异操作是按照编码的概率类似于基因突变的概率扰动变化的，一般采用随机取点的方法[16]，其整数取值范围为[1，m]。假设选取父代个体P1变异操作，当随机投点至第6个基因时，选定的基因值为3，在[1，4]范围内随机取不等于3的数，假设随机数取值为2，则对P1进行变异后得新个体nP1=[1，2，3，1，2，3，2，1，2，3，1，3，1，2，4，1]。

3 仿真模拟

实验所选取的模拟仿真平台为Matlab，同时以Ant软件为工具对CloudSim进行了重新的编译，此外在扩展的平台上将改进的模拟退火算法与遗传算法进行比较。最先对传统遗传算法和遗传模拟退火算法的系统操作人员的满意度程度进行比较。本文的实验参数如表1所示。

表1 参数设置

针对本研究中的行政管理系统的任务调度算法问题，目标函数考虑虚拟机在109指令/秒，对于任务调度分配时间、实际投入经费、占用带宽和任务长度分别为70 s、40 000、100 Mb和1010指令。为了研究不同的加权值对任务调度结果满意度的影响。因此，通过对不同的目标加权值变化设定5组实验，其中1～4组实验分别研究一个加权值对任务调度结果满意度的影响，第5组实验作为对比项。具体的权值设置如表2所示。

表2 实验权值设置

每组实验进行10次，每次实验模拟对70 s内的任务调度指令进行分配，根据调度结果计算平均每个任务调度需要分配的用户满意度。本研究提出的针对行政管理系统的任务调度算法利用遗传算法与退货算法相结合的方式，适应度反映用户对任务调度结果的满意程度。当适应度等于、大于和小于0时，分别代表着任务调度结果与工作人员的期望值相同、偏高和偏低。对于任务调度结果要高于或等于工作人员期望值才可以满意日常行政管理系统的正常运行。因此，将本研究提出的遗传退火混合算法与传统遗传算法的适应度进行对比，即对比行政管理系统工作人员的期望值。结果如图1所示。

图1 满意度对比

由图1可见，本研究提出的遗传退火算法的适应度高于传统的遗传算法，即可以更好的为行政管理系统的用户服务，遗传退火算法满意度平均值比传统遗传算法高8%。为了考查任务调度算法在计算上的效率和实际应用的效果，继续考查针算法的任务调度分配时间和实际投入经费与任务数量的关系。结果如图2所示。

图2 时间与花费对比

由图2（a）实验结果表明，遗传退火算法在任务调度执行总完成时间上相比传统遗传算法具有明显优势，随着任务个数的增加调度时间差距愈明显；在图2（b）中，在任务花费的比较上，遗传退火算法随着任务数量的增多优势越明显，整体平均实际投入经费比传统遗传算法少3 863。在处理60个任务调度时，遗传退火算法完成时间比传统遗传算法少410 ms，实际投入经费少2 888。

4 结 论

本研究针对行政管理系统的任务调度特点，利用遗传算法与退火算法相结合的方式提出了一种面向电子行政管理系统任务调度的混合算法策略。该算法策略将遗传算法的适应度函数应用到电子行政管理系统工作人员对任务调度的满意度中，并且通过退火算法调整适应度函数加快了算法的最优解搜索能力。该混合算法能够反映任务调度与执行时间、任务花费的关系，可以更加全面的评估行政管理系统。通过仿真模拟结果表明，本研究提出的任务调度算法满意度高于传统遗传算法，即更符合实际电子行政管理系统的使用，并且任务调度分配时间和实际投入经费明显低于传统遗传算法。该算法为行政管理系统下任务调度问题提供了更加便利的解决方案。

[1]蔺豆豆，张锐昕.电子行政审批系统的多元需求及其满足——以吉林省气象局为例[J].电子政务，2014（9）:77-83.

[2]曹洁，曾国荪，钮俊，等.云环境下可用性感知的并行任务调度方法[J].计算机研究与发展，2013，50（7）:1563-1572.

[3]陈英武，邢立宁，王晖，等.网络环境下社会管理的组织行为建模与计算实验研究综述[J].自动化学报，2015，41（3）:462-474.

[4]贾林.一体化视频会议管理系统应用研究[J].现代电子技术，2015（1）:122-124

[5]刘少伟，孔令梅，任开军，等.云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J].计算机学报，2011，34（11）:2121-2130.

[6]李文娟，张启飞，平玲娣，等.基于模糊聚类的云任务调度算法[J].通信学报，2012（3）:146-154.

[7]傅文渊，凌朝东.布朗运动模拟退火算法[J].计算机学报，2014，37（6）:1301-1308.

[8]马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）:1201-1206.

[9]李强，郝沁汾，肖利民，等.云计算中虚拟机放置的自适应管理与多目标优化 [J].计算机学报，2011，34（12）:2253-2264.

[10]邹伟明，于炯.云计算环境下基于用户满意度的遗传算法[J].计算机应用研究，2014，31（1）:85-88.

[11]杨水清，杨加明，孙超.改进的乘幂适应度函数在遗传算法中的应用 [J].计算机工程与应用，2014，50（17）:40-43.

[12]李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31（1）:184-186.

[13]祝家钰，肖丹，王飞.云计算下负载均衡的多维QoS约束任务调度机制[J].计算机工程与应用，2013，49（9）:85-89.

[14]徐达宇，杨善林，罗贺.云计算环境下多源信息资源管理方法[J].计算机集成制造系统，2012，18（9）: 2028-2039.

[15]赵新超，吴召军.求解背包问题的多位极贪婪遗传算法[J].广西师范大学学报：自然科学版，2013，31（4）:41-47.

[16]弭宝福，徐梅，王福林，等.交叉概率对遗传算法运算速度影响的测试与分析[J].数学的实践与认识，2013，43（22）:215-218.

Research on task scheduling algorithm for system of administration

TANG Yue-xia
（Shanghai Fengxian District Centeral Hospital，Ministry of Information Management Sum Statistics，Shanghai 201499，China）

To better address the cloud computing system administration task scheduling problem of large interactive data，this study based on the advantages of integrated genetic algorithms and annealing algorithm presents a genetic annealing hybrid algorithm.The algorithm for the administrative task scheduling system characteristic data relationships in a cloud computing environment to perform tasks integer coding genetic algorithm fitness function of task data to search the global optimal solution，coding task data crossover recombination process，using annealing algorithm to adjust the adaptive function of the ways to speed up the system on a virtual machine task scheduling is complete. Experiments show that the task scheduling algorithm fitness value is higher than the traditional genetic algorithm and has a strong search ability and convergence.

task scheduling；administration；GA；annealing algorithm

TN876.2

：A

：1674－6236（2017）06-0009-05

2016-08-19稿件编号：201608146

唐月霞（1982—），女，上海人，助理工程师。研究方向：信息管理。