前后台动态调度算法（精选7篇）
前后台动态调度算法 篇1
0引言
针对车辆动态调度问题,国内外专家学者开展了一系列研究。Gendreau等[1]着重研究了车辆动态调度问题中出现的各种不确定性信息的影响,指出在求解此问题时,对这些不确定性信息应加以全面考虑;Powell[2]详细分析了车辆动态调度问题中一 类随机车 辆调度模 型,采用改进的A-priori两阶段优 化方法求 解了该问 题;Minkoff[3]以马尔可夫决策模型为基础,完成了车辆动态调度问题基于马尔可夫决策过程的建模求解,研究提出的算法在中小规模(10个需求)的车辆动态调度问题求解中可以得到比较满意的解,但因其模型的局限性,算法对大规模的问题难以求解。针对动态车辆调度问题实时性强的特点,张景玲等[4]、王旭等[5]研究了车辆的动态调度问题,通过基于两阶段优化的方法对该类问题进行了有效求解。袁建清[6]以解决车辆利用效率最大化为目标,建立了几类随机数学模型,提出了相应的智能算法,解决了车辆调度的不确定调度问题。文献[7-9]针对车辆动态调度中的不同问题提出了相应的解决方法。
本文以军事行动中车辆动态调 度问题为 背景,提出了基于近似动态规划的车辆动态调度算法。通过对车辆调度问题进行形式化描述,利用近似动态规划方法对车辆动态调度问题进行建模,根据近似动态规划的思想,设计实现求解大规模、多类型车辆调度的算法,并对算法进行了仿真性实验,验证了算法的有效性和优越性。
1动态车辆调度的问题
车辆调度问题对实时性有较高要求,即在尽可能短的时间内,通过合理的运输方式、运输路径、运输工具组合来完成调度任务,是动态车辆调度问题领域关注的重点。对于动态车辆调度问题,本文以一个有关的军事任务中的车辆调度情景予以描述,如图1所示。
在某次军事演习中,共涉及有1个车辆调度中心和N个驻防要点,车辆调度中心拥有载重车、乘坐车、牵引车和特种车四种类型的运力资源,共K辆运输工具。每个驻防要点拥有兵员、物资、装备等参演要素。演习中,需要在这N个驻防要点之间完成兵员、物资和装备的调运服务。演习过程中无法预知哪个驻防要点具有运输任务请求。根据描述情况,可对上述场景进行抽象,得到如表1所示的信息。
将本文研究的问题看作一个系统,问题中每个时刻的调度场景就可看作是该系统的一个状态,那么每个时刻的系统状态与该时刻的调度决策是一一对应的,不同的调度决策导致系统到达不同的状态,因此,每个时刻不同的系统状态价值,可以反映不同调度决策的优劣。由此,文中系统状态价值的含义可以描述为:每个时刻不同的调度决策会对系统的现状和将来产生不同的贡献,由此,每个时刻的系统状态价值就是该时刻对应调度决策对系统的贡献值。
本文涉及的大规模、多类型车辆动态调度问题中,由于不同的运输车辆具有不同的代价权重,因此,当执行不同任务时,动用的车辆不同,相应的收益权重也不同。例如执行任务类别mi,它的回报权重为ζi,t时刻需要被满足的任务数(决策作用前)为nit,t时刻满足的任务数(决策作用后)为n′it;车辆类别为cj,代价权重为ηj,t时刻可调度的车辆数(决策作用前)为kjt,t时刻可调度的车辆数(决策作用后)为k′jt,那么定义贡献函数为
由此,我们用系统状态价值来定义本文研究问题的优化目标:根据每个时刻不断出现的运输任务请求和不断变化更新的车辆状态,在一定条件下(如运输任务类型、任务起止时间、车辆剩余载重、单次最大行驶里程等),动态查询所有车辆状态,挑选合适的车辆,规划合理的路线,尽可能地满足任务点的运输任务请求,使得每个时刻的系统状态价值最大。
2动态车辆调度问题模型
根据上述情景分析,对此调度场景建立相应的模型,主要包括 车辆资源、任 务信息和 调度决策等。
2.1车辆资源
车辆资源建模的基本思想是抽象出车辆资源的重要属性,明确车辆资源的使用规则,从而约束车辆属性向量的空间取值。车辆属性主要包括静态属性和动态属性:静态属性描述车辆资源的基本特点;动态属性刻画车辆资源的状态。
C为车辆资源类型集合,C = {c1(载重车),c2(客车),c3(特种车),c4(牵引车)};a为车辆资源属性向量,a=(a1(车辆编号),a2(车辆类型),a3(实时位置),a4(额定载重/员),a5(剩余载重/员),a6(额定里程),a7(剩余行驶里程),a8(平均速度),a9(下一任务 点),a10(起效时间),a11(上一次接受调度的任务点));A为车辆资源的向量空间;Rt,t′a为t时刻获知的,具有属性a、在t′时刻可用的车辆资源的数量,t′>t;Rta 为t时刻获知的,具有属性a、在当前时刻可用的车辆资源的数量,Rta=(Rt,t′a)t′=t;^Rta 为t时刻获知的,t-1时刻和t时刻之间发生的,由外部信息导致的、具有属性a的、可调度车辆资源的数量,其中外部信息包括:车辆故障停驶、故障车辆恢复行驶等。
通过以上对车辆资源的建模,可以得到:t时刻,可以调度的具有属性a的车辆资源的数量为
t时刻,可以调度的车辆资源的数量为
2.2任务信息
任务请求信息也可以看作是系统资源,为了刻画运输任务的多方面属性以及运输任务的静态属性和动态属性,笔者建立了调度决策模型。通过属性向量来描述和刻画运输任务的状态;通过明确运输任务的使用规则,来约束其属性向量的空间取值。
M为运输任务类型集 合,M = {m1(物资运输),m2(兵员运输),m3(弹药运输),m4(装备运输)};b为运输任 务属性向 量,b = {b1(任务编号),b2(任务类型),b3(任务开始时间),b4(任务结束时间),b5(任务起始 点),b6(任务结束 点),b7(任务量),b8(任务完成状态)};B为运输任务属性的空间向量;Mt,t′b为t时刻获知的,在t′时刻需要被满足的、具有属性b的运输任务请求的数量;Mtb为t时刻获知的,在当前时刻需要被满足的、具有属性b的运输任务请求的数量,即Mtb=(Mt,t′b)t′=t;^Mtb 为t时刻获知的,在t-1时刻和t时刻之间随机出现的,具有属性b的运输任务请求的数量。
那么,t时刻需要被满足的、具有属性b的运输任务请求的数量为
t时刻需要被满足的任务数量为
2.3调度决策
调度决策属于动态系统的内部信息,为了刻画调度决策的内容以及调度决策如何起效作用于车辆资源和运输任务,对调度决策的建模要从对车辆资源和运输任务的状态影响出发,抽象其重要属性,通过定义调度决策的策略集,来约束其属性向量的空间取值。
d为调度决策的属性向量,d = (d1(当前派遣),d2(暂不派遣),d3(执行车辆编号),d4(执行任务编号),d5(预派遣时刻));Da为可以作用于具有属性a的车辆资源向量;Π为可行调度策略的集合。调度策略是指在给定系统状态信息的前提下,决定一个调度决策的规则。在本文的研究中,调度策略由贡献函数(反映当前调度决策对系统当前贡献的影响)和近似价值函数(反映当前调度决策对系统未来的影响)共同来反映。xtad为t时刻,具有属性a的,被决策d作用的车辆的数量,则
σtad 为决策结果指示函数,用来捕获决策的结果,且
那么t时刻,被派遣执行运输任务的、具有属性a的车辆数量为σtadxtad;χt为t时刻,在给定有效信息下的可行调度策略的集合。
为了通过数学形式来反映决策结果,需要定义一个决策函数,一些调度策略,在每个取样时刻,给定系统的状态信息,返回调度决策。
Xtπ(Rt)为决策函数。t时刻,在调度策略π下,给定车辆资源状态Rt,返回一个决策值xt,其中Rt为t时刻系统的状态信息:
其中,γ为折扣因子,介于0和1之间,是指价值经过一段时间后等同的现在的价值,因为价值函数是对未来的一个预测价值,所以需要加上一个折扣因子;t为近似价值函数;Ct(Rt-1,ωt,xt)为系统贡献函数;RM(Rt-1,ωt,xt)=Rt为车辆资源状态转换函数;ωt为t时刻系统外部信息的一次取样。
本文在车辆调度决策过程中,考虑了两种车辆调度方式:一是单车多任务,二是多车单任务。
此外,为了计算的方便,对时间采取离散时间模型,如图2所示。在前述的对车辆资源、运输任务、调度决策的符号中,右下角的时间角标“t”,表示的是离散时间点t时刻或第t期,第t期指t=(t-1,t]。
2.4目标方程
把大规模、多类型车辆动态调度问题看作是一个“动态系统”,把每次作调度决策的场景看作是该系统在时间轴上的一个“状态”St。St由车辆资源状态Rt-1、运输任务信息Mt和调度决策xt 共同描述。St的价值是由贡献函数和近似价值函数共同决定。贡献函数捕获调度决策xt对当前系统状态的影响;近似价值函数捕获调度决策xt对未来系统状态的影响。本文优化目标为:“每期决策,使得在尽可能完成运输任务的前提下,动用的车辆数最少;长期目标是在完成尽可能多的任务前提下,车辆动用率最低。”,那么,大规模、多类型车辆动态调度问题的目标方程可以形式化表达为
其中,xt为式(3)的解,^vtn为系统状态从St条件转移到St+1的近似价值的数学期望。
当然,式(3)还要满足一定的约束条件:1调度决策作用的车辆资源数量不能超过当前已知的可调度车辆资源的数量;2每个时刻的调度决策满足的任务请求数不能超过当期已知的任务请求数;3调度决策作用的车辆资源数量、运输任务数量都是正整数。
3基于近 似动态规 划的动态 车辆调度方法
动态规划是基于多阶段决策过程寻优问题提出的,广泛应用于工程学、运筹学、经济学等多个领域[10]。但是,经典动态规划所面临的“维数灾难”使其只能解决小规模问题,限制了其应用[11]。通过上面的建模,本文采用近似动态规划(ADP)的思想设计动态车辆调度算法。
3.1基本思路和设计流程
基于ADP方法求解大规 模、多类型的 车辆动态调度问题需要划分为两个阶段,第一阶段是训练获取近似价值函数的表达式,第二阶段是应用训练得到的近似价值函数的表达式指导车辆调度。ADP在训练数据阶段是用本次系统产生的数据去更新上一次假设的数据,即将来对过去的影响,不断地更新进而产生出近似价值函数;在应用阶段就是利用训练阶段产生的近似价值函数来生成任务到来时的决策,即对未来的影响。
在第一阶段中,算法基于 “观察-更新”的思想,预先设定总的取样次数N和取样路径长度τ,给定每条取样路径上每个取样时刻对应的系统状态近似估计值的初值t0,然后利用价值迭代的策略,迭代计算目标方程(式(3))。在每次迭代中,通过在取样路径ωn计算得到的新的系统状态值tn更新上一时刻系统状态的近似估计值tn-1,以此来不断逼近系统状态的真实值。算法运行最后得到N组系统状 态近似值tn= {(t1)tτ=1,(t2)tτ=1,…,(tN)tτ=1},然后通过一组达到稳态的系统状态近似值,以线性拟合的思想,拟合这组稳态值,来得到近似价值函数的线性表达式。
因此,第一阶段算法的输入是仿真得到的任务信息,输出为训练周期中每期系统状态价值的近似值。通过仿真任务信息来获得、辨识和测量训练阶段算法的各种参数,比如折扣因子、步长以及系统状态初值等。在第二阶段,应用第一阶段训练得到的近似价值函数表达式,根据当前的运输任务信息,求解决策函数(式(2))以得到优化调度决策xt。因此,第二阶段算法的输入为当前运输任务信息,算法的输出为优化的调度决策xt。
3.2调度策略的启发式规则
在求解大规模、多类型车辆动态调度问题中,本文中车辆调度策略的启发式算法规则集如下:
(1)对于每期出现的新运输任务,尽量从已经派出在外执行任务的车辆中挑选满足新运输任务要求的车辆,而尽量避免从调度中心增派车辆去满足新任 务,以此来减 少每期的 车辆动用数量。
(2)对于当期出现的多个运输任务,按照任务开始时间的紧急程度,优先满足任务开始时间早的任务。
(3)对于在当期随机出现的运输任务请求,在任务开始时间和任务量满足的前提下,优先考虑与现有任务是否可以合并执行,以减少车辆动用的数量。
(4)对于可以满足某一运输任务的多辆可调度车辆,先将这些车辆按照剩余载重的大小进行排序,然后依次挑选剩余载重大的车辆去执行该运输任务;对于剩余载重也相同的车辆,按照可以到达任务起始点的时间排序,依次选择可以最早到达任务起始点的车辆执行该运输任务,这样可以在多车单任务中,减少车辆动用的数量,从而降低车辆的动用率。
启发式规则的输入为当前时刻的运输任务信息,即需要被满足、具有某属性的多个运输任务;输出为可调度的车辆序列和已调度的车辆序列。算法具体步骤描述如下。
(1)查询当期任务信息Mt,按任务类型分类汇总得到每种类型任务数量Mtb2。
(2)对于当期出现的每个任务Mtb,按当期任务的开始时刻从小(早)到大(晚)排序。
(3)for当期出现的、开始时间最早的任务:
do按任务类型要 求、开始时间 要求查询是否有在外 执行任务 的、可调度的相应类型的车辆资源状态。
if有在外执行任务的、可调度的车辆,do返回在外执行任务的、可调度的车辆资源序列。
else查询在调度中心的车辆资源,返回可调度的车辆资源序列:
(4)将步骤(3)中得到的可调度车辆按剩余载重/员从大到小进行排序,得到每种类型可调度的车辆序列:
(5)对步骤(4)中挑选出来的可调度车辆序列中,再对剩余载重相同的车辆按照起效时间从小(早)到大(晚)进行排序,得到每种类型可调度的车辆新序列如下:
(6)计算单车是否可以满足该任务。
if单车满足,do转至步骤(7),else转至步
骤(8)。
(7)从步骤(5)中挑选第一辆车。
(8)从步骤(3)中依次挑选车辆,直到车辆组合剩余载重之和满足任务量要求。
(9)按照贡献函数的定义式计算不同调度决策的贡献值,按当前最大贡献值对应的调度决策调度车辆执行任务。
(10)将当期没有车辆满足的任务顺延至下一期转至步骤(1)。
3.3采用价值迭代和平滑策略训练近似价值函数的算法设计
大规模、多类型车辆调度问题训练阶段的算法采用价值迭代和平滑策略来获取系统状态的真实值。具体算法步骤如下:
(1)初始化。
2设置n=1,N =100,n为取样路径标记,N为总的取样次数;
3初始化车辆资源状态R10。
(2)选择一条取样路径ωn,ωtn=Mtn。
(3)对于训练阶段的每一个取样时刻,t=1,2,…,30。
1令ωtn=Wt(ωn),进行取样的实现;
2调用前述的启发式规则算法,筛选得到最优的执行车辆;
3将执行车辆中可以推迟派遣的,推迟一期派遣;
4根据步骤3计算式 (3),xtn为式(3)的解。
5更新价值函数:
6计算车辆资源状态转换函数,更新车辆资源状态:
(4)n加1,如果n≤N,跳转至步骤(2)。
(5)返回每条取样路径的每组状态价值,即
定义的近似价值函数是关于车辆资源状态和运输任务的线性函数,而车辆资源状态和运输任务状态都是用向量描述的,如果以向量进行近似价值函数计算,其取值空间巨大,容易陷入“维度灾难”,难以求解;因此,笔者对这些向量的维度进行了一定程度的聚集,即忽略对车辆调度决策影响不大的维度。对于本文中的大规模、多类型车辆动态调度问题,每期可调度的车辆数量和已满足的任务数量对于车辆调度决策影响较大,因此,将车辆资源属性向量(Rtna)a∈A聚集为当前时刻可调度的车辆数数量(Rtna)a;将运输任务属性向量聚集(Mtnb)b∈B聚集为当前已被满足的运输任务数量(Mtnb)b。
接下来可计算近似价值函数的线性表达式:
其中,θ1、θ2和θ3为待定参数,根据上述ADP求解问题的算法步骤(5)达到稳态的一组有效值,采用线性回归的方法求解得到待定参数θ1、θ2和θ3,从而得到近似价值函数的线性表达式。
3.4应用近似值函数进行大规模、多类型车辆调度算法设计
大规模、多类型车辆动态调度问题应用阶段算法是对训练阶段获得的近似价值函数进行调度应用,具体算法步骤如下:
(1)初始化车辆资源的状态R0。
(2)输入当前时刻的运输任务信息Mt。
(3)调用前述的启发式规则算法,求解决策函数:
其中,调度决策xt为式(5)的解。
(4)更新车辆资源状态:
4实验
4.1实验场景以及训练结果
根据上文中算法的描述,进行了相应的实验。实验过程中,假定有4种不同类型的车辆,每种类型的车辆有10辆,10个任务点,4种不同的任务。价值迭代算法需要为其设计合理的收敛准则。实验中,在取样时间轴上,具有相同周期长度和固定期数的一组连续的系统状态,本文尝试分别取样50次和取样100次,观察每条取样路径上某一相同时刻系统状态价值的近似值是否趋于稳态,用MATLAB分析,结果如图3所示。
由图3观察比较可以发现:算法在迭代50次后系统状态近似值依然呈现出稳步上升趋势,说明值迭代策略还未逼近到系统状态的真实值;在迭代100次后,观察发现系统状态近似值已经趋于稳态,说明值迭代策略已经逼近到系统状态的真实值,算法已经收敛,所以算法可以终止。
取第100次迭代的最后一组系统状态近似值进行拟合求解,求得近似价值函数的线性表达式,如表2所示。
由此得到近似价值函数的线性表达式如下:
这里采用粒度比较大的线性拟合方式,拟合前这组系统状态近似值的空间表现形式和拟合后近似价值函数的空间展现形式分别如图4和图5所示,由于线性函数存在的误差较大,因此本文用尽可能多的离散值,用非线性的表达方式来得出这个函数。
图4、图5中,z轴为当期系统系统状态近似值,x轴为当期车辆动用数量,y轴为当期任务满足数量,由图可见近似价值函数的线性表达式能够比较好地匹配解空间的值。
4.2算法正确性验证
得到了近似价值函数的表达式之后,我们首先进行算法正确性的验证。利用单期决策(忽略一期以后的影响)的满意度“D”来反映算法的正确性,决策满意度的计算如下:
其中,N1表示当期应该被满足的运输请求任务数,N2表示应用近似价值函数计算后得到的当期实际被满足的任务数。决策满意度越高,说明算法越正确。
通过近似价值函数的表达式(式(6))求解决策函数(式(1)),得到的调度决策结果为x1ad=5,x2ad =1,即1时刻的任务全部派遣车辆执行,2时刻的任务执行任务6。
算法正确性分析:最优的调度决策为1时刻和2时刻的7个任务应该全部执行,即N1=7,而近似价值函数求解决策函数给出的调度决策是实际执行6个任务,即N2=6。如果下一时刻还能满足条件的话,会延期调度剩余的任务。
决策满意度由式(7)计算为85.71%,即正确性为85.71%。可见,算法能够在较短时间内,得到正确性较高的近似满意解。
4.3算法优越性验证
为了进行算法的优越性验证,首先从算法的策略角度进行分析。基于ADP的大规模、多 类型车辆动态调度算法的优越性,主要体现在算法在每期的调度决策中不但都考虑了当期决策对当期系统状态的影响,还考虑了当期决策对系统未来各期的影响。由此,如果我们 仅以基于ADP算法中的启发式规则集为基础,只考虑当期决策对当前系统贡献值的影响而不考虑对将来各期的影响,设计一个大规模、多类型车辆动态调度的贪心算法,贪心算法实现就是任务到达只要有车辆满足条件就立即调度,这样就可以比较出两种调度策略的差异,从而判断哪种调度策略更为优越。
为了评判两种调度策略的优劣,我们根据问题的目标函数定义如下评判指标:
其中,R为目标值,N(t)为每期被满足的任务数,N(v)为每期调度动用的车辆数。对于本文的问题,我们的优化目标是:对于每期调度决策,在尽可能完成任务的前提下,动用车辆数最少。那么,式(8)中的目标值越大,则表明每期执行相同任务数的前提下,车辆动用的数量越少。
对两种算法给定同一组算例参数:取样次数N为100,训练周期T为30,每期任务数为1~15的随机数。
经过运行后,两种算法的各期目标值的平均值的整体图和局部图分别如图6和图7所示。
由图6和图7可见,基于ADP的算法策略目标值的平均值在1.4左右,而贪心算法目标值的平均值在1.2左右,这表明,按照ADP算法策略进行车辆调度,任务完成数量与车辆动用数量比值的平均值要比按照贪心算法策略高16.7%,即对于同样的任务,按ADP的调度策略进行车辆调度比按照贪心策略调度进行车辆调度,平均每期的车辆动用数量要少16.7%。这说明,既考虑每期调度决策的当期贡献值,又考虑对未来各期影响的ADP策略,要比只考虑当期贡献值的贪心策略优越,从而验证了算法的优越性。
5结语
车辆调度问题因其规模大、类型多、不确定性强等特征需要动态的调度模型与调度优化算法。针对大规模、多类型车辆动态调度问题,基于近似动态规划的思想建立了系统状态模型和调度决策模型,提出了车辆动态调度的一系列启发式规则,在此基础上,提出了基于ADP的车辆动态调度训练算法和应用算法。基于训练算法所获得的仿真数据和属性聚集获得了系统的近似价值函数,基于该近似价值函数在应用阶段能够在线快速生成调度决策,为实际决策提供依据。实验结果表明,近似价值函数能够形成对状态价值的有效近似,算法(在缺少未来信息的前提下)所生成的调度能够兼顾当前和未来,显著好于贪心算法。因此,所提出模型和方法是解决大规模、多类型、不确定车辆动态调度问题的有效思路。实际应用过程中,其效果受模型的质量、参数的辨识准确性、训练数据的可获得性及准确性、对系统状态演化的实时跟踪能力等影响,需要针对真实系统进行适应性的调整、仿真和近似。
前后台动态调度算法 篇2
随着全球能源和环境问题的日益突出,风能等可再生能源发电技术得到迅速发展,风电并网的规模也越来越大[1,2]。由于风电出力具有很强的不确定性,含风电场的电网日前发电调度问题常描述成为一个含有随机变量的动态经济调度(DED)问题[3,4]。为了使获得的发电调度计划对于风电场出力不确定性具有适应性,通常采用场景法,通过对风电场出力随机变量进行抽样模拟,进而将随机模型转换为确定性DED模型[5,6,7,8,9,10]。由于随着抽样的场景数目的增多,场景法求解随机DED问题的模型维数将快速增大,直接求解非常费时,因而目前该方法主要应用于中小型系统的优化调度,应用于实际大型电网将面临模型维数太大、求解时间太长的问题。
另一方面,由于发电机组相邻时段出力的变化量存在爬坡率的限制,含风电场的电网日前发电调度问题是一个含有一天所有时段变量的联合优化模型,所有时段变量的同时求解是导致问题维数太大的另一个关键因素。动态规划(DP)法根据最优性原理,即Bellman方程可实现对于日前发电优化调度问题各个时段决策量的解耦求解[11,12]。然而,实际大电网机组众多,每个时段各个机组出力组成的状态维数非常之大,DP法应用于大电网发电调度问题将不可避免地面临着“维数灾”难题。
近似动态规划(ADP)理论通过近似描述值函数与状态量之间的关系来克服“维数灾”难题,文献[13,14]应用ADP理论求解大规模机组组合(UC)问题,不过没有考虑风电随机性对于电网UC的影响。文献[15,16]将ADP理论应用于含风电和储能装置的小型系统优化调度。文献[17]将含有单一风电场和抽水蓄能电站的电力系统随机DED问题描述为随机型存储模型,以抽水蓄能电站水库的储水电量作为系统的存储水平,并采用ADP算法克服随机规划问题中目标函数含有数学期望计算的难题。然而,所提方法只适用于必须含有抽水蓄能电站的电网调度问题;且建立的模型中并没有考虑网络安全约束,获得的调度计划无法满足工程应用需求;另外,目标函数采用机组出力的一次函数,能否适应于DED问题通常采用的二次目标函数还有待进一步验证。
由于目前国内大部分省级电网中不含有抽水蓄能电站,对于不含有抽蓄电站的大型电网,如何应用ADP算法求解其随机DED问题,同时考虑网络安全约束的影响,对于扩大ADP算法在求解随机优化调度问题方面的适用范围,无疑具有重要的实用意义。因而,本文以系统中多个风电场出力的日前预测曲线为基础场景,借助拉丁超立方抽样生成风电场出力误差场景。以当前时段的系统正旋转备用容量作为资源存储量,列写了相邻时段关系的系统状态转移方程,从而建立了不含抽水蓄能电站电网的随机DED问题的随机型虚拟存储器模型(VSM)。在考虑网络安全约束的条件下利用误差场景对随机DED问题各个时段的值函数进行训练,利用训练得到的值函数对预测场景下的VSM进行求解,得到考虑风电出力随机性影响的常规机组日前发电出力计划。
1 随机型VSM描述
存储模型通过设置一个表示系统资源存储量的变量作为系统的状态变量,很好地解决动态规划问题状态的“维数灾”。由文献[17]可知,对于含有抽水蓄能电站的电网,可以方便地以抽水蓄能电站水库的储水电量作为系统的资源存储量,但对不含抽水蓄能电站的电网,在系统中难以找到可直接表示系统资源存储量的变量,因此如何选取系统的资源存储量,成为此类系统存储模型构建的难点和应用ADP算法求解该类系统随机DED问题的关键。
由于在一般电力系统中,系统的旋转备用容量反映了系统的可调控发电能力,相当于存储在系统中可用于平衡风电场出力随机波动和负荷需求变化的容量,由于存储模型只设置一个表示资源存储量的变量,故本文选取系统的正旋转备用容量作为系统的资源存储量,并根据相邻时段的系统正旋转备用容量的变化关系,列写出系统的状态转移方程,从而建立适用于一般电力系统随机DED问题的VSM,并采用ADP算法求解。
1.1 目标函数
优化目标取常规机组总发电燃料耗量最小,由于风电出力的随机性,目标函数应表示为风电的各种可能出力下对应的常规机组总发电燃料耗量的期望值最小,如式(1)所示。
式中:T为调度周期总的时段数,本文取T=96;ΔT为每个时段的持续时间,即15min;St为t时段系统所处状态;xt为决策变量向量;Ct(St,xt)为时段t所有NgNg台常规机组的燃料耗量,
1.2 约束条件
1)基本约束
式中:Ploadj,t为负荷节点j在时段t的功率预测值;Nd为负荷节点数;Pwk,t为风电场k在时段t的出力值,为随机变量;Pi-和P-i分别为机组i的有功出力上、下限;rdi和rui分别为机组i的向下、上爬坡率。
其中,第1个式子为功率平衡方程,第2个式子为常规机组的有功出力上、下限约束,第3个式子为常规机组的爬坡约束。
2)网络安全约束
式中:Fl,t为时段t第l条支路的传输功率;Flmin和Flmax分别为第l条支路传输功率的下限和上限,一般Flmin直接取Flmax的负值;Fij,t为第i个安全断面中第j条支路在时段t的传输功率;Ωi为第i个断面包含的支路集合;FΩimin和FΩimax分别为第i个断面的安全下限和上限。
其中,第1个式子为输电线路安全约束,第2个式子为断面安全约束。支路传输功率Fl,t可由直流潮流模型近似表示为:
式中:Gl,i,Dl,j,Wl,k分别为第i台常规机组、第j个负荷和第k个风电场对支路l的功率转移分布因子,其值由网络结构和支路参数确定[18]。
由于实际大电网支路数众多,若在模型中加入所有的支路安全约束,优化模型的规模会大幅度增加,进而导致求解速度的快速下降。本文采用“求解→安全校验→添加越限支路约束再求解”循环的方法,直至所有支路功率都通过安全校验,这样可加快求解速度,并得到满足所有支路安全约束的最优解[19]。
3)旋转备用约束
为应对风电出力的不确定性和负荷预测误差,系统中应保留一定的旋转备用容量以保证系统安全可靠运行。系统及各常规机组备用约束如下:
式中:sui,t和sdi,t分别为机组i在时段t能够提供的正旋转备用容量和负旋转备用容量;T10为要求的机组旋转备用响应时间,取10min;Su,t和Sd,t分别为系统在时段t的正、负旋转备用容量;Lu和Ld分别为负荷对系统正、负旋转备用的需求系数,通常设定为2%~5%;wu和wd分别为风电场出力对系统正、负旋转备用的需求系数,根据目前国内风电功率预测系统的预测误差范围,可设定为10%~25%;P-wk为风电场k的额定出力。
4)状态转移方程约束
通过将系统正旋转备用容量Su,t设置为系统在时段t的资源存储量,取系统时段t的状态向量为St=(Su,t,Pw,t),则系统的状态转移方程如下:
式中:Ps,t为时段t系统正旋转备用容量相对上一时段的变化量;Pw,t为时段t所有风电场出力组成的向量。Ps,t既与时段t风电场出力随机变量Pw,t有关,又与时段t常规机组出力决策变量xt有关。该方程的物理意义是系统状态在随机变量和决策变量共同作用下的演化形式,体现了相邻两个时段系统正旋转备用容量之间的耦合关系。
5)系统旋转备用变化量约束
每一时段系统正旋转备用容量相对上一时段的变化量有一定的范围限制,这个范围可由风电出力变化量与负荷变化量确定。当风电出力增加大于负荷增长时,系统正旋转备用变化量应满足:
当风电出力增加小于负荷增长时,系统正旋转备用变化量应满足:
2 ADP思想与模型处理
2.1 DP的局限性
基于Bellman的最优性原理,求解多阶段决策问题时,严格意义上DP可以求得全局最优解[20]。对初值问题DP的求解决策过程如图1所示。图中:Jt为时段t的收益;St=fs(St-1,xt)为时段t-1到时段t的状态转移方程。令xt*为时段t的最优决策,求解时先从最后时段开始往前逐一时段递推,依次得到各时段最优决策和值函数与状态关系xT*(ST),VT(ST),x*T-1(ST-1),VT-1(ST-1),…,x1*(S1),V1(S1)的表达式,其中,Vt为时段t的值函数,即从时段t到末时段T内所有阶段收益总和的最优值,然后代入初始状态S0并结合状态转移方程,从前往后逐一求得各时段的最优决策和值函数。
由DP的求解过程可以看出,应用DP求解DED问题,当机组出力连续时,由于爬坡率约束的存在,相邻时段之间的决策变量具有耦合,机组出力可行域也是随不同时段变化的,难以用解析表达式描述决策、收益与状态之间的关系;当机组出力离散时,可以对所有的机组出力组合情况进行评估,但随着机组数、时段数、状态变量数的增加,组合情况呈指数式增长,将面临“维数灾”问题。
2.2 ADP思想
由DP的决策过程可知,DP在求解DED问题时虽然能够求得全局最优解,但对于实际大型电网来说其推导过程过于繁琐,求解的复杂程度难以接受。近年来,Powell等人将ADP方法运用到具有随机性可再生能源接入的电力系统调度中,很好地克服了DP求解DED问题的局限性。
由2.1节可知,DP在决策前需从后往前逐一推导每一状态St对应的值函数Vt(St)的表达式,这是DP求解的关键和难点。如果假定各时段值函数的表达式Vt(St)已知,则在求解当前时段t时,只需在St-1的基础上结合状态转移方程St=fs(St-1,xt)和当前时段值函数Vt(St),即可求得当前时段t的最优决策xt*。但各时段值函数的精确表达式Vt(St)事先无法预知,这为模型的解耦求解带来困难,ADP的思想就是通过采用近似值函数来逼近描述时段t的值函数与状态St的关系,从而实现模型的时段解耦求解,进而可依次求得各时段的近似最优决策xt。由此可以看出,ADP算法的关键就是近似值函数的合理表示。
2.3 模型处理
为了方便应用ADP对随机DED问题的VSM进行求解,需对模型进行一些必要的处理。为此将每个时段假想成两个阶段,分别对应决策前状态(Su,t,Pw,t)和决策后状态(Sxu,t,Pw,t)[21],并定义S^u,t(Pw,t)为时段t观察到随机变量的实现值后状态的变化量。其中,决策前状态(Su,t,Pw,t)表示仅考虑随机变量引起的状态变化量S^u,t(Pw,t)的作用,而未做出决策前的系统状态;决策后状态(Sxu,t,Pw,t)表示做出最优决策后系统的状态。因此系统状态转移方程转化为:
式(9)表示假定时段t观察到的风电变化量直接作用于系统正旋转备用容量,由Sxu,t-1增加演化为Su,t;式(10)表示做出决策得到常规机组出力值xt后,Su,t加上系统正旋转备用容量的实际变化量Ps,t(xt),并扣除没有实际作用效果的后,最终得到决策后系统正旋转备用容量Sxu,t。引入决策前状态和决策后状态后,可得时段t的决策前状态值函数Vt*(Su,t,Pw,t)和决策后状态值函数Vtx(Sxu,t,Pw,t)如下:
此处Πt为由式(2)至式(5)和式(7)、式(8)所确定的xt的可行域。
由式(9)可知,从时段t的决策后状态到时段t+1的决策前状态,仅考虑随机因素的作用,所以式(12)中含期望计算,这给求解带来不便。因此在应用ADP算法求解随机DED问题时,除了要解决近似值函数的合理描述问题,还要处理好系统中随机因素引起的期望计算。
根据文献[21]可知,对于资源分配问题,对于没有明显特性的值函数,可以通过查表与聚类、参数模型、非参数模型等一般工具获得近似值函数;而对于值函数相对资源存储量具有连续、线性或近似线性、非线性(凹性或凸性)性质的,可以采用接近其特性的函数对值函数进行近似。文献[22]给出了对于线性目标函数存储模型采用满足凸性的分段线性函数近似值函数的收敛证明,由于上述VSM的目标函数是二次函数,和线性函数一样具有凸函数特性,因而本文采用满足凸性的分段线性函数来逼近其决策后状态的值函数Vtx(Sxu,t,Pw,t)。因此,通过在决策后状态Sux,t的取值区间上取离散断点R=ρ,2ρ,…,mρ,令vt(Pw,t)=[vt(Pw,t,ρ),vt(Pw,t,2ρ),…,vt(Pw,t,mρ)]T为时段t值函数的斜率向量,其中,m为存储量的所有分段数,ρ为每段长度,则t时段决策后状态的近似值函数可表示如下:
式中:Vtb为时段t值函数的截距;ytr为第r段的存储量。
将式(13)代入式(11),则随机DED问题的VSM可转化为如下不含期望运算的确定性二次规划模型:
3 VSM的ADP求解
3.1 近似值函数的求取
应用ADP求解VSM时,近似值函数t(Sxu,t,Pw,t)对精确值函数Vtx(Sxu,t,Pw,t)的近似精度越高,则近似最优决策xt越接近xt*。为获得高质量的近似值函数,首先根据确定性优化模型求解结果对近似值函数的斜率向量和截距进行初始化,然后扫描误差场景,在每个场景下逐个时间段求解二次规划问题(式(14)),并根据求解结果采用逐次投影近似路径(SPAR)算法[16]修正每次迭代的近似斜率值vtn(Pw,t)和截距值Vntb,直到得到收敛的近似值函数tn(Sxu,t,Pw,t)。SPAR算法对近似值函数的求取过程如图2所示。图中,tn(Sxu,t,Pw,t)为第n次迭代所得近似值函数,Vtx(Sxu,t,Pw,t)为事先未知的精确值函数,和vtx分别为第n次迭代时段t值函数的斜率近似值和时段t值函数斜率的精确值。
斜率向量和截距初始化时,首先根据确定性优化模型的决策结果,获得各时段的资源存储水平Sux,,t0及相应时段的值函数值Vt0。斜率初值设定时以(Sux,,t0,Vt0)作为该时段值函数的极小值点,且其两边各段的斜率符号相反,与极小值点相邻的两段关键点的斜率初始值可根据优化目标的物理意义合理设定,本文主要根据常规机组的煤耗特性系数确定,其余段的斜率根据满足值函数凸性的斜率单调递增特性依次设定。在初始斜率向量给定后,初始截距V0tb根据式(15)确定。
式中:为时段t值函数的斜率初始值。
给定初始斜率向量和截距后,依次在每个场景下逐个时段求解二次规划模型(式(14)),再进行斜率和截距修正,斜率修正过程参见文献[17],得到第n个场景迭代的近似斜率分量和近似值函数值tn(·,Pnw,t)后,根据式(16)计算截距修正值Vntb为:
实际计算中,可只对图2所示关键区域的两段斜率进行修正,再结合截距修正,以节省值函数训练时间,提高计算速度。
3.2 ADP求解过程
ADP求解随机DED问题VSM的步骤如下。
步骤1:求解预测场景对应的确定性经济调度模型,得到各时段决策xt0、存储量和值函数值Vt0。
步骤2:初始化各时段的近似斜率向量,根据初始斜率值和来确定初始截距V0tb。
步骤3:借助拉丁超立方抽样生成基于预测场景P0w,1,P0w,2,…,P0w,T的误差场景样本,获得N个误差场景Pnw,1,Pnw,2,…,Pnw,T(n=1,2,…,N)[23];令n=1,t=1。
步骤4:若n>N则转步骤11,否则继续。
步骤5:若t>T则转步骤9;若t=1,则令的上限和下限设置为;否则计算决策前的资源存储量
步骤6:求解式(14)的二次规划模型,得到最优决策xtn,并计算得到决策后的资源存储量
步骤7:若t<T,则进行斜率和截距修正。
步骤8:t增加1,转步骤5。
步骤9:对场景n的求解结果进行网络安全校验,若存在支路越限,则将越限支路的安全约束加到式(14)所示模型,令t=1,转步骤5;若不存在支路越限,则转步骤10。
步骤10:n增加1,转步骤4。
步骤11:求解预测场景的VSM,获得调度计划。
4 算例分析
为验证本文所建立的随机DED问题的VSM和ADP求解算法的有效性,对某个不含抽水蓄能电站省级电网的发电调度进行建模和求解。以该省网2015年1月5号的数据为例,共有85台常规机组,其中火电机组46台,装机容量为14 560 MW;水电机组39台,装机容量为8 208 MW。风电场5座,额定容量分别为3 958.5,1 140,192,99,49.6 MW,其并网站点见附录A图A1,其中前两个风电场的出力预测曲线,以及系统日前负荷预测曲线和外送功率曲线见附录A图A2和图A3。系统共有线路498条,3个安全断面,各断面数据见附录A表A1。
假定风电出力预测误差服从正态分布,数学期望为各时刻的风电出力预测值,标准差为预测值的20%,借助拉丁超立方抽样方法分别生成20,50,100,200个误差场景进行求解。以20个场景的求解为例,训练过程中值函数变化如图3所示。可以看出,训练刚开始时误差场景的值函数与由确定性模型优化结果反推的值函数非常接近,随着训练的进行,后面误差场景求解得到的值函数慢慢趋向收敛,整个训练过程耗时198.39s。
本文构建的随机VSM和ADP算法求解结果与场景法求解结果的值函数对比见附录A图A4。采用本文模型和ADP算法求得的一天总发电燃料耗量为7.572 027万t,场景法求得的总发电燃料耗量为7.487 056万t,且由附录A图A4中各时段的值函数比较可以看出,ADP算法与场景法求得的燃料耗量结果十分接近。以上比较充分说明了本文建立的不含抽水蓄能电站的随机DED问题的VSM及ADP算法求解的正确有效性。
ADP算法求得的系统正旋转备用与场景法优化结果比较如图4所示。可以看出,两种方法得到的系统正旋转备用的整体变化趋势也基本一致,只是ADP算法得到的系统正旋转备用整体上比场景法略微大一些。
两种方法得到的机组出力计划比较如图5和图6所示。由图5可以看出,两种方法得到的火电机组的出力计划基本一致,部分机组在某些时段出力存在微小偏差。由图6可以看出,场景法得到的水电机组出力存在很大的跳跃,而ADP算法得到的水电机组出力则变化比较缓慢,这是由于水电机组功率调节速度快,每个时段可调节功率范围较大,因此场景法求解时在满足各种约束的条件下为了优化目标函数而使得机组出力会有较大的波动跳跃,这与水电机组自身的调节特性相吻合,而在采用VSM和ADP算法求解时由于式(6)至式(8)的约束,限制了系统正旋转备用的变化,使得备用响应容量较大的水电机组的出力变化也较为缓慢,这更符合实际电网运行调度中对机组出力的调控要求。
同时,由于模型中添加了断面安全约束,能够保证所获得调度方案下系统的安全运行。以20个误差场景的优化为例,与不含断面安全约束求解结果对应的安全断面2的输电功率对比如表1所示。可以看到,在未加断面约束时优化得到的总燃料耗量为75 706.61t,但断面2在某些时段存在功率越限;加入断面约束后,总燃料耗量为75 720.27t,比不加断面约束时增加了13.66t,但断面2功率都小于安全极限。因此,在模型中加入网络安全约束后,为了使系统的关键线路和断面的输送功率在限定范围内,机组的出力安排可能会使得系统总的燃料耗量有所增加,这在一定程度上使得系统的经济效益有所下降,但却避免了系统运行在不安全状态,对系统的安全可靠运行具有重要意义。
接下来分别将该算法与场景法在20,50,100,200个场景的情况下进行比较,验证该算法的计算性能。使用计算机为Intel(R)Core(TM)i7-4900MQ CPU 2.80GHz/32GB内存,计算结果如表2所示。由表2可见,场景法在场景数较少时具有较快的计算速度,但随着场景数的增加,计算所需内存和时间都大幅增长,这在很大程度上限制了场景法的应用,尤其是对于风电场数目多需要抽样很多个场景来准确模拟风电出力特性的大型电网调度问题,场景法求解将会受到计算机内存容量限制。而ADP算法由于实现了对各个场景和各个时段的解耦求解,将大规模优化问题分解成若干个小规模优化问题逐个求解,所以随着场景数的增加,所需内存无明显增长,求解时间也基本只增加了新增加场景进行值函数训练所增加的时间。对于100个场景求解时间只有16min左右,约为场景法的1/12;即使对于200个场景求解时间也只有33min左右,计算速度明显提高。
同时,将所提出算法与基于极限场景集的鲁棒优化调度(RS)方法比较[24]。为保证极限场景能覆盖95%的可能风电出力,取风电功率的变化范围为[μ-2σ,μ+2σ],其中,μ为期望值,σ为标准差值,由于系统中含有5个风电场,故共有25即32个极限场景,RS方法求解总耗时6 378.83s,优化结果的总燃料耗量为75 654.04t。
由此可以看出,虽然RS方法比场景法更能保证对风电出力大范围波动的适应性,但其目标函数值也更大,且在极限场景只有32个的情况下,其求解时间已经分别达到50个场景下场景法和ADP算法的3.3倍和12.9倍,当系统中风电场数目增大时,其求解时间将增加得更为明显。因此,ADP算法与RS方法比较同样能够大幅提高计算速度。
另外,由于极限场景的数目与风电场数目呈指数关系增长,随着风电场数目的增大,RS方法和场景法一样会面临由于问题规模过大超出计算机内存容量限制进而无法求解的问题。因此,ADP算法对于含多个风电场的大型电网随机优化调度问题具有更好的适应性,在求解速度上相对RS方法及场景法具有明显的优势,能够很好地满足应用于实际大型电网日前发电调度的要求。
5 结语
本文将ADP理论推广应用于不含抽水蓄能电站的电网随机DED问题,以正旋转备用容量为存储量,建立不含抽水蓄能电站的电网安全约束随机DED问题的VSM,并通过与场景法和鲁棒优化调度方法求解结果的比较分析验证了所建模型和求解算法的正确有效性,为ADP理论应用于快速求解一般大型电网的随机DED问题提供了新途径。ADP算法实现了对随机优化调度模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列小规模优化问题,有效提高了对大电网随机优化调度模型的求解速度。采用ADP算法求解随机型VSM的优化结果中对应的水电机组出力变化比场景法更加合理,符合实际电网运行调度中对机组出力的调控要求。另外,对于含有抽水蓄能电站的电网调度问题,也可以采用本文提出的VSM建模方法并通过ADP算法快速求解;即便是对于含有多个抽水蓄能电站的电网调度问题,文献[17]的建模方法由于只适用于含单一抽水蓄能电站的电网,会存在建模困难,而本文的VSM建模方法同样能够适用。
本文研究中采用分段线性函数对值函数进行近似,所得调度方案对应的目标函数值比场景法的结果有所增大,如何提高值函数的近似精度,以获得更优的调度方案是本文下一步工作重点;同时,本文建立模型中未考虑不同时段机组启停状态的变化,如何应用ADP算法求解随机机组组合问题是本文的进一步研究方向。
附录见本刊网络版(http://www.aeps-info.com/aeps/ch/index.aspx)。
摘要：针对大电网安全约束随机动态经济调度(DED)问题的求解时间太长,提出了应用近似动态规划算法快速求解不含抽水蓄能电站电网的安全约束随机DED问题的方法。建立了随机DED问题的虚拟存储器模型,以系统的正旋转备用容量作为存储变量,构建系统相邻时段的状态转移方程,并考虑了各输电线路和断面的安全约束。以风电场日前功率预测曲线为基础,通过拉丁超立方抽样产生风电场出力的误差场景,并逐一场景递推求解每个时段的二次规划模型以对各个时段的值函数进行训练,形成收敛的值函数,再代入预测场景求解以获得最终的优化调度方案。该方法实现了对随机DED模型各个场景和各个时段的解耦求解,将一个大规模优化问题分解为一系列的小规模优化问题,有效提高了对大电网随机DED模型的求解速度。以某一实际省级电网为算例,通过与场景法和鲁棒优化调度方法的比较验证了所提出模型和求解方法的正确有效性。
前后台动态调度算法 篇3
电力系统调度决策需要兼顾系统运行的经济性与可靠性, 而旋转备用配置是其中的关键。从目前研究来看, 对于具有前瞻能力的动态经济调度问题[1,2,3,4], 其旋转备用配置有确定性与概率性的2类处理方法。其中, 确定性的备用配置方法多基于文献[4]中提出的方案, 要求每个调度时段系统配置的旋转备用容量均多于某一预先给定的最小限值。然而, 由于该类方法没有计及元件故障的随机特性以及系统的实际运行情况, 难以将系统的响应风险维持在一定水平, 其调度结果难免保守或冒进[5,6,7,8,9,10,11,12,13,14,15]。
针对确定性备用配置方法的缺陷, 文献[10]提出动态经济调度应能使系统在各调度时段维持相同的响应风险, 并通过调度与响应风险评估迭代求解的启发式方法, 将响应风险维持在给定水平。文献[11]在文献[10]的基础上, 通过引入0-1变量将系统需维持的响应风险以约束形式并入动态经济调度模型形成0-1混合整数优化问题, 使调度与响应风险评估同步完成, 避免了启发式算法可能存在的缺陷。文献[12]进一步指出动态经济调度在确定各个时段系统所需维持的响应风险时, 应兼顾旋转备用的成本与效益[13,14], 并对文献[11]的模型进行了改进, 在目标函数中考虑了由于备用不足而造成的用户停电损失, 协调了动态经济调度中备用过多造成发电效率低下与备用过少造成用户停电损失过大之间的矛盾。文献[10,11,12]所述方法均基于单母线模型, 未考虑线路传输功率极限的影响, 其调度结果存在不可行的可能。对此, 文献[15]利用发电联合转移因子[16]将线路传输功率极限约束引入模型, 提出了考虑网络安全约束及用户停电损失的概率动态调度模型。针对所构建模型, 文中给出了一种解耦内点算法, 能满足一定规模系统的求解需求, 但对于较大规模实际系统, 由于矩阵规模过于庞大, 该方法难以奏效。
采用概率性方法解决动态调度中的备用配置问题能够定量地协调系统运行的经济性与可靠性, 其在理念上是较为先进的, 但模型复杂、求解困难制约着该类方法的进一步发展与应用。由此, 本文在前文研究的基础上, 针对概率动态调度的求解问题, 提出一种基于Benders分解的新算法。
1 问题描述
计及网络安全约束及用户停电损失的概率动态调度模型可表示为:
式中:t=t0, t0+1, …, t0+NT, 为调度时段;t0为调度目标时段;NT为前瞻时段数;k=1, 2, …, K, 为事故号;K为需考虑的事故总数;
式 (1) ～式 (3) 构成了概率动态调度模型, 其决策变量为机组输出功率、事故后机组输出功率调整量以及切负荷量。式 (1) 所表达的目标函数由2个部分叠加构成:其一为系统的发电成本, 其二为在各种预想事故发生后, 系统运行状态的调整成本期望。式 (2) 表示正常运行状态下系统的各种等式及不等式约束。其中, 等式约束为发电与需求的平衡约束;不等式约束依次为支路传输功率上限约束、机组输出功率范围约束以及相邻时段间机组的功率变化率约束。式 (3) 表示对于每种预想事故, 调整应满足的约束。其中, 等式约束表示机组输出功率调整以及削减负荷后系统发电与需求的平衡;不等式约束依次为支路传输功率上限约束、机组输出功率上限约束、机组输出功率下限约束、机组向上调整能力约束、机组向下调整能力约束以及切负荷量约束。
模型中, 机组在时段t所需配置的上调备用量与下调备用量为
2 求解方法
2.1 基于Benders分解的算法流程
上述概率动态调度模型构成线性规划问题, 对于实际系统, 其规模较大, 难以直接求解。实际上, 所构成的优化问题在各种运行状态之间仅存在较弱的耦合关系, 充分利用这一规律, 可将原问题分解, 达到减小优化问题求解规模、提高问题求解速度的目的。
为表述方便, 将式 (1) ～式 (3) 抽象表达为:
式中:x为所有时段机组的输出功率向量;yw为情况w下机组的调节量及切负荷量;ρw为情况w发生的概率;f和fw为与成本相关的系数;A, Bw, Hw为约束中的系数矩阵;b和hw为对应约束的限值。
观察式 (4) 不难看出, 模型具有图1所示结构, 即原问题由2个部分组成:其一为不考虑事故调整的动态经济调度部分, 称之为主问题, 其仅含变量x;其二为一组对各时段各预想事故的调整决策问题, 称之为子问题, 其决策变量为相应的yw。其中, 子问题的可行域受主问题影响, 即在各子问题的约束中除了含有自身的决策变量外还含有主问题的决策变量。
由此结构, 参考文献[18], 构建如下算法 (推导过程见附录A) 。
步骤1:初始化原问题目标函数上界UB为+∞, 下界LB为-∞;初始化子问题情况w下对偶问题的上界zw为0;设置初始化迭代次数m=0。
步骤2:求解主问题
采用调度结果更新原问题目标函数下界, 即将max (Fmav, m, LB) 赋给LB。
步骤3:依次或并行求解各子问题 (此时, x为已知量) :
或其对偶问题:
若子问题情况w下有解, 则进行解的最优性检验, 即比较Fsuv, m与主问题中求出的zw的大小, 若前者较小, 则该子问题的解满足最优性条件, 在此次迭代中不产生Benders割;反之, 若后者较小, 则该子问题需向主问题返回Benders最优割作为主问题的附加约束:
若子问题情况w下无解, 即Fsuv, m无限大, 则该子问题需向主问题返回Benders可行割作为主问题的附加约束:
步骤4:若所有子问题均有解且满足最优性条件, 则迭代结束。此时, 此次迭代所得的x以及y1, y2, …, y (NT+1) K即为原问题的最优解。若各子问题均有解, 但存在子问题不满足最优性条件, 则说明此次迭代得到的x以及y1, y2, …, y (NT+1) K是一组可行解, 但并非最优解。此时, 利用此次迭代中得到的解求出原问题的目标函数值, 此处将其设为FPRV, m, 并用该值更新原问题目标函数的上界。即将min (FPRV, m, UB) 赋予UB。
步骤5:若UB与LB之差小于预先设定的允许误差ε, 则迭代结束。此次迭代得到的x及y1, y2, …, y (NT+1) K即可近似认为是原问题的最优解。否则, m增加1, 转到步骤2, 重新计算加入新Benders割后的主问题。
2.2 子问题预筛选
从上述算法描述可以看出, 在每一次迭代过程中, 需要对 (NT+1) K种子问题进行优化求解, 这一过程需要消耗大量的计算时间。而实际上, 从子问题模型可以看出, 各子问题的目标是在受主问题解影响的可行域内寻找指定事故发生后调整费用最小的调整方案, 其最理想的情况无疑是调整费用为0 (调整量为0) 的情况。也就是说, 如果在某次迭代m中, 根据主问题的解, 某子问题情况w下的可行域中包含各决策变量均为0的点, 那么, 该点必然对应该子问题的最优解, 而且一定能够满足最优性条件zw, m小于zw, mav。在此种情况下, 该子问题的目标函数为0, 且不会对主问题返回任意形式的割。
在实际运行中, 由于系统的支路传输容量通常具有一定的冗余度, 在某些传输支路故障时, 上述情况经常出现, 即在不改变各机组运行点及不切负荷的情况下, 系统运行的各项要求仍能被满足 (满足节点功率平衡约束、支路传输功率上限约束, 等) , 那么, 出于子问题对调整费用最小的需求, 此时, 此类子问题的各调整量的最优值均将为0。在此种情况下, 这些子问题便可以忽略, 不必进行优化计算, 从而在每次迭代中省去大量对子问题的解算时间。
据此, 本文算法在步骤2与步骤3之间添加了传输支路故障筛选子程序, 利用断线后的潮流转移因子来实现支路开断事故的快速预先筛选[19]。
3 算例分析
为检验本文方法的正确性与有效性, 本文对源自山东省网的一个445节点系统进行了测试计算。测试中, 考虑单重机组及传输线路故障。算法采用MATLAB R2010a编程实现, 运行在CPU为CORE i3的LEVONO微型计算机上, 该计算机内存为3.24 GHz。
测试系统有48台在线机组和693条线路, 机组总容量为19 618 MW。负荷分布在194个节点上, 根据文献[20]对动态调度解耦充分条件的论述, 算例中动态调度前瞻5个时段 (每个时段持续10 min) , 在未来6个时段 (1个调度目标时段与5个前瞻时段) 中, 系统总负荷需求变化见表1。
算例中, 机组发电成本的平均值设为0.3元/ (kW·h) , 依机组特性不同, 各机组的发电成本在平均值上下10%范围内浮动。机组的调节成本设为其发电成本的1.5倍, 负荷的停电损失评价率依节点负荷组成的不同在1.8元/ (kW·h) 至3.6元/ (kW·h) 之间取值 (见参考文献[21]) 。事故后, 机组允许响应时间设为10 min, 系统失负荷后的平均恢复供电时间设为4 h。
算例中, 6个时段的预想事故总数达到4 446种, 变量总数在129万个左右, 由于内存限制, 无法直接采用ILOG CPLEX或MATLAB LINPROG求解, 由此可见该问题的复杂程度[22,23,24]。
采用本文所述迭代求解方法, 取收敛标准为:①迭代中没有新的Benders割产生;②UB与LB之差小于1元。
迭代20次时, UB为4 392 420.12元, LB为4 392 419.56元, 差值为0.56元, 程序收敛, 用时310.47 s。迭代中UB与LB的变化如图2所示。原问题的解为4 392 420.12元。正如文献[15]中所作的分析, 该解相对于无备用约束调度解所对应的发电成本4 377 550.54元, 其发电成本增加至4 381 255.02元, 增加了3 704.48元;其事故后调整成本期望从18 177.57元降至11 165.10元, 下降了7 012.47元;发电成本与事故后调整成本的合计成本从4 395 728.11元降至4 392 420.12元, 下降了3 307.99元, 系统运行总体经济效益增强。
在计算过程中, 每次迭代产生的Benders割的数目以及进行优化计算的子问题数目由表2给出。从表中可以看出:①Benders割的数目随着迭代次数的增加而逐渐减小, 但这一过程并非单调的;②实际进行优化计算的子问题数目明显小于子问题的总数目, 但多于每次迭代产生的新割的数目;③迭代结束时, 即第20次迭代时仍然产生了3个新割, 但由于其对原问题目标函数减小的作用不明显 (必然小于1元) , 算法并没有继续进行至不产生新割 (迭代27次时, 无新割产生, 此时计算时间为433.46 s, 计算结果为4 392 419.77元) 。
为检验不同系统参数及运行情况对算法计算速度的影响, 继续进行如下2项测试:①将各时段各负荷节点的负荷等比例变化, 变化范围为原负荷值的-15%～15%, 观察迭代次数及计算耗时的变化情况;②将各线路的传输容量上限改变, 变化范围为原传输容量上限的-20%～20%, 观察迭代次数及计算耗时的变化情况。测试结果见表3和表4。
从表3和表4结果可以看出, 负荷需求与线路传输能力均对计算耗时有影响, 但计算时间多维持在300 s左右。其中, 从表4可以看出, 随着线路传输能力的增加, 单次迭代的计算时间逐渐缩短, 其主要原因是由于线路传输能力的增加使每次迭代中需计算的子问题数目减少, 从而导致单次迭代的计算耗时减少。
4 进一步的探讨
对系统运行态势的精确掌控是电网智能化发展的必然要求, 将系统运行风险评估与调度相结合的概率动态调度方法是符合电网这一发展趋势的, 其对机组旋转备用的精细化配置不仅可以节约系统运行成本, 更可满足电力系统改制中对“公平、公开、公正”的要求, 为明确备用责任、分摊备用成本做好必要的技术准备。然而, 正如文献[22,23,24]所述, 对该类随机规划问题的求解是有相当难度的, 从目前研究来看, 尚无在实际系统中进行应用的实例。
本文所提出的基于Benders分解的计算方法及事故预筛选方法在一定程度上解决了实际系统中应用概率动态调度所面临的“维数灾”问题, 且其所采用的分解协调机制还为并行计算提供了算法基础。每次迭代中由原问题分解产生的众多事故调整子问题可在多个CPU或多机间进行并行协调计算, 从而更大幅度地提升计算速度。因实验条件限制, 组建多机系统对此问题进行测试还有待时日, 但为说明情况, 此处暂时利用MATLAB的并行计算功能, 在测试用计算机的2个CPU之间进行了子问题的并行计算测试, 计算耗时明显缩短为167.71 s, 由此不难看出, 本文所提出的分解算法的计算优势。而关于开发高效的多机协调并行计算程序求解概率动态调度问题的研究也正是进一步工作开展的方向。
5 结语
本文针对概率动态调度问题提出了一种基于Benders分解的求解方法。该方法依据问题在系统运行状态间的弱耦合性, 采用Benders分解方法形成求解动态调度主问题与事故后调整子问题的迭代求解格式, 将大型线性优化问题分解求解, 在节约内存使用量的同时提高了计算速度;同时, 算法通过潮流转移因子对支路开断事故进行了预先筛选, 可以在不降低计算精度的前提下, 减少每次迭代所需计算的子问题数目, 提高每次迭代的计算效率。测试表明, 所提出的方法能够对较大规模实际系统的概率动态调度问题进行有效求解, 虽然方法的计算时间与系统运行状态以及系统参数有关, 但对于在一定负荷波动范围内的给定系统, 计算耗时相对稳定且计算速度较快。因而, 该种方法具有在实际生产中进行应用的潜力。
附录见本刊网络版 (http://aeps.sgepri.sgcc.com.cn/aeps/ch/index.aspx) 。
前后台动态调度算法 篇4
当前的作业优化调度算法通常针对产品的生产流程、运输车辆的调度过程以及服务作业的调度[3],与保障站点维修作业的调度有类似的地方,都是为了使生产或服务的效率最高,而保障站点维修作业调度也有其不同之处,主要体现在:各维修作业的对维修资源需求不同;即使是对同一种故障件的维修作业,随着故障模式不同,其维修流程会发生变化,且所需的维修时间也不同;各个下级站点提出的维修作业对应的装备系统型号各异,且优先级不一样等。因此,对保障站点维修作业调度要充分考虑各种不同的约束因素,使作业的调度能取得尽可能好的效果。
1 装备保障站点维修工作调度问题概述
1.1 保障站点维修任务分析
各国现行的装备保障体系通常采用多级保障体制,例如对于海军的某些装备系统,采用基层级、中继级、基地级相结合的三级保障体系;而空军的某些装备则采用二级保障体系[4,5]。现以二级保障模式为例对一个保障站点的维修任务进行分析:一个基地级保障站点通常有多个下属的基层级保障站点,各个基层级站点部署了数量不一、型号各异的装备系统,在某个装备系统出现了故障时,通过故障分析后,得出本次故障的修理级别,如果在本站点(基层级)无法维修,则将故障件后送至所属的上级保障站点(基地级)进行维修。在多个下级站点提出了各种型号系统各种部件的维修需求后,在有限的维修资源下,基地级站点需要决定维修作业的先后次序问题。对维修作业进行调度的目的在于充分利用现有的维修资源,在整体上提高对所有下属站点的保障效率,从而提高所有装备系统的平均可用度。
1.2 保障站点维修工作调度方法
保障站点的维修工作调度主要考虑到故障件的预计维修时间,维修任务优先级和站点的可用维修资源。维修资源包括通用维修设备和设施、用于拆卸和修理的工具、故障件中子部件的替换备件和维修人员等,维修人员又可以分为专业技术人员和维修工人。
在维修资源足够的情况下,保障站点对于所有送来的故障件都立即分配所需的维修资源,对故障件进行拆卸和维修,可以在尽可能短的时间内将所有故障件同步进行修复。然而实际中保障站点的维修资源是有限的,当需要修复的数目超过了其维修能力时,一部分故障件不可避免地要等待维修资源。怎样决定哪个故障件立即进行修复而另外的故障件继续等待,是维修工作调度要完成的任务,这实际上也是如何分配维修资源的问题[6]。
如果不采用专门设计的调度算法,通常采用先进先出或后进先出法,将所有故障件按事先规定的顺序加入维修队列,这种方法容易造成维修资源的浪费,并且一些急需用件可能长时间得不到维修;为此,有方法将故障件加上维修优先级的属性,在故障发生后,装备所在站点给急需的部件加上优先维修的标识,这种方式对于提高保障效率有一定的作用,但是当多个下级站点送来许多高优先级的待修件时,上级站点仍然面临优化调度的问题。
针对上述不足,本文设计了处理故障件维修优化调度的算法,根据故障件的修复时间、可用维修资源、下级站点各装备系统故障状况以及所有装备系统的整体状况等多方面因素,动态决定等待队列中的故障件的维修次序。
为了便于区分上下级站点,将部署和使用装备系统的下级站点简称为场站,而负责对故障件进行维修的上级站点简称为基地。对于三级保障体系而言,基层级对应于场站;中继级是对基层级负责修复的基地,从更高层次来看,又可将多个中继级看成是场站,而基地级负责完成多个中继级站点的故障件修复。
2 装备保障站点维修工作动态调度算法
2.1 维修工作动态调度模型
不同的保障站点可能具有不同的功能,例如有的站点只负责提供备件,而不负责维修;有的则只负责维修不提供备件;还有的既能提供备件又能对故障件进行维修。然而只要是有维修任务的站点,都可能涉及到维修工作的调度问题。
记场站的个数为L,这L个场站共部署了M种不同类型的装备系统,各场站分别部署L1、L2…LL个系统;装备系统发生故障后,经过故障定位、拆卸后运送至基地进行维修的部件种类共有N种。不同的装备系统之间可以共用某种部件,各个场站可以部署不同的装备系统,也可以多个场站部署同一种装备系统。
在序号为l的场站在装备系统发生故障后,经过故障定位,场站需要将序号为n n=,1,2,…,N,的故障件后送至基地,在发送故障件之前,该场站先对隶属于本场站的所有装备系统进行状况统计,本场站所有的装备系统总数为Ll,能正常执行任务的系统数目记为LlWork,则失效的系统数目为:
2.1.1 故障件维修优先级影响因素建模
故障件维修优先级由场站和基地共同确定。场站推荐的维修优先级要反映该场站对该部件的需求,将其定义为:
有时一个场站需要维持一定数量(记为LlLimit)的可用系统才能执行某种任务,当该场站的可用系统数目低于LlLimit时,其故障件的维修优先级将乘以比例因子μμ,>1,,使得其故障件能较快得到修复:
场站在将该故障件后送至基地时,故障件的属性可以用一个向量表示:
FailedItem n,,p,l,
式中,n是故障件的序号,p是场站给出的优先级,l是送出该故障件的场站的序号。
负责维修的基地在收到故障件之后,对其进行维修性分析,计算修复该件所需要的维修资源并估计修复时间。为了简便起见,现只针对一种维修资源进行讨论,在要对多种维修资源进行建模时可以扩充。记修复该件需要的资源数目为r,而修复需要时间为t,注意即使是同一种故障件,由于故障程度和故障模式不同,所需的r和t也不一样,一般地,认为所需维修资源属于一组参数条件下的泊松分布,而维修时间t符合一定参数条件下的正态分布,其均值即为平均修复时间<MTTR<:
式中,T0=MTTR是对应部件的故障件平均修复时间,σ2为方差;
因此一个等待维修的故障件信息在基地表示为:FailedItem n,<p,l,t,r<。多个故障件信息的序号值n可能一样,所有等待维修的故障件表示成一个向量队列:
基地对该等待队列按故障件的序号进行排序,并记队列中序号n为的故障件总数为Dn,而队列中的故障件总数目记为DT,Dn反映了所有站点对这种类型部件的需求,因此是调度算法的一个重要参考信息;此外,基地对等待队列中所有故障件的修复时间进行遍历,找出最长的修复时间记为tmax,最短的修复时间记为tmin;需要的维修资源最大值为rmax,最小值为rmin,而基地的可用维修资源总数为R,故障件开始维修需要占用资源,而修复完成后释放维修资源,因此R是不断变化的。
(1)维修时间对维修优先级的影响
为了在最短的时间内提供最多的可用件,修复所需的时间t越长,则故障件的修复优先级越低:
pt越大,优先级越高。由于tmax和tmin是随队列的变化而不断变化的,因此一个故障件的pt 0<<pt<1<也在动态地变化。对于一个不可修件,可以定义其修复时间为一个较大的值,对应的pt值则非常小,从而该件将得不到修复,当累积的该件较多时,基地考虑为该件安排再订购活动。
(2)所需维修资源对维修优先级的影响
修复所需的资源r越多,则故障件的修复优先级越低:
pr越大,优先级越高。一个故障件的pr同样是不断变化的。
(3)积压的故障件数目对维修优先级的影响
如果某种类型的故障件所需的修复时间较长,或所要求的维修资源较多,则会导致其修复优先级较低,从而会积压较多的该类型故障件。现根据某类部件的积压数目Dn设立调整用的优先级pd:
pd越大,优先级越高。
(4)场站装备状况对维修优先级的影响
负责维修的基地难以获知各个场站装备的实时状况,因此,场站在将故障件送往基地时,就附带指定了场站推荐的维修优先级p。
至此,影响维修优先级的4个因素都已经在对应的参数中表示出来。一个故障件的维修优先级Φ由其对应的4个参数的加权和确定:
式中k=1,2,…,是故障件在队列中的序号;α为加权系数:如果各个场站必须保持不低于某数量<LlLimit<的可用系统时,α取较大的值;如果要让所有场站可用系统的数目最大,则α取较小的值。Φk最大值对应的故障件最先被修理。
2.1.2 同类故障件挑选规则
按照上述方法,可以在等待队列中找出当前最需要修理的部件类型与对应的需求单位。但是队列中可能存在更容易修理(修复时间短且需要较少的维修资源)的同类型部件:
此时将k1与k2项的p,l值互换,然后开始修复k2项代表的故障件。例如场站1急需修复3号部件,而场站2也有需求且送来的3号故障件更容易修复,则将场站2送来的故障件修复后,送回给场站1,下次修复的3号部件再送回场站2。
同类故障件挑选规则使得最先修复的部件同时也是该类型中最容易修复的部件(如果存在),那些被一再推迟修复的部件总是最不重要的和最难修复的,在达到一定数量时可以通过再订购处理。
2.2 维修工作动态调度算法流程
在故障件到达、故障件修复完毕或故障件开始维修等事件发生后,就要开始挑选下一个进行维修的故障件。但是由于维修资源的限制,经过优先级比较选择出的故障件不一定能够得到立即维修,可能还需要等待维修资源的释放。等待维修资源的部件在有新的故障件到达后,要重新进行比较。算法流程如图1。
3 装备保障系统模型与实例分析
3.1 多级装备保障仿真系统
根据装备保障体系运行的过程与特点,以ExtendSim为平台,建立了任务驱动的多层级多等级装备保障仿真系统[1],并在仿真系统中负责维修的站点加入维修调度算法,算法以ModL语言实现。仿真系统中可修复故障件的产生和处理过程如图2。
3.2 保障方案想定
现考查由6个场站和一个基地构成的保障系统,每个场站部署并使用8台同一类型的装备系统,每台装备由10个子系统构成。当某场站可用的系统数量在6台以上时,该场站才能执行某种任务,即LlLimit=6。在执行任务的过程中所有的可用装备都可能发生故障,各个子系统发生故障的频率由各自的可靠性参数决定。当一台系统发生2个以上的子系统故障后,该系统将变为不可用。发生故障后由所在场站拆卸下对应的子系统并送往基地维修,所需的维修资源设为专业技术人员。基地共有45名技术人员,且分为3班,实行8小时轮班制,因此任意时刻有15名技术人员值班。比例因子σ=2,α=1.5。
仿真系统对一年的任务时间进行过程仿真,通过该时间段内资源利用率、各场站执行任务时间、各场站可用系统数目、总的系统可用率变化等指标来评估保障系统的保障效率。运行中产生的数据由ExtendSim输入Excel中进行分析。
3.3 不同调度策略下的保障效率分析
(1)在不考虑维修优先级的情况下,基地采用先进先出(FIFO)方式控制故障件的维修次序。通过1 000次仿真后,得出的资源利用率为78.09%,所有场站累积执行任务1 662.5天,所有场站的可用系统总数平均为39.05,对应的系统平均可用率为81.35%。
(2)采用资源适配法。基地对所有等待修复的故障件按到达的时间排序,然后检查可用资源,并从等待队列中选择第一个故障件,若维修资源足够,则该件进入修复;否则,查看维修资源是否够修复第二个故障件,若足够,则将第二个故障件进行修复,而第一个继续等待。依此类推,直至剩余的维修资源不够任一个故障件进行修复。
采用资源适配法控制故障件的维修次序,通过1 000次仿真后,得出的资源利用率为81.42%,所有场站累积执行任务1 867.3天,所有场站的可用系统总数平均为41.55,系统的平均可用率为86.56%。
(3)采用动态优化调度方法。按照前述的维修工作动态调度算法对等待的故障件进行优化调度,通过1 000次仿真后,得出的资源利用率为85.32%,所有场站累积执行任务2 106.6天,所有场站的可用系统总数平均为44.89,系统的平均可用率为93.53%。
图3显示了多次仿真运行中三种方法下各场站累计执行任务天数的变化。在FIFO法下,如果先到的部件没有得到维修,则后续故障件根本没有机会维修,从而各场站可执行任务的时间较少,从而累积执行任务时间较少;在资源适配法下较FIFO法有所提高;而在动态优化调度方法下,累积执行任务时间最长,且波动的幅度最小。图4(a)显示了3种方法下资源利用率的变化,动态优化调度方法使得资源的利用率最高;而图4(b)显示了平均可用系统数目的变化,动态优化调度方法使得平均可用系统数目较前两种方法有了较大幅度的提升。
所有场站累积执行任务时间的变化情况如表1。
4 结论
为任务繁忙的保障站点设计维修工作动态调度算法,可以更加充分地利用保障站点的各种维修资源,提高故障件平均维修速度,降低故障件的平均等待时间,装备系统总的可用度因此得到了提高;并且由于兼顾了各个下级站点的总体状况,使得各站点的可用装备系统都能维持在一定的水平,增加了各站点能执行任务的时间。
维修资源利用率的提高,以及各站点平均可用系统数目的增加,都可以为实际的保障工作带来较好的效益。论文设计的算法能根据实际的装备保障工作中遇到的各种问题进行扩展,例如增加维修资源的种类,改变装备使用场站的数量和增加其他限制等,因而具有较好的实用性和可扩展性。
参考文献
[1]毛德军,李庆民,彭英武.基于ExtendSim的舰船装备维修保障系统模型[C]//装备保障过程建模理论方法与应用.北京:兵器工业出版社,2009:108-112.
[2]David J P..Tactical Logistics and Distribution System(TLOADS)Simulation[C]//Proceedings of the 1999 Winter SimulationConference,1999:1174-1178.
[3]Cohen,M.A.,Kamesam,P.V.,Kleindorfer,P.,Lee,H.,Tekerian,A..Optimizer:IBM's multi-echelon inventory system formanaging service logistics[J].Interfaces,2006(1):65-82.
[4]邹伟,张涛,郭波.装备维修保障系统的多视图建模方法[J].武器装备自动化,2005,24(2):24-25.
[5]彭英武,李庆民,任海东.基于HLA的海军装备军地一体化保障仿真系统[J].计算机仿真,2009,26(4):18-20.
前后台动态调度算法 篇5
大部分动态车间调度研究都专注于问题规模、算法收敛速度而忽略了工件本身的数据结构和它们之间可能存在的关系。于是, Mohammad提出了一种改进的变邻域搜索算法 (Modified Variable Neighborhood Search, MVNS) , 即搜索前采用K-means聚类后, 利用工件之间的距离来得到更好的结果。但是, 变邻域搜索较为简单, 对所得结果准确度的提升有限。而GA等算法在迭代时因群组过大会出现耗时太长的问题, 因此, 本文采用将分散搜索与改进的变邻域搜索相结合的方式来完成全局搜索。在大规模的车间调度下, 采用这种全新的混合分散搜索算法 (Hybrid Scatter Search, HSS) 来解决动态车间调度问题对实时性有较高的要求。实验结果显示, 与现有的几种动态车间调度算法相比, 这种新的算法得到了更好的结果, 凸显了其实时性和高效性。
1 混合分散搜索算法 (HSS)
与静态车间调度问题相比, 动态车间调度问题中所有的工件并不是在调度一开始就到达的, 而是随着调度的进行而逐渐到达工厂。除此之外, 在动态车间调度问题中, 我们还需要考虑机器的损坏。动态车间调度算法就是解决如何在这种情况下找到一种优化的工件调度序列。
分散搜索算法 (Scatter Search, SS) 是一种已经被成功应用到很多领域来解决优化问题的算法。由于分散搜索的每个步骤都是独立的, 可以分别改进, 因此具有很高的可调整性。除了五个标准的部分外, 我们还在分散搜索中引入了精英策略, 以确保最好的调度个体不会在进化过程中遗失。图1所示为混合分散搜索算法流程。
动态环境中, 机器故障和新工件的增加使得原来的调度已不再适应新的局面。因此, 在发生这些事件时, 需要重新调度。图2所示为实时动态系统。在初始状态下, 有3 个工件, 每个工件有3个工序, 其加工时间都为1.图2 (a) 为整个系统的初始态;图2 (b) 为在正常运行条件下且时间等于1 时, 工件1, 2, 3 的第一个工序均已完成;图2 (c) 中的机器3 发生了故障, 维修时间为1, 系统重新调度, 将工件2 的第二个工序的加工时间延迟了1;图2 (d) 为新工件到来, 可以看到工件4 被置于整个调度中。
本文研究的是10 台机器 (6 台机器以上为复杂的车间调度问题) 处理300 个工件, 每个工件有10 个工序, 每个工序的处理时间均平均分布, 工件到达车间的时间按照泊松分布。在计算平均流程时间时, 由于工件会无休止地到来, 因此采用从稳定态到某一个时间点的算法计算。这种计算方法避免了初始态不稳定的情况对结果造成影响。
1.1 编码方法和适应度函数
在车间调度算法中, 一个关键问题是如何将一个调度计划编码成一种合适的形式。不同的编码架构有不同的优缺点。在研究中, 我们采用了一种基于工序的表示方式。采用这种编码方式可将一种调度计划编码成一个工件编号的序列。假设每一个工件都必须在m个机器上加工一次, 在这种编码方式下, 每个工件编号都将出现m次。通过从左到右依次对编码序列扫描, 我们得到的第k次出现的某个工件编号代表了这个工件的第k个工序。比如, [2 1 3 2 3 3 1 1 2]这串序列就代表了以下这些工序的排序:[O21, O11, O31, O22, O32, O33, O12, O13, O23], 其工件的加工顺序如图3 所示。
适应度函数是车间调度问题中的另一个关键性问题。我们用适应度函数来评价所得到的不同调度计划的表现优劣。在静态车间调度问题中, 我们的优化目标是最小化调度计划的总制造时长 (makespan) 。然而, 在动态车间调度问题中, 通常, 我们的优化目标是最小化所有工件的平均制造时间。在本文中, 一个调度计划S的目标函数被定义为:
式 (1) 中:n为当前已经完成的工件个数;tck为第k个工件的完成时间;trk为第k个工件的到达时间。
1.2 多样性生产方法
基于给定的初始解, 多样性生成方法将产生一组多样性的调度计划作为整个分散搜索算法的第一代解。“多样性”这个词的含义可以理解为, 产生的这些第一代调度计划和初始解具有很大的不同, 并且每个解之间也具有很大的差异。生成的方法可用以下公式表示:
S (h∶t) ={[t], [t+h], [t+2h], …, [t+rh]}. (2) 式 (2) 中:h待定;t=1, 2, …, h, t+rh<l, l为初始解长度。
比如, 给定初始解p= (1, 2, 3, 4, 5, 6, 7, 8) , 如果我们选择h=4 作为多样性生成方法的参数, 那么将得到
p (4∶4) = (4, 8) , p (4∶3) = (4, 8) , p (4∶2) = (2, 6) , p (4∶1) = (1, 5) 。合并这4 个集合, 我们将得到一个新解p (4) = (4, 8, 3, 7, 2, 6, 1, 5) 。类似地, h取n个不同的值, 就可以得到n个不同的解。
1.3 改进部分:结合聚类的变邻域搜索
在用于解决静态车间调度问题的分散搜索中, 这个步骤则为简单的局部搜索。本文采用了结合MVNS的搜索方法:在工件进入车间后, 我们会根据工件本身的特性, 即在各个机器上所需的加工时间用K-means对其聚类。聚类的依据为加工时间的相似度, 相似度越高, 越可能被分为一类。这个分类信息在接下来的交换和插入中会被用到。简单来说, 相距越远的两个类中的工件, 越容易被选中并进行变换, 距离计算公式可参考公式 (2) 。由于距离越远, 意味着两个工件的加工时间差异越大, 交换或者插入这两个工件越容易使整个调度产生更大的变化, 从而使整个搜索变快, 更快地取得更出色的解。
总体的思路如下:
初始化:选择一组用于搜索的邻域Ni (i=1, 2, …, imax) , 产生一个初始解, 设置终止条件 (迭代次数为N) 、设置聚类数。用K-means完成聚类, 计算各类中心之间的距离。
重复以下步骤直至满足终止条件: (1) 设置i←1. (2) 重复以上步骤, 直到i=imax. (3) 随机搜索。根据聚类中心的距离, 随机在第i层产生解x´ (x´∈Ni (x) ) 。 (4) 局部搜索。将上一步得到的x´作为初始解进行局部搜索, 得到局部最优解x´´. (5) 更新。如果x´´比x´好, 则用x´´代替x´, 并在N1 (i←1) 中继续搜索;否则, i←i+1.
VNS算法非常简单、有效, 已经被广泛运用于很多这类问题的优化中。简单来说, VNS的中心思想是在初始解的附近搜索, 如果没有找到比初始解更好的解, 则跳到下一层, 直至k层;如果有比初始解更好的解, 则替换初始解再搜索, 原理如图4 所示。VNS算法优于一般局部搜索之处在于, 它的搜索范围在不断变动, 更加灵活, 所以收敛速度也快得多。
对于VNS算法中“邻域”的定义, 本文采用的是交换和插入, 其中, 交换是指两个工序交换位置, 互相替代;插入是指一个工序插到另一个工序之前。这里要变换的两个工序并不是完全随机挑选的, 而是要结合K-means算法的结果。在这个调度算法中, K-means算法的分类依据为最小方差和, 具体计算公式如下:
式 (3) (4) 中:k为分类的数量;Xij表示第j个工件被分在第i类;Ci为第i类的中心;ni为第i类工件的个数。
1.4 精英策略和引用集
在改良方法、优化步骤之后, 我们对组内所有的调度计划进行了精英策略操作。迭代时, 保留这一代中最好的解, 用来替换下一代中最差的解。原来的分散搜索中没有这个操作, 所以会在迭代过程中丢失暂时取得的最优解。
分散搜索中的引用集是一个兼具多样性和强化性这两个关键特性的解集。根据引用集, 我们可以得到子集。子集的形式为 (x, y) , 其中, (x, y) 均来自引用集。根据不同的方法, 我们将得到3 个子集: (1) 根据引用集A中的解, 两两组合得到; (2) 根据引用集B中的解, 两两组合得到; (3) 第一个解来自引用集A, 第二个解来自引用集B, 其中, 来自B的解为与第一个解距离最远的那个解。我们可以将这三个子集理解为对引用集中的多样性和强化性这两个特性的进一步深化, 可使搜索更加快速、有效。最后一步是对这三个子集中的元素内部交叉变异产生两个新的解。
2 实验结果
为了更直观地看到结果, 我们在编程中加入了显示部分, 用于甘特图的实时输出。每次重新调度时, 系统会自动截取这一刻生成的最优调度方案。图5 所示为混合分散搜索算法下系统产生的甘特图。图5 中, 5 号机器发生故障, 62 号工件为最新加入的工件, 这次的重新调度是因为机器故障, 原本在5 号机器上的60 号工件的最早开始时间由原来的“当前时刻”变成了机器故障被修复后的时刻。
为了更为公平地进行比较, 我们建立了一个与Adibi M A和Shahrabi所写论文中相同的动态实验环境。为了在初始时可以调度, 本文设置的是在刚开始时已经有10 个工件可供调度。两个工件之间的平均到达时间差符合平均值为100~300 的泊松分布, 共5 组实验。之所以这样设置, 是因为间隔超过300时, 工件的到来太过稀疏, 机器上常常只有两三个工件, 调度意义不大。而如果间隔小于100, 则太过密集, 绝大部分工件在等待, 与实际生产不符。机器的平均损耗时间为5 700, 平均修复时间为300.工件的各工序在各机器上的处理时间为平均值为300 的正太分布。工件的加工顺序为随机产生。
在计算时, 为了减少开头静态10 个工件带来的影响, 我们在计算平均流程时间时, 不是计算所有工件的平均流程时间, 而是计算当第150 个工件到达时, 最近完成的100 个工件的流程时间的平均值 (一般说来, 当第150 个工件到达车间时, 已经完成了100 个以上的工件) 。
为了更好地比较本文算法的有效性, 我们在相同的动态环境下, 对以下四种算法, 即混合分散搜索、分散搜索、改进遍邻域搜索和先入先出 (FIFO) 进行了仿真。在参考文献[13]中, 分散搜索用于解决静态车间调度问题, 本文的算法是分散搜索首次用于解决动态车间调度问题;而FIFO和MVNS已经有研究用于动态调度中, FIFO的思想非常简单, 即先到的工件先被安排到调度中, 在参考文献[12]中用于跟MVNS作比较。
图6 所示为各算法运行时间的比较。从图6 可以看出, 我们设置的是工件平均到来的间隔在150~300 之间, 这符合一般实际生产中的情况, 即工件来得不是特别频繁, 但机器总是保持忙碌, HSS与SS和MVNS所花费的时间比较接近。图7 所示为各算法平均流程时间比较。从图7 可以看出, 混合分散搜索在各种工件间隔条件下, 始终比其他算法表现得出色。图8所示为HSS与MVNS比较。从图8 可以看出, 与目前比较有效的MVNS相比, 混合分散搜索所用的时间增加了24%左右。
从以上3 个图不难看出, 我们提出的HSS在动态车间调度问题的解决上有很强的应用性。混合分散搜索之所以能有这样出色的表现, 我们认为主要有以下三个原因: (1) 在引用子集中, A集为最优解, 而B集为与之距离最远的解。将这两个子集用于后续的交叉操作, 既保证了接下去可以强化结果, 又保证了多样性。能兼顾这两点的算法非常少, 而这两点是启发类算法中至关重要的两点。 (2) 融合了MVNS中K-means和VNS后, 相比于简单的局部搜索, 能结合工件本身的特性, 整个搜索变得更加有效、快速。 (3) 引入精英策略使得每代中最好的解被保留下来, 与原来的分散搜索相比, 最优解不会在迭代过程中丢失。
3 结束语
在本文中, 我们设计了一个事件驱动的实时动态系统, 并提出了一种全新的混合分散搜索方法来解决动态车间调度问题。这是分散搜索首次应用于动态车间, 并用改进遍邻域搜索代替了原来分散搜索算法中的局部搜索, 在迭代次数相近、搜索时间相近的情况下, 使得工件的平均流程时间大大缩短。在大规模的条件下, 实验结果表明混合分散搜索算法可以有效解决动态车间调度问题, 对于自动化程度较高的产业具有一定的指导意义。
摘要：车间调度问题是最为人熟知的生产自动化调度问题之一, 而在实际生产中, 动态车间调度问题更为常见。动态车间调度问题包括机器故障和新工件的到来, 这对调度算法的实时性和效率提出了更高的要求。为提高调度算法的实时性和效率, 设计了实时动态系统, 并提出了一种全新的混合分散搜索算法:用改进的变邻域搜索代替分散搜索中简单的邻域搜索, 使得搜索更快;同时, 引入精英策略, 使得搜索结果更好。大规模的实验证明, 提出的混合分散搜索算法在解决动态车间调度问题上表现出色, 应用效果非常好, 且实时性强。
前后台动态调度算法 篇6
生产调度作为企业管理的一个重要组成部分, 在企业的生产经营活动中, 起着举足轻重的作用。虽然经典调度调度理论取得了重大进展, 但是随着经济的高速发展, 消费者对消费的多样化要求, 使得商品的生命周期变得很短, 需要解决很多新的问题。因此面临着严峻的挑战, 制造厂商要想在激烈的市场竞争中获利, 必须把单一品种大批量生产模式转变成多品种小批量生产模式, 在这种背景下, 提出了柔性车间调度系统。柔性柔性车间调度系统具有设备利用率高、在制品占用量少、生产能力相对稳定、产品质量高、运行灵活和产品应变能力强等诸多优点、为克服多品种中小批量生产小效率低、周期长、成本高及质量差等问题提供了新的生产模式。提高生产运作系统的柔性, 是现代企业关心的主要问题之一, 成为一种生产运作战略的核心理论, 高效的柔性作业车间调度 (Flexible Job shop seheduling problem, FJsp) 问题就成为研究的重点。
实际的生产调度涉及的因素很多, 正常情况下有投产期、成产成本、加工顺序、加工设备和原材料的可用等等。有些约束条件可以作为确定因素考虑, 如生产成本等, 而设备故障、生产任务变化、原材料供应变化等非正常情况, 都是事先不能预见的, 在进行调度时大都作为不确定因素考虑。实际生产过程中的多目标优化, 最优解的定义发生了变化, 已经不能单独用大小来判断, 真正试图找到的是一种多个目标之间的妥协解。该类调度问题的约束多样性、复杂性、动态性决定了对该问题的研究能够反映实际的生产过程, 具有一定实际意义。Kacem[1]等人用GA解决FJSP, 并且采用两个方法分别解决机器分配问题和工序调度问题:局部搜索法, 建立理想的资源分配模式;分配模型控制的遗传算法, 用它求解单目标和多目标的FJSP。Mariano Frutos和Ana Carolina Olivera等提出了备忘录算法, 它是基于两个染色体的非控制分类遗传算法来解决多目标柔性调度问题。算法采用模仿兼并的算法进行搜索[2]。山东大学的乔威[3]针对模型的特殊性 (机器可选择) , 在染色体的解码操作中同时考虑加工时间、工件最早允许加工时间和机器当前空闲时间三种因素, 来选择相应机器。华中科技大学的张超勇、饶运清、李培根和邵新宇[4]针对柔性作业车间调度问题, 设计基于工序编码和基于机器分配编码的两种交叉和变异算子, 并提出一种双层子代产生模式的改进遗传算法。
本文动态多目标柔性作业调度问题的特点, 利用熵权法求解各个目标的权重, 利用权重法线性加权和公式把多个目标函数值映射为染色体的适应度。通过改进的遗传操作, 得到更加符合问题要求的最优解或近优解。
2 动态多目标调度问题的描述及模型
2.1 动态多目标调度问题的描述
本文中描述的调度问题如下:假设在m台机器上加工N个工件, 每个工件Jj由nj个工序组成, nj个工序之间由工艺上的先后约束, 工件的每道工序可由m台机器中的多台机器加工, 用Mij表示工件Jj的第i道工序可用机器集合, Mij A{1, 2, , , m}, Oijk表示第j个工件的第i道工序可用的机器Mk。且车间的生产能力受机器设备, 各种模具等其他类制造资源的约束, 例如:某工序到达加工该工序机器设备时, 设备正处于可用状态, 而该工序所需的其他类资源不一定处于可用状态。通过调度, 目的是安排每台机器上的工件加工顺序, 在满足各种约束条件制约下, 尽可能最大限度的优化指标[5]。
2.2 调度问题的模型
本文调度问题模型的目标函数主要考虑完成周期, 零件延误时间, 设备负载。
目标函数如下:
1) 完成周期
式中cj:某工件的完工时间;
2) 零件延误时间
每个种类工件的时间指标主要有三种时间变量组成, 即 (ti, tijk, tei) 。零件延误时间指标T的计算公式为:
式中ti为工件i的交货期, tijk为工件i的j道工序在机器k上的加工时间, tei工件i的完工时间。li为第i类工件的超期惩罚权重系数, 该系数和订购工件的客户级别密切相关。
其中i=1, 2, …m;n=1, 2…pi;k=1, 2…n。
3) 设备负载率 (最大负荷和平均负荷)
上述各式中:
m:机器设备数;N:工件数;j:某工件;Pijk:工件j的第i道工序在机器k的加工时间;Xijk:加工工序Oij选择使用K类资源中的资源m时是1, 其他为0。
2.3 约束条件
调度目标是在不同机器上对所有工序的加工顺序进行排列, 使总优化目标达到最优, 并且在加工过程中还要满足以下基本假设和约束条件:
1) 每类工件加工工序事先已经确定, 工件在不同机器的加工时间是已知的。
2) 在零时刻所有的工件都可以被加工。
3) 加工过程中, 任一道已开始加工的工序不允许中途中断。
4) 同一时刻, 同一台机器只能加工一道工序。
5) 每道工序必须在其紧前工序完成才能进行后续工序, 即上一工序j-1完成后才能开始下一工序j。
6) 工件被加工时对各个资源的占用持续到工件的加工结, 结束后即对工件使用的各资源释放, 各资源处于可用状态。
3 改进遗传算法
本文把禁忌搜索算法嵌入到遗传算法中, 这种混合结构由于融入了禁忌搜索法的思想, 使得那些只有通过禁忌检验的个体, 才能真正地被作为新的个体所接收, 这一方面使得那些有效基因缺失、但适宜度不高于其父代的个体被禁忌掉, 另一方面, 也使得那些包含有有效基因、但适宜度较低的个体有更多的机会参加交叉和变异, 从而延缓或避免了早熟收敛的发生, 也提高了遗传算法的爬山能力[6]。
3.1 编码和解码
本文结合柔性车间的特点, 并考虑到计算机处理整数数据速度较快, 所以染色体的编码采用整数的形式, 同样在解码的时候由于采用整数处理, 运算速度也会大大提高。考虑到柔性的路径存在, 具体的编码采用基于工序的表示方法更加有效, 在此基础上采用一种新的编码方法。在这种方法中, 对于m个工件n个工序的柔性生产调度, 每条染色体的长度:mxn+k。其中前k位表示对应的机器编号, 由于是柔性工序, 基因中的机器编号不是固定的, 是在可选的机器中进行随机选择的。mxn是加工工序的总数。
例如, 在2台机器上加工3个工件, 以工件3为例, 该工件有3道工序, 分别用 (3, 1) , (3, 2) , (3, 3) 表示。工序 (i, j) 表示第i个工件的第j到工序。在染色体的表示中都用/30表示, 由于工序的先后顺序是固定的, 所以在染色体中第一次出现的/30代表工序 (3, 1) , 第二次代表工序 (3, 2) , 最后出现的/30代表工序 (3, 3) 。比较容易看出染色体的任意排列总会产生可行的调度, 而且可以肯定这种编码方法一定包含最优调度。
初始种群生成过程是:首先随机生成部分基因;然后根据可能解约束条件, 生成其他的基因, 使个体属于可能解空间;根据可
行解的约束条件, 判断其是否属于可行解空间, 若是, 将其加入初始种群;否则拒绝;判断是否达到种群规模要求, 是则结束, 否则重新开始。这样在种群生成过程中大大减节约了遗传算法的计算时间[6]。
解码时根据对应关系得出各机器上工件的加工次序, 从而产生一个调度方案。因为最优调度应该是一个主动调度, 根据主动调度的构成步骤将所得各工序的加工次序进行解码, 得到可行的调度解。本文解码过程如下:
1) 初始化工件的加工工序向量, L[Ni]=1, i=1, 2…n。
2) 从染色体中读取要加工的工件。
3) 在Qm (Oi, L[Ni]) 查找当前工序L[Ni]的所有可用机器序列, 选择加工结束时间最早的机器;若存在结束时间相同的机器, 取耗时较短的。
4) 比较该机器的空闲时间段, 如果工序可以插入到机器的中间空闲时间段, 则转入步骤5, 否则进步骤6。
5) 插入该工序, 并更新工件当前工序的结束时间和机器的开始时间和空闲时间。
6) 在机器加工序列的末尾接着安排该工序, 更新机器的当前结束时间和工件的当前工序的结束时间。
7) 工件Ni的工序号L[Ni]加1, 返回步骤2, 直到处理完该染色体中的所有工序。
8) 循环结束, 生成所有的可行解。
3.2 多目标转化为单目标决策方案
遗传算法需要一个标量的适应度信息才能计算, 根据权重法把所有的目标值乘以不同的权重, 再线性加和作为有待优化的单一目标, 按照式 (5) 把多目标的优化问题转化为单目标的优化问题。这种方法的优点是效率高, 同时可得到一个很好的非劣解。
线性加权和公式:
式中:Xi为某一种指标值;Ui为第i个方案的综合指标;Wj为第j个指标的权系数。
本文以完成周期, 零件延误时间, 设备负载为优化目标, 需要对这三个目标根据熵权法分别确定加权系数。熵权法是把各个待评价的目标信息进行量化与综合, 采用此方法确定权系数, 可以简化评价过程, 因此本文采用熵权发确定各个指标的权值。
使用熵权法确定权重的步骤如下:
1) 数据矩阵归一化处理
已知3项指标, 设有m个待评方案, 形成原始指标数据矩阵X= (xij) mx3, 对其归
一化得到矩阵R= (rij) mx3, 归一化公式为:
2) 计算第i个因素下第j个评价值的比重Pij
3) 计算第i个因素的熵值ei
若取, 则0≤ei≤1
4) 计算第i个因素的差异系数
5) 计算权系数
3.3 选择操作
选择操作是建立在群体中个体的适应度评估基础上的选择优胜的个体和淘汰劣质个体, 目的是把优化的个体 (或解) 直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、最优保存策略法。本文采用最优保存策略和随机遍历抽样法相结合的方法, 即是在简单纯选择后, 用最优保存策略法保留最优个体加入到下一代种群, 用随机遍历抽样法选择保留上一代的部分其他解。这样操作有较好的全局收敛性。
3.4 交叉操作
由于种群多样性是逐渐降低的, 因此采用不断引入新的种群个体的方式进行改进。种群生成包括初始种群生成和修正种群生成两种。修正种群生成的过程是:根据修正条件, 判断是否引入修正种群, 否则继续;根据适应值和与当前最优个体的广义海明距离, 降序对种群的其他个体排序;随机生成规模为p的修正种群, 并替换当前种群的后p个个体。
3.5 变异操作
重组之后是子代的变异, 子个体变量以很小概率或步长产生变异, 变量转变的概率或步长与维数 (变量个数) 成反比, 与种群大小无关。本文对解群以0.01的概率进行基因突变操作。
3.6 终止条件
本文采用优化过程中相邻两次迭代的全部工件完工时间的差 (可选择接近0或等于0的数) 和相应的迭代次数作为判断优化过程是否应终止的条件, 从而控制优化过程。
3.7 禁忌搜索法与遗传算法相结合
利用遗传算法与禁忌搜索法相结合, 克服遗传算法早熟和收敛慢的缺点。1) 对选择操作产生的新种群的个体进行禁忌搜素;2) 查找禁忌表中是否有此个体记录;3) 如果有, 再看是否满足特赦准则;4) 如果满足特赦准则, 再看是否满足收敛准则;5) 满足收敛准则, 继续进行交叉操作, 产生新种群, 然后转到1) ;6) 如果不满足特赦准则, 禁忌表中也没有此个体记录, 则放入禁忌表;7) 继续查看是否满足收敛准则, 满足后输出结果, 否则进行上述的交叉操作。
4 仿真实验及分析
本文改进的遗传算法选择采用优化过程中相邻两次迭代的全部工件完工时间的差 (可选择接近0或等于0的数) 和相应的迭代次数作为判断优化过程是否应终止的条件。采用文献[7]中的示例进行仿真实验分析。该例子中有8个工件和4台机床, 每个工件在4台机器上分别各加工一次, 每个工件的每道工序和加工路线加工时间见表1。
上表中M (4, 3) 表示机床4和工时3, 算法的种群规模为50, 修正种群规模为30。算法运行10次的结果为:最优的设备最长加工时间为33;平均的设备最长的加工时间为34, 最优的设备空闲等待时间都为0, 平均的设备空闲等待时间为2。最后得出该算法的最优解, 仿真结果如下图1所示, 明显优于文献[7]的优化结果。
5 结束语
本文针对动态多目标调度问题首先建立了问题的数学模型, 并在遗传算法基础上提出了一种改进调度算法。研究了以完成周期, 零件延误时间, 设备负载为目标的柔性作业调度问题, 该算法在染色体的编码、变异、交叉算子的设计上具有较高的效率, 有效地防止了早熟收敛的产生。由熵权法产生的权系数与优化技术相结合, 能够搜索到多个优良的调度方案。仿真结果表明, 该算法是可行的, 有一定的优越性。
本文进行的仿真实验使用的是固定的参数, 没有考虑各个参数间的互相作用及对最终结果的影响。由于遗传算法的性能对参数的选择很敏感, 这需要经验来进行选择。同时本文求解适应度函数和遗传算法的“早熟”现象没有进行更深入的研究, 这些是在今后的研究中重要关注的地方, 使其更好地应用于实际柔性作业调度问题的解决中。
摘要：随着经济全球化的发展, 世界市场发生很大的变化, 用户对产品的需求干变万化, 而且要求供货及时, 这是市场新的发展趋势。该文主要针对完成周期, 零件延误时间, 设备负载动态多目标柔性作业车间调度问题, 基于改进遗传算法提出了一种新的优化求解方法。首先建立了该类问题的调度模型和目标函数, 利用权重法把多目标的优化问题转化为单目标的优化问题;然后, 用熵权法确定多目标问题的各个目标权重值;同时为了延缓或避免早熟收敛的发生, 在基本遗传算法框架的基础上集成了禁忌搜索算法, 从而保证了算法的收敛性。最后使用实例仿真实验, 证明提出的方法能够有效解决这类动态多目标柔性作业调度问题。
关键词：柔性作业调度,动态多目标,改进遗传算法,熵权法
参考文献
[1]Kaceml, Hammadi S, Borne P.APProachby localizationand multiobjeetive evolutionaryo Ptimization for flexible job-shop seheduling Prob lems[J].IEEE Transactionson Systems, Manand Cybernetics.PartC:APPlicationand Reviews, Manand Cybernetics.PartC:APPlicationandReviews, 2002, 32 (l) :l-13.
[2]Mohammad Reisi, Ghasem Moslehi.Minimizing the number of tardy jobs and maximum earliness in the single machine scheduling usingan artificialimmune system[J].Int J Adv Manuf Technol, 2010 (4) .
[3]乔威.基于遗传算法求解两类复杂JobShop调度问题[J].山东大学学报, 2007, 5 (15) :118-123.
[4]张超勇, 饶运清, 李培根, 邵新宇.柔性作业车间调度问题的两级遗传算法[J].机械工程学报, 2007 (4) :119-124.
[5]官春平.多资源约束作业车间调度问题的模型研究[J].广东轻工职业技术学院学报, 2008 (6) :9-12.
[6]梁迪, 陶泽.多目标柔性作业调度的优化研究[J].计算机工程与应用, 2009, 45 (15) :223-240.
前后台动态调度算法 篇7
近年来关于炼钢-连铸调度问题的理论研究,国内外已取得了一些理论成果,例如静态调度[1,2,3,4],重计划调度[5,6,7,8]和动态调度[9,10,11,12]。在实际生产过程中由于工艺复杂,设备繁多,常常出现一些不可预知的扰动,如:设备故障、工序延迟等。静态调度无法在系统出现扰动的时候做出快速有效的调整;而重计划调度往往是系统运行状态与原计划出现较大偏差时才重新编制计划,灵敏性较低。动态调度研究就是为了提高炼钢-连铸系统应对这些扰动因素的能力,及时调整调度方案,保障生产过程稳定高效运行。文献[9],建立了非线性规划的数学模型,通过约束的变化实现各种方式下的动态调度,但未明确给出当系统出现故障时的解决办法。文献[10]基于多Agent动态调度系统与人体免疫系统的相似性,建立了炼钢-连铸免疫多Agent动态调度系统,但应对扰动的措施过分依赖调整铸机拉速。文献[11]和文献[12],均提出了基于人机交互技术的动态调度,但这种方法对于操作人员的经验和能力要求较高。
本文针对炼钢-连铸动态调度问题,提出一种在给定浇次计划的基础上,将多Agent系统与蚁群算法相融合的求解算法。多Agent系统具有自治与协调的优势,而蚁群算法可以同时利用启发式信息和历史积累信息。通过多Agent间信息交互,对蚁群算法中的启发因子进行整定,然后利用蚁群算法对炉次的起始时间和各阶段占用的具体设备进行搜索,多次迭代得出模型的最优解。最后,以某钢厂仿真实验数据,验证模型和算法的有效性。
1 问题描述
1.1 炼钢-连铸生产过程
炼钢-连铸过程包含冶炼(LD)、精炼(LF、RH等)和连铸(CC)三个主要环节。转炉每次冶炼的钢水与一个钢包的安全容量相符,每炉钢水称为一个炉次。若干个炉次组合成一个浇次,同一个浇次必须连续浇铸不能中断。基本流程如图1所示,将铁厂运来的高温铁水倒入转炉进行冶炼;当温度与成分达到一定要求时,将转炉中的钢水倒入钢包经天车和轨道车运送至精炼炉进行精炼;待温度与成分达到一定要求时,再将钢包运送至连铸机的回转台,准备浇铸。
在精炼阶段,炉次可能依次经过多个精炼设备。
1.2 炼钢-连铸动态调度问题
炼钢-连铸动态调度问题可以归类为作业车间调度问题(job shop oroblem,JSP)。炉次即为被加工的工件,每个工件都需要依次经过多个工序,每道工序都有多台机器可以完成对该工件的加工。在满足约束条件的前提下,动态地确定某一工件在某一工序上的具体哪台机器上进行加工以及具体何时开始加工,从而尽可能消除等待时间,提高生产效率,降低生产成本。
图2所示炼钢-连铸调度示意图可视为有向图<V,E>,结点集V表示对炉次进行操作的各个设备,其中St和En是两个虚拟过程(表示炉次的起点和终点);边线集E表示对炉次可能的操作顺序。图中X表示精炼设备。
在满足约束条件的前提下,以每个炉次在整个炼钢-连铸过程中所占据的时间尽可能小作为调度目标。并通过多Agent协商机制来消解不同炉次间的冲突。对炼钢-连铸JSP的求解归结为在约束条件内寻找每个炉次从起点到终点的最优路径。该路径包含了炉次在具体设备上的操作顺序,且可能受其他因素影响而发生变化。它与该炉次之前各炉次的进展情况以及各设备的运行状况相关,并对后续炉次的路径选择产生影响。
1.3 数学模型
1.3.1 基本假设
钢铁制造流程是一个复杂过程系统,钢铁生产过程是一个准连续或间歇生产过程[13]。为了便于用数学模型描述实际问题,对本文所研究内容作出如下假设:①已知浇铸一批钢的浇次计划;②正常情况下,铸机拉速恒定,若出现特殊情况(如钢水供应不足),铸机的拉坯速度可在允许范围内调整;③炉次按照工艺流程,依次在各设备上操作,整个过程中没有回环。
1.3.2 符号定义
(1)序号及标号。
i为炉次序号;j为工序标号;k为浇次序号;ki为浇次k的第i个炉次;m为设备标号;Ok,i,j,m为k-i在阶段j的设备m上的操作;
(2)集合。
I为炉次集合;J为工序集合,J={1,2,3,…,n};K为浇次集合,K={1,2,3,…,s};M为设备集合,M={LDx,LFx,RHx,…,CCx|x=1,2,3,…};Mj为阶段j的并行机集合;Ik为浇次k中所有炉次的集合,Ik={1,2,3,…,nk};Im为在机器m上加工的炉次的集合;
(3)变量。
st(Ok,i,j,m)为k-i在阶段j的设备m上进行操作的开始时间;et(Ok,i,j,m)为k-i在阶段j的设备m上进行操作的结束时间;p(Ok,i,j,m)为k-i在阶段j的设备m上完成加工所需的必要时间;stmin(Ok,i,j,m)为k-i在阶段j的设备m上进行操作的最早开始时间;stmax(Ok,i,j,m)为k-i在阶段j的设备m上进行操作的最迟开始时间;etmin(Ok,i,j,m)为k-i在阶段j的设备m上加工完成时间,是允许离开设备m的最早时间;etmax(Ok,i,j,m)为k-i在阶段j允许离开设备m的最迟时间;st(max-min)(Ok,i,j,m)为k-i在阶段j的设备m上的松弛开始时间;et(max-min)(Ok,i,j,m)为k-i在阶段j的设备m上的松弛结束时间;δmax为两工序间运送钢包最大允许时间。
(4)常量。
tnow为当前时间;δ为两工序间运送钢包的时间期望值;Δtcc为连铸机在相邻浇次间准备工作所需的必要时间。
1.3.3 目标函数及约束条件
基于对模型的基本假设,构建目标函数如下:
目标函数使每个炉次从开工到完成浇铸所占用的时间尽可能小。根据炼钢-连铸过程的实际情况,模型需要满足以下约束条件:
式(2)表示每个炉次只能属于一个浇次;式(3)和式(4),分别为工序开始时间约束和工序结束时间约束。为了协调冶炼、精炼和连铸三阶段的生产节奏,各工序作业时间可在允许范围内调整;式(5)为工序顺序约束,每个炉次从开工到完成浇铸,其先后工序的顺序固定不变;式(6)为设备能力约束,在同一时刻某设备加工炉次数量不能超出该设备的能力;式(7)为操作时间约束,每个工序加工过程不会在必要时间之内完成;式(8)为连浇约束,每个浇次中从第二个炉次开始都要在前一炉次完成浇铸之前到达钢包回转台;式(9)表示钢包在工序间等待时间约束;式(10)为连铸准备时间约束,连铸机在相邻浇次间需要留有一定时间更换中间包、送引锭等。
2 多Agent蚁群算法求解上述问题
2.1 多Agent与蚁群算法融合策略
多Agent调度系统强调自治与协调,其将计算和决策能力分配到各功能实体,各功能实体解决子问题后,再通过协商解决更高层次或全局问题,因此具有简化问题规模、并行计算、处理局部问题灵活等集中式调度方法所不具备的一系列潜在优点[14]。
蚁群算法(ant colony optimization,ACO)是一种通过模拟蚁群觅食行为提出的模拟进化算法,在解决组合优化的问题上,得到了广泛应用,并取得了良好效果。
在本文中,将多Agent系统与蚁群算法相融合,提出多Agent蚁群算法(multi agent-ant colony optimization,MA-ACO)。每个Agent都与一个炉次或设备相对应。如图3所示,省略部分为可能包含的其它精炼设备。每一个Agent都能够实时采集自己所负责炉次或设备的相关信息,同时还能与相关A-gent通信,获取或递送必要信息。
MA-ACO的结构图如图4所示,炉次Agent每间隔一定时间运行一次蚁群算法,运行过程中需要与未经历阶段的所有设备Agent通信,获取设备信息来确定蚁群算法中的启发因子;当炉次Agent求出解后,与相关设备Agent通信,将该炉次相关信息添加到其待操作列表中。在设备加工炉次的过程中,实际时间与计划时间往往会出现偏差。当出现时间偏差后,设备Agent及时更新其待操作列表中各炉次的起始时间;而炉次Agent向计划中的后续设备Agent发送信息,使后续设备Agent更新其列表中该炉次的起始时间。若设备出现故障,无法继续加工炉次时,该设备Agent将即刻以广播方式向全局Agent发送故障信息(若能获取维修所需时间,也将一并发送),炉次Agent重新运算,寻找最优路径,保证正常浇铸。假如某炉次Agent求解过程出现无解,即无论怎样调整炉次都无法保证其所属浇次连续浇铸,那么炉次Agent将与目标铸机Agent通信,铸机Agent调整铸机拉速,更新待操作炉次列表中的起始时间。然后再通知相应炉次Agent重新求解。
2.2 Agent协商机制
系统内炉次Agent相互独立,各自搜索自己负责炉次的最优路径,必然会发生冲突。为了消解冲突需要创建Agent间协商机制,本文将炉次k-i到达j阶段的设备m的最迟时间定义为安全裕量———φ,如式(11)所示。
当炉次Agent i计算从m-1转移到设备m的启发因子时,会与设备m Agent待加工炉次逐个比较安全裕量φ值的大小。设x属于设备m待加工炉次,若φi<φx,则炉次i允许排入炉次x之前;若φi>φx,则炉次i不允许排入炉次x之前。
2.3 算法实现
基于图2对算法实现过程进行阐述,将每个设备m看作一个结点v。对于任意炉次i,算法虚拟出与该炉次相关属性一致的若干只蚂蚁,共G代,G={1,2,3,…,g},每一代ng只。任意蚂蚁ρ都按照结点间的转移概率从当前结点到En随机行走。转移概率公式[14]:
式(12)中,Pρvv'(g)为第g代蚂蚁k从结点v转移到结点v'的概率;τvv'(g)为第g代,边(v,v')上的信息素量;ηvv'为边(v,v')的启发因子;allowedρ为蚂蚁ρ下一步允许选择的结点集合;α、β分别表示信息素和启发式因子的相对重要程度。
启发因子根据Agent间交互的信息计算:
式(13)中,Δtvv'是当炉次从结点v上操作完成,到它转移到v'并且从结点v'上完成操作所需的时间。如果结点v'在该炉次之前还有其它需要操作的炉次,那么Δtvv'中还包含了等待时间。
每一代蚂蚁行程结束后,更新各路径上的信息素:
式中λ(0<λ<1)表示信息残留系数,Δτvv'(ρ)表示蚂蚁ρ在边(v,v')留下的信息素量。
2.3 求解步骤
炉次Agent从分配给炉次开始,到该炉次浇铸完成,为一个完整周期。本文将该周期分为规划期和调整期前后两个阶段。规划期,炉次并未开始,也没有对应的实体,只是给计划中的炉次分配了一个炉次Agent,该炉次Agent每间隔一定时间对炉次的最优路径和最优开工时间进行一遍搜索。并根据运算结果对上层铁水供应提出优化要求,使其按需供应。调整期,炉次已经开工,炉次Agent通过运行算法搜索从当前结点到En的最优路径。
2.3.1 规划期求解步骤
Step1:读取当前时间tnow,计算出炉次i的最早开工时间stmin(Ok,i,j,m)和最迟开工时间stmax(Ok,i,j,m)以及松弛开工时间st(max-min)(Ok,i,j,m)。在松弛开工时间内,每相隔Δt取一个开工时间st(n),组成一个开工时间组ST={st(1),st(2),st(3),…,st(n)}。设定各路径的信息素初始值为Q,信息素残留系数λ以及决定信息素和启发因子相对重要程度的α和β。
Step2:构造蚁群系统,共G代,每一代ng只蚂蚁,每只蚂蚁都与炉次i相对应。将ST中的元素st(1)作为开工时间st(Ok,i,j,m),并以此时间为基准计算出炉次i到达任意转炉m并完成操作的时间et(Ok,i,j,m)。根据式(13)计算出启发因子,带入式(12)求得第一代蚂蚁选择转炉m的转移概率P。对于转炉m=1,2,3,…;可以求得转移概率P1,P2,P3,…。每只蚂蚁按照转移概率随机选择转炉。同理,可以使第一代蚂蚁随机选择精炼炉和连铸机。当第一代蚂蚁全部完成路径选择,更新各路径的信息素。
Step3:第二代蚂蚁同样按照上述方式进行路径选择,以此类推,直到G代蚂蚁全部完成路径选择。此时,根据各路径信息素浓度,即可确定出以st(1)作为炉次i开工时间的最优路径W(1)。
Step4:根据Step2和Step3,依次以ST中的其他元素作为开工时间st(Ok,i,j,m),求得不同开工时间下的最优路径W(2),W(3),…,W(n)。通过比较,确定出炉次i的最优开工时间和路径。
Step5:将所求路径包含的设备信息存入炉次Agent待进行操作设备列表,并与这些设备通信,将该炉次信息存入相关设备Agent的待加工炉次列表。
2.3.2 调整期求解步骤
在调整期,不再计算炉次的开工时间,而是计算出炉次i在当前设备上完成操作的时间et(Ok,i,j,m)作为搜索路径的起始时间。其他步骤与规划期相同。
3 仿真实例
某钢厂,设有180 t转炉3座(LD1,LD2,LD3),LF炉3台(LF1,LF2,LF3),RH炉2台(RH1,RH2),板坯连铸机3台(CC1,CC2,CC3),其中CC1为一机两流,CC2和CC3为一机一流。以表1中的浇次计划进行仿真实验。
通过对该钢厂系统运行的相关数据进行统计,求得炉次在各设备上完成加工所需时间的期望值及其合理波动范围,如表2所示。炉次在相邻工序两设备间运输所需时间的期望值E(δ)=6 min,合理范围3~8 min。各Agent将以各项所需时间的期望值为基础推算炉次各阶段的起止时间。仿真实验将从各项所需时间的合理波动范围中,随机生成一个时间作为其实际占用时间。
在生产过程中,有些常见的设备故障,可以根据经验提前估计出解决故障的时间。从而在动态调度过程中,可以在该时间之后将设备编入计划中。表3列举出解决一些常见故障或事故所需的时间。
采用Visual Studio.net 2010设计出各Agent的仿真程序。炉次Agent按浇次计划及炉次顺序依次建立,炉次完成浇筑时关闭。考虑到仿真设备的运算能力,本文限定对应每台目标铸机的炉次Agent,最多同时运行10个。
MA-ACO算法参数设置:蚁群代数100,每代蚂蚁数量100;初始各路径信息素τvv'(0)均为1;蚂蚁每次经过路径留下信息素Q=1;α=1,β=1。
实验1,设所有设备均未发生故障,运行仿真程序。根据给定各浇次开浇时间,各炉次Agent搜索炉次的最优开工时间及路径,并在加工过程中对路径进行调整。以最早开工炉次的开工时间作为横坐标的起点,对表1浇次计划的仿真动态调度结果绘制甘特图,如图5所示,系统完成浇次计划总生产时间603 min。
在一次寻优过程中,采用ACO算法和MA-ACO算法分别求解并对比其收敛曲线,如图6所示。其中横轴为蚂蚁代数,纵轴为炉次全程占用的时间。通过对比,表明MA-ACO求解速度较快,且不易陷入局部最优。
该钢厂在生产过程中主要依赖人工调度。图7将人工调度、ACO动态调度和MA-ACO动态调度进行对比,表明MA-ACO动态调度能够有效减少各炉次全程占用时间。
实验2,设系统运行195 min时,精炼炉LF2出现突发故障,不能继续加工炉次。其他条件与实验1相同,将仿真程序动态调度结果绘制成甘特图,如图8所示。图中灰色区域表示LF2处于故障状态。
该实验中,3-4、3-5以及4-4,仅通过调整炉次顺序无法满足连浇要求,于是相应的铸机Agent适当延长其上一炉次的浇铸时间(将3-3、3-4、4-3的浇铸时间分别延长了8 min、7 min、7 min,实际生产中通过适当调整拉速实现),达到连浇要求。完成浇次计划总共用时602 min。实验2表明当系统出现扰动后,MA-ACO动态调度方法能够快速做出合理的调整,使各工序协调稳定的生产。
4 结论
(1)针对钢厂炼钢-连铸动态调度问题,根据钢厂实际运行原则,以缩短每个炉次在炼钢-连铸过程中占用的时间为目标,并建立了炼钢-连铸动态调度的约束满足模型。
(2)在给定浇次计划的前提下,提出了多Agent系统与蚁群算法相融合的方法求解炼钢-连铸动态调度问题,并建立了Agent间的协商机制,避免系统紊乱。由于生产过程中存在不确定的扰动因素,每间隔一定时间对所求解进行优化调整。