本发明涉及电力通信网的技术领域，更具体地，涉及一种电力通信网现场运维作业工单调度方法。
背景技术：
随着我国电网事业的不断发展和智能电网的提出，通信技术在整个电网系统中的重要性不断提升。电力通信传输网的设备不断增多，拓扑结构日益复杂，承载的业务数量和种类也在增加，这对电力传输网的运维工作提出了更高的要求。如何合理地进行现场运维工单调度，制定出高效率且合理的计划，对于切实满足运维需求，保证通信业务正常运行有着重要意义，直接关系到电力通信系统是否可靠稳定，进而影响到电力系统的运行状况。显然对于如何调度电力传输网现场运维作业工单的研究工作有着重要的现实意义。
电力传输网现场运维作业工单调度的主要目标是在尽量保证通信业务(尤其是生产调度通信业务)正常运行的前提下，根据制定的目标函数对各个检修机构提交的检修工单进行合理的调度。目前电力通信网的现场运维调度主要存在现场运维数据交互不畅的问题，这将导致通信网运维作业工单往往无法在第一时间进行流转，不仅会制约现场作业的高效实施，同时现场环节数据无法及时回传也会影响现场作业规范性的落实，造成了现场运维任务调度不合理，运维人员利用率和运维效率较低等问题。此外，电力通信网现场运维作业工单调度过程中还需要综合考虑人员技能、工作难度、人员位置、已承担任务、绩效考核、人员利用率、业务互斥性和设备差异性等多种因素。根据电力通信网现场运维作业工作序列的管理需求，分析电力通信网现场运维任务调度特征，研究现场运维任务调度技术，优化电力通信网现场运维作业工单调度方案，提高运维效率，保证运维作业质量，因此深入研究面向电力通信网现场运维作业工单调度优化方法是十分重要的。
现有技术中如下：
技术方案1：一种基于边际效用函数的电力通信网网络资源调度方法，引入边际效用函数去研究效用函数。以人们对所获得的网络服务质量的满意程度为标准，根据效用值与网络服务质量参数(如带宽)之间的关系确定其效用函数，然后根据效用函数得到基于效用的调度模型，最后求解模型。此方法将电力通信网网络应用分为弹性和非弹性两类，通过边际效用函数求出效用函数，并应用于调度函数；在求解模型时，根据模型最优解的必要条件设计了求解算法。
具体实施流程：
(1)弹性、非弹性应用的边际效用与效用函数
弹性应用的边际效用与效用函数：
非弹性应用的边际效用与效用函数：
(2)确定效用函数参数
(3)基于效用的资源调度模型如下，
其中，
(4)模型求解
技术方案2：基于任务动态优先级分配策略dpa(dynamicpriorityassignment)的电力通信网实时任务调度算法drpa(dynamicrealtimetransactionscheduling)。dpa是一种综合考虑了电力通信网现场运维作业工单调度的任务价值、截止期与空余时间3个特征参数提出的综合任务动态价值密度与执行紧迫性的动态优先级分派策略。drtp是在dpa策略的基础上，提出的一种新的电力通信网实时任务调度算法，详细分析了任务调度中可能出现的情况，讨论了任务抢占与非抢占调度的条件。具体实施流程：
(1)确认系统避免颠簸的条件。
(2)计算任务的动态优先级。
(3)将活动任务及等待任务中优先级最高的任务与执行任务的优先级优先级进行比较。
(4)确定合适的调度策略。
技术方案3：一种获得接近最优的遗传算法，该算法对多项目建设下的电力通信网工单调度问题进行建模，并将目标函数视为资源使用差异的最小化。
具体实施流程：
(1)在搜索空间u上定义一个适应度函数f(x)，给定种群规模n，交叉率pc和变异率pm，代数t；
(2)随机产生u中的n个个体s1,s2,…sn，组成初始种群s＝{s1,s2,…sn}，置代数计数器t＝1；
(3)计算s中每个个体的适应度；
(4)若终止条件满足，则取s中适应度最大的个体作为所求结果，算法结束。
(5)按选择概率p(xi)所决定的选中机会，每次从s中随机选定1个个体并将其染色体复制，共做n次，然后将复制所得的n个染色体组成群体s1；
(6)按交叉率pc所决定的参加交叉的染色体数c，从s1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体s2；
(7)按变异率pm所决定的变异次数m，从s2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体s3；
(8)将群体s3作为新一代种群，即用s3代替s，t＝t 1，跳转到步骤(3)；
现有技术的缺陷在于：
技术方案1采用一种基于边际效用函数的电力通信网网络资源调度方法，它根据边际效用函数的特点，将网络应用分为弹性和非弹性应用，并通过每个应用的边际效用函数求出其效用函数，该方法具有良好的求解效果和速度，但是并未考虑到电力通信网网络的普实用性，降低了网络资源调度的灵活性。
技术方案2采用一种基于dpa的实时任务调度算法，该算法分析了任务抢占调度的各种可能条件，以及系统中可能出现的颠簸调度，并给出避免颠簸的条件，该算法能够提高系统价值收益，降低任务截止期错失率，并大大减少任务抢占的次数，但是该算法没有考虑到电力通信网的人为因素约束条件，忽略了人力资源技能和能力的差异，在一定意义上降低了获得更优目标值解的几率。
技术方案3采用一种遗传算法对多项目建设下的问题进行建模，并将目标函数视为资源使用差异的最小化，该算法有效解决了并行调度问题，但是并没有考虑电网系统中多任务人力资源的调度问题。这严重限制了算法模型的应用，不能合理有效利用电网系统现有资源，导致作业调度效率低下。
技术实现要素：
本发明旨在至少在一定程度上解决上述技术问题，本发明的目的是为了保证电力通信网现场运维作业质量和提高运维作业效率，提出来一种基于多种群粒子群算法的电力通信网现场运维作业工单调度方法，该方法应用于解决电力通信网现场工单调度效率低下问题，该方法首先针对电力通信网现场工单调度业务特征，结合运维人员技能、作业资源等特点，描述并建立多资源约束下的现场运维作业技能最大化与时间最优工单调度模型，然后使用多种群粒子群算法结合k-means 算法进行求解，实现多资源约束条件下的运维工单合理派送。
本发明的技术方案是：一种电力通信网现场运维作业工单调度方法，其中，包括以下步骤：
步骤1：确认现场运维工单调度影响因素，对其进行需求分析，总结出各个影响因素的属性，在此基础上建立模型的约束条件；
步骤2：建立现场运维工单调度优化模型；
步骤3：使用多种群粒子群算法结合k-means 算法进行求解。
所述的步骤1中，具体包括：
(1-1)确认电力通信现场运维作业整个调度过程中需要考虑到的影响因素；
(1-2)建立模型的约束条件。
所述的步骤(1-1)中，具体如下：
电力通信现场运维作业调度问题描述如下：整个作业调度过程中需要考虑到运维人员、运维资源、运维工单3大类；对3类运维影响因素进行需求分析，总结出各个影响因素的属性；
对于运维人员，其包括各种类型的技能、熟练程度和权限状态；
对于运维工单，每个运维项目有不同的工作序列，每道工序有所需工作技能、工作资源和相应完成时间；
对于运维资源，包括运维种类和数量。
所述的步骤(1-2)中，具体如下：
在对现场运维工单调度影响因素的分析基础上，根据电力通信网现场运维的实际需求，总结模型的约束条件如下：
不同项目之间的任务工作序列没有约束，同一项目中存在约束；
如果为当前工作组设置的候选项为空，则需要花费一些时间，并等待部分资源释放后才能部署；
启动后，任务工作序列不能中断；
每个任务工作序列可由1～3人完成；
预先分配和完成项目的时间。
所述的步骤2中，具体包括：
(2-1)建立技能最大化工单调度优化模型maxf，maxf为平均技能因子之和最大化函数，f为平均技能因子之和；
(2-2)建立时间最优的工单调度优化模型minz，minz为时间之和最小化函数，z为时间之和；
(2-3)根据现场运维工单调度约束条件，构建约束公式。
所述的步骤3中，具体包括：
(3-1)基于k-means 聚类算法划分子群；
(3-2)使用多种群粒子群算法进行求解。
所述的步骤(3-1)具体如下：
从粒子群中随机选择一个粒子作为第一个中心粒子c1；
首先计算每个粒子与当前己有的中心粒子之间的最短欧式距离d(x)，然后以公式计算每个粒子被选为下一个中心粒子的概率p(x)，再以轮盘赌法选择下一个中心粒子；
重复上述步骤直到选择出k个中心粒子；
对于剩余的粒子，计算该粒子和所有中心点的欧式距离，将该粒子归属于距离最近的中心点；
对于每一个子群，计算其中心点的位置，方法是计算该子群中粒子在所有维度上的平均值；
如果中心点不发生变化则完成聚类过程。
所述的步骤(3-2)具体如下：
初始化粒子群，依据k-means 算法将粒子群划分成k个子群；
按照目标函数计算每个粒子的适应度；
更新每个粒子历史最优位置、每个子群最优位置和整个种群最优位置；
设粒子i的位置为xi＝(x1,x2,…,xα)，其速度为vi＝(v1,v2,…,vα)，该粒子的位置与速度变化公式为：
其中，w为惯性权重，k代表当前迭代次数，pik为粒子i的历史最优位置，
按照公式更新每个粒子的速度与位置；
每隔m次迭代对整个粒子群重新进行k-means 聚类划分；
检查是否满足退出条件；如果己经满足则结束算法，否则跳转到步骤：按照目标函数计算每个粒子的适应度。
与现有技术相比，有益效果是：本发明使用的k-means 算法是k-means算法的一种改进算法，在选择初始聚类中心这一点上进行了优化，使得聚类中心分布相对均匀，划分子群的效果比较好。
本发明使用多种群粒子群算法，根据一定的规则将粒子群划分成若干个子群，每个子群内部单独进行寻优操作，并且种群之间可以通过共享全局最优解或者种群动态重组等方式交换信息。这样有效增加了整个粒子群的种群多样性，避免算法陷入局部最优解，使最终求得的解更优。
本发明充分分析了电力通信网现场工单现场调度业务特征，结合运维人员、作业资源等特点，构建多资源约束下的电力通信网现场可穿戴运维作业工单调度数学模型，并基于多种群粒子群算法结合k-means 算法进行求解，解决运维现场作业调度中作业任务请求效率低下、作业任务无法自行调整等问题，以提高服务质量以及资源的利用率，实现多资源约束下的运维工单合理派送。
附图说明
图1是本发明k-means 聚类算法流程图。
图2是本发明多种群粒子群算法流程图。
图3是本发明平均等待时间对比图。
具体实施方式
附图仅用于示例性说明，不能理解为对本专利的限制；为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。附图中描述位置关系仅用于示例性说明，不能理解为对本专利的限制。
一种电力通信网现场运维作业工单调度方法，其中，包括以下步骤：
步骤1：确认现场运维工单调度影响因素，对其进行需求分析，总结出各个影响因素的属性，在此基础上建立模型的约束条件；
步骤2：建立现场运维工单调度优化模型；
步骤3：使用多种群粒子群算法结合k-means 算法进行求解。
具体的，步骤1：确认现场运维工单调度影响因素，对其进行需求分析，总结出各个影响因素的属性，在此基础上建立模型的约束条件。
(1-1)确认电力通信现场运维作业整个调度过程中需要考虑到的影响因素：
电力通信现场运维作业调度问题描述如下：整个作业调度过程中需要考虑到运维人员、运维资源、运维工单3大类。对3类运维影响因素进行需求分析，总结出各个影响因素的属性。
a.对于运维人员，其包括各种类型的技能、熟练程度和权限状态；
b.对于运维工单，每个运维项目有不同的工作序列，每道工序有所需工作技能、工作资源和相应完成时间；
c.对于运维资源，包括运维种类和数量。
(1-2)建立模型的约束条件:
在对现场运维工单调度影响因素的分析基础上，根据电力通信网现场运维的实际需求，总结模型的约束条件如下：
a.不同项目之间的任务工作序列没有约束，同一项目中存在约束。
b.如果为当前工作组设置的候选项为空，则需要花费一些时间，并等待部分资源释放后才能部署。
c.启动后，任务工作序列不能中断。
d.每个任务工作序列可由1～3人完成。
e.预先分配和完成项目的时间。
步骤2：建立现场运维工单调度优化模型。
(2-1)建立技能最大化工单调度优化模型maxf，maxf为平均技能因子之和最大化函数，f为平均技能因子之和；
(2-2)建立时间最优的工单调度优化模型minz，minz为时间之和最小化函数，z为时间之和；
(2-3)根据现场运维工单调度约束条件，构建约束公式。
步骤3：使用多种群粒子群算法结合k-means 算法进行求解。
(3-1)基于k-means 聚类算法划分子群。
a.从粒子群中随机选择一个粒子作为第一个中心粒子c1。
b.首先计算每个粒子与当前己有的中心粒子之间的最短欧式距离d(x)，然后以公式计算每个粒子被选为下一个中心粒子的概率p(x)，再以轮盘赌法选择下一个中心粒子。
c.重复第步骤b直到选择出k个中心粒子。
d.对于剩余的粒子，计算该粒子和所有中心点的欧式距离，将该粒子归属于距离最近的中心点，如下表所示。
表1：欧式距离表
e.对于每一个子群，计算其中心点的位置，方法是计算该子群中粒子在所有维度上的平均值。
f.如果中心点不发生变化则完成聚类过程。
(3-2)使用多种群粒子群算法进行求解
a.初始化粒子群，依据k-means 算法将粒子群划分成k个子群.
b.按照目标函数计算每个粒子的适应度.
c.更新每个粒子历史最优位置、每个子群最优位置和整个种群最优位置。
d.设粒子i的位置为xi＝(x1,x2,…,xα)，其速度为vi＝(v1,v2,…,vα)，该粒子的位置与速度变化公式为：
其中，w为惯性权重，k代表当前迭代次数，pik为粒子i的历史最优位置，
按照公式更新每个粒子的速度与位置，如下表所示。
表2：粒子数据表
e.每隔m次迭代对整个粒子群重新进行k-means 聚类划分。
f.检查是否满足退出条件。如果己经满足则结束算法，否则跳转到步骤b。
下面结合仿真实例进行说明：
假定所处理环境为电力通信网环境，所获取的数据来源于该电力通信网现场工单中。具体的处理过程如下：
(1)电力通信网现场运维作业工单调度问题描述为：一个项目组有m1,m2,…mm成员，每个成员都有不同类型的技能和熟练程度。项目团队现在需要完成p1,p2,…pn不同的项目，每个项目都包含j1,j2,…jk任务工作序列。流任务工作序列预先给出，并且还给出完成每个任务工作序列的时间：t1,t2,…tk。每个任务工作序列都有所需工作技能类型和工作时间来表示。
不同项目的每个任务工作序列可能需要具有不同技能的员工。员工wi(i＝1,2,…,m)具有技能s1,s2,…sf，相应的技能因子是y1,y2,…yf(f是技能类别的数量，技能因子yi等于[0,2]，0表示没有技能；1表示平均技能，这意味着工人已经掌握了基本技能；2表示技能很熟练，技能因子由团队领导给出(可以使用专家评估方法)。由于项目团队成员具有技能因子大于0的各种技能，当他们有空时，成员将与任务工作序列进行多对多的关系映射：可以选择一名员工来部署多个任务，一项任务还可选择多名工作人员完成。部署成功后，可以在完成当前任务之前为其分配任务。
(2)建立现场运维工单优化模型
①建立技能最大化工单调度优化模型maxf
maxf为平均技能因子之和最大化函数，f为平均技能因子之和，表示如下：
其中，yij为第j个运维人员具备的第i个任务序列所需技能类型的技能因子；numberi为完成第i个任务序列的运维人员数量；n为待完成项目的数量；k为每一待完成项目的任务序列数量。
②建立时间最优的工单调度优化模型minz
minz为时间之和最小化函数，z为时间之和，表示如下：
其中，cij为第j个运维人员完成第i个任务序列所需的时间；xij为第j个运维人员针对第i个任务序列的完成度；m为运维人员的数量。
③构建约束公式
根据现场运维工单调度约束条件，构建约束公式如下：
其中，ti是一个任务工作序列的结束时间。为确保任务的高质量，员工部署应确保将多个具有最高容量值的免费员工分配到当前任务。
(3)粒子群的初始化
①将搜索空间内每一维度均分成n份，n是粒子的数量，即电力通信网项目组的成员数量m。
②对粒子群中每一个粒子进行初始化，在初始化第i维度的数值时，从该维度未被选过的区间中随机选择一个区间，在该区间内随机生成一个数值，最后将这一区间标记为已选择。
③循环对剩下的粒子按步骤②进行初始化。
(4)根据步骤3-1的k-means 聚类算法将粒子群划分成k个子群，即项目组所有成员完成聚类过程后划分为k个子群。
(5)根据步骤3-2所述计算每个粒子的适应值，更新粒子的自身最优位置、最差位置与子群的全局最优位置、全局最差位置。
(6)基于云模型的惯性权重和学习因子的动态调整
粒子群算法涉及到的参数有惯性权重、学习因子，这些参数对于粒子群算法的收敛速度、求解的优劣、稳定性等性能有着重要的影响。
①惯性权重调整策略
惯性权重决定了粒子继承历史速度的程度，影响着粒子在全局搜索和局部搜索之间的平衡程度。w的取值一般在[0,1]之间，如果是w只定义成常量，那么将不利于算法的性能。一种w的经典取值算法，就是线性递减方式，公式表示为：
其中，wi 1是惯性权重在第i 1次迭代中的取值，i-count是算法规定的最大迭代次数，wmax和wmin是两个常数，分别表示算法中规定的惯性权重的最大值和最小值。
采用云模型算法对惯性权重w进行动态调整，避免了惯性权重不合理导致的“震荡”现象。公式如下：
其中，μ是对应的隶属度，favg是种群平均适应值。
②学习因子
学习因子分为两部分：个体认知c1和群体认知c2。一种常见的动态调整策略为：
使用云模型对学习因子进行调整，以调整c1为例，公式如下：
c1＝c1max-μ*(c1max-c1min)
其中，c1max和c1min分别是给c1设定的最大值和最小值，μ是对应的隶属度。
(7)迭代次数达到m的倍数时重新用k-means 算法对粒子群进行划分。
(8)检查迭代次数是否达到最大值，如果达到则结束算法；否则跳转到步骤(5)。
通过以上步骤，最终可以获得多资源约束下的现场运维作业工单调度最优解。
结合我国某省省级电力通信网部分现网数据对本文提出的算法进行仿真，以该区域在2017年4月的检修计划作为研究对象。该检修周期内需要调度的检修任务列表，以及依据人工方式调度的检修计划分别如表3和表4所示：
表3：实验数据4月检修周期内检修任务
表4：人工调度制定的检修计划
本文分别用多种群粒子群算法对这些检修任务进行调度，为了尽量减少误差对算法进行5次求解，最终结果取平均值。粒子群中粒子数量为80，划分的子群个数为5，惯性权重的最大值最小值分别为0.6和1，学习因子c1和c2的最大值与最小值分别为2和1.2，算法的最大迭代次数为100。
表5：使用多种群粒子群算法调度后的检修计划
如图3中，左侧表示人工调度的平均等待时间，右侧表示多种群粒子群算法调度的平均等待时间。
本发明保护的要点是：根据现场运维工单调度影响因素和调度策略，建立了技能最大化与时间最优的工单调度优化模型、以及约束公式。基于k-means 聚类算法对粒子群进行划分。使用多种群粒子群算法进行求解，求得最优解。一种电力通信网现场运维工单派发方法专利中工单派发模型由工单完成质量之和最大化函数、工单完成时间之和最小化函数、运维人员利用率最大化函数、工单等待时间之和最小化函数，以及约束条件构成，并提出基于布谷鸟算法和极值动力学优化算法求解工单派发模型。一种电力通信网现场运维工单调度方法专利中工单调度模型由平均技能因子之和最大化函数、任务完成时间之和最小化函数以及约束条件构成，并提出病毒遗传算法求解工单调度模型。
显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。
1.一种电力通信网现场运维作业工单调度方法，其特征在于，包括以下步骤：
步骤1：确认现场运维工单调度影响因素，对其进行需求分析，总结出各个影响因素的属性，在此基础上建立模型的约束条件；
步骤2：建立现场运维工单调度优化模型；
步骤3：使用多种群粒子群算法结合k-means 算法进行求解。
2.根据权利要求1所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤1中，具体包括：
(1-1)确认电力通信现场运维作业整个调度过程中需要考虑到的影响因素；
(1-2)建立模型的约束条件。
3.根据权利要求2所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤(1-1)中，具体如下：
电力通信现场运维作业调度问题描述如下：整个作业调度过程中需要考虑到运维人员、运维资源、运维工单3大类；对3类运维影响因素进行需求分析，总结出各个影响因素的属性；
对于运维人员，其包括各种类型的技能、熟练程度和权限状态；
对于运维工单，每个运维项目有不同的工作序列，每道工序有所需工作技能、工作资源和相应完成时间；
对于运维资源，包括运维种类和数量。
4.根据权利要求3所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤(1-2)中，具体如下：
在对现场运维工单调度影响因素的分析基础上，根据电力通信网现场运维的实际需求，总结模型的约束条件如下：
不同项目之间的任务工作序列没有约束，同一项目中存在约束；
如果为当前工作组设置的候选项为空，则需要花费一些时间，并等待部分资源释放后才能部署；
启动后，任务工作序列不能中断；
每个任务工作序列可由1～3人完成；
预先分配和完成项目的时间。
5.根据权利要求4所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤2中，具体包括：
(2-1)建立技能最大化工单调度优化模型maxf，maxf为平均技能因子之和最大化函数，f为平均技能因子之和；
(2-2)建立时间最优的工单调度优化模型minz，minz为时间之和最小化函数，z为时间之和；
(2-3)根据现场运维工单调度约束条件，构建约束公式。
6.根据权利要求5所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤3中，具体包括：
(3-1)基于k-means 聚类算法划分子群；
(3-2)使用多种群粒子群算法进行求解。
7.根据权利要求6所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤(3-1)具体如下：
从粒子群中随机选择一个粒子作为第一个中心粒子c1；
首先计算每个粒子与当前己有的中心粒子之间的最短欧式距离d(x)，然后以公式计算每个粒子被选为下一个中心粒子的概率p(x)，再以轮盘赌法选择下一个中心粒子；
重复上述步骤直到选择出k个中心粒子；
对于剩余的粒子，计算该粒子和所有中心点的欧式距离，将该粒子归属于距离最近的中心点；
对于每一个子群，计算其中心点的位置，方法是计算该子群中粒子在所有维度上的平均值；
如果中心点不发生变化则完成聚类过程。
8.根据权利要求7所述的一种电力通信网现场运维作业工单调度方法，其特征在于：所述的步骤(3-2)具体如下：
初始化粒子群，依据k-means 算法将粒子群划分成k个子群；
按照目标函数计算每个粒子的适应度；
更新每个粒子历史最优位置、每个子群最优位置和整个种群最优位置；
设粒子i的位置为xi＝(x1,x2,…,xα)，其速度为vi＝(v1,v2,…,vα)，该粒子的位置与速度变化公式为：
其中，w为惯性权重，k代表当前迭代次数，pik为粒子i的历史最优位置，
按照公式更新每个粒子的速度与位置；
每隔m次迭代对整个粒子群重新进行k-means 聚类划分；
检查是否满足退出条件；如果己经满足则结束算法，否则跳转到步骤：按照目标函数计算每个粒子的适应度。
技术总结