并行调度范文

并行调度范文（精选6篇）

并行调度 第1篇

车间调度问题(job shop scheduling problems,JSSP)也称为工序调度问题,目的是安排每台机器上的工件加工顺序,并满足约束条件,使制造系统某些性能指标得到最大限度地优化。JSSP是最有名的组合优化问题之一,属于NP(Non-deterministic Polynomial-time)难题。许多实际工程问题均可以与之相转化。具有建模、计算复杂性,而且具有动态随机性、多约束性、多目标性,一直是学者研究的热点。

近年来,计算智能技术因具有普遍适用性和较低的经验复杂性等优点而被应用来求解JSSP。其中,蚁群算法在作业车间调度问题等方面获得了成功的应用。文献[1]给出了解决车间作业调度问题的蚂蚁优化算法的一般步骤和模型。文献[2~4]在原有标准蚁群算法的基础上采用了新的状态转移规则。还有研究者将Palmer启发式算法、NEH启发式算法、双向调度算法等与蚁群算法结合[5~7],取得了较好的效果。但是这些研究都是借鉴蚁群算法在求解TSP问题[8]中的方法,将蚂蚁随机或均匀分布到各个城市,基于单个蚂蚁的搜索路径活动,进而再寻求全局最优解,缺乏对蚁群算法中的并行性的利用。

蚁群算法中各个体的运动是随机的,但是整个群体寻优过程中所体现出的并行性、协同性、自组织性、动态性等特点。这与JSSP的许多特点是相似的。本文借鉴蚁群活动的规律,通过蚁群中的并行、多样化寻优活动,在加速解的收敛的同时扩大解的搜索空间,以保证JSSP的更优解的突现。

1 蚁群信息素分布多样性

蚁群最优解的搜索过程可分为初期,中期和后期三个阶段,需要在“探索”(exploration)、“利用”(exploitation)、“再探索”之间建立一个平衡点[9]。

在搜索初期,小生境中可利用的经验信息还不多,这时蚂蚁运用初始启发信息,以“探索”为主;随着搜索的演进,小生境中经验信息增多,这时蚂蚁的搜索则以“利用”经验信息为主,加速解的收敛;而到了搜索的后期,要避免算法早熟、停滞的现象,就要在已有解的基础上“再探索”,以扩大解的搜索空间,使更优解得以突现。

所以,蚁群算法对经验信息和启发信息的利用是随着搜索演化进程而变化的。蚂蚁既考虑下一段路的长度,也考虑其信息素的分布强度,在相邻结点中以一定的概率选择下一到达结点。

位于结点i的蚂蚁k,按以下选择策略选择下一结点j:

其中,allowedk(k=1,2,,m)表示当前允许蚂蚁k通过的结点。τij表示散播在结点i与结点j之间的路段(i,j)上的信息素,是搜索解空间的一种趋向信息,是蚂蚁从结点i向结点j移动的动力;ηij为从结点i向结点j移动的启发函数,是评价蚂蚁个体在结点i结点j之间的路段(i,j)上的搜索代价,ηij=1/dij;α(t)用于描述经验信息的重要性,β(t)用于描述启发函数的重要性,均为正实数。

为了保证蚂蚁构造的解是相对较优的,在搜索初期,需要更多的利用启发信息,这是缩小搜索空间的需要;而在算法后期,为了保证更优解的突现,需要更多的“利用”经验信息,而淡化局部特征的影响。因此,设置,

其中α0和β0为初始设置的参数数值,取值范围同于基本蚂蚁算法,0α05,1β05。kα,kβ为两个正常数(0

为了扩展解的搜索空间,MPACO在这三阶段对不同的寻优群体设置不同的控制参数值,进行相对独立的寻优,使得各子蚁群具有不同的信息素分布模式。

2 蚁群更新信息素策略

在每一次搜索周期结束时(即所有寻优群体都搜索结束时),更新全部路径的信息素,即全局更新。全局更新考虑了每一次寻优的结果,隐含了信息反馈,将上一步得到的局部最优结果反作用于问题空间,使得算法更容易趋优。

设信息素挥发率为(1-ρ),每次寻优循环结束时路段(i,j)上的信息素强度τij(t+n)为:

Visitedij为该次循环中经过路段(i,j)的蚂蚁集合,

Lk为第k只蚂蚁在该循环中的局部最优目标函数值。

因为经验信息和启发信息的利用是随着搜索演化进程而变化的,所以信息素强度采用时变函数Q(t)。Q(t)随着搜索逐渐变大,更新量也逐渐变大。根据局部最优解计算全局信息增量。

kQ的取值依据经验。一般取为和kα、kβ同一个数量级,使得Q(t)的变化不太大。

全局更新后,继续迭代直到满足停止条件。停止条件为最大迭代次数或解处于停滞状态。

3 车间调度问题

典型规模的静态JSSP可以描述为:有n项加工任务T={T1,T2,,Tn}要在m台机器M={M1,M2,Mm}上加工,每项任务都有若干项有序的加工工序,每台设备分别完成不同的工序。每项任务在每台机器上不间断地加工一段时间,一台机器任何时刻都只能最多加工一个任务。在满足约束条件的前提下,将每一个工序分配到对应机器的某个工作时间段,使得调度目标趋于优化。

JSSP具有两类固有的约束特点。一类是体现为逻辑上串行的任务自身的工序约束,第二类是通过对任务的并行选择而得到对机器的独占性约束。串行的工序约束体现了同一任务的工序之间的串行时序关系。独占性约束体现加工队列中不同任务之间的并行时序关系。

JSSP可用非连接图表示[10]。非连接图G=(N,A,E)的形式如图1所示。其中,N包含代表所有工序的节点,A包含连接同一工件的邻接工序的有向边,E包含连接同一设备上加工工序的非连接边。非连接边有两个可能方向。

A所包含的有向边,体现了JSSP逻辑上对任务的工序串行约束。调度将确定E所包含的非连接边的优先方向,这体现了JSSP工序对机器的独占性约束。

调度目的在于找出每台设备上的工序加工顺序,也就是确定非连接边的方向,使得其结果是非循环的(工序间无先后冲突),并且起点到终点的最大权路径的长度(最大流程时间)最小。在调度过程中,JSSP满足以下约束。

设rijk表示在机床Mi上加工任务j的第k道工序,ftijk、stijk、etijk分别表示rijk的加工所需时间、加工开始时间、加工完成时间。

任何一道工序的完工时间减去开始时间不能小于其加工时间,即,

若rimn为正在机床Mi上加工的工序,则stijk=max(stij(k-1)+ftij(k-1),stimn+ftimn)。

对于具有确定工艺路径的JSSP问题,同一任务的不同工序在逻辑上是串行的,它们之间的时序关系是确定的。工序约束表现为后一工序需在前一工序完成后才能开始,即:

若机器M={M1,M2,Mm}可加工的任务集合为MT={MT1,MT2,MTk}(0

式中,t为机器Mk的工作时间。独占性约束则要求不同任务在同一设备上的加工时间不能重叠,即一台机器任何时刻都只能最多加工一个任务。不同任务之间的时序关系具有不确定性。生产过程中,可能出现不同任务同时需要在同一设备上进行加工,形成机器的并行待加工队列。从待加工队列中选择适当的任务作为当前任务,就是一个并行选择过程。同时,整个车间的设备运行和任务分配也处于并行工作状态。

JSSP一般采用下列调度策略对车间作业进行调度求解。1)完成该批零件的加工时间最短。该调度策略的目标函数为该批零件加工完成时间最小。2)使该批零件占用加工设备的时间最短。该调度策略的目标函数为该批零件的工件流通时间最小。3)保证该批零件的交货期延时最小该调度策略的目标函数为该批零件交货延迟时间最小。4)基于准时制造思想的调度策略,保证工件在需要的时候完成加工。该调度策目标函数为该批零件的交货延迟时间与提前完成时间之和最小。

不同的实际情况要求采用相应的调度策略。通常情况下考虑尽早完成零件的加工任务,采用第一种调度策略。本文在求解动态车间调度问题时以该批零件最小加工完成时间为目标函数f,

其中,etj为任务Tj的完工时间。

4 调度算法步骤

在JSSP中存在着顺序约束,并不是每个节点都允许在初始化的时候放置蚂蚁的。并且因为JSSP的并行性,在同一时刻,可能有多个任务在加工或者选择设备。这就造成任务的工序之间和设备之间存在耦合关系。TSP中的单只蚂蚁遍历搜索方式,则较难体现这种耦合。

本文将每个任务设置一个蚂蚁。n项任务构成一个寻优蚁群,其蚂蚁数目为n。JSSP中的n项任务对设备的选择过程就转化为n只蚂蚁从起点向终点并行前进的过程。寻优蚁群中的蚂蚁全部完成路径的搜索,就构成一个调度解。设置acnum个寻优蚁群,就可得到acnum个调度解。基于并行蚁群优化的JSSP调度能够简捷地模拟刻多个蚂蚁和设备的并行活动,调度步骤如下:

步骤1,根据具体的JSSP建立非连接图G。初始化非连接图中各节点所关联的边的信息素强度。

步骤2,初始化。根据任务数量n设置寻优蚁群的蚂蚁数目n。设置总的寻优蚁群数目acnum,最大循环数目Cyclemax。寻优蚁群蚂蚁的初始出发点置于虚拟节点Nstart上。

步骤3,蚂蚁并行移动。设置寻优蚁群相应的控制参数kα、kβ、kQ。扫描当前已经搜索结束的寻优蚁群数目,如果该数目小于acnum,转步骤4。如果该数目等于acnum,转步骤5。

步骤4,扫描寻优蚁群的工序。

如果有工序未结束,则将未处于加工状态的蚂蚁加入可移动蚂蚁集AM。根据信息素分布多样性公式(1)计算AM中的蚂蚁当前各可行节点与蚂蚁所在节点之间的信息素τijα(t)和启发函数ηijβ(t),以及选择概率Pij。根据各蚂蚁的选择概率大小,采用轮盘方法(roulette wheel),对AM中的蚂蚁进行排序,得到调度顺序集AMO。根据AMO蚂蚁移动次序,确定当前可以移动的蚂蚁前往工序节点。如果该工序节点的设备空闲,则蚂蚁占用该设备。该蚂蚁标志从可移动转为工作,该设备标志从空闲转为工作,该设备加工的工序集EP记录该蚂蚁号和相应的工序号。扫描设备状态,正在加工的设备上的工序时间减1。调度时间加1。

如果工序已经全部结束,记录该次搜索结果的最小流通时间(Makespan),转步骤3。

步骤5,对acnum个寻优蚁群的搜索结果进行路径“再探索”。按照交流信息多样性策略,对这acnum个解采用遗传操作(遗传交叉,遗传变异),求出局部最优解。

步骤6,按更新信息素策略公式(5),根据设备加工的工序集EP记录该蚂蚁号和工序号,更新非连接图G中相应的路径的信息素。

步骤7,如果达到最大搜索次数,所建立的所有局部最优解中,最小值的解作为当前迭代次数的全局最优解,即最短路径的距离值。否则转向步骤3。

通过信息素分布多样性,蚁群更新信息素策略,以及寻优结果通过信息交流,实现并行蚁群优化。

5 仿真计算和分析

本文对JSP Benchmark中的基准算例[11]分别进行用本文算法、基本蚁群算法和基本遗传算法进行了计算。算法采用MATLAB7语言编写,运行环境为WindowsXP,1G RAM。对每个算例,分别独立进行20次运算,其平均结果见表1。

由表1可知,对于不同规模的JSSP,本文算法的结果比基本蚁群算法和基本遗传算法的结果更优,可以得到最优解。

6 结论

模拟蚁群的并行活动,对不同时段出发的寻优群体赋以不同的控制参数,各寻优群体分别进行相互独立的蚁群寻优,体现寻优活动多样性和并行性。各寻优群体的寻优结果通过信息交流,实现蚁群之间的寻优信息交换。整个寻优过程结束后,得到待求解问题的最优规划方案及若干次优方案。最优解的获取是多个蚁群协同进化的综合结果。在JSP Benchmark问题上的仿真结果表明,这种方法求解Job-Shop问题的结果令人满意。仿真结果说明,利用蚁群寻优的并行性能比基本蚁群算法的集中式方法有效。

参考文献

[1]赵虎,李睿.蚂蚁算法在车间作业调度问题中的应用[J].计算机工程与应用,2003,22:6-8.

[2]刘志刚,李言,等.基于蚁群算法的Job-Shop多资源约束车间作业调度[J].系统仿真学报,2007,19(1):216-220.

[3]陈知美,顾幸生.改进型蚁群算法在Job Shop问题中的应用[J].华东理工大学学报(自然科学版),2006,32(4);466-470.

[4]王万良,赵澄,等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报,2008,20(16):4326-4328,

[5]Ying Kuoching,Liao Chingjong.An ant colony system for permutation flow-shop sequencing[J].Computers&Opera-tion Research,2004,31:791-801.

[6]刘延风,刘三阳.基于蚁群优化的置换流水车间调度算法[J].系统工程与电子技术,2008,30(9):1690-1692.

[7]李燕,陈华平,等.自适应蚁群算法在双向生产车间调度中的应用[J].运筹与管理,2008,17(3):160-163,159.

[8]Marco Dorigo,Thomas Stutzle.蚁群优化[M].北京:清华大学出版社.2007.

[9]甘屹,齐从谦,等.基于蚁群算法的动态联盟伙伴选择研究[J].系统仿真学报,2006,18(2):517-520,525.

[10]玄光南,程润伟.遗传算法与工程优化[M].北京:清华大学出版社.2004.

并行调度 第2篇

模型构建和算法求解是关于水库(群)优化调度问题研究的两个主要方向[1]。水库群规模至今已逐渐发展成串联、并联以及由串并联组成的混联模式,构建的优化模型更加复杂与精细,相应优化算法随之更加计算繁重。随着并行技术的兴起与发展,学者们提出了针对多种优化方法的并行化策略,可进一步提高水库(群)优化调度计算效率,实现求得满意最优解和计算耗时较少的双重目标。

本文以单一水库、并联水库群、串联水库群以及混联水库群优化调度为背景,较全面综述了诸多学者在主要传统求解方法和智能优化方法计算中应用的并行策略及其原理。并行技术有效缩短了复杂的优化计算耗时,然而目前并行策略大都还是基于或改进于传统求解方法的并行动态规划和智能优化算法中分解后子群并行性特点。串联水库群发电优化调度算法一直是学者们致力研究的重点和难点,一般很难同时兼顾优化解的精度和计算耗时。郑慧涛[2]的博士论文中,基于水库群短期发电优化调度模型计算特点,拓展粗粒度并行思维,将混联水库群分解成独立计算的单库,使具有并联、串联关系的各个子水库优化计算实现并行,在水库群发电优化调度并行策略研究中有了质的飞越。然而在串联水库群中长期发电优化调度中,郑慧涛博士研究有关出入流关系水库的并行策略依据准则并不适用。因此是否可以像并联水库群一样,在中长期优化调度中将上下库具有出入流关系的串联水库群分解为独立计算的单库子系统,分配于不同的对应的计算单元,实现粗粒度并行计算模式,将是本文致力于研究串联水库群创新性并行策略的切入点,文中将此计算模式称为异步并行计算。

之后以我国西南地区李仙江流域上崖羊山、石门坎水库组成的串联水库群为例,在其中长期发电优化调度中,对分解协调异步并行计算展开了相关论证。本文针对水库(群)展开并行策略的研究,为复杂水库群系统在发电、防洪、灌溉等水资源优化调度领域提供了新的研究与应用方向,为人力、物力、财力等资源优化配置提供了一定的理论依据。

1 水库(群)发电优化调度计算的并行策略研究进展

1.1 并行策略的主要研究方向

在单库和水库群发电优化调度中,传统优化方法主要为动态规划、线性规划、非线性规划、逐次逼近法、逐步优化法等;智能优化方法主要是以遗传算法、蚁群算法、粒子群算法、模拟退火算法、人工鱼群算法、混沌算法以及人工鱼群算法等为典型代表。

万新宇[3]针对水库发电优化调度,分析了传统串行动态规划算法的计算特点,由此建立了主从模式的并行动态规划模型。李想[4]以经典四水库问题为例构建多维动态规划模型,也是基于主从模式的并行动态规划算法,并成功在高性能并行计算机上进行求解。二位学者的并行策略基本一致,都是基于状态点相互独立的并行动态规划思想,不同之处是前者应用于单库,后者以简单的混联水库群作为研究对象。

李想[5]针对水库优化调度采用的是并行遗传算法中的粗粒度模型,基本思想是将某种群分割成若干个子种群,各子种群在对应不同编号的处理单元上相互独立地并发执行进化操作,实现计算时间的重叠,经过数次迭代进化,各子种群间会交换部分个体,从而丰富各子种群的多样性,防止早熟发生,不断积累优秀基因。陈立华[6]对水库群优化调度中的粗粒度并行粒子群算法展开研究,其基本思想是参照处理单元的数目把对象粒子群分成数个子群体,并对应分配至每个处理单元,使各处理单元上的子群体能够独立搜索最优解,实现计算时间的重叠。可见两种智能优化算法并行思想的基本点都是将待计算群体分成不相关联的子群,再分配到不同的计算单元作为子任务处理,实现并行计算。

总之,目前有关发电优化调度的并行策略可归纳为两大类:在传统优化算法的并行策略中,最常用的是基于状态点相互独立和阶段重构的并行动态规划;而在各种智能优化算法中的并行策略,基本都是将待计算群体分解成不相关联的子群,分配到不同的计算单元处理,实现并行计算。

以上两类主要并行策略可适用于单一水库以及串联水库群的优化计算。

对于并联水库群优化计算,可以遵循两种并行思路:第一,对于其中的组成单库可以应用以上两类以分解算法计算过程为子任务的并行策略;第二,将各单库独立计算体作为不同子任务分配到各自对应的处理单元并行处理,即实现粗粒度并行计算,可将对应不同组成单库的数台计算机互联,作为该并联水库群发电优化调度的仿真系统。

若将数台互联的独立计算机对应串联水库群中前后毗邻的各单库,仿真该串联水库群系统,由此可产生是否能实现此串联水库群中各单库独立计算粗粒度并行化的思考。

针对混联水库群,初步思想是将其分解成并联和串联子水库群,再用相应的并行策略解决其优化计算问题。

1.2 串联水库群优化计算新型并行策略研究切入点

毛睿[7]根据上下库无出入流关系特征把混联水库群分解出可并联的数个串联子水库群,将各自优化计算作为子任务进行了并行处理。

目前有关串联水库群的并行策略大都是围绕着并行动态规划和智能算法中并行子群的计算模式,只是在此基础上改进或进行几种算法结合,较长时间没有在串联水库群优化调度中实现并行计算的实质性算法创新。直至郑慧涛在博士论文中对串联水库群短期发电优化调度设计出了独特的并行计算方法。郑慧涛博士在大规模混联水库群短期联合优化调度模型中并行策略的关键点是根据并联、串联水库群特点,遵循单库间分布特性、单库间水流传播特性以及水库调节性能三原则,对水库群有效分解成不相关联独立计算的单库子系统,实现优化计算粗粒度并行化。

三原则的详细内容陈述如下:

(1)依据单库地理位置分解,例如在不同流域上的单库之间属于并联关系,水流上不存在直接联系,其特性可体现并行性,因此可以在模拟计算时将隶属不同流域、河流的单库进行简化分解。

(2)依据水流传播特性分解,因在水库群短期优化调度问题中,水流传播时间具有时滞性的特点。若上库泄流传播到下库时间超过了调度期长度,可将预报入流作为下库的流量输入条件。由此,单库之间可进行简化分解。此分解方式适用于串联水库群短期优化调度,但由水流特性可知其明显不适用于串联水库群的中长期优化调度。

(3)依据电站调节性能分解,即上库具有日调节的特点或是径流式,而下库具有季以上中长期调节能力,则上库时段泄流量相对于下库的调节库容来说比较小,对于下库水位的变化影响也较小,可近似认为下库水位不会随上库的泄流变化而变化,因此下库可采用预报入流作为入库流量条件。当单库之间调节性能满足上述条件时,可将此水库群进行简化分解。根据其特点,此分解方法依旧不适合串联水库群中长期优化调度模型。

总结郑慧涛的博士论文可知,将分解后各单库计算作为独立子任务依次分配给不同计算机处理单元,各自可通过优化算法得到求解,可由并行计算提高求解速度。基于划分与分治思想对水库群进行并行计算,经模拟计算结果表明该方法可以提供在较短时间内大规模水库群计算出的短期调度方案,满足了短期调度的时效性要求。得到各子任务结果后,再归约合并得到整体水库群优化调度的最优解。

求串联水库群中长期发电优化调度可借鉴郑慧涛博士分解水库群实现粗粒度并行计算的基本思想,然而水库群分解三原则只适合并联水库群或是短期优化调度的串联水库群。如何分解中长期发电优化调度的串联水库群是本文新型并行策略———异步并行计算的切入点,为研究混联水库群中长期发电优化调度粗粒度并行计算做出了铺垫。

串联水库群可以被看成一个完整的大系统。李爱玲[8]提出了如何将大系统分解协调方法应用于串联水库群中长期发电优化调度模型最优解计算,水库群中各单库之间的关联统一由协调层处理,分解后的各单库优化计算可以不相关联独立进行。吴昊[9]、纪昌明等在此模型基础上,应用多线程技术实现分解后单库子系统的并行动态规划计算,但未实现各单库的粗粒度并行计算。

在毛睿的文献[7]中提到,对于并联水库群,不管是短期还是中长期优化调度,某个单库的入流情况不会受到其他单库出流的影响,因而各单库调度计算可以实现并行;而在串联水库群中长期发电优化调度中,上库调度方案的变化直接影响下库的入流,即下库的入流只有等到上库对应时段的泄流计算得出后方可计算,即串行计算。目前还没有在串联水库群中长期发电优化调度中,实现以各单库作为独立计算体的粗粒度并行计算,即实现各单库计算时间的重叠。

参照动态规划将调度期分成数个时间段,入流随之分成数段,按时间的先后顺序入流有先有后,由此考虑到后库在较早时间段是否可先计算先获得的入流值,使分解后各单库实现计算时间重叠,这是本文研究串联水库群中长期发电优化调度新型并行策略的关键点,为今后混联水库群中长期发电优化调度实现粗粒度并行计算模式奠定了研究基础。

2 串联水库群优化计算的新型并行策略

2.1 串联水库群中长期发电优化调度的大系统分解协调模型

假设某串联水库群由R个以季调节的水库组成,以整个调度期限内的发电量最大作为该水库群中长期发电优化调度准则,可建立基本模型为:

其中约束条件表达式如下:

式中:Qit为第i单库第t时段的来水量,m3/s;IBit为第i和第(i+1)单库在第t时段区间来水量,m3/s;ηi为第i单库的出力系数;Δt为时段计算时间,s;T为时段数;R为串联库群系统中单库个数;hit为第i单库第t时段的水头;Nit min、Nit、Nit max为第i单库第t时段的最小容许出力、决策出力、最大容许出力,k W;qit min、qit、qit max为第i单库第t时段的最小容许放水量、决策放水量、最大容许放水量,m3/s;Vit min、Vit、Vit max为第i单库第t时段的最小容许蓄水量、决策蓄水量、最大容许蓄水量,m3。

串联水库群发电优化调度联合最优解并不是简单的各单库最优解相加,不能简单地将各单库计算分割,毗邻单库间不仅具有上下库的出入流关系,同时毗邻单库间的水力关系共同以合力的形式决定了整个水库群的最优解大小,是潜在的一种关联;郑慧涛博士论文中对串联水库群的分解方法也不适合中长期发电优化调度。

大系统分解协调方法以递阶控制形式将大系统分解成若干相对独立的子系统,作为分解级;并用协调器来处理各子系统间关联作用,作为协调级。通过上下级之间反复交换信息,经数次迭代求得各子系统极值,待收敛时可获得整个大系统的最优解[10]。可应用大系统分解协调方法将串联水库群发电优化调度中的单库分解成计算相互独立的子任务,而之间的关联统一由协调器来负责计算。

根据大系统分解协调方法,令μit、λit分别为式(5)、式(6)的拉格朗日乘子,由式(1)的模型表达式可构造拉格朗日函数为:

由式(7)可把该串联水库群分解成如下R个单库子系统求解模型:

其约束条件表达式与串联水库群中长期优化调度模型的一致。

该分解级单库子系统模型以及之后提及的协调级表达式,其原理可参考李爱玲的文献[8],其中协调级表达式如式(9)、式(10)。

大系统分解协调方法应用在串联库群中长期发电优化调度中,使计算耗时大幅度减少。为进一步减少计算耗时,提高计算性能,可以充分利用计算闲置资源。基于大系统分解协调方法,将分解后的单库子系统优化计算作为子任务分配于对应的计算处理单元,为实现粗粒度并行计算奠定了基础,如图1。

2.2 并行策略分析

并行计算的基本思想是把求解问题尽量分解成相互独立的子任务,并被分配到对应的计算机处理单元,各自独立计算的时间重叠实现了各子任务的并行处理,再将各子任务的处理结果汇总后得到整个问题解[11]。

分解后的各单库优化计算是相互独立的,可以被分配到各自对应的计算机进行仿真最优化计算,之间的关联由协调级处理。然而正如毛睿提及,由式(9)可知,上库对下库的入流关系是不容改变的,下库需等待上库整个调度周期内下泄流量计算得出后方可计算,每个时间点只有一台计算机处理对应的单库优化计算,各单库无计算时间重叠固然没有实现并行计算。

若将调度周期等分数个时段,下泄流量相对于每个时段都会有对应的值。为实现不同单库计算时间重叠,可以想到是否可以将上库各时段的下泄流量按计算先后顺序依次下传给下库对应时段,下库先得到入流数据的时段可先进行计算,依次直至该库群末库计算完毕。若此方法可行,各单库优化计算时间的重叠便可实现,并行计算模式自然而成。

单库优化调度计算应用动态规划算法[12]时,调度期被等分数个时段,并且每个相邻时段按逆时序依次花一定的时间寻优计算,因此上库各时段的下泄流量似乎可以逆时序先后传给下库,下库可以先计算先获得的下泄流量,最终可实现相邻单库的并行计算,直至末库计算完毕。然而在动态规划算法实际计算过程中,各时段决策变量需在逆推计算结束后再进行回代方可统一获得,那么对于下库仍需要等待上库计算得到整个调度期内的下泄流量后方可计算,各单库计算时间重叠实现又出现困难。有关单库动态规划算法原理可参考文献[12]。

设调度周期被均分成T个时段,在单库的动态规划逆推计算过程中,假设第t时段的初、末库容各有状态离散点M个,那么由此会产生M2个决策变量,而在这第t时段可得到M个较优决策变量并组成集合,占所有决策变量总数的1/M,可以看出M值越大,该集合中决策变量整体精度越高。可设定某规则选取该集合中的某个决策变量作为该时段的最优决策变量,并且所有时段决策变量的选取方法都遵循此规则,例如选定中间号为[M/2]的决策变量,其中[]表示取整。各时段决策变量计算时间基本一致,可设定为TN。按此规则在动态规划逆推计算过程中,第i单库各时段的决策变量qit值可以按时间顺序先后依次计算得出,即获得第(t+1)时段放水量qi(t+1)值比相邻的第t时段放水量qit值早TN时间,可将qi(t+1)值先下传于第(i+1)单库计算,不再需要通过回代过程求得各时段最优策略值,以及相应状态值Vit、hit等。毗邻下库的计算时间可不用等待上库TN×T时间,只需等待TN时间方可开始计算,以同等方式,直至末库计算。依此而来各单库最优决策变量计算实现了计算时间重叠,为并行计算模式奠定了坚实的基础,由于毗邻的后库比前库计算开始时间慢一个时段计算时间TN,可命名此新型计算模式为异步并行计算,原理如图2所示,表示为应用大系统分解协调方法下某次迭代过程中串联水库群各单库的并行策略。

3 实例计算与方法验证

3.1 计算模型建立

李仙江是云南省红河的一级支流,本文实例背景是以其具有调节性能的崖羊山、石门坎两座水库作为串联水库群系统,参考数据自1957年开始,调度期为43 a。

在本串联水库群系统中,崖羊山作为上库,来水量Q来自43 a统计的实际数据,石门坎作为下库,来水量Q来自崖羊山的放水量q与他们之间的区间来水量IB之和。每年按月化为12个时段,总共43 a则为43×12个时段。

以研究期内总电能最大作为优化调度准则,该串联水库群系统发电优化调度模型为:。应用大系统分解协调方法可将该串联水库群系统分解成两个单库子系统,作为分解级一为崖羊山水库发电优化调度模型:,二为石门坎水库发电优化调度模型:,其中各模型的约束条件可参考式(2)-式(6)。协调级的表达式为:

3.2 异步并行计算方法设计

本实例计算基于多核计算机,开发环境为visio studio2010,应用C#普通多线程技术控制参与工作的计算机内核数来实现异步并行计算。

将基于标准动态规划方法逆推计算的单库发电优化调度计算模块化,对于崖羊山、石门坎模块主要是输入与输出参数不同,代码构造基本一致,每一时段的最优出力计算时间基本相同,即上述的时间TN,离散点M取值越大计算结果越趋于最优值,但计算成本大幅增加,在本实例中取值为50。在主进程中开启两个子线程,将崖羊山、石门坎两模块分配于两核独立计算,在两模块外的主进程中设置一个43×12的数组,共有43×12个空位分别过渡存储崖羊山各对应时段的出水量qit。对于石门坎的43×12个时段的来水量Q2t时刻监听崖羊山模块中对应时段的q1t。在t时段一旦数组中的q1t由0值转为非空,石门坎由协调级函数Qk2t=qk1t+IB1t即刻取得值Q2t进行计算,实现此t时段与崖羊山(t-1)时段较优出力计算的并行,从而实现异步并行计算。

算出整个系统的解后,将石门坎子系统相关参数传给主进程的协调级函数λ1tk+1=η2hk2t,算出协调因子传于崖羊山用于第二次迭代计算,如此循环直至大系统目标值收敛。两库部分时段计算的程序流程图如图3所示。

3.3 实例计算结果

在本实例中,由于崖羊山、石门坎水库应用的是标准动态规划算法的逆推计算独立获得各时段的较优决策变量,在应用2.2节中异步并行计算方法的基础上,对于两单库的独立计算,可以将各个时段离散变量的所有组合进行并行处理,应用双重并行计算无疑可以更进一步节省本实例的计算时间。然而离散变量的组合并行计算方法在现今水库群调度研究中比较成熟广泛,且本文研究重点是创新型异步并行计算方法的可行性,因此在本实例的程序设计中,没有在各个时段离散变量的所有组合中应用并行计算方法。

在崖羊山、石门坎水库组成的串联水库群系统发电优化调度中,由表2可知,采用单一的标准动态规划算法求得水库群联合最优发电值所用的时间大致是采用大系统分解协调方法后计算时间的9.56倍。而采用大系统分解协调方法后的最优年平均发电量是采用单一标准动态规划算法的97.9%左右,是偏于理想值5%的可承受范围之内,因此,应用大系统分解协调方法高效求解串联水库群系统发电优化调度最优值是非常可取的。以大系统分解协调方法以及单库标准动态规划算法逆推计算为基础,结合异步并行计算求得系统发电最优解的计算时间约为并行处理之前的60%,最优年平均发电量基本与单一大系统分解协调方法一致,是单一标准动态规划算法的97.69%,亦是偏于理想值5%的可承受范围内,因此结果表明分解协调异步并行计算应用于串联水库群系统发电优化调度中,为明显减少耗时是可行的。在以后的研究中可以进一步证明串联水库数目越多,同时均匀分布于每个处理单元且应用分解协调异步并行计算方法进行计算,耗时减少的会越明显。

4 结语

并行调度 第3篇

传统的基于单机的文本处理方法,在存储容量和处理速度上都遇到了瓶颈,如何处理海量数据是一个重要问题。云计算平台动态调度提供的海量数据的处理能力在文本数据挖掘领域中是非常有效的方案,它能体现出对海量数据的并行计算优势。因此,文本数据挖掘领域的众多研究者将研究重心转移到传统文本数据挖掘算法的并行化研究之中以提高海量数据的处理能力。

本文研究基于朴素贝叶斯算法的海量中文微博的情感分类以及算法的并行化。通过有效的情感特征识别方法提取出中文微博的情感特征,在这些特征的基础上对微博进行情感分类,致力于在精度、效率上提高。对微博情感分类技术的研究集中于以下几个方面:设计实现海量微博情感分析系统、设计基于朴素贝叶斯的微博情感分类模块以及在大数据下的算法并行化研究等。最后,将其推广到集群模式下进行实验分析,用开源云计算平台Hadoop框架和下一代云计算大数据核心技术Spark以及通过GPU下CUDA的编程技术提高文本分类效率和性能。基于动态调度改变算法的编程模型,实现算法预期的并行性能优化,解决了海量微博数据的情感分类问题。

1 微博情感数据挖掘分类模块

情感数据挖掘模块包括:微博数据处理、特征计算和分类器模块。微博数据处理包括数据获取,微博预处理;特征计算模块包括特征提取、构建向量空间模型;分类器模块包括分类器、结果评估。整体的研究结构图如图1所示。

1.1 微博数据处理模块

微博数据处理模块包括:数据获取和微博文本预处理。

(1)实验中训练集样本和测试集样本来源于互联网,是由实验室根据新浪微博网站API和网络爬虫获取。由于获取的微博中包含的话题标签与句子的情感极性没有必然的联系,为了不影响最终的分类结果,首先要将微博文本中的话题标签去掉,只留下文本中的主体部分。同时还应该做以下几项工作:微博文本规则化处理,统计所选取微博的条数,提取并去除话题标签,按照积极性和消极性把句子分成两类。微博文本的规则化处理目的是减少分词时可能引起的误差,其中包括把英文字符统一成大写,多个标点符号重复出现转化为一个标点符号只出现一次,全角符号转化为半角符号,所有不规范的省略号转化为规则的省略号等。

(2)微博文本预处理模块主要是基于一些自然语言处理方法实现的,主要包括中文微博分词、去除停用词等。主要功能包括:中文分词、词性标注、命名实体识别、用户词典功能;它支持多种编码;支持微博分词、新词发现与关键词提取。由于中文微博语言包含了很多口语化、非正式的用语以及一些简写和缩写等,所以自动分析的效果可能会差一点。停用词包括助词、虚词、叹词和标点符号(本次包含),在去除停用词时需要将这些词语都去掉。

文章中把中文分词和停用词放到了一起,首先调用NLPIR汉语分词系统中的NLPIR.NLPIR_Paragraph Process()函数对文本进行分词,并保存到String类型的数组中,然后读取停用词表中的数据,也存入到String类型的数组中。最后把分词的结果和停用词表数组进行一一比对,找出其中的停用词,并从数组中删除掉。最后得出String类型的分词结果数组以行存储,每行就可以看作是一篇文档的向量。

1.2 特征计算模块

通过上一个模块的处理之后,形成了文档以词项为元素的向量,特征提取就是要从已经形成的文本向量中抽取具有明显情感倾向和能说明该条微博主题的词汇作为特征词。经过二次抽取之后形成的文本向量基本上就可以作为用于分类器中训练或测试数据的文本向量了。接着对向量进行进一步处理,转化为计算机能识别的表示模型,即向量空间模型。转化时需要对文档进行遍历,统计每个词项的词频。最后对每一个类别进行整合,所形成的就是该类别的类别矩阵,在进行数据集训练时,利用TF-IDF计算出每个词项在文档中的权重,构成带权重的类别矩阵。进行分类器测试时,利用分类器对文档进行分类。

2 基于NB的情感分类数据并行研究实现

2.1 NB算法模型

朴素贝叶斯的思想基础是:利用类别的先验概率以及样本的数据信息计算未知类别的文本属于某一确定类别的后验概率。朴素贝叶斯微博情感分类的任务就是将待分类微博t表示成为属于某一类的概率。即设该t的特征向量(ω1,ω2,⋯,ωn)归类到与其关联最紧密的M个分类C1,C2,⋯,CM中去,由于情感分类是正负两元分类,故M=2。通过求解向量(ω1,ω2,⋯,ωn)属于给定类别Ci的概率值Pi,其中Pi为(ω1,ω2,⋯,ωn)属于Ci的概率,则取最大后验概率max(P1,P2)对应的类别就是文本(ω1,ω2,⋯,ωn)所属的类别。因此,微博情感分类问题即为求解式(1)的最大值:

分母对于所有类别计算无影响,而且分类器的特征向量(ω1,ω2,⋯,ωn)独立同分布,其联合概率分布等于各个特征属性概率分布的乘积,故:

式中:P{ωj|Ci}为特征词在类Ci中的条件概率,即词对微博ti属于类Ci的权重。在分类中,最大后验概率所在的类别Cmap就是微博最可能所属的类别,公式如下:

式中:P(Ci)表示微博属于类Ci的先验概率,计算P{ωj|Ci}和避免其估计值为零,采用Laplace平滑技术,简单地对每一项处理,研究中采用式(4)进行计算:

式中:Nij是特征词ωi在Ci类别文档中的权重,文章采用特征词ωi的TF-IDF值;是在类Ci中所有特征词的权重总和;|V|为平滑因子。

2.2 算法并行化可行性研究

当数据的规模不断增多后,不论是训练集的学习过程,还是文档统计分类工作,都需要占用相当大的内存与计算资源。由于串行计算导致训练集生成速度缓慢,机器学习效率低下,因此单机显然不能胜任海量数据。分析上述朴素贝叶斯算法条件独立性假设的特点,可以发现无论是分类模型的生成过程,还是测试集的分类过程,都是由许多组独立的计算叠加而成。因此,其算法本身就具有并行计算的可行性。综上所述,并行化后的朴素贝叶斯分类流程,如图2所示。

由并行化后的朴素贝叶斯分类流程可知,训练阶段内的每一篇微博文本的计算处理过程都是相同的、独立的。因此将一篇接一篇的串行计算过程并行化处理,把训练集数据分割切片后,由多个并行计算节点分别对训练微博进行分词、统计等计算。可以根据具体计算单元数目的情况适当选择数据分割的大小。在测试阶段的工作是计算微博的每个特征词属于各个类的概率并且叠加,得到文档属于正、负类别的概率,最终取最大值作为分类的结果。朴素贝叶斯分类过程中最耗时的是需要计算大量的P{ωj|Ci},而各个特征词的计算过程是相互独立的。因此,将特征词统计过程改造成在各个节点并行完成各个部分的P{ωj|Ci}计算,最后合并输出结果到分类结果中。

2.3 Spark下的算法并行化实现

结合Spark MLlib设计的接口对原有MR程序改造,考虑Spark MLlib良好的可扩展性和基于面向对象封装,分析和设计了当前平台中各个算法模块的组织关系。故继承Spark MLlib接口原有的Classification Model,设计一个便捷的内存数据模型Naive Bayes Model用于评估和预测,提供标签类别先验概率和特征属性在指定类别下出现的条件概率。本次朴素贝叶斯算法主要考虑其并行化后速度上的提升,算法的并行策略主要是计算类别的先验概率以及特征的条件概率。基于分类算法的并行思路,任务同样分为训练阶段和测试阶段,Spark下的分类流程,如图3所示。

(1)加载训练集到Spark空间,则要创建弹性分布式数据集RDD。本文采用外部存储系统上的数据集创建RDD。从Hadoop的任何存储源中构建出RDD,包括本地文件系统,HDFS,HBase等。Spark支持TEXT-FILE,SEQUENCEFILE以及其他任何Hadoop Input Format,为使用上一节预处理后的数据提供便利。算法的训练集和测试集的输入是(Label,key:value)的序对,使用Spark Context提供的text File()接口,MLlib内部会转换成RDD[Label Point]类型。Label Point对情感分类来说,一个标签或为0(负向)或为1(正向)。

(2)训练阶段,包括统计词频TF和计算权重TF-IDF。为了扩展性将TF和IDF分开,TF-IDF是TF和IDF简单相乘。统计词频使用散列技巧,基于映射索引值计算实现,包括运用一个哈希函数将原始特征映射到一个特征索引值。这种方法避免计算全局“词-索引(term-toindex)”映射,而在海量的微博语料中计算全局“词-索引”的代价非常高。由于这种方法会出现潜在的哈希值冲突(不同原始特征被映射到同一个哈希值,从而变成同一个词),通过增加目标特征的维数(哈希表中散列桶的数量)来降低这种冲突概率。训练阶段完成上述步骤后,设计整合数据获得模型。训练阶段得到Naive BayesModel模型,包括标签类别先验概率pi,特征属性在指定类别下出现的条件概率θ。

(3)朴素贝叶斯分类器测试阶段,输入的测试数据集转化为TF-IDF形式的特征用来文本分类,对两边取对数作为实现,加法的计算效率比乘法更高,同样的结果返回后验概率最大的那个类别。

2.4 基于GPU的算法并行实现

在训练过程之前,需要把生成的预处理后的微博数据加载到内存。所有的文档加载到一个矩阵,其中矩阵的一行表示属于一个分类下的一篇文档中的全部特征词。如ωij中i代表分类的标号,j代表不同的特征词编号。如下所示:

为了方便词频汇总,使用散列方法,基于映射索引值计算来实现,运用一个哈希函数将原始特征映射到一个特征索引值。得到一个惟一特征词的向量,用来统一表示微博文本的特征向量。在保存分词处理结果时,保存该词在分词词典中的下标。根据分词词典的词数建立一个索引表,并用0值初始化。

在海量微博数据朴素贝叶斯分类中,由于涉及到的数据量非常庞大并且数据类型种类繁多,为了实现高性能算法,选择高效的数据表示形式起着至关重要的作用。主要目标是算法在GPU取得优异的并行性能,但是当前图形处理硬件受到严重的内存限制,尽管实验设备的显存有5 GB,但仍然存在数据不能全部加载到显存的可能,所以采用一个密集的数据结构:按照特征词进行索引来表示文档集合。利用两个Vector,即Term I-ndex Vector(TIV)和Doc Term Vector(DIV),DTV存储了每条微博中出现过的特征词wj。TIV是DTV中特征词的索引用来区别DTV中的不同微博文档。故TIV的每个位置指向DTV中每篇微博的首位特征词wj。

3 实验与结果分析

3.1 实验过程

实验一,在单机上利用朴素贝叶斯分类方法对采集的微博小规模实验数据集进行串行的分类实验,验证基于朴素贝叶斯微博情感分类方法的精度效果。本次原始语料经过预处理得到降噪、分词微博文本。在实验中,通过人工筛选的方式,根据之前的研究内容分别使用不同的分类器和多种特征以及不同特征权重计算方式的组合进行实验,选择效果较好的分类器和特征。

实验二,利用分布式爬虫并行爬取大规模数据集,采用上文设计的并行算法进行并行化的分类实验,验证分类方法的加速效果。依赖云计算的工作流调度系统配置运行本实验的任务节点。

首先,本实验是数据获取,start节点开始后在基础库中获取微博话题的URL,然后使用网络爬虫和API获取微博数据集。其次,在weibo_content_data节点将微博数据处理划分为训练集和测试集,此时应当记录节点开始运行的时间T0。然后,任务有3个大分支,分别是朴素贝叶斯在Hadoop,Spark以及CUDA三个并行计算平台上运行,分别运行完test⋅naive Bayes节点的时间为TH,TS,TC,此时间差用于实验计算加速比与运行性能等。最后,分类结果汇总到sentiment_report_storage节点中,将分类的结果与中间结果数据存储到结果展现层的关系型数据库中,供数据挖掘演示平台Vdata系统使用。文章中为每个任务节点编写shell脚本,shell脚本中执行jar包等处理过程,从中向集群或GPU提交相应任务。

3.2 运行性能对比

在不同的问题规模上对比单机串行,CUDA,Hadoop与Spark的不同版本实现的运行效率。其中,单机串行算法运行在单台Linux服务器上,Hadoop与Spark版本的实现未做深度调优处理。数据集方面,本文使用了微博50 KB,500 KB以及5 MB数据集,其中分别包含了5万行,50万行和500万行微博文本。这些不同大小的数据集可以很好地测试朴素贝叶斯算法并行的实际性能。于是依次使用这三个数据集在实验集群上,而且特征维数取值3 500,进行性能测试。对比运行时间,如图4所示。

从图4可以看出,当数据集较小时,单机算法计算性能并没有明显劣势;但当问题规模增大时,单机算法则表现越来越差,运行时间成倍增加,若数据量级持续增长可能会超过机器可运行范围。而在GPU平台上,分类运行时间则缓慢增加,这是因为在单机上,影响程序运行时间的最大因素是分词汇总模块,当文本数据量增大时,该模块需处理的时间也随之大大增加。在GPU平台上,由于可使用更多的线程块来处理增加的数据量,因而程序运行时间的增加更多来自于磁盘I/O操作次数的增加。在Spark与Hadoop上实现的算法仍然可以明显地反映一个问题,处理的数据规模越小,其处理单位数据的耗时越长。随着数据量的增大,所占用的运行时间比较平稳,这与他们框架内部实现机制有关:输入数据在HDFS被分成若干块后,得到的中间结果保存到HDFS或者内存中。当数据规模较小时,大部分时间都消耗在进程的初始化以及HDFS读写中;而对于大数据集,初始化开销以及HDFS读写开销只是总开销中很小的部分。但是,Spark仍然能表现出很好的内存计算优势,算法在Spark实现的运行时间上大量减少,极大地提高了运行效率,而其中处理5 MB数据集的任务运行总时间显著减少。

4 结论

本文提出了海量数据情感分析系统,可适应不同机器学习与数据挖掘算法处理场景的任务。介绍了系统框架思想与设计实现思路,并详细介绍了2个子系统,即面向云计算的工作流调度、Vdata系统,随后针对本文研究微博情感分类模块进行重点分析,有效地阐明分类算法并行化研究在海量微博情感分析系统的重要地位。

参考文献

[1]黄萱菁,张奇,吴苑斌.文本情感倾向分析[J].中文信息学报,2012,25(6):118-126.

[2]向小军,高阳,商琳,等.基于Hadoop平台的海量文本分类的并行化[J].计算机科学,2011,38(10):184-188.

[3]江小平,李成华,向文,等.云计算环境下朴素贝叶斯文本分类算法的实现[J].计算机应用,2011,31(9):2551-2554.

[4]李海生.一种热点话题算法在微博舆情系统中的应用[J].现代电子技术,2015,38(6):44-46.

[5]HUANG L Q,LIN L Q,LIU Y H.Algorithm of text categorization based on cloud computing[J].Applied mechanic sand materials,2013,311:158-163.

[6]HARVEY J P.GPU acceleration of object classification algorithms using NVIDIA CUDA[R].New York:Wallace Memorial Library,2009.

[7]JOSHI A,BALAMURALI A R,BHATTACHARYYA P,et al.C-Feel-It:a sentiment analyzer for micro-blogs[C]//Proceedings of 2011 Annual Meeting of the Association for Computational Linguistics:Human Language Technologies.Stroudsburg:ACM,2011:127-132.

并行调度 第4篇

关键词：JBPM工作流,并行任务,调度机制

1 JBPM引擎

1.1 JBPM基本模型

JBPM定义了自己的流程定义语言jPdl，用它来精确描述业务流程，并为用户提供了可视化的面向图形的编辑流程定义的方法，其流程定义采用XML格式。JBPM的流程引擎模型由Node(节点)、Transition(变迁)、Token(令牌)要素组成。见图1所示。

Node：类似于Petri网中的库所(Place)。节点代表流程中一个状态，如开始、结束、等待等。

Transition:变迁。每一个流向有一个名称及其将流向节点的名称。名称用来标识流向，目标节点名称起导航作用。如果一个变迁的每个输入库所都拥有令牌，该变迁即为被允许。一个变迁被允许时，变迁将发生。变迁的发生是原子的。

Token：令牌，是库所中的动态对象，可以从一个库所移动到另一个库所。

1.2 JBPM的过程调度机制

在工作流中对业务的调度过程是一个关键的问题，JBPM采用令牌来表示当前实例运行的位置，也利用令牌在流程各个点之间的转移来表示流程的推进。

1.2.1 流程及令牌的创建

当JBPM试图去启动一个流程的时候，首先是构造一个流程实例，并为此流程实例创建一个根令牌，并把这个根令牌放置在开始节点上。

1.2.2 令牌的推进

当令牌已经在开始节点时，我们可以开始往前推进令牌，来促使流程实例往前运行。因为节点与节点之间是变迁这个桥梁，所以，在转移过程中，会首先把令牌放入相关连的变迁对象中，再由变迁对象把令牌交给下一个节点。

1.2.3 事件-动作机制

JBPM提供了可扩展的事件-动作机制，来辅助活动的扩展处理。在令牌的推进过程中，当令牌运行到满足预先设置好的事件时，就会触发动作执行相应的代码。

2 动态并行任务设计方案

2.1 解决方案

基于JBPM创建动态个数并行任务时，有两种基本方法。

第一种如上文提到的在同一个任务点内创建多个任务实例。在令牌到达相应的任务节点后，利用事件执行的一段程序逻辑创建所有的任务，并将节点属性设置为last-wait，这个属性决定了该节点将在完成该节点内的所有任务以后才会进入下一个节点。采用这种方法实现容易，但无法满足将该任务返回的回退操作。

第二种利用子流程，把每种分支都预先做成单独的子流程，在父流程中动态分裂执行线路，在每个执行线路上创建一个子流程，在每个子流程里独立完成自身的业务逻辑，上面提到的回退操作可以在子流程内完成。在聚合时采用聚合节点，通过执行一段程序逻辑可以满足不同的聚合条件，具体如图2。

考虑到在实际的工作流项目中，在各个并行的任务中常常会遇到多步操作，本文使用第二种方式。

2.2 设计方案

要想实现上述方案，不能使用JBPM中自定义的分裂节点来完成分裂工作。可以采用普通节点，并通过事件-动作机制在其中加入用于分裂的逻辑程序。

在JBPM中的分裂也是通过对令牌的操作实现的，由于每个分支都需要一个令牌来推动流程，所以分裂的实质上就是使用当前的令牌作为父令牌创建N个子令牌，并让每个子令牌实施相应的变迁，此时父令牌将停留在分裂所在节点，处于非激活状态。直到满足一定的合并条件时，将父令牌移动到聚合节点并重新激活父令牌。

分裂后的并行任务，都为一个单独的子流程。在没有聚合前，所有的工作都在子流程内完成。在子流程的创建上，使用JBPM自带的ProcessState节点。在JBPM中，所有的节点都继承了一个node类，并重写了一个叫execute的方法。在默认情况下，当令牌到达一个节点后，流程引擎将会调用这个execute方法。在ProcessState的execute方法中，将使用当前令牌和子流程定义创建一个子流程实例，并完成两个流程上下文之间的复制工作。子流程的创建过程同普通流程实例一样，在根据流程定义构造一个流程实例后，会为此流程实例创建一个根令牌，并把这个根令牌放置在开始节点上。在整个子流程的执行过程中将使用自己的根令牌，而ProcessState中创建子流程的令牌将处于等待状态，直到子流程结束后调用token.Signal方法。

通过上面的分析可以看出，通过触发ProcessState节点内的execute方法，一次只能创建一个子流程。要创建动态个数的子流程，只需要创建所需个数的子令牌，让它们实施变迁依次进入ProcessState节点，从而为每个子令牌创建一个子流程。同样在子流程完成后，让子令牌实施同一个变迁到达预先设置好的聚合节点，完成聚合。具体如图3所示。

3 动态并行任务实现方案

3.1 应用案例

以某《质量检验系统》为例，在该实际业务中，首先由检验部门创建流程，然后根据需求创建N个检验项目并分配给相应的科室。各个科室主任接到任务后分配给该科室的业务员。业务员在完成任务后将由科室主任审批，主任有权选择返回业务员重新检验或通过。当任意一个科室的检验任务通过后，将数据提交给流程创建人。

3.2 实现方案

针对这个实例，将采用上述的设计方案为每个科室创建一个单独的子流程。从主任分配任务一直到主任审批，都将在各自的子流程内完成。

3.3 核心代码

由于分裂与聚合是核心技术，在这里主要列举了这两部分的代码：

(1)执行分裂控制器DepartmentFork，继承自org.JBPM.graph.def.ActionHandler，该类主要用于分裂子令牌，并将其推送到下个节点。在业务上，该类实现了按照科室将检验项分类，并预备为每个科室创建子流程。将该类配置在上图中fork node的action中，保证流程执行到fork node时该类能被自动执行，代码如下：

(2) 在聚合时, 采用JBPM自身提供的JOIN节点, 但JOIN节点默认是AND聚合, 虽然在JOIN节点中定义的执行中包含了OR聚合, 但在流程定义时不支持对OR聚合进行持久化。所以我们在JOIN节点中加入自定义的代码, 在流程执行时动态改变JOIN节点的属性, 实现OR聚合。

用于聚合控制的DataOperator.java, 继承自org.JBPM.graph.def.ActionHandler。

对应的流程定义部分:

4 结束语

文中所讨论的技术，已应用于笔者开发的实际应用系统。经测试，该方案能够完全实现各种复杂的业务需求。相对于JBPM自身提供的分裂与聚合节点，采用上述方法具有更好的灵活性、通用性。

参考文献

[1]Tom Baeyens, The State of Workflow, 2004.http://www.theserverside.com/tt/articles/article.tss-l=Workflow.

[2]Wil van der Aalst, Kees van Hee.工作流管理-模型、方法和系统[M].北京:清华大学出版社, 2005.

[3]范玉顺.工作流管理技术基础[M].北京:清华大学出版社, 2001.

[4]张世宏.基于JBPM工作流的电力固定资产管理系统的设计与实现[M].成都:电子科技大学, 2007.

[5]谢艳平.基于J2EE和Jbpm的分布式工作流的研究与应用[M].武汉:武汉理工大学, 2006.

并行调度 第5篇

一、任务分配的基本概念

操作系统中“任务”和“进程”是同一概念的不同说法。任务分配与调度中的“分配”和“调度”也属于同一概念。在操作系统的客户/服务器模型中, 分配是从服务器考虑的, 而调度是从客户方所看到的。按通常的习惯, 我们分别成为静态分配和动态调度。

任务分配是指在多处理机系统中, 针对某一目标, 按照一定的策略将规模为N的任务划分并映射到P个处理机上。任务分配的主要目标是寻找一种合适的分配算法, 使T降低到最低程度。

二、任务配置模型

主机任务由任务定制生成, 每项主机任务定义一次数据发送内容的完整信息。按执行方式任务分为轮循任务、间隔任务和触发任务。每项任务以任务编号为标识, 包括任务名称、任务类型、执行时间、数据源信息、传输数据配置信息等。

三、任务描述模型

任务调度模型描述如下:1.系统有一组处理器 (Pi) 和一组实时任务 (Ti) 组成, 并有一个处理器作为专门的中心调度器;

系统中每个传输节点有一台主机用于任务定制和子机调度, 因此它作为中心调度器, n (n>=1) 个处理子机完成数据解析、数据发送和数据接收任务, 子机集合P={P1, P2..Pn}。每个子机Pi (i=1, 2, ..n) 拥有子机IP, 传输速度等属性[1]。

2. 任务队列T={T0, T1, Tm}表示m (m>=0) 个不同的任务, Ti包含子任务Ti1, Ti2, Tin.。每个实时任务Ti都是周期性任务。有任务定制随机产生。每个任务Ti (i=1, 2, m) 拥有任务ID、任务f类别、开始时间 (Bi) 、执行周期 (pi) 、执行时间 (Ri) 、数据源信息、目标节点等属性。

3. ei, j为Ti, j的最大执行时间, 即子任务Ti, j的每个作业的执行时间不会超过ei, j。

4. di为实时任务Ti的截止期 (结束时间) , 由于pi是执行周期, di=pi, 如第一个子任务的作业释放被的时刻为t, 则最后子任务Ti, n相应作业必须在 (t+di) 时刻完成。

5. 每个子机有自己的调度队列。这样, 在它执行完当前任务以后, 就从其调度队列中取出一个新的任务来执行。

6. 主机调度器与各处理器之间的通信通过调度队列来实现。

四、并行任务分配与调度策略

并行传输过程由主机完成任务分配及子机调度, 子机进行数据解析和传输。由任务定义程序在完成一项传输任务的定制后, 保存相应传输信息, 并将在主机任务队列生成一条任务记录。任务代理[2]负责监控任务队列, 发现匹配的任务向子机分配任务。

(1) 竞争调度策略

竞争调度方式不需考虑各子机的数据传输能力, 采用让子机竞争方式完成任务。主机任务代理检测到主机任务队列中有需立即执行的任务, 向每个空闲子机的任务队列发出传输数据任务, 子机接到任务后开始执行。

(2) 平衡调度策略

平衡调度方式将解析和传输处理同时进行, 主机动态调节解析子机和传输子机的负载平衡。

(1) 主机任务代理检测到主机任务队列中有需立即执行的任务, 向每个空闲子机的任务队列发出解析数据任务, 子机接到任务后开始执行。

(2) 子机解析数据时每次从业务数据库中读取2000 (参考数据) 条记录直接解析到主缓冲池。

(3) 子机检查子机任务队列:1) 无任务, 等待;2) 有解析任务, 重复解析2000条记录直接解析到主缓冲池, 重复2;3) 有发送任务, 从主缓冲池读取2000条记录到子缓冲池, 同步发送到接收端, 重复3。

(4) 主机按设定时间间隔监控主缓冲池动态, 当未发送记录数大于L1时, 将一台解析子机任务转为发送;当未发送记录数小于L2时, 将一台发送子机任务转为解析。任务调整后, 子机在完成上次任务后再次检查子机任务队列时领取新任务。设定值L1、L2在系统运行时根据实际情况调节设定。

(5) 当所有子机任务均已完成时, 主机认为本次发送任务完成。

平衡调度策略适用于子任务分配 (在子任务中再细分, 任务号_表名) , 没有足够的时间进行整体任务分配, 需要按子任务细分。

摘要：本文对并行传输任务分配与调度机制的环境与策略进行了较为详细的介绍。对任务分配的基本概念、任务配置模型、任务描述模型、任务调度的种类和并行任务分配与调度策略等都做了较为详尽说明, 尤其对任务分配与调度算法的可行性进行了严密的论证。

关键词：并行,任务,调度,策略

参考文献

[1]沈卓炜, 汪芸.基于EDF调度策略的端到端实时系统可调度性分析算法, ISSN1000-1239/CN11-1777/TP, 43 (5) :813～820, 2006

[2]Jesus M.Milian_Franco.Adaptive Middleware for Data Replication[A].H.-A.Jacobsen.Middleware2004[C].LNCS3231:IFIP International Federation for Information Processing, 2004:pp.175-194.

并行调度 第6篇

动态规划算法是一种多阶段优化算法, 具有全局收敛性, 目前在单一水库优化调度计算中的应用较为成熟[2,3,4], 但“维数灾”问题使其在大型梯级水库优化调度计算中的应用受到很大限制[5]。动态规划算法应用于梯级水库优化调度计算时的“维数灾”问题主要体现在运行时间长、内存占用量大以及计算程序复杂度高等3个方面。内存占用量大和程序计算复杂的问题可以通过合理的算法设计而得到缓解, 算法运行时间长则可通过现行的并行处理技术来解决。并行技术近年来已成为一种普遍认可的能够提高算法计算性能的有效手段[6,7]。随着多核CPU的不断发展与更新, 串行方法并行化以避免处理器的闲置状态已成为必然趋势。因此设计合理的多维动态规划计算模式并将其与并行处理技术相结合将是解决上述“维数灾”问题的一种有效方法。

本文基于单库动态规划原理和多层嵌套结构的思想, 针对梯级水库优化调度模型提出了多层嵌套多维动态规划 (Multilayer Nested Dynamic Programming, MNDP) 算法, 并从运行时间、计算机内存占用量以及程序设计复杂度等方面与传统多维动态规划算法进行了详细的对比分析, 并针对MNDP算法运行时间长的缺陷, 引进并行处理技术, 构建了多层嵌套多维动态规划并行算法 (Multilayer Nested Parallel Dynamic Programming Algorithm, MNPDPA) 。最后, 以李仙江流域三库梯级为研究背景进行了实例研究。

1 梯级水库优化调度模型

1.1 目标函数

以多年平均发电量最大为目标, 建立梯级水电站优化调度模型, 其目标函数为:

式中:E为调度期内梯级总发电量;t、T分别表示调度时期内时段编号和总时段数;i、n分别表示水电站编号和梯级水电站总数, 梯级水电站从上游向下游依次编号为1, 2, , n;Nti为第t时段第i个水电站的出力;Δt为时段长度。

1.2 主要约束条件

(1) 水量平衡约束。

式中:qti为第i个水库第t时段的发电引用流量;Vti为第i个水库第t时段的末库容;Iti为第i个水库第t时段的区间入流;Wti为第i个水库第t时段的弃水流量;Qti-1为第t时段第i-1个水库的下泄流量, 且Qti=qti+Wti。

(2) 其他约束。包括库容约束、下泄流量约束以及出力约束等:

2 多层嵌套多维动态规划算法

2.1 算法原理

对一个三库梯级系统, 上库的每一个下泄流量组合, 中下两库动态规划模型都有一个对应的最优解;同样, 对于中库的每一个下泄流量组合, 下库动态规划模型也都有一个对应的最优解。因此在求解三库梯级动态规划时, 可根据多层嵌套的思想, 将三库梯级大系统看成是由一个上库单库和一个中下两库子系统组成, 而将中下两库子系统又看成是由一个中库单库和一个下库单库组成。经过如此处理, 求解三库梯级动态规划就可理解为:对应上库的每一个下泄流量组合嵌套求解一个由中下两库组成的两库梯级动态规划。而求解这个中下两库梯级动态规划又可理解为:对应中库的每一个下泄流量组合嵌套求解一个下库单库动态规划。这样三库梯级动态规划的求解最终也就变成了3个单库动态规划的求解。同理, 对于其他多个水库组成的梯级系统, 也可以采用相同的方法进行处理。如此, 可大大减轻梯级水库动态规划计算中的状态组合数, 进而减轻算法设计的复杂度。

以三库梯级系统为例, 基于多层嵌套结构的梯级水库动态规划算法计算原理可用图1表示。图1中的TN表示下游子系统对应上游水库一个确定来流组合下的最优总出力。

该方法在三库梯级系统的求解过程中, 其逆时序递归计算过程与单库动态规划类似, 所不同的是上库的最优余留期效益代表的不是上库, 而是三库系统的最优余留期效益, 中库的最优余留期效益代表的不是中库, 而是中下两库系统的最优余留期效益, 下库的最优余留期效益则单指下库。各库的逆时序递归方程可表示如下:

式中:f*t () 为下库最优余留期效益函数, 表示下库从第t时段出发到第T时段的最优出力之和;y*t () 为中库最优余留期效益函数, 表示中、下两库从第t时段出发到第T时段的最优出力之和;g*t () 为上库最优余留期效益函数, 表示梯级三库从第t时段出发到第T时段的最优出力之和;V表示库容, 为状态变量;Q表示出流, 为决策变量;各变量的上标表示水库编号, 下标表示时段编号;Nt (V1t-1, Q1t) 表示上库在第t时段初库容为V1t-1、下泄流量为Q1t时的出力;Nt (V2t-1, Q2t) 表示中库在第t时段初库容为V2t-1、下泄流量为Q2t时的出力;Nt (V3t-1, Q3t) 表示下库在第t时段初库容为V3t-1、下泄流量为Q3t时的出力。

三库梯级动态规划的逆序递归计算过程可用图2表示。

2.2 计算步骤

MNDP方法具体的逆时序递归计算步骤可总结如下:

(1) 对任意时段, 例如T-3时段, 对于上库库容组合m5-n3, 对应时段末库容离散点n3的最优余留期库容过程已知, 设为图2中上库的细点虚线所示, 其对应有一组下泄流量, 由此下泄流量组合加上上库容组合m5-n3所对应的时段下泄流量对中、下两库系统进行动态规划计算, 可得中、下两库对应的最优水位过程, 如图2中的中、下库的细点虚线所示, 3条虚线所对应的出力加上上库库容组合m5-n3的时段出力即为组合m5-n3所对应的最优梯级余留效益。

(2) 对于m5所对应的所有时段末库容离散点 (n1, n2, , nM) , 都以步骤 (1) 进行计算, 从中找出本时段梯级总余留期效益最大的末库容离散点, 并以此作为本时段初上库库容离散点m5的最优梯级余留期效益所对应的时段末库容点。

(3) 对于当前时段所有的时段初库容离散点 (m1, m2, , mM) , 重复步骤 (1) 、步骤 (2) , 以计算当前时段初所有上库库容离散点mi (i=1, 2, , M) 的最优梯级余留期效益值和所对应的时段末库容点, 并保存。

(4) 重复步骤 (1) 、步骤 (2) 、步骤 (3) , 对上库所有时段进行逆时序计算, 得出所有库容离散点的最优余留期效益信息 (余留期效益值、库容点号等) 。

(5) 利用与单库动态规划相似的方法对上库进行顺推计算, 得出整个调度期的梯级最优效益、上库最优库容过程、以及上库最优库容过程所对应的下泄流量等信息。

(6) 以上库最优库容过程所对应的下泄流量加上区间入流作为中库的入流, 对中、下两库系统进行两库动态规划计算, 计算出各库的出力、出流过程。

对于步骤 (1) 和步骤 (6) 所提到的两库系统动态规划算法, 其计算过程可仿照三库系统动态规划算法的步骤进行。

2.3 对比分析

目前, 常规多维动态规划 (Conventional Multi-dimensional Dynamic Programming, CMDP) 算法应用于梯级水库优化调度问题时, 是将梯级系统各库时段初的所有离散库容状态点进行组合, 并将每一个库容组合作为一个状态, 从后向前逐个时段遍历所有库容组合进行逆时序递归计算, 最后通过与单库动态规划类似的顺时序递归计算而得到全调度期效益最优的各时段库容组合。其逆时序递归计算流程如图3所示。

由此可见, 对于CMDP, 每个时段梯级各水库的所有状态点同时进行组合计算, 因此对于一个三库梯级系统, 逆时序递归计算过程中每个时段的计算将有6层循环、M6个库容组合 (M为库容离散数) , 变量的内存占用量随着水库数目的增加以指数形式增加。而MNDP是将梯级系统分解为多个单库进行分步嵌套计算, 每个水库每个时段的计算只有2层循环、M2个库容组合。虽然系统总的计算次数因部分计算重复而有所增加, 但在计算过程中变量的内存占用量随着水库数目的增加基本保持不变, 而只随离散数的增加而增加。由此可以看出, 在计算复杂度和内存占用方面, MNDP与CMDP相比具有一定的优势。

CMDP算法其实质是以内存空间占用量的增加为代价换取运行时间的缩短, 在水库规模小、离散点数不大的情况下该方法具有很大的优势, 但对于水库数目较多、状态离散点数较大的情况, 其编程复杂度和内存占用量的剧增会在很大程度上限制其推广应用。而MNDP算法其实质是以运行时间的延长为代价换取内存空间占用量的缩减, 运行时间长的缺陷同样会在很大程度上阻碍其推广应用。若能在内存空间占用量减少的同时也缩短其运行时间, 那么MNDP算法就可以在程序复杂度、内存占用以及运行时间3个方面来缓解多维动态规划算法的维数灾问题, 从而实现其在梯级水库优化调度中的有效运用。因此, 将现行的并行处理技术与MNDP算法相结合以提高其计算效率就成为了必然, 而且其嵌套结构计算模式将下游水库系统作为一个独立的子系统, 使得并行计算不仅可以在龙头水库的时段内离散点间进行, 还可以在一个下游子系统内部进行, 从而实现多级并行。

3 多层嵌套多维动态规划并行算法

3.1 MNDP并行性分析

MNDP算法的具体计算流程包含3层循环, 即最外层整个调度期内的时段循环、中间层时段初库容离散点循环和最内层时段末库容离散点循环。由MNDP算法的逆时序递归计算过程可知, 后一个时段的计算依赖于前一个时段的计算结果, 因此时段间的计算不具备独立性, 故最外层时段变量循环不能实施并行计算, 而中间层和最内层循环计算是以离散的水库库容状态点为基础进行, 其计算只和离散点本身的位置有关, 与当前时段的其他状态无关, 对于当前时段其他离散点的寻优计算也没有影响, 即从一个时段初状态点到一个时段末状态点之间的出力计算是相互独立的。因此, 可以利用时段内状态离散点间计算任务的独立性, 对MNDP算法进行并行化改进。时段初状态离散点间的并行计算示意图如图4所示, 时段末状态离散点间的并行计算示意图如图5所示。

从图4、图5可以看出, 在时段末状态离散点间进行并行计算时, 相比于时段初并行, 其每一个内核的任务量要小很多, 因此在相同的总任务量下, 时段末并行所产生的通信时间将会比时段初并行有较大程度增加, 这对运行时间的缩减很不利。故本文采用时段初状态离散点间的并行计算方式对MNDP进行并行化改造。

上述是针对梯级龙头水库时段内状态离散点间的并行化处理, 前面提到MNDP的嵌套结构计算模式可实现多级并行, 即对于一个三库梯级系统, 在已知上库的一个下泄流量组合下, 求解中下两库子系统动态规划时, 可以对中、下库时段内的离散点循环计算进行并行化处理。其原理如图6所示。

3.2 并行性能评价指标

并行算法的性能评价指标主要有并行程序执行时间、粒度、加速比、效率以及可扩展性等。并行加速比SP是用来衡量并行机相对于串行机的加速倍数, 在处理器资源独享的前提下, 假设某串行应用程序在并行处理器上的执行时间为TS, 而该程序并行化处理之后, P个进程在P个处理器上并行执行所需的执行时间是TP, 则该并行程序在该并行机上的加速比SP定义如式 (7) 所示:

并行效率EP是用来衡量一个处理器的计算能力能被有效利用的比率。在一个理想并行机中, 加速比应该等于处理器数量P, 并行效率数值等于1。但在实际系统中, 加速比是小于P的, 效率通常在0至1之间取值。效率EP的计算公式如式 (8) 所示:

4 实例应用

4.1 流域背景及基本数据

李仙江位于我国云南省境内, 属红河水系, 为红河一级支流, 其干流在中国境内河道长473km, 天然落差约1 790m, 出境处多年平均流量约460m3/s, 控制流域面积约19 309km2。李仙江干流上7座水电站, 依次为崖羊山、石门坎、新平寨、龙马、居甫渡、戈兰滩、土卡河。总装机容量148.5万kW。有调节性能的水电站包括崖羊山、石门坎、龙马3座水电站。本文选取崖羊山、石门坎、龙马3座水电站作为研究对象。各电站基本参数见表1。流域长系列径流资料时间为1957-2000年, 共43a。选取其中的1988年作为枯水年以用于模型计算。

4.2 方案设置及计算条件

为了测试MNPDPA在不同CPU核数及不同状态离散数情况下的并行效率, 建立12个含2个不同状态离散数、6个不同核数的并行计算方案。各方案的相关参数设置见表2。

因离散数取为10的倍数, 为使各个内核的任务量均衡, 所用内核数需以10为公倍数。表2中方案4~6以及方案10~12是在上、中两库都进行并行化处理的多级并行方案, 以方案5为例, 其中2表示上库采用2个内核并行, 5表示中库采用5个内核并行。

MNPDPA在Microsoft Visual Studio 2010开发平台上采用C#编程语言实现, 并行开发工具为.NET4的并行拓展库 (Parallel Extensions) 。采用的计算平台为联想万全T350服务器, CPU类型为Intel (R) Xeon (R) E5520@2.27GHz, 16核, RAM为16.0GB。选取程序运行时间、并行加速比以及并行效率3个指标作为MNPDPA的并行性能评价指标。

4.3 计算结果及分析

以枯水年数据为基础, 在状态离散点数分别为10、20的情形下, 利用MNPDPA、MNDP、CMDP以及POA进行三库梯级系统调度期总发电量最大模型 (无梯级保证出力约束) 的求解计算, 所得年发电量如表3所示。

亿kWh

由表3可以看出, 4种方法的年发电均随着状态离散数的增加而增加, 而对于MNPDPA、MNDP和CMDP 3种方法, 在同一状态离散数下的年发电量完全一致, 而且都比POA的结果要好, 验证了此3种方法的全局收敛性, 同时说明了MNDP算法设计及其并行处理的正确合理性。

MNPDPA不同并行方案的运行时间、加速比及效率等结果如表4所示, 其中CPU核数为1时的计算结果表示并行处理前的MNDP计算结果。

从串行计算时间角度分析, 当状态离散数为10时, 其运行时间为46min, 而当状态离散数为20时, 其运行时间增加到1 260min, 耗时较长, 是离散数为10时的27.4倍, 由此可见状态离散数的增加对运行时间的影响非常显著。

而当MNDP经并行处理之后, 由于充分利用了计算机闲置的处理器资源, 运行时间显著下降。与串行方法相比, 各方案的运行时间减少量如表5所示。总的来看, 在并行环境下, 计算中使用的CPU核数越多, 算法的计算时间就越短, 其加速比值也越大。各方案的最大加速比值可达到7.13, 可见充分利用了内核资源, 避免了资源闲置。

min

此外, 由表4可以看出, 在CPU核数相同时, 随着离散数的增加, 算法的加速比值逐渐增大, 计算性能显著增强, 即在相同的并行环境下, 计算任务的规模越大, 计算加速比越大, 且越接近于理想加速比。例如方案1的加速比为1.77, 而方案7的加速比为1.96;方案4的加速比为4.94, 而方案10的加速比为5.81。在相同的总任务下, 随着CPU核数的增多, 每个子线程的计算量减少, 而处理器之间的通信将变得更加频繁, 计算加速比与理想加速比的差距会逐渐加大, 并行计算的效率开始下降。例如方案1的效率为0.89, 而方案6的效率仅为0.33;方案7的效率为0.98, 而方案12的效率仅为0.48。处理器间通信量的增加会在很大程度上影响并行程序的运行时间, 其负面影响程度有时甚至会超过内核数的增加对运行时间所带来的正面影响。这也是方案3和方案5的核数大于方案4, 但运行时间却更长的原因。

综合考虑表4中各并行方案下的加速比和计算效率, 可以看出对于状态离散数为10时的7个方案, 其中方案4的加速比和计算效率均较高, 而且其所用内核数也仅为6, 因此, 此时采用该方案进行并行计算最佳;同样, 对于状态离散数为20的情况, 采用方案10进行并行计算最佳。由此可见, 在现有4核和8核计算机普及的情况下, 不需要增加硬件投资, 多核技术并行化就能有效提高系统的计算效率。此外, 并行算法在一定的总任务下所用的最佳CUP内核数不是越多越好, 而是与任务量以及具体的运行环境等有关。

本实例中所用离散数为10和20, 取值较小, 对于调节库容很大的水库而言, 如果状态的离散数太少, 得到的结果与最优解可能差得较远, 此时可采用类似DDDP的计算模式来处理, 即先以较小的离散数 (例如10) 进行计算, 求得该离散数下所对应的最优解, 然后在该解的上、下一个离散点的范围内 (一个廊道) 进行再一次的离散求解, 同样取离散数为10, 也就是将前2个离散点细化为10个离散点进行求解, 以此类推直到离散程度满足精度要求。与DDDP相比该方法的优点是其第1次优化解是特定离散数下的最优解, 而不是通过其他方法而来, 保证了最终解的全局最优性。同时, 这种在解的周围逐步细化的离散计算方式, 其总计算量仅随着细化次数的增加以和的形式递增。假设离散数为10时第1次优化的计算量是N, 那么如此细化计算4次的总计算量为4 N, 而以离散数10细化计算4次的效果与以离散数 (10/2) 4=625细化计算1次的效果是一致的, 但以离散数625计算1次的计算量却是远远大于4 N。

5 结论

本文以李仙江流域三库梯级为研究背景, 构建了基于多层嵌套结构的多维动态规划算法, 并针对其运行时间长的缺陷, 在多核环境下实现了该算法的并行计算, 有效缓解了多维动态规划应用于梯级水库联合优化调度计算时的维数灾问题, 增强了动态规划算法对梯级水库联合优化调度问题的求解能力。通过实例计算分析发现:1在并行处理之前, 运行时间随着变量离散数的增加增幅显著;2在相同的总任务量下, 随着CPU核数的增加, 一般情况下并行加速比会逐渐增大, 计算耗时逐渐减小, 但处理器之间的通信时间将逐渐增大, 计算效率逐渐下降;3在相同的多核CPU环境下, 计算任务的规模越大, 计算耗时减少幅度越大, 并行计算的优势越显著;4综合考虑并行加速比和计算效率, 并行算法在一定的总任务下所用的最佳内核数与任务量以及具体的运行环境等有关。

由本文的计算实例可以看出在15核并行模式下, MNPD-PA的并行加速比能达到7.13, 有一定的效果, 但其并行效率较低, 仅为0.48。因此如何进一步提高该算法的并行效率是其能否有效应用于大型梯级水库群优化调度计算的关键所在, 值得更进一步的研究。

摘要：为增强动态规划算法对梯级水库群联合优化调度问题的求解能力, 基于多层嵌套的思想, 提出了多层嵌套多维动态规划算法。通过与传统多维动态规划算法的对比分析, 发现该方法能在内存占用量以及程序复杂度2方面有效缓解多维动态规划算法应用于梯级水库群联合优化调度时的维数灾问题。针对该方法在运行时间上的缺陷, 引入并行处理技术, 利用状态离散点间的计算独立性构建了多层嵌套多维动态规划并行算法。以李仙江流域三库梯级为背景进行了实例研究, 并从运行时间、并行加速比、并行效率以及CPU核数等方面对该并行算法进行了详细的性能分析。结果表明在现有的计算条件下该并行算法能有效提高计算效率和缓解多维动态规划维数灾问题。

关键词：梯级水库,多维动态规划,并行算法,优化调度,李向江流域

参考文献

[1]王赢.梯级水库群优化调度方法研究与系统实现[D].武汉:华中科技大学, 2012.

[2]Becker L, Yeh WW G.Optimization of real time operation of a multiple-reservoir system[J].Water Resources Research, 1974, 10 (6) :1 107-1 112.

[3]韩桂芳, 陈启华, 张仁贡.动态规划法在水电站厂内经济运行中的应用[J].水电能源科学, 2005, 23 (1) :48-51.

[4]许自达.动态规划在整体防洪优化调度中应用[J].水力发电学报, 1988, (1) :12-25.

[5]李安强, 王丽萍, 蔺伟民, 等.免疫粒子群算法在梯级电站短期优化调度中的应用[J].水利学报, 2008, 39 (4) :426-432.

[6]Zhongbo Zhang, Shuanghu Zhang, Yuhui Wang, et al.Use of parallel deterministic dynamic programming and hierarchical adaptive genetic algorithm for reservoir operation optimization[J].Computers&Industrial Engineering, 2013, 65:310-321.