面向分布式环境的信号驱动任务调度算法

辛宇，杨静，谢志强

（1. 哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001；2. 哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨 150001）

1 引言

随着云计算技术的迅猛发展，云计算技术可将计算、存储、软件、服务等资源从分散的个人计算机或服务器移植到互联网环境中，以集中管理大规模高性能计算机、个人计算机、虚拟计算机，从而方便用户使用云资源。从层次上云计算平台可以分为以下3种服务模型：软件即服务(SaaS, software as a service)，平台即服务(PaaS, platform as a service)，基础架构即服务(IaaS, infrastructure as a service)。

目前 IaaS模型是当前最重要的云平台模型，IaaS的意义在于，用户可通过云接口利用IaaS云服务提供商所提供的 IT设备资源运行所需应用，且无需考虑硬件的维护及更新[1]。IaaS的技术核心是硬件虚拟化，通过利用虚拟化技术，把物理主机的各种硬件整合起来，屏蔽其硬件的物理细节，以资源池的概念统一代表物理硬件，保证资源的可定制能力和统一分配能力[2]。目前，有很多企业和科研机构推出了自己的IaaS云计算平台，面向用户提供计算资源和存储资源。最具代表性的是亚马逊(Amazon)的弹性计算云(EC2, elastic compute cloud)[3]，它通过Web服务的方式让用户弹性地运行自己的Amazon机器映像，用户可以在自己申请的虚拟机镜像上运行任何自己所需的软件或应用程序。同时，还有一些开源 IaaS云计算平台：与EC2兼容的云平台Eucalyptus (elastic utility computing architecture for linking your programs to useful systems)[4]，美国国家航空航天局和Rackspace合作研发的OpenStack[5]以及中科院的LingCloud[6]等。

IaaS通过虚拟设备实现用户的服务，IaaS在进行虚拟设备管理时，将一台物理设备划分为多台独立的虚拟设备，各个虚拟设备之间能进行有效的资源隔离和数据隔离；由于多个虚拟设备共同享一台物理设备的物理资源，能够充分复用物理设备的计算资源，提高资源利用率。IaaS将云环境中的所有物理设备资源转化为对用户透明的统一资源池，并能按照用户需求分配不同性能的虚拟设备。IaaS模型的框架体系如图1所示，其中用户的服务请求通过Scheduler模型进行虚拟设备的任务分配。

图1 IaaS的拓扑结构

为提高资源分配及数据处理的效率，近些年来面向IaaS的虚拟设备资源调度问题逐渐成为学术研究的重点，其研究内容主要包括任务分配调度和数据传输调度。在任务分配调度方面，主要研究内容是处理用户的任务分解及分配，对此Marcos等对IaaS模型的调度模块设计了6种面向弹性计算云(EC2)的兼容策略，并提出了 cloud schedule和sub-schedule两级调度模式，分别从宏观和微观角度进行任务分配优化[7,8]；在数据传输调度方面，主要研究内容是根据数据的分布式存储特性建立以通信损耗化及数据时效优化的调度策略，对此Nan等[9]提出了cost model及queuing model模型，构建了多媒体数据的传播评价方法，并设计了以多媒体数据传输QoS优化为导向的云资源分布调度算法，Kllapi等[10]建立了流式数据的 split、compute和 merge过程，实现了分布式数据流的传输调度。为统一IaaS分配和数据传输的调度模型，Lin等[11]根据虚拟机的处理能力及网络的数据传输能力，将功能和位置相近的虚拟机划归为cluster单元，从而将IaaS模型的调度问题转化为DAG(directed acyclic graph)调度优化问题，统一了IaaS任务调度模型。

目前可面向IaaS模型的DAG调度算法主要分为以下5类。

1) 权值选择算法。如HEFT[12]、ACPM算法[13]等，此类算法是早期DAG调度的主要算法，其实现原理是根据DAG的结构关系预先计算各个任务分片的EFT(earliest finish time)，以确定任务分片的先后关系。

2) 层次优先选择算法。如 PCH(path clustering heuristic)[14]、优先工序集调度[15]等，此类算法以最大化同一层任务分片的并行处理为手段，将任务分片的层数作为优先级，以确定任务分片的调度次序。

3) 堆栈式回退算法。如 HEFT-lookahead[16]、回退抢占算法[17]等，此类算法考虑了后续调度中空闲时段被占用的情况，当出现预先计算的EFT与实际的结束时间偏差较大时，采用重定向的方式回退前续调度任务分片。

4) 路径聚合算法。如HH(hybrid heuristic)[18]、动态关键路径法[19]等，此类算法考虑优先调度关键路径上的任务分片，增加关键路径上任务分片的优先级，从纵向角度优化调度结果。

5) 启发式优化算法。如遗传算法[20]，粒子群算法[21,22]等，此类算法通过建立代价函数对调度结果进行局部优化，建立并利用循环选择策略逐步保留局部优化结果，从而实现全局调度优化。

为实现高效处理用户IaaS任务请求，本文设计了一种基于信号驱动的DAG调度算法，由于采用了信号驱动的形式，可使算法结合权值选择算法、层次优先选择算法和路径聚合算法的特点，即在每一调度时刻根据任务分片的纵向权值进行横向并行优化选择，从而实现了DAG任务分片的纵横双向筛选，使调度过程更加合理化。另外，该算法由于回避了堆栈式回退算法的重定向操作，以及层次优先选择算法和路径聚合算法的预调度操作，因此，算法的复杂度较低(约为O(nlog(n)))且优于传统DAG调度算法，更适于应对云计算环境中的海量任务请求问题。

2 IaaS模型的DAG调度问题分析

根据 IaaS模型的分布式特性和虚拟设备的异构特性，IaaS任务以分片的形式进行调度且各任务分片之间满足以下约束[7,20,21]。

1) IaaS任务具有唯一的起始任务分片（DAG入口节点）和唯一的终止任务分片（DAG出口节点）。

2) 某一任务分片仅在满足其要求的虚拟设备中执行，且满足同一任务分片要求的虚拟设备不唯一，任务分片在各虚拟设备中的执行时间已知。

3) 任一虚拟设备在同一时刻只能执行同一任务的一个任务分片。

4) 任务分片vi的紧后任务分片vj需要等待vi执行完毕后的通信数据，若vi与vj在同一虚拟设备中执行，则通信时间为0。

5) 每一任务分片必须在其前任务分片均执行完毕，并收集到所有前序任务分片的通信数据时才可开始执行。

可根据IaaS模型的任务约束建立DAG调度模型，其符号描述如下。

1) DAG模型以图G=(V,E)表示，G表示某一任务，V={v1,v2, …,vn}表示任务G的任务分片集合，其中n=|V|为任务分片的个数。

2)D={d1,d2, …,dm}表示虚拟设备的集合，其中m=|D|表示IaaS模型中虚拟设备的个数。

3)ci,j表示虚拟设备di到虚拟设备dj的通信代价。

图2为某任务的DAG结构模型，其中节点表示任务分片，节点1和节点8为起始任务分片和终止任务分片，有向边表示任务分片的有序关系，其权值代表任务分片间的通信代价，表1为任务分片在各虚拟设备中的执行时间。

图2 DAG结构模型

表1 任务分片执行时间

3 IaaS调度系统设计

3.1 系统结构设计

定义1任务完毕信号(Sig_F)：NS在任务分片执行完毕时向CS发送的反馈信号。

定义2数据传递信号(Sig_T)：CS在分配任务分片时向NS发送的通知信号，该信号包含通信数据的源虚拟设备ID和目标虚拟设备ID。

定义 3任务分配信号(Sig_A)：CS在分配任务分片时向NS发送的通知信号，该信号包含被分配的任务分片ID及虚拟设备ID。

定义 4就绪信号(Sig_R)：NS在某一任务分片集齐所有所需的通信数据时向CS发送的信号。

图3为CS和NS的信号交互过程示例，图中CS包含了3个任务分片(vi,vj,vk)，NS包含了3个虚拟设备(d1,d2,d3)，vi、vj、vk分别在d1、d3、d2中执行，实箭头和虚箭头分别表示信号交互和数据传递，序号标识了CS与NS的信号先后次序，分别表示为：①任务分片vj在d3中执行完毕时，NS向CS反馈信号；②任务分片vi在d1中执行完毕时，NS向CS反馈信号；③CS通知d1和d3向d2传递数据；④NS内部的数据传递；⑤d2在集齐所需的数据时向CS反馈信号；⑥CS通知NS在d2中执行vk；⑦任务分片vk在d2中执行完毕时，NS向 CS反馈信号。

3.2 系统状态分析

每一任务分片的运行过程中均会经历 4种状态，各状态的定义如下。

定义 5接收数据状态：某一任务分片的任一紧前任务分片执行完毕时所处的状态。

图3 CS和NS信号交互

定义 6就绪状态：某一任务分片在接集齐所有所需的通信数据时所处的状态。

定义 7执行状态：某一任务分片在开始执行时所处的状态。

定义 8完毕状态：某一任务分片执行完毕时所处的状态。

虚拟设备会经历2种状态，其定义如下。

定义 9忙碌状态：某一虚拟设备执行任务分片时所处的状态。

定义10空闲状态：某一虚拟设备无任务分片执行时所处的状态。

图4为任务分片和虚拟设备的状态变化示例，该示例直观表示了任务分片和虚拟设备在运行过程中的状态变化关系，图中右(左)侧虚框表示某一任务分片vi在某一虚拟设备dj中执行(完毕)时，vi和dj的状态同时变化。其中，信号起到信息传递及驱动状态转化的作用。

3.3 调度系统优化分析

由于各任务分片的执行时间和各虚拟设备的数据传递时间均为已知，因此任务的寻优过程是静态过程，可向所有的虚拟设备发送Sig_A作寻优假设，具体的优化方案如下。

1) 当某一任务分片vi的任一紧前任务分片执行完毕时(此时变为接收数据状态)，CS向NS发送m个不同目标虚拟设备ID的信号Sig_T，为vi预分配所有m个虚拟设备。

2) CS建立任务分片就绪表(RT)，记录任务分片在不同虚拟设备中变为就绪状态的时刻。

3) NS建立虚拟设备空闲表(DT)，记录任一虚拟设备下一次变为空闲状态的时刻。

4) 由于RT和DT会随CS和NS的状态变化而变化，当RT或DT发生变化时利用current记录当前时刻，并利用下一节描述的并行优化选择策略进行任务分片的选择。

图4 任务分片和虚拟设备的状态转化

4 并行优化选择策略

任务分片的执行需具备 2个条件：1) 任务分片处于就绪状态；2) 虚拟设备处于空闲状态。为此本文所提出的并行优化选择策略以RT或DT的更新作为一次任务分片分配的时刻，为处于就绪状态的任务分片分配空闲虚拟设备，将该时刻定义为调度时刻。

由于当某一任务分片变为接收数据状态时，CS会向NS中所有的虚拟设备发送Sig_A，因此当调度时刻来临时，就绪的任务分片与空闲的虚拟设备间会存在多对多的关系，为实现任务分片与虚拟设备的一对一执行关系，本文在调度时刻利用如下策略为空闲的虚拟设备分配执行任务。

1) 利用 HEFT算法[12]计算就绪任务分片的rank值，rank值最大者优先选择空闲虚拟设备，HEFT的计算公式为

其中，succ(vi)为任务分片vi的紧后任务分片的集合，wi为vi在各虚拟设备中执行时间的均值，当vi为终止任务分片时ranki=wi，表2为图2实例的rank值。

表2 图2示例的rank值

2) 计算就绪任务分片在每个虚拟设备的执行完毕时刻，选择执行完毕时刻最小者作为该任务分片的执行虚拟设备。

3) RT和DT中的最小值为下一个调度时刻。

表3记录了图2示例的调度优化过程，表中各行记录了各调度时刻RT与DT的变化过程，2列和3列为调度之前RT与DT的内容，4列和5列为调度之后RT与DT的内容，第6列为预算出的下一调度时刻，如2列和3行可表示为：当current为17 时，d1、d2、d3均空闲且v2、v3、v4、v5均只能在d1中执行，此时利用优化选择策略选择在d1中执行v2，RT和DT中的最小值为30，即为下一个调度时刻；当current为30时，仅d2,d3空闲且v3和v5只能在d1中执行，因此无法调度v3和v5，又由于此时v4可在d2,d3中执行，此时利用优化选择策略选择在d2中执行v4，并计算下一调度时刻为33。在RT表格中R表示在当前时刻任务分片vi可在dj中执行，即dj在当前时刻已集齐了vi所需的数据，DT记录了虚拟设备所执行的任务分片及执行结束时间。任务分片的调度结果如图5所示。

5 算法设计及复杂性分析

5.1 调度算法设计

通过以上分析，在以下2种情况发生的时刻，可作为调度时刻：①NS在任务分片执行完毕时，通过改变DT内容的同时驱动CS改变RT的内容；②当某一任务分片变为就绪状态时，CS改变RT的内容。本节通过分析CS和NS内部运行机制，从全局角度设计调度算法。

1) 信号设计。根据CS和NS的运行机制，设计了信号Sig_A、Sig_T、Sig_R和Sig_F进行数据通信与执行任务分片的交互，其中，Sig_T和Sig_R用于数据通信的交互，Sig_A和Sig_F用于执行任务分片的交互，4种信号的说明如表4所示。

2) NS内部运行算法。

①NS等待CS传来的信号；

②若CS传来的信号为信号Sig_T则转③，若为信号Sig_A则转④；

③此时说明CS需求Sig_T->D_ID接受数据，NS驱动虚拟设备Sig_T->S_ID向虚拟设备D_ID传递数据，并转⑤；

④此时说明CS需求Sig_T->D_ID执行任务分片，任务分片Sig_A->partition在Sig_A->DB_ID中执行，转⑥；

⑤当任务分片vi在虚拟设备dj中变为就绪状态时(即此时dj已接收到所有所需的数据)，向 CS反馈信号Sig_R(Sig_R-> partition=vi, Sig_R->DB_ID=dj)，此时利用Sig_R向CS报告虚拟设备dj可执行调度任务，转①；

⑥当任务分片vi在虚拟设备dj中执行完毕时，向CS反馈信号Sig_F(Sig_F->partition=vi，Sig_F->DB_ID=dj)并更新DT，若vi为终止任务分片则转⑦否则转①；

⑦结束。

表3 图2示例的rank值

图5 图2示例的调度结果

表4 信号说明

3) CS内部运行算法。CS内部在RT和DT的内容变化时(收到Sig_R或Sig_F时)，利用并行优化选择策略对就绪任务分片进行分配，其运行机制如下：

①等待NS传来的信号；

②若为Sig_F则转⑥，若为信号Sig_R转③；

③根据Sig_R->partition和Sig_R->DB_ID更新RT；

④利用并行优化选择策略对处于就绪状态的任务分片进行调度；

⑤任务分片vi在虚拟设备dj中执行，向NS反馈信号 Sig_A(Sig_A->partition=vi，Sig_A-> DB_ID=dj)，驱动NS执行任务vi，若vi为终止任务分片则转⑦否则转①；

⑥向NS反馈信号Sig_T(Sig_T->S_ID =Sig_F->DB_ID，Sig_A-> DB_ID=所有虚拟设备ID)，对执行完毕的任务进行后续执行的数据传递，转①；

⑦结束。

图6为CS与NS算法流程。其中，实线表示单一任务分片的运行过程，虚线表示多个任务分片的实时等待过程。

5.2 复杂度分析

本算法的复杂之处在于某一调度时刻到来时，利用并行优化选择策略，实现任务分片与虚拟设备一对一的选择，设任务分片总数为n，虚拟设备总数为m，总体复杂度分析如下。

1) NS算法复杂度分析

NS只接收信号Sig_T和Sig_A，在调度过程中CS为每一任务分片发送m个信号Sig_T和1个信号 Sig_A，NS共需处理n(m+1)个信号，且 Sig_T和Sig_A的处理过程仅为常数复杂度，因此NS的复杂度为O(mn)。

2) CS算法复杂度分析

① 根据文献[12]计算每个任务分片rank值的时间复杂度为O(mn)；

图6 CS与NS算法流程

②n个任务分片按rank值进行排序的时间复杂度为O(nlog(n))；

③ 每一调度时刻，处于空闲状态的虚拟设备个数最大为m，因此，就绪任务分片对虚拟设备的选择次数据最大为m，总选择次数为mn，其时间复杂度为O(mn)。

综上所述，本文算法的时间复杂度为O(mn+nlog(n))，由于在现实环境下虚拟设备总数为较小的常数，因此本文算法的复杂度可近似为O(nlog(n))，文献[12～19]的复杂度分别为O(n2)、O(n2log(n))、O(n2log(n))、O(n2log(n))、O(n3)、O(n2log(n))、O(n2log(n))、O(n3)均高于本文算法。

6 实验分析

为验证本文算法的有效性，本实验以文献[23]的DAG数据NSL(normalized schedule length)为标准随机生成任务，以模拟IaaS云计算平台的DAG任务分片结构，并以 HEFT[12]、PCH[14]、HEFT-lookahead[16]和HH算法[18]作为对比算法（本文算法用 SD表示）。本实验平台软件：Win7 32位，Matlab2012；硬件：intel i3处理器，4 GB内存，所设计的4组实验如下。

1) 资源占用时间分析实验。本组实验通过计算100组随机任务的调度结果，分析任务对虚拟设备的占用时间

其中，makespanvi为任务分片vi的执行时间，makespan越小说明运行结果对虚拟设备的占用率越低，算法有效性越高。由于100组随机任务的结构差异较大，为直观显示实现各算法的对比结果，分别按各算法的makespan对100组结果进行排序，其结果如图7所示，该图分别以各算法为视角，对比各算法的资源占用时间，其中曲线越靠近底部说明算法有效性越高，从图7可直观看出，在资源占用时间方面 lookahead和本文算法优于其他算法且HEFT算法的效果最差。为消除各组随机任务的结构差异，本实验采用对每组结果进行[0,1]区间映射的方法整理各组数据，并以各算法结果之和作为各算法的数值评价，本实验中各算法的计算结果分别为：84.54，76.00，18.09，60.32，10.99，数值越小表示算法有效性越高，因此在本实验中各算法的有效性排序为：SD（本文算法）、lookahead、PCH、HH、HEFT。

图7 资源占用时间对比

图8 总执行时间对比

2) 任务总执行时间分析。本实验以实验1的结果为数据集分析各算法的执行时间，其执行时间越短，说明调度算法的有效性越高，本实验采用与实验 1相同的方式，分别按各算法的执行时间对100组结果进行排序，其结果如图8所示，其中曲线越靠近底部说明算法有效性越高，从图8中可直观看出，HEFT算法的效果最差，其他算法性能相近。本实验采用实验1的[0,1]区间映射求和方法进行计算，结果分别为：96.57，31.59，21.98，34.63，23.39，其中数值越小表示算法有效性越高，因此各算法的有效性排序为：lookahead、SD、HH、PCH、HEFT。

3) CCR(communication computation ratios)分析实验。CCR分析的目的在于通过改变随机任务的通信时间以验证调度算法的稳定性，本实验以[5,25]为随机区间生成各任务分片的执行时间，以[6,26]CCR(CCR=0.5～3)为随机区间生成通信时间，创建6组DAG任务样本(每组100个样本)作为实验数据。图9为各算法在执行6组数据后的平均总执行时间和平均资源占用时间对比，图9的结果说明了本文算法在不同 CCR条件下，相较于其他算法在资源占用方面的优越性较高。

4) DAG任务顽健性实验。调度算法的顽健性表现在处理异构DAG任务时的稳定性，本实验随机生成 6组(每组 100个样本)层数为 5～10的异构DAG模型，统计各算法执行每组数据后的平均总执行时间和平均资源占用时间，其对比结果如图 10所示，从图中本文算法与其他算法的性能对比变化可知，异构DAG任务对SD算法影响较小。

5) 虚拟设备个数稳定性实验。本实验生成了6组(每组 100个样本)虚拟设备个数不同(3～8)的任务，统计各算法执行每组数据后的平均执行时间和平均资源占用时间，其对比结果如图 11所示，从图中本文算法与其他算法的性能对比变化可知，虚拟设备的个数变化对SD算法的影响较小。

图9 CCR分片对比

图10 DAG模型顽健性对比

图11 虚拟设备个数稳定性对比

6) 实验结论。本实验分别从5个方面实证了算法的有效性，在CCR分析实验、DAG任务顽健性实验和虚拟设备个数稳定性实验方面，通过与其他算法结果的对比，验证了本文算法的稳定性，说明本文算法面对各类DAG任务调度问题时可保持其有效性；在任务总执行时间分析实验方面，本文算法执行结果近于同类算法最优值，在资源占用时间方面优于其他算法。

7 结束语

本文根据 IaaS模型中各虚拟设备离散分布的特点，建立控制子系统CS和节点子系统NS及IaaS模型的DAG任务调度模型，并利用信号驱动的方式处理DAG任务调度问题。由于该算法以并行计算的DAG任务调度模型为基础使该算法具有普适性，可解决一般并行计算优化问题，本文算法的创新性和意义如下：所设计的利用信号交互机制进行驱动式调度，是面向IaaS的DAG任务调度的一次创新；所设计的并行优化选择策略，从全局角度考虑了DAG结构，使调度结果更加合理化；算法的复杂度为O(nlog(n))，低于传统DAG调度算法，使得该算法更加简单适用；算法的稳定性高于其他算法，适用于各类异构任务；相较于其他算法，本文算法的执行总时间近于最优，且对虚拟设备的占用时间最低。

因此，本文提出的算法不仅可以解决IaaS模型的调度问题，且对深入研究并行调度优化问题具有一定的理论和实际意义。

[1] ZHANG J X, GU Z M, ZHENG C. Survey of research progress on cloud computing[J]. Application Research of Computers, 2010, 27(2):429-433.

[2] 谢亚龙, 丁丽萍, 林渝淇等. ICFF：一种IaaS模式下的云取证框架[J]. 通信学报, 2013, 34(5): 200-206.XIE Y L, DING L P, LIN Y Q. ICFF: a cloud forensics framework under the IaaS model[J]. Journal on Communications, 2013, 34(5):200-206.

[3] AMAZON Inc. Amazon elastic compute cloud (Amazon EC2)[EB/OL].http://aws.amazon.com/ec2.

[4] NURMI D, WOLSKI R, GRZEGORCZYK C,et al. The eucalyptus open-source cloud-computing system[A]. Proceedings of the 9th IEEE/ACM Conference on International Computing and the Grid[C].Tsukuba, Japan, 2009.124-131.

[5] COMPUTING R C. Openstack open source cloud computing software[EB/OL]. http://openstaek.org.

[6] LU X Y, LIN J, ZHA L,et al. Vega LingCloud: a resource single leasing point system to support heterogeneous application modes on shared infrastructure[A]. Proceedings of the 9th IEEE Conference on Parallel and Distributed Processing with Applications[C]. Busan, Korea, 2011. 99-106.

[7] MARCOS D, COSTANZO A, BUYYA R. A cost-benefit analysis of using cloud computing to extend the capacity of clusters[J]. Cluster Computing, 2010, 13(3): 335-347.

[8] MARCOS D , COSTANZO A, BUYYA R. Evaluating the cost-benefit of using cloud computing to extend the capacity of clusters[A]. Proceedings of the 18th ACM international Conference on High Performance Distributed Computing[C]. Munich, Germany, 2009.141-150.

[9] NAN X, HE Y, GUAN L. Optimal resource allocation for multimedia cloud based on queuing model[A]. Proceedings of the 13th IEEE Conference on Multimedia Signal[C]. Hangzhou, China, 2011.1-6.

[10] KLLAPI H, SITARIDI E, TSANGARIS M M,et al. Schedule optimization for data processing flows on the cloud[A]. Proceedings of the 2011 ACM SIGMOD Conference on Management of Data[C]. Athens,Greece, 2011. 289-300.

[11] LIN C, LU S. Scheduling scientific workflows elastically for cloud computing[A]. Proceedings of the 2011 IEEE Conference on Cloud Computing[C]. Washington DC, USA, 2011. 746-747.

[12] TOPCUOGLU H, HARIRI S. Performance-effective and low- complexity task scheduling for heterogeneous computing[J]. Parallel and Distributed Systems, 2002(13):260-274.

[13] 谢志强, 刘胜辉, 乔佩利. 基于 ACPM 和 BFSM 的动态 Job-Shop调度算法[J]. 计算研究与发展, 2003, 40(7): 977-983.XIE Z Q, LIU S H, QIAO P L. Dynamic job-shop scheduling algorithm based on ACPM and BFSM[J]. Journal of Computer Research and Development, 2003, 40(7): 977-983.

[14] LUIZ F B, EDMUNDO R M. Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing,2010, 8(3): 419-441.

[15] 谢志强, 杨静, 杨光. 可动态生成具有优先级工序集的动态Job-Shop调度算法[J]. 计算机学报, 2008, 31(3): 502-508.XIE Z Q, YANG J, YANG G. Dynamic Job-Shop scheduling algorithm with dynamic set of operation having priority[J]. Chinese Journal of Computers, 2008, 31(3): 502-508.

[16] LUIZ F B, RIZOS S, EDMUNDO R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[A].Proceedings of the 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing[C]. Pisa, Italy, 2010.27-34.

[17] 谢志强, 辛宇, 杨静. 可回退抢占的设备驱动综合调度算法[J]. 自动化学报, 2011, 37(11): 1332-1343.XIE Z Q, XIN Y, YANG J. Machine-driven integrated scheduling algorithm with rollback-preemptive[J]. Acta Automatica Sinica, 2011,37(11): 1332-1343.

[18] RIZOS S, HENAN Z. A hybrid heuristic for DAG scheduling on heterogeneous systems[A]. Proceedings of the 18th IEEE International Parallel and Distributed Processing Symposium (IPDPS)[C]. Santa Fe,USA, 2004.266-286.

[19] 谢志强, 杨静, 周勇等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报, 2011, 34(2): 406-412.XIE Z Q, YANG J, ZHOU Y,et al. Dynamic critical paths multi-product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers, 2011, 34(2): 406-412.

[20] TAYAL S. Tasks scheduling optimization for the cloud computing systems[J]. International Journal of Advanced Engineering Sciences And Technologies, 2011, 5(2): 111-115.

[21] PANDEY S, WU L, GURU S M,et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[A]. Proceedings of the 24th IEEE Conference on Advanced Information Networking and Applications[C].Perth, Australia, 2010.400-407.

[22] WU Z, NI Z, GU L,et al. A revised discrete particle swarm optimization for cloud workflow scheduling[A]. Proceedings of the 2010 IEEE Conference on Computational Intelligence and Security[C]. Guangzhou, China, 2010.184-188.

[23] LUIZ F B, EDMUNDO R M. Towards the scheduling of multiple workflows on computational grids[J]. Journal of Grid Computing.2010, 8(3) : 419-441.