于晓义 吴 毅 王达达 杨 昆

(1.云南电力试验研究院 (集团)有限公司电力研究院，云南 昆明 650217;2.西北工业大学系统集成与工程管理研究所，陕西 西安 710072)

1 前言

云南电网公司电力研究院具有人员学历水平较高、容易掌握和接受新的管理思想和方法、有强大的软件开发团队、有与云南电网公司生产管理信息系统同平台、同架构设计开发的生产MIS系统等特点。基于上述云南电网公司信息化发展的大环境与云南电力研究院的基础与特点，选定云南电力研究院作为云南电网公司ERP项目试点单位。

通过前期调研发现，随着业务的发展，电力研究院目前存在的问题的根源为资源的冲突与协调。其主要表现在资源调配、项目管理、人员发展三个方面。

在资源调配方面:多头管理现象突出，人员安排经常出现冲突;缺乏全局性资源调配机制和计划，资源未能得到最优配置，利用率低，造成“准备的资源不用，要用的资源不在”现象;资源控制未和现场实际情况紧密结合起来，造成有限资源并未用在关键的、合适的、亟须的环节，资源负荷不均;资源过程管理粗放，追踪困难，无法细化工时/标准费率定额以指导资源的精细化管理。

在项目管理方面:主要原因是资源管理与项目计划管理协作松散，因人员紧张导致项目质量难以保证，影响客户满意度;对项目人员的时间成本缺乏精细化的控制与管理。

在人员发展方面:员工数量难以满足快速发展的业务需求，核心员工劳动强度大;缺乏系统性的员工职业发展规划与辅导机制，员工职业发展受限。

综上所述，云南电网公司电力研究院在资源优化配置方面已提出了迫切的需求，亟须在资源优化配置方面取得突破，建立面向电力生产技术监督、技术服务和科研开发的全业务的资源优化配置平台，保证业务工作的实时紧密协作，保证生产任务的均衡、生产计划的可执行性、资源的高利用率、项目交付的客户满意度，为电网安全、稳定、经济运行提供技术保障。

2 工作中心协同任务分配问题描述

在电力研究院服务型企业运作境下，企业接收的订单按WBS分解成相互关联的任务，由传统的每个任务有指定的承接专业所，转变为每个任务根据其特点可以有多个可选的承接工作中心，在此条件下产生了多工作中心的负荷均衡优化问题。工作中心任务分配的本质是任务与工作中心资源的映射。

由于任务是按照WBS分解的，所以任务之间的关联关系呈现出一种树状结构，用一个无向图GT(V，E)描述任务之间的关联(见图(1);顶点|V|=N表示待分配的N个任务，用ωi表示任务i的完成周期;边E表示两个任务之间的关联，用eij表示边(i，j)∈E连接的两个任务i与j由不同工作中心完成时的协作消耗工时。

用一个无向完全图GP(P，D)描述K个工作中心的关联关系(见图(2)，dpq表示边(p，q)∈D连接的两个工作中心p与q的单位协作成本。

设每个任务在K个工作中心中能且只能被分配一次。

式1，2分别表示各工作中心的负荷与企业的协作成本。

其中，M(i)表示任务i的承接工作中心，如M(i)=p表示任务i被分配给工作中心p。式1中Loadp表示工作中心p的负荷，即所有分配到p的任务i所消耗的资源ωi之和。式2中，当任务i与j被分配到不同的工作中心，即M(i)≠M(j)时才产生协作成本。协作任务i与j被分配到工作中心M(i)=p与M(j)=q产生的协作成本为:任务i与j的协作消耗工时eij乘以不同的承接工作中心p与q的单位协作成本dpq。

图1、2给出了一个多工作中心任务分配问题的示例。图1描述了一个N=20个任务的无向图GT，图2给出了K=5个工作中心的关联关系图GP。图中圆圈中的数字分别代表任务与工作中心编号。图1中顶点与边上的数字分别代表任务的完成周期与协作消耗工时。图2中边上的数字代表两工作中心的单位协作成本。表1给出了一个关于图1、2的任务分配方案。

图1 任务关联图GT

图2 工作中心关联图GP

表1 分配方案示例表

采用一个K×N的任务资源匹配矩阵描述任务与资源的匹配状态。矩阵的元素spi，代表任务i分配到工作中心p的概率值。因此spi的取值区间为［0，1］，并且每一列的和为1。spi的初始值在满足任务特性要求时取为为任务i的可选承接工作中心数量)，否则取为0。当最终分配方案被获得时，spi趋近于0或1，spi=1是指任务i被分配给工作中心p。

表2、表3分别显示了与图1、2示例相关的任务资源匹配矩阵初始状态和一个分配方案状态的任务资源匹配矩阵，不失一般性取

表2 任务资源匹配矩阵初始状态

表3 分配方案状态的任务资源匹配矩阵

目标函数如式3所示，目的是平衡各工作中心的负荷 (式1)，同时最小化企业的协作成本(式2)。

eij:任务i与任务j的协作交互量(通常用协作消耗工时度量);

ωi:任务i的资源消耗量(通常用任务完成周期表示);

dpq:工作中心p与工作中心q的单位协作成本;

spi:任务i被分配给工作中心p的概率;

Cp:工作中心p的能力总和。

从式3可以看出目标函数由两部分组成。第一部分表示当任务i与任务j分别被分配到不同的工作中心p与q时的协作成本，因此当协作交互量大的两个任务都被分配到同一工作中心完成时，第一部分协作成本取得最小值。第二部分是一个平方和函数，它是每个工作中心的能力利用率与满负荷的差值的平方和函数，在各个工作中心的负荷分配均匀时该函数取最小值。由于第一部分与第二部分都要求极小化，在式3中未采用权重累加的方式合成目标函数，而是采用乘积的方式，这样更能体现每一部分对目标函数影响的敏感性。

3 基于IA的协作优化分配算法

免疫算法是模仿生物免疫系统处理机理和基因进化机理，通过人工方式构造的一类全局寻优搜索算法。尽管免疫系统具有许多优良的计算性能，但现有免疫算法模型仍存在一些问题，主要在抗体的评价形式、抗体的促进和抑制以及记忆库的使用上。抗体评价主要依据抗体与抗原的亲和度，促进高亲和度抗体和抑制低亲和度抗体，往往易陷入局部优化，导致“早熟”。并且，记忆库仅在产生初始种群时被使用，在算法以后的过程中仅更新记忆库而不再利用它，这没有起到加速收敛的效果。葛红等对免疫算法进行了改进，根据期望繁殖率对抗体降序排列，然后一次性消除期望繁殖率低的抗体，试验表明收敛速度有所提高，但这会使不少较优抗体被一块消除，不利于有效提高收敛速度。针对现有免疫算法的不足，提出了基于动态任务资源匹配矩阵的免疫算法，其主要流程见图3。

免疫进化时首先进行抗原识别，分析问题及解的特性并进行抗体编码，本文采用K进制编码，对参与协同工作的工作中心资源按1，2，…，K进行编码，抗体长度为任务数N。若抗体第i个基因位对应的值为p，则表示任务i被分配到工作中心p进行生产加工。此编码直观，易于操作，且不需解码。抗体编码样例见表1。

免疫进化过程中，首先根据任务资源匹配初始矩阵随机产生规模为popsize的初始抗体群体antiby(t)。抗体群体根据抗体繁殖率进行免疫选择，高繁殖率的抗体(优化解)被促进，低繁殖率的抗体(非优解)被抑制。通过促进/抑制抗体的进化，既突出适者生存，又防止个别个体绝对占优，实现免疫系统的动态平衡自调节功能。接着，在这些必要、有效的抗体群体基础上进行免疫操作。经过免疫操作进行免疫进化后，将会产生免疫接种抗体种群antiby_v、交叉克隆的抗体种群antiby_c、亲和突变的抗体种群antiby_m，以及募集的新的抗体种群antiby_n，将这些免疫种群与记忆的较优抗体种群antiby_o合并，生成下一代免疫进化的抗体种群antiby(t+(1)。再在此进化基础上循环进化，直到满足进化的终止条件，输出免疫进化的结果。

图3 基于动态任务资源匹配矩阵的免疫算法流程

3.1 抗体的评价与选择

免疫进化过程中，需要对各抗体进行评价。如果以抗体的适应度为评价指标，当群体中的某个抗体占据了相当规模，而又不是最优解时就极易导致过早收敛。采用抗体浓度来抑制规模较大又不是最优解的抗体，并以信息熵作为衡量相似度的指标，以期望繁殖率作为评价抗体的标准。抗体的繁殖率计算如下:

式中，fit(v):抗体的适应度;F(v):将抗体v作为分配方案代入目标函数式3时对应的函数值;cv:抗体浓度;λac:亲和度阀值;axv，w:抗体 v与抗体w之间的亲和度;H(2):抗体v和抗体w的信息熵，两抗体所有基因都相同时，H(2)=0;N:抗体的基因长度，即为待分配任务数;Hi(2):两个抗体第i个基因位的信息熵;K＇i:第i个基因位可选字符个数，其代表满足任务特性约束，可完成第i个任务的工作中心个数。

由式4显见，抗体的期望繁殖率刻画了适应度、亲和度和浓度的关系，综合考虑了抗体与抗原之间的关系 (即抗体的适应度)、抗体与抗体之间的关系 (通过抗体的亲和度来评价抗体间的相似程度，抗体的浓度来表示抗体与其相似的抗体的规模)。

免疫选择是指在抗体群中依据抗体的期望繁殖率选择抗体。从免疫机理的角度，免疫选择反映了抗体选择的不确定性以及抗体的抑制与促进机制。本文中按照比例选择规则选择抗体种群中的抗体。在免疫种群中抗体被选择的概率如式5:

3.2 疫苗的抽取与接种

有效的疫苗对算法的收敛性和有效性具有重要的正面作用，本算法从动态任务资源匹配矩阵中抽取疫苗，每代进化过程任务资源匹配矩阵是动态更新的，通过该方式来获得有效的疫苗，在深层次上隐含了疫苗也是随抗体进化而不断进化的思想，更加符合生物的进化规律。通过式6计算免疫进化过程中每代对应的任务资源匹配矩阵，其中表示第i个基因位出现p的概率;表示个体第i个基因位的编码值。根据任务资源匹配矩阵中值，当某等位基因上的概率最大且大于某个设定阀值时，将其作为该等位基因上的疫苗，最终提取的疫苗如式7所示。

疫苗接种进行特异性免疫 (Specific Immunity)，有导向性地产生特异性抗体，利用待求解问题的先验知识有效地加速算法的收敛。针对每代进化得到的抗体种群，以事先设定的免疫概率，随机选择父代群体中要进行接种的抗体g1。对选中的抗体g1，将疫苗Y的基因码依次接入，通过置换抗体相应基因位置上的码值产生新的免疫抗体g2，最终形成免疫种群antiby_v。疫苗接种的一个示例如图4所示。

3.3 抗体交叉与变异

交叉是在肯定基因位进化的基础上，通过基因重新组合产生新的抗体，使子代能够继承父代的优良基因，优秀抗体的基因模式得以迅速繁殖并在种群中扩散，使进化向最优方向进行。当交叉由于基因的局部相似而无法产生新的抗体时，通过变异可避免寻优过程陷入局部最优，改善种群的多样性，引导进化探索新的搜索空间。

本文算法的交叉/变异操作采用两点交叉/变异。对于交叉操作，根据交叉概率，随机的从免疫种群中选取两个抗体g1和g2作为父代，在g1中随机选取两个非零且不相等的基因位x1和x2，从而得到交叉区间 ［min(x1，x2)，max(x1，x2)］，在g2上找到对应的交叉区间，将这两个区间内基因互换，就产生了两个新的子代抗体g3和g4，这些子代抗体最终组成一个交叉种群antiby_c。对于变异操作，根据变异概率，随机从免疫种群中选择抗体g1。在g1中随机选取两个非零且不相等的基因位x1和x2，得到变异区间 ［min(x1，x2)，max(x1，x2)］，对该区间上每一个基因位，根据动态任务资源匹配矩阵相应的选择概率，重新组合该区间上的基因，从而形成新的抗体g2，这些抗体最终组成变异种群antiby_m。

3.4 算法的特点分析

在本文算法中，免疫选择将进化群体中较好的候选解确定性地选择参与进化，提供开拓更好候选解的机会。免疫记忆不仅为问题的解决提供高效求解的机会，而且为算法的局部搜索提供必要的准备。这一操作与抗体交叉操作及亲和突变操作共同作用，增强算法局部搜索能力，使算法有更多机会探测更好的候选解。浓度抑制可确保种群中相同或相似的抗体不会大量繁殖，其作用不仅在于保存好、中、差的抗体，而且减轻了免疫选择算子选择存活抗体时的选择压力。免疫选择的作用在于:不仅给适应度高的抗体提供更多选择机会，而且也给适应度及浓度皆低的抗体提供生存机会，使得存活的抗体种群具有多样性，这一机制主要反映了抗体促进和抑制机理以及抗体选择的随机性。本文在抗体种群初始化与募集新成员时，采用基于动态任务资源匹配矩阵的抗体产生方法，通过该方法产生的抗体能够微调群体多样性及增强全局搜索能力，而且由于考虑了动态的任务资源匹配概率，能够加快算法的寻优速度，同时使算法随时有自我抗体被引入而具有开放式特点。这些算子相互作用，使算法具有如下特点:

1)抗体的选择受适应度与浓度的制约，是确定性和随机性的统一;

2)抗体交叉与变异体现了邻域搜索及并行搜索的特性;

3)搜索过程中处于开采、探测、选择、自我调节的协调合作过程，体现了体液免疫应答中抗体学习抗原的行为特性;

4)搜索过程处于开放，随时有自我抗体被加入进化群体，以增强群体多样性，提供产生更好解的机会的同时能够加快算法的寻优速度。

4 仿 真

算法仿真环境为 Windows XP操作系统，3.0GHz CPU，1G内存。仿真工具采用Matlab7.0。基于动态任务资源匹配矩阵的免疫算法参数选取为:进化代数100，种群规模50，种群中交叉产生的个体比率为0.4，变异产生的个体比率为0.2，接种疫苗的个体比率为0.2，募集的新个体比率为0.1，记忆的优良个体比率为0.1，优异基因抽取阀值为0.85，亲和度阀值为0.85。

在算法运行初期，会出现优异的基因未能达到抽取的阀值，导致在接种操作时无疫苗使用，而能够体现基因特异性信息的任务资源匹配矩阵随着抗体种群的进化而不断进化，因此，此时采用依据动态任务资源匹配矩阵产生新的抗体种群是疫苗接种种群的最佳替代，可有效避免无疫苗可用而引起的算法的寻优效率降低的缺点。对本文第一节中的示例问题进行仿真，该问题中所有工作中心的初始负荷为0，其免疫进化过程如图5所示。

图5 免疫进化过程

图5中标识了每代最优任务分配方案对应的目标函数值、协作成本函数值及平方和函数值，分别对应公式3的函数值及式3中第一、第二部分的函数值。其中目标函数值与协作成本函数值共用图中左侧纵坐标轴，平方和函数值使用右侧纵坐标轴。从图中可见，算法进化至第44代取得最优分配方案。由于该问题中设定，决定了工作中心之间具有互换性，因此算法进化过程中将寻找到多个最优分配方案，并且当且初始负荷为0，多个最优方案中的任何一个方案对于该问题都是无差别的。表4给出了最优任务分配方案。

表4 多工作中心任务最优分配方案

图6标识了该最优分配方案对应的各工作中心的能力、负荷、利用率、最高利用率、平均利用率及最低利用率状态。综合图5与图6可见，本文提出的算法实现了平衡各工作中心的负荷的同时最小化企业的协作成本。

图6 工作中心负荷状态图

图7 新增任务的任务关联图

在实际的企业运作中由于有新项目订单情况，存在为新增加任务进行分配的问题，解决该问题有两种方式:一是将新任务与原任务作为一个整体重新进行任务分配;二是在保持原任务分配方案不变的前提下，对新增加的任务再分配。现假设企业有新项目订单到达，需对新增任务进行分配。图7给出了新增任务的任务关联图，新增任务的任务资源匹配初始矩阵如表5所示。

表5 新任务任务资源匹配初始矩阵

第一种方式采用本算法重新计算即可，但在实际生产中由于产生的分配方案将作为计划调度等系统的重要数据输入，该种方式不但涉及任务重分配计算成本，而且还将涉及重计划/调度等成本。故在实际应用中，该方式较第二种方式虽然可能获得相对较高质量的解，但仍较少采用。下文给出了在保证原分配方案不变的基础上，运用提出的免疫算法对新增任务进行分配，即动态的任务再分配。由表5可知，此时问题的初始状态为，且由于是在已有任务分配的基础上进行任务分配，所以各工作中心的初始负荷不为0。因此，对新增任务进行再分配，不仅可以验证该算法在处理新增任务分配问题的灵活性，同时还可以将其作为一个当且初始负荷不为0的新的任务分配问题 (初始负荷不为0，更能代表企业实际运作中的多工作中心任务分配问题)。

表6给出了新增任务在表4给出的任务分配方案的基础上，进行任务再分配获得的新增任务的优化分配方案。图8给出了任务再分配后新的优化方案对应的工作中心负荷状态。从图8中可以看出，该任务再分配结果可以满足实际的生产需要，同时验证了算法在解决多工作中心任务组合优化分配的有效性。

表6 任务再分配优化方案

图8 任务再分配工作中心负荷状态图

5 结束语

从多工作中心协同工作的角度，研究了云南电力研究院面向负荷均衡的任务分配问题，提出了用于解决该问题并支持任务重/再分配的免疫算法。运用免疫算法在求解多工作中心任务组合优化分配的过程中，引入动态任务资源匹配矩阵的概念，提高了算法的搜索效率。仿真实验表明该算法的有效性和实用性特点。