蚁群算法解决网格环境下任务调度问题的研究

本资料包含pdf文件1个，下载需要1积分

Research on Solving the Problem of Task Scheduling in Grid Envi-ronment by Ant Colony AlgorithmZHAo Fei，WU Hang，G0NG Yue(School of Computer Science and Technology，Changchun University of Science and Technology ，Changchun 130022)Abstract：Task scheduling in grid environment is a typical NP-hard combinatorial optimization problem，and has beenthe focus which scholars study intensely in recent years.The traditional Min-Min algorithm has the defects such aslong task completing time and poor load balance performs，therefore we propose using ant colony algorithm to solvethe problem.According tO the nature by which that ants Can always find the shortest path from the cave to the foodsource，one task allocation process is abstracted aS a path finding procedure of ants allocation and experimental simula-tion results wene obtained。

Key words：grid；task scheduling；Min-Min algorithm；ant colony algorithm 网格概念的产生是为了消灭资源孤岛” ]，利用互联网将地理位置分散的资源连成-个整体 ，从而形成-个计算能力不亚于当今世界上任何-台超级计算机的巨大网格。就连现今炙手可热的云计算，其核心思想也渗透着网格的理念。网格的任务调度问题已被证明是-个典型的NP难组合优化问题，对网格的性能产生着重要的影响，并且网格中的计算资源具有异构性、动态性和不稳定性等特点心 ，所以如何合理分配任务到网格中的各个节点使其展现出预期的性能，-直是个亟待解决的难题。

传统的Min-Min算法是目前人们研究的比较多的主流调度算法之-，具有简单高效等优点，然而Min-Min算法易产生任务完成时间长，资源负载不平衡的现象。蚁群算法是1991年由意大利人DorigoM提出的-种模拟蚂蚁觅食行为的智能启发式仿生优化算法，采用了正反馈并行 自催化机制，根据蚂蚁总能在蚁穴和食物源之间找到最短路径这-自然特性，在解决许多复杂的组合优化问题上已展现出优异的性能和巨大发展潜力口]。本文针对Min-Min算法的局限性，提出了-种应用蚁群算法解决任务调度问题的方法，将任务的-次分配过程抽象为蚂蚁从蚁穴到食物源的-次探路过程，将任务的完成时间抽象成路径长度，通过蚁群的多次探路和信息素的启发，最终找到-条较优的短路径，即完成时间较短，负载均衡性较好的任务分配方案。蚁群算法具有较强的鲁棒性，优良的分布式计算机制和可扩展性等优点。]，因此，非常适合解决网格环境下的任务调度问题。通过仿真实验表明，采用蚁群算法进行收稿日期：2012-O7-l3作者简介：赵飞 (1987～)，男，硕士研究生，E-mail：zhaofei1987gz###163.corn。

通讯作者：龚跃 (1960-)，男，教授，E-mail：Gongyue888878###sina.corn。

长春理工大学学报 (自然科学版)任务调度的网格在完成时问Ⅲ和资源负载㈨这两方面都好于Min-Min算法。

1 问题描述网格任务调度问题的形式化描述如下：假设有- 个规模很大的作业 ，网格 自动将其分割为 个相互独立的子任务去分配执行，且任务之间没有次序依赖关系(这里作业在网格中是怎样被划分的不在我们讨论范围之内)。网格环境由m个节点构成 ，节点问的效率相差不应过于悬殊(当然有-定的差别是正常的，符合真实的网格情况)，否则任务都将集中分配到效率最高的节点上去执行以争取最短的完成时间，失去网格应有的意义。任务的分配结果可以构造为-个大小为m× 的矩阵尺 。R 1，表示将任务 J交由结点i处理，R ：0表示任务 ，不由结点i处理。这里，-个任务只能由-个节点处理，-个节点可以依次处理0到多个任务。同时，有-个大小为 ×72的预期处理时间矩阵 尺 ， ，表示节点 执行任务 的预期处理时间。

则网格任务调度问题的约束条件为： oRl尺 o(-个节点依次完成O到多个任务)R ：1(-个任务由-个绐点完成)其中，fl，2， ；J1，2， 。

目标函数是网格处理所有任务所花费的时间卅 ”makespan： (Rogj) (1)， 1要使makespan为最小值，即最优跨度(网格完成所有任务的最短执行时间)。

2 Min-Min算法解决任务调度问题的局限性Min-Min算法通过两次最小值的计算来完成任务的启发式分配。该算法首先在待分配的任务集合中分别计算出每个任务的最短完成时间并记录相应节点。调度时，从任务最短完成时间列表中选择值最小的任务分配到对应的节点上，同时从任务集合中删除该任务，并更新最短完成时间列表。然后开始新的调度，重复上述过程，直至任务集合为空。

以下用-个实例来说明Min-Min调度算法的局限性。假设共有3个任务t ，t2 t。需要分配到两个0 1 o ]节点 r。上去执行，敦阵为： 3l 。 I，每个节点的等待就绪时间初始为0，因此预期完成时间矩阵EcTz s丁2 sl 2 24 暑6。计算出每个任务完成时间最短的节点集合，并从中选择值最小 的任务 2分配给节 点 1，得到任务分配矩 阵R ×3 Lo l，更新ECT矩阵EcT2lX32 1 2 l，以此类推，最终得到分配结果矩阵R2×3 l 10 l。从本例中可以看出，三个任务全部集中分配到节点 r 处，资源负载严重不均衡 ，因为任务都全部分配到-个节点上去处理，根据公式(1)，makespanmax(1×61×21×18，0×120×40×36)26，所以makespan并不为最优跨度。

3 用蚁群算法解决任务调度问题3.1 解决问题思想任务分配问题是-个组合优化问题。如2中例子所示，假设网格由m2个节点组成，现有 3个任务需要处理。则任务分配的所有情况可以看成是-颗深度为nl的m叉树上的所有叶子结点。如图1所示 ：l 1 o0]20] JIo lf1 0D] io 0oJ、 1r0 01 1 1图1 节点数m2，任务数n3的网格任务分配树从图l可以看出网格任务分配树边带权 ，权值跟预期处理时间矩阵尺 中的元素--对应。

其中树根节点可以看成是蚁穴，叶子节点可以看成是食物源，蚂蚁从-个节点移动到它的某个孩子节点需要花费时间代价 根据蚁群算法原理，蚂蚁总能从蚁穴到食物源之间找到-条最短路径。路径最短即花费的时间代价makespan最小(最优跨度)，因此，能够同时避免任务过于集中到某个节点上造成不必要的时间花费。蚂蚁的-次寻路过程即是任务的-次分配过程，蚂蚁从蚁穴到食物源需要走步们，。 。 m 。

第 l-2期 赵飞，等：蚁群算法解决网格环境下任务调度问题的研究3.2 算法实现根据前面分析，首先建立3个数据集 ：(1)节点集 Nodenode1，node z..node.node ，表示 网格环境由 m个节点组成。(2)任务集 Tasktask ，task2taskjtask.，表示有n个子任务需要调度处理。(3)禁忌表tabu 记录第 只蚂蚁遍历时已分配的任务。

存储有4种类型的矩阵：(1)信息素矩阵 ，初始时 为常量 P，用来存储蚂蚁遍历时所留下的信息素。(2)预期处理时间代价矩阵 。(3)效率矩阵E ，E ，1/ 。(4)第k只蚂蚁遍历后的分配结果矩阵 R ，初始 R o。蚂蚁遍历图1中的网格任务分配树时，按照概率 选择下-条要走的路径，即P 表示第k只蚂蚁遍历时将第 个任务分配给第个节点的概率。

//第3步：更新任务分配结果矩阵Rmxn求 出 代 价 向 量 makespanC中 最 小 的makespanfcif(NclI makespanfc

为了检验算法的性能，本文采用了C编程语言在VC6.0平台下进行了实验仿真模拟。得到了如下实验结果 ：实验1：将5个任务分配给3个节点。设计预期r2 4 8 l6 32]处理时间矩阵T3 5l4 8 16 32 64 I，对于任 Ls 16 32 64 128J务的最终分配结果，用网格中节点的最高负载数highest减去最低负载数lowest来作为衡量网格负载是否均衡的-个指标，如果差值(0 highest-lowest≤ )越小 ，表示任务越平均地分配到各个节点上 ，负载均衡性越好；反之，负载均衡性就越差。此例中，已知网格任务分配的最优跨度makespan最优36。采用Min-Min算法(这里忽略任务分配的先后顺序，只考虑任务最终的分配结果，因为我们关心的只是完成所有任务的时间和节点的负载情况)得到厂1 1 l 1 1]的分配结果矩阵为R3 5：l0 0 0 0 ol，网格处 f)0 0 0 oJ理所有任务所花费的时间根据公式1得makespan-i-In62，highest-lowest5-05。使用蚁群算法ACA(Ncmax100，Q100， 3， l，M-ANT10， ID ：0.05) 得 到 的 分 配 矩 阵i)l 0 0 1]R3 5l1 0 O 1 0l，makespanAcA36，high Lo 0 1 0 0jest-lowest2-1l。在实验l中可以发现蚁群算法无论是在任务的完成时间还是负载均衡性这两方面都明显优于Min-Min算法。

100 长春理工大学学报 (自然科学版) 2013年实验 2：设计-个由3个节点组成的网格环境 ，其中第-个节点是第二个节点执行效率的两倍，是第三个节点效率的三倍。这种现象的产生是合理的，可以理解是由各个节点CPU性能的差异所造成的。共有 9个任务需要分配，任务分配给节点-的处理时间在1到100之中随机产生，分别用蚁群算法和Min-Min算法进行仿真模拟，得到表1。

通过多次仿真实验进行数据对比，由表1可知，采用蚁群算法进行任务调度的网格作业完成时间比Min-Min算法需要的时间短，并且负载均衡性更好。

5 结束语本文在详细分析了Min-Min任务调度算法的基础上，针对其自身的缺陷，提出了应用蚁群算法解决任务分配问题的方法〃立了数学模型并使用C语言在vc6.0平台上编写程序进行仿真模拟，实验结果表明蚁群算法能够有效的缩短作业的完成时间，改善网格环境中节点的负载均衡性，提高了资源的利用率。