混合调度 篇1
在实际离散制造过程中,产品生产过程一般包括零件加工、部件装配和产品总装,其生产形式是作业车间和流水车间集成的混流混合车间模式。零件加工车间、部件装配车间与产品总装车间在计划制定、物料供应和调度执行方面都紧密相关。生产调度及其执行过程中,优化多集中于单一车间而忽略与其他车间的关联影响。如零件加工车间往往以产品切换费用、换模费用的最少等目标来安排生产,而部件装配车间、产品总装车间以生产周期最短等目标来安排生产,从而导致零件的加工进度跟后续的部件装配或者产品总装不相匹配,造成大量的缓冲区在制品库存,拉长了产品的整个生产周期,影响了生产流程化,无法达到系统最优。在混流生产模式下,这种情况尤为严重。因此,对于具有自制件的混流装配生产过程,必须从整体优化的角度出发,建立多车间的集成调度。
目前的研究主要针对零部件车间的加工调度或者零部件装配车间的排序调度等单一车间展开,对作业车间和流水车间的集成研究较少。Lee等[1]研究了三机装配型流水车间的调度问题,优化目标是最小化最大完工时间。文献[2-3]以最小化最大完工时间为优化目标,研究了带装配操作的两机流水车间调度问题。上述研究考虑的加工装配车间过于简单,只是将装配车间看成一台机器,研究的是单品种生产,且没有考虑各个车间之间的缓冲区在制品库存问题。王炳刚等[4,5]研究了带有限缓冲区的流水车间集成调度问题,建立了带并行机的流水部件线和单机流水总装线的集成调度模型,有效弥补了上述研究的不足,但仍没有关于作业车间与流水车间的混合模型。
1 问题描述
1.1 混流混合车间模型
本文所要研究的混流混合车间由三部分组成:第一部分为加工零件的作业车间,以批为单位进行生产;第二部分为装配部件的流水车间,以个为单位进行装配;第三部分为产品总装的流水车间,以个为单位进行装配。图1所示为所要研究的混流混合车间简化模型。
混流混合车间主要有以下特点:(1)混合车间生产不同品种的产品,且以混流生产方式组织生产;(2)零件加工车间、部件装配车间、产品总装车间之间由缓冲区连接;(3)零件加工车间为部件装配车间和产品总装车间提供物料,部件装配车间为产品总装车间提供物料;(4)各生产单元间通过物料约束关联,适当的缓冲设置可在生产流畅的情况下减少生产运作成本;(5)同时具有作业车间调度和流水车间调度问题的各种约束条件;(6)加工零件的作业车间以批为单位进行生产,部件装配、产品总装的流水车间以个为单位进行生产。
1.2 混流混合车间调度模型的构建
在混流混合生产系统中,各生产单元是相对独立的子系统,虽然具有不同的生产特征和优化目标,但仍相互依赖、相互制约。在生产调度过程中,各生产单元通常单独制定调度方案,单方面进行各自生产单元的优化,虽然达到各自的生产目标,但却以其他单元生产目标的弱化为代价,使生产内部不协调,经常出现需要的零部件未生产,而暂时不需要的零部件却大量堆积,产生大量在制品库存,严重影响了生产物流的流畅性,增加了企业生产、场地和资源的成本。因此,集成调度零件加工车间、部件装配车间、产品总装车间,并控制其之间的缓冲区在制品库存具有非常重要的实际意义。针对混流混合车间调度问题,建立以最小化缓冲区在制品库存成本为目标的优化模型。
混流混合车间调度问题可描述为,以零件加工车间、部件装配车间和产品总装车间组成的三段生产系统中,零件加工车间有m台机器,加工n种零件,部件装配车间有l1个装配工位,生产r1种部件;产品总装车间有l2个装配工位,生产r2种产品,生产调度旨在安排各工件在各设备和工位上的生产顺序,实现既定目标的优化。为了便于研究混流混合车间调度问题,给出以下假设条件:
(1)只对自制件在流水车间装配的调度进行研究,外购外协件不在考虑范围内。
(2)若零件加工车间为部件装配车间、产品总装车间的装配工位加工了一批零件,或者部件装配车间为产品总装车间的装配工位加工了某种部件,而装配工位不需要,即装配工位已有的零部件能够满足装配所需要的数量,或者已加工的零部件不是装配工位所需要的类型,则将此批零件或者此种部件暂存在缓冲区,反之向相应工位配送,其中的配送时间假定为零。
(3)作业车间内零件的工序之间有工艺约束,不同零件之间不存在工艺约束。
(4)在零时刻,所有的零件都可以被加工。
(5)在零时刻,所有的机器及装配工位都已经准备就绪。
(6)工序加工时间已经包含了工序的准备时间和搬运时间。
目标函数为最小化缓冲区在制品库存成本,模型如下:
式中,Ai为一批自制零件i所占的面积;Ax为一个部件x所占的面积;Ci为单位面积的零件i在缓冲区存放单位时间所占用的成本;Cx为单位面积的部件x在缓冲区存放单位时间所占用的成本;Ti为一批零件i被加工出来的完工时刻;T′i为此批零件被下游领走的时刻;Tx为一个部件x被生产出来的完工时刻;T′x为此部件被下游领走的时刻。
1.2 模型约束
1.2.1 工艺顺序约束
(1)零件加工车间约束。自制零件的前一道工序加工完成后,才能加工后一道工序,其约束表达式为
式中,Eij、Eih分别为零件Ni在机器Mj和Mh上加工的完工时刻;D是一个足够大正数,作为对约束违背的惩罚系数;tij为一批自制零件Ni在机器Mj加工所需要的时间。
(2)部件装配车间约束。部件的前一道工序装配完成后,才能装配后一道工序,其约束表达式为
式中,Exk、ExH分别为部件装配流水车间中部件x在第k个装配工位和第H个装配工位上的完工时刻;txk为一个部件x在第k个装配工位上装配所需要的时间。
(3)产品总装车间约束。产品的前一道工序装配完成后,才能装配后一道工序,其约束表达式为
式中,Eys、EyK分别为产品总装流水车间产品y在第s个装配工位和第K个装配工位上的完工时刻;tys为一个产品y在第s个装配工位上装配所需要的时间。
1.2.2 资源约束
(1)零件加工作业车间约束。在同一台机器上,一批零件的加工任务完成后,方能开始下一批加工,其约束表达式为
(2)部件装配流水车间约束。在同一个装配工位上,一个装配任务完成后,方能开始下一个任务,其约束表达式为
(3)产品总装流水车间约束。在同一个装配工位上,一个装配任务完成后,方能开始下一个任务,其约束表达式为
1.2.3 时间约束
(1)部件装配完工时间等于该部件进入工位的时间与装配操作时间以及在该工位的等待时间之和:
式中,Bxk为部件装配流水车间中部件x在装配工位k上可以开始装配的时刻,即表示部件x已经完成前一道工序的装配任务,装配工位k已经完成前一个部件的装配任务;Δxk为部件装配车间部件x在装配工位k上开始装配的延迟时间(停工待料时间);Qikt、Qikt′分别为t和t′时刻部件装配车间的装配工位k含有的自制零件i的数量;Oixk为t时刻部件装配车间部件x在装配工位k上装配时需要的自制零件i的数量;txk为一个部件x在第k个装配工位上装配所需要的时间。
(2)总装配件完工时间等于该产品进入工位的时间与装配操作时间以及在该工位的等待时间之和:
式中,Bys为产品总装流水车间产品y在装配工位s上可以开始装配的时刻,即表示产品y已经完成前一道工序的装配任务,装配工位s已经完成前一个产品的装配任务;Δys为产品总装流水车间产品y在装配工位s上开始装配的延迟时间(停工待料时间);Qist为t时刻产品总装车间装配工位s含有自制零件i的数量;Qiys为产品总装车间的产品y在装配工位s进行装配时需要的自制零件i的数量;Qxst为t时刻产品总装车间装配工位s含有部件x的数量(前面已经假设零部件从缓冲区配送到装配工位的时间为零,此时的数量为装配工位和缓冲区中数量的总和);Qxys为产品总装车间产品y在装配工位s上进行装配时需要部件x的数量;tys为一个产品y在第s个装配工位上装配所需要的时间。
模型中,aihj、bigj、a′xHk、b′xgk、a′yKs、b′ygs为指示变量,aihj、a′xHk、a′yKs为0,表明该调度方案不符合工艺顺序约束要求;bigj、b′xgk、b′ygs为0,表明该调度方案不符合资源约束要求。
2 混合遗传算法求解调度模型
遗传算法是求解组合优化问题的优秀算法,具有良好的全局搜索能力,针对混流混合车间调度解空间大的特征,具有较好的优化效果。目前,GA在装配线和作业车间独立优化问题上已取得良好的应用效果[6?8],与模板退火算法结合的混合算法也取得了良好效果[9]。因此,将遗传算法作为算法主流程。为提高局部搜索能力,在遗传算法的流程中嵌入模拟退火算法,建立了一种混合算法。模拟退火算法可以对每一代种群中最好的部分个体执行退火操作,有效提高邻域搜索效率,弥补遗传算法在局部搜索方面的不足。
2.1 算法流程
图2所示为混合算法的主要流程。相关说明如下:(1)算法包含5个基本参数(种群规模N、最大迭代次数M、初始温度θ0、终止温度θend、退温系数λ),随机产生规模为N的初始种群P(T),初始代数T=0;(2)适应度计算,计算种群中每个个体的适应度值;(3)对种群进行选择、交叉、变异操作,产生新一代种群P(T+1),并将种群中具有最佳适应度值的个体集合作为P(x);(4)对种群P(x)进行模拟退火操作;(5)判断迭代条件,如果满足则输出最优解,并终止算法。
2.2 算法详细设计
2.2.1 编码
混流混合车间调度问题的编码规则如下:根据给定的生产任务,先将产品级分解为部件级、零件级,然后根据各种零件的数量、比例和加工批量确定零件生产车间的零件生产批量;部件装配车间和产品总装车间是流水车间,取各产品数量的最大公约数,并通过各产品数量除以该值确定各部分的最小生产循环,对一个循环中的产品装配工序进行编号;编码分成三部分,其中,第一部分为零件加工车间零件的批量编号,第二部分为部件装配车间的部件编号,第三部分是产品总装车间的产品编号。为了修正操作运算后产生的非法解,分别对零件加工工序和装配工序的对应编号从小到大进行重排序,从而保证产生的新种群都为合法解。
示例:产品总装流水车间要生产10个A、10个B;装配1个产品A需要1个部件U、1个零件a和1个零件b;装配1个产品B需要1个部件V、1个零件a和1个零件c;装配1个部件U需要1个零件d,装配1个部件V需要1个零件e。其中,各零件加工批量为10。假定零件加工作业车间由4台设备(M1、M2、M3、M4)组成,加工零件a、b、c、d、e。各零件工序作业时间及作业顺序如表1所示。表1中,逗号左侧的数字为加工时间(s),逗号右侧的数字为加工工序的顺序号。
由已知条件可以知道,生产10个产品A、10个产品B需要零件20个a、10个b、10个c、10个d、10个e,需要部件10个U、10个V,即零件加工作业车间需要加工2批a、1批b、1批c、1批d、1批e。零件序列为[a,a,b,c,d,e],分别对各零件工序进行编号,如表2所示。表2中,a出现2次,表示零件a的2个不同批次;部件装配流水车间需要装配10个U、10个V,则部件装配流水车间的最小生产循环为1个U、1个V,对其进行编号,如UV为1个最小生产循环;产品总装流水车间的最小生产循环为1个产品A和1个产品B,如AB为一个最小生产循环。
图3所示为一条染色体编码。染色体采用三段式的编码方法,S1段为作业车间编码,S2段为部件车间编码,S3段为装配车间编码。其中,编号1~4的码值为1,该码值按照顺序分别代表第一个工件即工件a的4个工序。采用该编码方法可在交叉变异操作时避免非法染色体的产生。
2.2.2 适应度函数
由于优化目标为缓冲区在制品成本最小化,因此将目标函数适当改变作为适应度函数:
2.2.3 种群选择
算法根据适应度函数值采用赌轮盘法选择个体遗传到下一代群体中。
2.2.4 交叉与变异
鉴于混流混合车间调度问题特点,零件加工车间、部件装配车间、产品总装车间的各段染色体编码进行各自独立的交叉和变异操作。交叉方法采用单点交叉;变异采用交换变异方法,即交换两个随机位置上的基因[10]。
2.2.5 模拟退火算法
为提高精英群体的质量,算法采用变温度的模拟退火算法对每代最优的群体P(x)执行模拟退火操作SA。最优解x操作后得到的新解x′=SA(x)。如果x′优于x则保留新解,否则以概率exp(-Δθ′/θ)接受新解,其中,θ为当前温度,Δθ′为原解与新解的适应度差。新解的产生通过交换变异的方法,分别对三段编码各自进行交叉,防止不同类调度工件的串码,从而保证染色体的合法性。算法进程由初始温度θ0、终止温度θend、退温系数λ控制。模拟退火算法增强了个体的局部搜索能力,但增加了时间和计算成本,为平衡算法效率,算法采用变温度的温度适应算法,其中,当前温度为
式中,T为当前迭代代数;ceil(*)表示对括号中内容向下取整。
为保证迭代末期的有效温度,设定θ′e不小于1。在变温度的支持下,算法初期可提高算法的全局寻优能力,算法后期可加快算法的收敛速度,从总体上提高了算法的执行效率。
2.2.6 终止准则
以预先设定的最大进化代数M为终止条件。
3 实例验证
混流混合车间在生产中应用广泛,现以某冰箱制造企业为例对模型和算法进行验证。该生产系统由零件加工车间、部件装配车间和一条总装配线组成。零件加工车间的主要任务为生产8种自制零件。自制件集合为{N1,N2,…,N8},作业车间机器集合为{M1,M2,…,M10}。自制件在各机器上的加工以批为单位,工艺顺序及加工时间如表3所示。
注:“-”表示自制件不需要在该机器上加工;逗号前的数字为工序加工顺序;逗号后的数字为工序加工时间,s。
部件装配车间主要负责门体A、B的装配,其装配工艺与时间如表4所示。
s
产品总装流水车间共有33个装配工位,流转产品Q1、Q2、Q3、Q4,对应的装配工序作业时间如表5所示。
s
表6为零部件对应的产品需求矩阵,对应值为所需数量。
注:“/”表示产品与需求部件没有需求关系。
元/(d·m2)
计划期内产品Q1、Q2、Q3、Q4的生产任务分别为320台、160台、320台、160台。门体A、B的生产任务均为480个;内胆A、内胆B、侧板A、U壳A、后背板A、后背板B,门壳A、门壳B的加工任务均为3批。因此,产品总装车间的产品Q1、Q2、Q3、Q4生产任务比例为2∶1∶2∶1;部件装配车间的门体A、B生产任务比例为1∶1;零件加工车间比例均为1∶1。算法初始种群大小设为100,交叉率为0.9,变异率为0.02,最大迭代次数100,θ0=10,θend=0.1,λ=0.9。根据已知条件,以MATLAB为算法软件编程平台进行求解运算。取最佳结果之一,得到三段式编码[1_1_1_2_2_2_3_5_7_4_6_3_8_7_6_3_3_4_4_5_5_5_6_6_7_8_8]-[1_2]-[2_1_3_3_1_4],对应总的最小成本费用为1643元。其中,部件段最小投产循环为[门体A,门体B],总装线最小投产顺序为[Q2,Q1,Q3,Q3,Q1,Q4],零件车间调度甘特图(图4)中,N11代表第1个工件的第1个工序,其余以此类推。
4 结语
混流混合车间是离散生产中常见的生产组织方式,本文描述了混流混合车间调度问题的特点,建立了混流混合车间缓冲区在制品成本最小优化模型,给出了集成模拟退火算法的混合遗传算法,并对模型进行求解,最后通过某冰箱企业混流混合车间调度问题的实例研究,验证了所建模型和算法的有效性。文中仅针对混流混合车间做了初步的集成调度研究,但混流混合车间作为一种混合生产系统,影响因素多,并涉及多个优化目标,后续研究应发掘影响生产系统的瓶颈因素,实现各子系统的多目标协调调度。
摘要：为解决一类具有多品种混流生产特征和作业车间与流水车间集成的混流混合车间协同调度问题,给出了以在制品成本最小为目标的混流混合车间调度问题模型;采用零件加工、部件装配、产品总装的三段协同编码方法,给出了一种集成模拟退火算法的混合遗传算法,并在模拟退火算法中引入变温度参数来平衡算法效率。最后,通过某冰箱混流装配企业典型实例验证了模型和算法的有效性。
关键词：混流混合车间,流水车间,作业车间,混合遗传算法,模拟退火算法
参考文献
[1]Lee C Y,Cheng T C E,Lin B M T.Minimizing theMakespan in the 3-Machine Assembly-type FlowShop Scheduling Problem[J].Management Science,1993,39(5):616-625.
[2]Cheng T C E,Wang G.Scheduling the Fabricationand Assembly of Components in a Two-machineFlow Shop[J].IIE Transactions,1999,31(2):135-143.
[3]Lin B M T,Cheng T C E.Fabrication and AssemblyScheduling in a Two-machine Flow Shop[J].IIETransactions,2002,34(11):1015-1020.
[4]王炳刚,饶运清,邵新宇,等.基于多目标遗传算法的混流加工/装配系统排序问题研究[J].中国机械工程,2009,20(12):1434-1438.
[5]王炳刚.混流加工/装配系统集成优化研究[J].机械工程学报,2010,46(17):114-122.
[6]苏平,于兆勤.基于混合遗传算法的混合装配线排序问题研究[J].计算机集成制造系统,2008,14(5):1001-1007.
[7]Chul J H,Kim Y.A Genetic Algorithm for MultipleObjective Sequencing Problems in Mixed Model As-sembly Lines[J].Computers and Research,1998,25(7):675-690.
[8]袁坤,朱剑英.一种求解多目标柔性Job Shop调度的改进遗传算法[J].中国机械工程,2007,18(2):156-160.
[9]鲁建厦,蒋玲玲,李修琳.基于混合粒子群算法求解装配线第二类平衡问题[J].中国机械工程,2010,21(4):420-424.
混合调度 篇2
云计算环境具有任务规模大、资源异构性，云计算资源管理的服务质量对计算系统性能影响很大，因此寻找更优的云计算资源调度策略一直是云计算研究领域的热点和难点[1,2]。
国内外学者对云计算的资源调度问题进行一些研究，提出了静态和动态两类云计算资源调算法[3]。静态调度算法只是简单地将M个任务分配到N个资源上，而云计算资源调度过程中存在资源动态申请与释放，而且云计算是对外提供服务的，必须考虑资源消耗的成本，静态算法难以满足云计算资源调度要求，容易造成资源的浪费，因此当前主要采用动态调度算法[4,5]。大量研究表明，云计算资源实际上是一种多约束、多目标优化问题，是一类NP难题，为此，学者们提出了遗传算法、粒子群优化算法、蛙跳算法等云计算资源调度策略，这些算法模拟自然界生物行为，具有速度快，性能好等优点，获得较优的云计算资源调度方案[6,7,8]。但是它们均存在各自的不足[9]。
混合蛙跳算法(SFLA)是基于群体智能的启发式计算技术，其结合了粒子群算法和Memetic算法的优点，具有全局搜索能力强的特点[10]。为了获得更优的云计算资源调度方案，提出了一种改进混合蛙跳算法(ISFLA)的云计算资源调度策略，并通过性能仿真测试和分析。
1 云计算资源调度问题描述
云计算中系统不仅要尽可能为用户提供高质量服务，同时保证资源得到最大利用，减少浪费。但是云计算系统资源是有限的，且具有异构性，经常出现资源竞争现象。如何防止多任务争抢一个资源，只能通过资源调度算法将任务合理进行分配到最适合的云计算资源上执行。
在云环境中，云计算资源以虚拟方式提供给云计算用户，对于任一资源VMi，可以采用如下形式进行描述:
式中，Memory表示计算机的内存大小;CPU为CPU数目;Cost为运行成本;BandWidth为计算机网络带宽;MIPS为CPU能够执行的指令数目。
那么，云计算用户提交的任务可以具体描述如下:
式中，OutputsSize为输出文件大小;FileSize为输入文件大小Length为任务长度。
在实际的云计算系统中，运行成本、用户要求完成任务时间、计算速度等均对服务质量(Qo S)产生影响，为简化计算复杂度，同时不失一般性，本文采用云计算用户任务完成时间作为QOS。
在云计算系统中，第i任务表示为Task[i]，第j资源采用VM[j]表示，那Task[i]在VM[j]上执行时间为time(Task[i]→VM[j])，对于一个云计算资源调度方案X，其总完成时间为:
式中，k为任务数量;l为云计算资源的数量。
2 ISFLA的云计算资源调度
2.1 混合蛙跳算法
2003年，Eusuf提出混合蛙跳算法(SFLA)，其通过对青蛙觅食行为进行模拟，并集成了粒子群优化(PSO)算法和模因算法的优势，在多个领域得到了广泛应用[11]。
(1)划分族群
SFLA首先随机生成F只青蛙粒子，并将它们组合成初始种群:P={X1,X2，…，XF}，每只青蛙代表待解问题的一个潜在可行解，那么第k只青蛙的位置为Xk={xk1,xk2，…，xkn};然后计算每只青蛙适应度值f[Xk]，并按降序对它们进行排列，平均分配到M个族群中，第j个族群Ej，则有:
式中，每个族群的青蛙数为N，显然有F=M×N。
(2)局部搜索
在基本SFLA算法搜索过程中，只对每个族群的最差青蛙Xw的位置进行更新，具体更新方式如下:
式中，为移动距离;Xb为族群中最佳青蛙的位置;r为随机数。
若Xnew>Xw，则有Xw=Xneww;否则Xb=Xg，重新更新;如果仍然有Xnew<Xw，则随机生成一只青蛙取代Xw。
每个族群不断执行上述过程，直到迭代次数大于局部搜索次数就终止。
(3)全局信息交换
当青蛙完成局部搜索后，将它们组合一起产生一个新的种群，并根据适应度值的降序排序，更新Xg，并重新执行划分族群、局部搜索操作，直到达到寻优终止条件为止。
2.2 改进混合蛙跳算法(ISFA)
(1)改进青蛙更新策略
在SFLA局部搜索机制中，局部搜索区域受限，收敛速度慢，陷入局部最优概率大。为此，采用文献[12]青蛙个体更新策略:
式中，ri为[-1,1]间的随机数;c为[1,2]间的常数;wi,max为最大不确定性。
采用上述更新策略，算法搜索范围增大了，但只采用Xb，因此学习能力仍然没有改变。
在粒子群优化算法中，其通过粒子位置和速度更新找到最优解，因此引入粒子更新机制对青蛙位置进行更新操作，同时在模拟算法中引入上次移动距离D'及历史最优个体X'g，保持更新连惯性，避免了早熟现象的发生，改进后的青蛙移动步长为:
式中，R为权重因子;r2、r3为[0,1]间的随机数。
(2)混沌优化全局最优青蛙策略
随着迭代次数增加，青蛙与Xg越来越靠近，个体之间差异丧失，陷入局部最优解的概率增加，为了防止该问题的产生，对最差个体进行混沌扰动，提高种群多样性。采用随机性能良好的Logistic映射作为混沌优化模型，迭代方程为:
式中，μ为混沌变量。
混沌优化最优青蛙策略过程如下:
Step1设Xg=(Xg1,Xg2，…，Xgd)，将Xgi映射到SFLA优化变量的取值范围内。
式中，xL、xu分别代表变量的最小和最大值。
Step2对通过式(10)多次迭代，得到具有m个点混沌序列:。
Step3采用式(12)逆映射回原解空间，得到的可行解为:
Step4采用混沌映射后个体代替以概率Pg的部分个体。Pg的计算公式为:
式中，CR为[0,1]的随机数;t为当前迭代次数。
2.3 ISFLA的云计算资源调度设计
(1)调度方案编码
将p个任务分配到l个云计算虚拟资源上，那么青蛙个体具体编码方式为:
式中，xi为实数，且xi∈[1,l+1)。
最后通过寻优找到最优解时，其解码方式为:
式中，?xi」表示对xi向下取整的资源序号。
例一云计算系统共有3个资源，5个任务，其编码为:
那么解码后为:
那么解码结果表示第1、3和5个任务分别分配到资源2上执行，任务2和4分别在资源3和l上执行。
(2)适应度函数设计
由于考虑任务完成时间，适应度函数定义如下:
式中，为当前任务完成时间最长的调度方案;为当前任务完成时间最短的调度方案。
2.4 ISFLA的云计算资源调度求解步骤
Step1初始种群数目Npop，族群memeplex数目Nm,memeplex的最大迭代次数Iter。
Step2对青蛙个体进行编码，并根据式(17)计算每一只青蛙的适应度值，并降序排列，将青蛙群体划分m个族群。
Step3更新每一个子群Xw，具体为:
(a)根据适应度值，在memeplex找到各自全局位置并记为Xb和最差位置并记为Xw。
(b)根据式(9)计算青蛙移动步长，然后根据式(6)-式(8)对青蛙进行更新，得到新个体。
(c)计算其适应度f[Xnew]，如果f[Xnew]>f[Xw]，则Xw=Xnew，否则再更新，如果仍然有Xnew<Xw，则随机生成一只青蛙取代Xw。
(d)如果t<Iter，转到步骤(a)。
Step4青蛙在族群混合在一起，计算各青蛙适应度值并按降序排列，并对最优青蛙Xg进行混沌优化。
Step5如果满足终止条件，寻优过程便结束，否则转向Step2继续优化。
Step6根据最优个体得到最优的云计算调度方案。ISFLA的云计算资源调度求解流程如图1所示。
3 仿真实验
3.1 仿真环境
在PIV3.0GHz CPU,2GB RAM,Windows XP操作系统，采用cloudsim仿真软件进行仿真实验。为了使ISFLA的仿真结果具有说明力，在相同条件下采用标准SFLA、遗传算法(GA)、粒子群优化算法(PSO)进行对比实验。
3.2 SFLA改进前后的收敛速度对比
对云计算资源数为20，任务数为2万的云计算系统，SFLA和ISFLA最优调度方案的求解曲线如图2所示。对图2进行分析可以知道，相对于SFLA,ISFLA的寻优速度明显加快，在450代便找到了最优方案，而在700左右SFLA达到相同的目标，这主要在青蛙更新策略中借鉴粒子更新思想，能够延续上次更新惯性，而且在局部寻优过程中引入最优个体的模拟信息，加快算法的收敛速度;在全局寻优过程中借鉴混沌优化策略思想对最优个体进行混沌扰动，降低族群陷入局部最优的概率，提高了云计算系统资源调度问题的求解速度。
3.3 结果与分析
(1)小规模任务时的算法性能对比
在资源数量为20的云计算系统，将10～200个任务分配到资源节点上，GA、PSO、SFLA、ISFLA对任务进行分配，并对资源进行调度，得到最优调度方案的完成，所有任务的时间变化如图3所示。从图3可知，当任务数较少时，用户竞争资源的概率较小，发生冲突的概率也较小，因此GA、PSO、SFLA、ISFLA均可以获得云计算资源调度性能较优的方案，可以保证任务的顺利完成，性能没有什么差别。
(2)大规模任务时的算法性能对比
云计算资源数为50，任务数为2～10万，GA、PSO、SFLA、IS-FLA的最优云计算资源调度方案的任务完成时间如图4所示。从图4可知，随着任务数增加，任务之间的竞争更为激烈，任务冲突概率增加，所有算法完成任务时间逐渐增加，当任务超过6万时，ISFLA的优势更加明显，其任务完成时间要远远少于对比算法，对比结果表明，ISFLA利用改进青蛙更新策略，加快了收敛速度，引入混沌优化策略，避免了算法陷入局部最优解，更加适合大规模任务的云计算资源调度问题求解。
(3)资源节点数量对任务完成时间的影响
将10万个任务随机分配到20～200个资源节点进行运行，结果如图5所示。随着节点数的增加，GA、PSO、SFLA、ISFLA任务完成时间逐步减少，主要是由于资源节点数增加，任务竞争资源慢慢变弱，尤其当资源数超过150的时候，时间大幅度降低，对比结果表明，适当增加云计算资源节点数量可以提高云计算任务调度问题求解效率和速度。
(4)资源节点的负载均衡对比
对10万个任务，将它们分配到8个资源节点，表示为{r1,r2,r3,r4,r5,r6}，其处理能力为{200,300,400,500,600,700,800}，GA、PSO、SFLA、ISFLA的资源负载情况如图6所示。从图6可知，由于云计算资源节点处理能力存在差异，它们的负载不相同，其中ISFLA的资源负载最均衡，实现了资源公平利用，主要是因为其找到了更优的资源调度方案，而SFLA、PSO、GA的节点均出现负载均衡现象，导致出现处理能力强的资源却分配到较少的任务，处理能力差的资源出现了任务较繁重的现象。
4 结语
云计算环境中如何更加合理使用资源是当前研究的主要问题，针对基本混合蛙跳算法求解速度慢和易陷入局部最优解的缺点，提出一种云计算环境下的改进混合蛙跳资源调度算法。仿真结果表明，ISFLA可以获得更优的云计算资源调度方案，尤其在大规模任务的云计算资源调度问题求解优势更加明显。
摘要：资源合理调度是云计算研究热点。针对混合蛙跳算法不足,提出一种改进混合蛙跳算法的云计算资源调度策略(ISFLA)。首先在局部寻优过程中引入粒子更新思想,加快收敛速度,然后在全局寻优中对最优个体进行混沌扰动,降低局部最优出现的概率,最后在Cloud Sim平台进行仿真实验。结果表明,ISFLA缩短了云计算任务的完成时间,资源的负载分配更加合理。
关键词：云计算,资源调度,混合蛙跳算法,混沌优化算法,粒子群优化算法
参考文献
[1]李乔,郑啸.云计算研究现状综述[J].计算机科学,2011,38(4):32-37.
[2]刘愉,赵志文,李小兰,等.云计算环境中优化遗传算法的资源调度策略[J].北京师范大学学报:自然科学版,2012,48(4):378-382.
[3]Ochwerger B,Breitgand D,Levy E,et al.The reservoir model and architecture for open federated cloud computing[J].IBM Journal of Research and Development,2009,53(4):1-17.
[4]Li J Y,Mei K Q,Zhong M,et al.Online optimization for scheduling preemptable tasks on Iaa S cloud systems[J].Journal of Parallel and Distributed Computing,2012,72(2):666-677.
[5]李建锋,彭舰.云计算环境下基于遗传算法的作业调度[J].计算机应用,2011,31(1):184-187.
[6]知万军,张盂华,郭文越.基于MPSO算法的云计算资源调度策略[J].计算机工程,2011,37(11):43-45.
[7]薛景文,田玉玲.基于改进克隆选择算法的云计算任务调度算法[J].计算机应用与软件,2013,30(5):167-170.
[8]Xu B M,Zhao C Y,Hua E Z,et al.Job scheduling algorithm based on Berger model in cloud environment[J].Advances in Engineering Software,2011,42:419-425.
[9]华夏渝,郑骏,胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报:自然科学版,2010,11(1):127-134.
[10]王登科,李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件,2013,30(1):290-293.
[11]吕立霞,李学庆.一种改进的混合蛙跳算法[J].中南林业科技大学学报,2011,31(10):177-180.
混合调度 篇3
【关键词】置换流水车间调度；分布估计算法；遗传算法；模糊逻辑控制
0.前言
置换流水车间调度问题（PFSP）是对经典的流水车间调度问题进行简化后得到的一类子问题，最早在石化工业中得到应用，随后扩展到制造系统、生产线组装和信息设备服务上[1]。该问题一般可以描述为，n个待加工工件需要在m台机器上进行加工。问题的目标是求出这n个工件在每台机器上的加工顺序，从而使得某个调度指标达到最优，最常用的指标为工件的总完工时间（makespan）最短。
PFSP最早由Johnson于1954年进行研究[2]，具有NP难性质[3]。求解方法主要有数学规划，启发式方法和基于人工智能的元启发式算法[4]。数学规划等适用于小规模问题，启发式方法计算便捷，却又无法保证解的质量。随着计算智能的发展，基于人工智能的元启发式优化算法成为研究的重点。
遗传算法（GA）是研究与应用得最为广泛的智能优化算法，利用遗传算法求解PFSP问题的研究也有很多。遗传算法具有操作简单、容易实现的优点，且求解时不受约束条件限制。然而，遗传算法通常存在着过早收敛，容易陷入局部最优的现象。导致这一现象的原因在于遗传算法的交叉、变异操作具有一定的随机性，在求解PFSP问题的过程中往往会破坏构造块，产生所谓的连锁问题。为了克服遗传算法的缺陷，研究人员提出了一种不进行遗传操作的分布估计算法[5]（EDA）。EDA是一种运用统计学习的新型优化算法。相比GA，EDA在全局搜索上有较大的优势，而局部搜索能力不足，同样会导致局部最优[6][7]。以混合优化为思路，本文将设计一种EDA与GA结合的混合算法来求解PFSP问题，混合算法通过EDA的概率模型和GA的交叉变异操作两种方式来生成个体，并引入模糊控制理论[8]来自适应调节两种算法生成个体的比例。
1.置换流水车间调度问题
PFSP问题通常假设：
（1）n台工件在m台机器上加工。
（2）每个工件以相同的顺序在m台机器上加工。
（3）每个工件在每台机器上的加工时间是预先确定的。
（4）每台机器只能同时加工一个工件。
2.混合算法设计
2.1种群初始化
初始种群含有PS个个体，利用经典的启发式方法NEH[9]算法产生1个个体，其余PS-1个个体采用随机初始化的方法生成。
2.2选择
根据PFSP问题所给的加工时间表计算出种群中所有个体的总完工时间Cmax，显然Cmax越小，个体的质量就越好，据此可将评价个体好坏的适应度函数设为1/Cmax。本文选择的是轮盘赌法，加工时间越小，适应度值越高，个体被选择的概率也就越大
2.3概率模型
2.4局部搜索
对概率模型采样即可得到新一代的个体，对个体进行局部搜索可以提高EDA的性能[11]，本文将对较好的个体进行局部搜索，分别有如下三种搜索方法：
插入：选择一个工件并随机插入到某一位置。
交换：随机选择两个工件并交换其所在位置。
倒置：随机选择两个工件，将这两个工件之间的序列反转。
2.5交叉算子
本文采用的交叉算子为次序保留交叉。例如，亲代个体为{2，3，5，1，4，9，8，6，7，10}和{1，2，4，5，6，7，8，3，9，10}，在交叉过程中保留的片段为{4，9，8，6}，则生成的子代个体为{1，2，5，7，4，9，8，6，3，10}和{2，3，4，5，6，1，8， 7，9，10}，图示如下：
2.6变异算子
本文选取的变异算子为移码变异，例如，变异前的个体为{6，8，9，10，7，4，3，1，2，5}，选择7，8这两个位点进行变异，变异后个体为{6， 9，10，7，8，4，3，1，2，5}，如下图所示：
2.7模糊逻辑控制
混合优化策略中，不同算法的比例是影响算法性能的关键，传统的算法比例混合方法主要包括固定比例和动态比例两种。使用固定比例时，比例值将在整个算法搜索过程中保持不变。这种方法需要进行试验来确定合适的比例值，其缺点在于为寻找到最佳比例值所需进行的试验多，耗时久。而动态比例调节则只需预先确定一个比例的初始值，而在运行过程中会根据搜索情况调节比例。调节方式又可以分为两种：一种是应用传统的启发式规则控制算法生成个体的比例，这些规则可以用确定的数学公式表示；而另一种是用人工智能技术自适应调整生成个体的比例，最常见的是将模糊逻辑应用于比例调节，能根据算法性能的变化来实现比例控制[12]。为了使混合算法具有优良的适应性，本文采用模糊逻辑控制来进行比例调节：在EDA表现良好时提高EDA生成个体的比例发挥其全局搜索的优势，在EDA求得解的质量下降时提高GA生成个体的比例，以避免出现局部最优。
3.EDA-GA混合算法
通过以上设计，EDA-GA混合算法的步骤如下：
3.1种群和概率模型的初始化
产生初始种群，迭代次数t=1，概率模型P中pij=1/n
3.2对种群个体进行评价并选择出优势个体
以轮盘赌法选择出用以更新EDA概率模型的优势个体和待进行交叉变异操作的父代个体。
3.3更新概率模型并对概率模型取样生成个体
对优势个体进行统计学习完成概率模型的更新，然后对概率模型抽样产生PS个个体，局部搜索后，把最好的rate（t）*PS个个体加入到下一代种群，rate（t）为当前EDA所生成个体的比例。
3.4交叉操作和变异操作
对父代分别进行交叉操作和变异操作，共产生（1-rate（t））*PS个个体，将这些个体加入到下一代种群中。
3.5模糊逻辑控制调节比例
新一代种群生成后，将种群平均完工时间与上一代进行比较，得到模糊输入量，根据模糊判断规则确定下一次迭代时EDA所生成个体的比例rate（t+1）。
3.6终止条件判断
若满足终止条件，输出此时得到的最优解；否则，t=t+1，进入步骤2）。
4.实验结果
4.1参数设置
将EDA-GA混合算法的参数设为种群大小PS=200，迭代次数iteration_times=300，优势个体所占比例为superior_rate=0.2，GA变异比例mutation_rate=0.1，EDA初始生成个体的比例rate=1，概率模型学习速率α=0.2。
4.2结果分析
PFSP问题的基准算例有很多，其中Car和Rec类算例运行时间段短，计算快捷，因此选用这两种算例來验证本文所设计混合算法的有效性。每个算例用matlab独立运行10次，并与GA，EDA的结果进行比较。测试结果如表3所示。其中，BRE=×100、ARE=×100为每种算法求得的最优解C与三种算法测试所得的最好解C*的相对偏差百分比的最小值和平均值。
从表3的实验结果可以看出，对测试问题Car1～Car8和Rec01～Rec37，本文设计的EDA-GA混合算法ARE与BRE均优于EDA和GA，说明GA的引入使得EDA的优化性能有了很大的改进。对于Rec39、Rec41，混合算法BRE不如GA，说明优化性能稍弱于GA，但相比EDA解的质量有显著提高。因此总体而言，EDA-GA混合算法的性能是要强于GA和EDA。
5.结论
针对EDA和GA各自在全局搜索和局部搜索的不同侧重，本文设计了一种EDA-GA混合算法对以最小化总完工时间为优化目标的PFSP问题进行了求解。在混合算法中， EDA和GA各自生成一定比例的个体进行混合，在两种算法比例的调节上使用了模糊逻辑控制的方法，其中模糊输入量为每一代种群个体总加工时间的平均值的变化，而模糊输出量为EDA在下一次迭代中所生成个体的比例。由此，混合算法综合了EDA和GA的优点，运用Car和Rec类进行算例仿真，实验结果证明上述EDA-GA混合算法是有效的。 [科]
【参考文献】
[1]Pan Q-K，Suganhan PN，Tasgetiren MF，Chua TJ.A discrete artificial bee colony algorithm for thelot-streaming flow shop scheduling problem. Information Sciences，2011，181（12）：2455-68.
[2]JohnsonS M.Optimal two-and three-stage production schedules with setup times included[J].Naval research logistics quarterly，1954，1（1）：61-68.
[3]Zhang Y，Li X.Estimation of distribution algorithm for permutation flow shops with total flow time minimization[J].Computers & Industrial Engineering，2011，60（4）：706-718.
[4]周驰，高亮，高海兵.基于 PSO 的置换流水车间调度算法[J].电子学报，2006，34（11）：2008-2011.
[5]LarranagaP，LozanoJA.Estimationofdistributionalgorithms：Anewtoolforevolutionary
computation[M].Springer，2002.
[6]叶宝林，高慧敏，王筱萍，等.基于分布估计算法的二阶段置换流水车间调度算法[J].计算机应用研究，2011，28（10）：3702-3706.
[7]ChenSH，ChenMC，Chang P C，et al.Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems[J].Expert Systems with Applications，2010，37（9）：6441-6451.
[8]Chan F T S，Prakash A，Mishra N.Priority-based scheduling in flexible system using AISwithFLCapproach[J].International Journal of Production Research，2013，51（16）：4880-4895.
[9]Nawaz M，Enscore Jr E E，Ham I.A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J].Omega，1983，11（1）：91-95.
[10]王圣尧，王凌，许烨，等.求解混合流水车间调度问题的分布估计算法[J].自动化学报，2012，38（3）：437-443.
[11]Wang S，Wang L，Liu M，et al.An effective estimation of distribution algorithm for solving the distributedpermutationflow-shopscheduling problem [J]. International Journal of Production Economics，2013，145（1）：387-396.
[12]何宏，钱锋.遗传算法参数自适应控制的新方法[J].华东理工大学学报：自然科学版，2006，32（5）：601-606.
[13]Kim K W，Gen M，Yamazaki G.Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling[J].Applied Soft Computing， 2003，2（3）：174-188.
混合调度 篇4
与传统的作业车间调度问题JSP (Job-shop Scheduling Problem) 相比, 柔性作业车间调度问题FJSP (Flexible Job-shop Scheduling Problem) 是对其的扩展, 是更为复杂的调度问题, 也是实际生产中迫切需要解决的一类问题。与JSP中每道工序只有一台加工设备不同, 在FJSP中, 每个工件可以对应多条加工路径, 对于每个工件的每道工序而言, 可以有多台机器选择来加工。现代化的加工车间都配备了多功能的数控机床、加工中心, 可以满足多种工序的不同加工需求。由此可见, FJSP减少了对加工设备的约束, 扩大了可行解的搜索范围, 相比JSP更加接近实际加工, 问题的求解也更加复杂。
Bruker等[1]于1990年最早对FJSP问题进行了研究, 提出了求解只有2个工件的简单FJSP的多项式算法。FJSP不仅要决定工件的加工次序, 还要对工序进行加工机器的选择。随着工件数量和机器数量的增加, 求解的难度将大大的增加。目前, 求解FJSP常用的方法有遗传算法 (GA) , 模拟退火 (SA) , 演化算法 (EA) , 禁忌搜索 (TS) , 粒子群算法 (PSO) 等智能优化算法。这些研究主要分为两大类:一类是将几种智能算法结合起来, 构成混合算法来进行求解。Lin Lin等[2]将遗传算法和粒子群算法结合提出了混合演化算法;Jianchao Tang等[3]将混沌粒子群算法与遗传算法结合提出了一种混合算法, 该算法在改进Kacem作业方案的基础上提出了一种新的粒子群初始化方法, 并针对性的提出了一种遗传算子;Weijun Xia等[4]将模拟退火与粒子群算法结合起来提出了一种混合算法。另一类是针对单一算法进行改进后来求解。Wannaporn Teekeng等[5]提出了一种改进遗传算法, 改进的方面包括:使用“模糊轮盘赌选择”的选择方法、利用层次聚类将每一代中的群体聚集起来的新的交叉算子、新的变异算子来保持种群多样性, 克服过早收敛;张超勇等[6]与陈伟达等[7]提出了两级遗传算法。张静等[8]对离子群算法进行了改进, 提出了一种基于POX和RPX交叉算子的改进粒子群优化算法。徐晓红等[9]将入遗传算法中的交叉算子和变异算子引入粒子群算法, 对其进行了改进。宋存利[10]提出了协同进化粒子群算法, 运用基于粒子位置取整的编码方法来进行工序加工机器的选择。总之, 在粒子群算法中粒子编码占了很重要的地位, 编码方法的好与否直接决定了算法求解性能的优异性。
在研究了FJSP特点的基础上, 从粒子编码方法的角度出发, 将文献[11]提出的基于轮盘赌的编码方法运用于求解FJSP, 同时采用基于邻域互换的局部搜索方法, 并与基于粒子位置取整的编码方法进行了对比分析。最后对两个不同规模的FJSP算例进行了试验计算, 说明了采用轮盘赌编码的混合粒子群算法求解柔性作业车间调度问题的有效性。
1 柔性作业车间调度问题描述
柔性作业车间调度问题可以描述为:有n个工件在m台机器上加工, 已知每个工件的加工工序数, 每道工序有多个备选机器进行加工, 每道工序只能在机器上加工一次, 由于机器性能的不同导致每道工序在不同机器上的加工时间不同, 在满足一定约束条件的前提下, 调度目标是如何对工件的加工顺序进行排序, 进而使得某个性能指标达到最优。
需要满足的约束条件有: (1) 所有工件具有相同的优先级, 即初始时刻, 所有工件都可以被加工; (2) 每道工序在不同备选机器上的加工时间是确定的; (3) 每台机器在同一时间内只能加工一个工件; (4) 每个工件在同一时间内只能在一台机器上加工; (5) 每道工序可以选择加工的机器具有相同的优先级。
设定的性能指标是最小化最大完工时间Make Span。假设有n个工件, 每个工件有Ki (i=1, 2, …, n) 道工序, m台加工机器, 在某一确定的加工序列中, Sijk为工件i (i=1, 2, …, n) 的第j (j=1, 2, …, Ki) 道工序在第k (k=1, 2, …, m) 台机器上的开始加工时间, Tijk为工件i的第j道工序在第k台机器上的加工时间, Cijk为工件i的第j道工序在第k台机器上的加工完成时间, CIJk为第k台机器上的加工的最后一道工序 (工件I的第J道工序) 的完成时间, CTk为机器k上所有工件的完工时间。则最大完工时间最小的目标函数为:
约束条件为:
式 (1) 为目标函数表达式;式 (2) 表示工件i的第j道工序在机器k上的完工时间为其开始时间与加工时间之和;式 (3) 表示工件i的第j道工序在机器k上的开始加工时间由该机器上上一道工序的完工时间与该工件上一道工序完工时间两者共同决定;式 (4) 表示机器k上所有工件的完工时间为该机器上最后一道工序的加工完成时间。
2 求解FJSP的粒子群算法设计
2.1 粒子群算法
在粒子群算法PSO中, 将每个优化问题的解看作搜索空间的一个粒子, 粒子都有一个被优化的函数决定的适应值, 还有一个速度决定其方向和速率, 所有粒子通过追随当前最优粒子在解空间中搜索。算法首先生成一群初始化粒子, 然后通过迭代找到问题的最优解。在每次迭代中, 粒子通过追踪个体最优粒子和全局最优粒子来更新自己的速度与位置。粒子群中, 粒子的速度和位置按以下公式更新:
其中, Vij、Xij分别为第i个粒子在第j维的速度和位置。Pij为该粒子当前搜索到的最优位置, Gj为整个粒子群当前的最优位置。c1和c2为学习因子, 一般取c1=c2=2, rand () 为 (0, 1) 之间的随机数。ω是惯性权重, 较大的ω有利于种群在更大的范围内搜索, 而较小的ω能够保证种群具有更好的局部搜索能力, 可以采用惯性权重线性递减的方法对ω进行处理, 一般的做法是设定其初始值为0.9, 然后线性递减至0.4。
2.2 基于粒子位置取整的三维粒子编码
基于粒子位置取整的编码方法需要限定粒子位置在正数范围内, 然后对其进行取整操作来得到柔性作业车间调度问题的解。该方法已经在很多文献中被证明是一种有效的编码方法。
(1) 编码
采用三维粒子编码的方法对粒子进行编码。第一维用自然数1, 2, …, n来表示n个工件;第二维粒子位置以实数形式随机生成来进行粒子位置更新, 前两维用来映射调度问题中的加工工序;第三维粒子位置在正数范围内随机生成后, 进行取整操作, 用来映射每道工序对应的机器。粒子长度为所有工件的所有工序数的和。假设有n个工件, 每个工件有Ki (i=1, 2, …, n) 道工序, m台加工机器, 则一个完整的三维粒子可以如表1所示来表示 (其中粒子位置y<m+1) 。
(2) 解码
首先, 对粒子位置x进行排序, 得到所有工件的有序加工序列, 同时相应地调整第一维和第三维的位置;然后, 对粒子的第三维粒子位置y进行取整操作, 得到每道工序所对应的加工机器, 从而得到每个工件的加工路径;最后根据工件的有序加工序列和加工路径来生成调度方案。
(3) 粒子修正
在迭代过程中, 若粒子位置y超出了 (0, m+1) 区间, 则对y在区间内重新随机生成来进行粒子修正, 这样就保证了粒子更新以后仍然是可行的调度解。
2.3 基于轮盘赌的三维粒子编码
基于粒子位置取整的编码方法在粒子的迭代过程中一旦出现粒子位置y超出区间的情况, 就会在区间内重新随机生成来进行粒子位置修正, 这样就舍弃了按照位置更新公式更新得到的新的粒子位置, 对迭代过程进行了人工干预, 为了避免这一弊端, 提出一种基于轮盘赌的粒子编码方法, 这种方法只会对粒子位置y进行相关处理, 而不会舍弃更新后的粒子位置, 这样一来粒子的迭代更新过程就更加符合事物发展的客观规律。
遗传算法中的轮盘赌选择策略是一种按适应度大小随机选择父代优良个体的方法, 个体的适应度越大, 则个体被轮盘选中的概率就越大。在柔性作业车间调度问题中, 每道工序可能有多台机器可以选择来加工, 所以主要考虑的就是工序如何选择加工机器的问题。在确定了每道工序选择机器的轮盘赌概率以后, 看其概率落在哪台机器的概率区间内, 就选择哪台机器来进行加工。因此, 可以将轮盘赌选择策略引入到求解柔性作业车间调度问题的粒子群算法的粒子编码中来, 设计一种随机生成轮盘赌概率的方法来让每道工序选择其加工机器。
(1) 编码
同样采用三维粒子编码的方法对粒子进行编码。其中前两位的含义与上一种方法相同。不同的是第三维粒子位置y在 (0, 1) 区间内随机生成, 用来表示工序选择机器的轮盘赌概率。粒子长度为所有工件的所有工序数的总和。
(2) 解码
根据轮盘赌概率选择策略的方法来进行解码。
首先, 对粒子位置x进行排序, 得到所有工件的有序加工序列, 同时相应地调整第一维和第三维的位置;然后, 对于粒子位置y, 得到了每道工序的轮盘赌概率以后, 用轮盘赌概率选择的方法来选择工序对应的加工机器。假设工件i的第k道工序有m台备选加工机器, 那么由于每台机器被分配工件的概率是相同的, 均为1/m。从而每台机器被选择的轮盘赌概率为:rj=j/m (j=1, 2, …, m) 。因此如果工件i的第k道工序的轮盘赌概率qik∈ (rj-1, rj], 其中j>1, 那么工件i的第k道工序就选择机器j进行加工。这样就可以得到每个工件的加工路径;最后, 根据工件的有序加工序列和加工路径来生成可行的调度方案。
(3) 粒子修正
在迭代过程中, 若粒子位置y超出了 (0, 1) 范围, 则对y取其小数位来进行粒子修正, 如果y为负数, 还需对其取绝对值。这样就保证了粒子更新以后仍然是可行的调度解。
2.4 基于邻域互换操作的局部搜索方法
采用惯性权重线性递减的粒子群算法虽然可以平衡粒子的全局搜索能力和局部搜索能力, 但是对于复杂的柔性作业车间调度这类组合优化问题, 仍然容易陷入局部最优, 导致求解结果过早的收敛, 因此考虑一种基于邻域互换操作的局部搜索方法。
(1) 局部搜索的原理
局部搜索用来实现对每个粒子在其邻域内进行局部最优解的搜索过程。在粒子进行迭代更新操作之前, 首先搜索其粒子邻域, 如果其邻域中存在某个“邻居”具有更好的个体最优值, 那么就用该“邻居”替换掉当前的粒子, 成为新的个体最优粒子。完成对所有个体粒子的局部搜索以后, 从个体最优中找出全局最优, 即确定全局最优粒子, 然后在对粒子种群进行迭代更新。
(2) 局部搜索的实现
基于互换操作的局部搜索方法按以下步骤来实现: (1) 针对粒子种群中的每个粒子个体, 随机选择个体编码中的两个不同位置p、q (p<q) , 不改变它们的工件次序, 交换它们各自对应的粒子位置, 从而得到一个新的粒子个体; (2) 对新个体进行解码计算, 计算其调度适应值, 如果优于互换前的旧个体, 那么就用新的粒子个体替换掉旧个体; (3) 返回步骤 (1) , 设置一定的互换次数来重复进行互换操作。
对粒子编码进行互换的过程如表2和表3所示。
3 试验结果与分析
3.1 算例计算
为了研究基于轮盘赌编码的混合粒子群算法的有效性, 采用两种不同规模的柔性作业车间调度问题进行试验。
(1) 4×6问题
采用与文献[7]相同的4×6FJSP算例进行试验测试。该算例的具体数据如表4所示。
表5反映的是一个具有4个工件, 6台加工机器, 每个工件都具有3道加工工序的简单柔性车间作业调度问题。以最大完工时间Make Span最小化为优化目标, 分别采用惯性权重线性递减的基本粒子群算法 (PSO) 和混合粒子群算法 (HPSO) 进行优化求解, 其中的参数设置为种群数量为20, 最大迭代次数为100次, 互换操作次数为3次, 连续优化l0次, 并与遗传算法 (GA) [7]的求解结果进行比较。GA[7]参数设置为种群数量为40, 最大迭代次数为200, 杂交概率0.75, 变异概率0.15, 连续优化10次。
上述结果表明, 在求解上述简单的柔性作业车间调度问题时, 在种群数量更小, 迭代次数更少的情况下, 粒子群算法的优化性能均要比遗传算法要好。从计算结果表可以看出, 分别采用两种不同的编码方法的两种不同的粒子群算法得到的最优值和平均值都一样, 但是在收敛速度方面, 基于轮盘赌的编码方法要优于基于粒子位置取整的编码方法, 而与基本粒子群算法相比, 考虑了局部搜索的混合粒子群算法具有更快地收敛速度。
(2) 6×10问题
采用与文献[12]相同6×10FJSP问题来进一步进行试验测试。该算例与上一算例相比拥有更多的工件, 更多的加工工序以及更多的加工机器, 因而找到调度最优解的难度要比上一算例大很多。该算例的具体数据如表6和表7所示。
表8反映的是一个6个工件, 10台机器, 每个工件有6道工序的柔性车间作业调度问题。以最大完工时间Make Span最小为优化目标, 分别采用惯性权重线性递减的基本粒子群算法 (PSO) 和混合粒子群算法 (HPSO) , 种群数量设定为20, 最大迭代次数设定50次, 互换操作次数为3次, 连续优化20次, 并与遗传算法 (GA) [12]的求解结果进行比较。GA[12]参数设置为种群数量40, 最大迭代次数50次, 交叉概率0.8, 变异概率0.6。
上述结果表明, 在求解上述较为复杂的FJSP时, 粒子群算法在种群数量少一倍的情况下求解结果仍要优于遗传算法。而且, 与基于粒子位置取整操作的相比, 基于轮盘赌的编码方法具有更好的求解结果和更快的收敛速度, 同时考虑局部搜索的混合粒子群算法比基本粒子群算法也具有更好的求解性能。
为了进一步分析基于轮盘赌编码的混合粒子群算法的有效性, 其他参数不变, 对上述算例设定最大迭代次数为500次, 来进行试验分析。连续优化20次得到的结果如表9所示。
上述结果更加进一步说明了基于轮盘赌编码的混合粒子群算法的有效性, 其求解结果具有更好的上下界, 更好的平均值, 而且找到了最优值42。
3.2 参数设置分析
在局部搜索过程中, 互换操作次数的设置是一个很重要的参数。次数设置过少, 则局部搜索的效果不明显, 无法体现局部搜索的作用;次数设置过多, 则加大了算法的搜索空间, 影响算法的求解效率。通过设置不同的互换操作次数, 采用试验对比的方法来确定合适的次数。
采用文献[12]的6×10FJSP算例进行试验测试, 该算例相关数据详见表6和表7。以最大完工时间Make Span最小为优化目标, 采用基于轮盘赌编码的惯性权重线性递减的混合粒子群算法, 种群数量设定为20, 最大迭代次数设定为50次, 连续优化20次。分别设置1到10次不同的互换操作次数进行试验。
从表10的结果可以看出算法的求解结果与互换操作的次数并不是成正比例关系, 设置合理的互换操作次数不仅可以得到较好的求解结果, 还可以缩小算法的搜索空间, 加快算法的搜索效率。综合分析得出, 设置互换操作的次数为3次较为合理。
4 结语
在研究了柔性作业车间调度问题特点的基础上, 将粒子群算法用于求解FJSP, 从粒子编码角度出发, 采用基于轮盘赌的编码方法, 并采用了基于邻域互换操作的局部搜索方法。最后, 通过两个不同规模的算例试验计算, 与基于粒子位置取整的编码方法进行对比分析, 说明了基于轮盘赌编码方法的混合粒子群算法在解决柔性作业车间调度问题时具有更好的求解性能。
参考文献
[1]Bruker P, Schlie R.Job shop scheduling with multi-purpose machines[J].Computing, 1990, 45:369-375.
[2]Lin Lin, Gen Mitsuo, Yan Liang, et al.A Hybrid EA for Reactive Flexible Job-shop Scheduling[J].Procedia Computer Science, 2012, 12:110-115.
[3]Tang Jianchao, Zhang Guoji, Lin Binbin, et al.A Hybrid Algorithm for Flexible Job-shop Scheduling Problem[J].Procedia Engineering, 2011, 11:3678-3683.
[5]Wannaporn Teekeng, Arit Thammano.Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science, 2012, 12:122-128.
[6]张超勇, 饶运清, 李培根, 等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报, 2007, 43 (4) :119-124.
[7]陈伟达, 达庆利.工艺路线可变车间作业调度的两级遗传算法[J].系统工程学报, 2002, 17 (2) :161-166.
[8]张静, 王万良, 徐新黎, 等.求解柔性作业车间调度问题的改进离散粒子群算法[C]//2010全国现代制造集成技术学术会议论文集, 2010:664-673.
[9]徐晓红, 曾令李, 付跃文.求解柔性作业车间调度的混合PSO算法与实现[J].计算机仿真, 2010, 27 (10) :187-206.
[10]宋存利.求解柔性作业调度问题的协同进化粒子群算法[J].计算机工程与应用, 2013, 49 (21) :15-18.
[11]刘志雄, 杨光祥.基于轮盘赌概率分配编码方法的并行机调度优化[C]//Proceedings of the 29th Chinese Control Conference, Beijing, 2010:1775-1780.
混合调度 篇5
作为发挥分布式发电效能的有效手段,微电网技术成为当前智能电网理论与技术研究的热点[1,2,3,4,5]。 微电网运行方式灵活,具有并网和孤岛2种运行方式,且能根据 需要实现2种运行方 式的无缝 切换[6,7]。微电网能量管理不仅需要在满足负荷需求及电能质量的前提下保证微电网经济、安全、稳定的运行,还要协调不同响应速度电源的出力、降低网内风电和光电等可再生能源出力不确定性的干扰[8]。
针对微电网内可再生能源出力的不确定性,日前—滚动—实时3层框架[9]和日前—日内2层框架[10]先后被提出。3层框架和2层框架均基于分层控制理论,根据当前运行工况和最新功率预测结果,在更小的时间尺度上调整上一层控制量,降低不确定性因素的干扰,是较有前景的微电网能量管理解决方案。其中,日内调度计划是对日前调度计划作进一步修正,其实质为 考虑运行 安全的最 优潮流模 型[11]。文献[12-13]采用遗传算法求解,但求解速度及结果稳定性难以满足工程应用的要求。
储能系统在调剂微电网能量余缺、平滑风电和光电波动性方面发挥着重要作用,因此储能系统建模在微电网能量管理理论研究与工程应用方面备受关注[14]。日内调度计划将储能运行费用纳入目标函数,常见的解决方案有:1以充放电功率为变量形成罚函数,基于非线性优化算法求解[15];2建立蓄电池充放电状态的线性化模型,对调度周期的充放电次数作约 束,采用混合 整数规划 (MIP)算法求解[16];3以充放电过程为单位量化储能损耗费用, 利用遗传算法求解[17]。方案1和2所需的单位充放电功率维护成本在工程中难以获得;方案2所作充放电次数限制主观因素大;基于工程给定的电池充放电循环次数[18],方案3将电池投资费用均摊到每次充放电循环中,但其采用遗传算法求解,同样面临求解速度和结果稳定性的矛盾。
微电网日内调度计划本质上是混合整数非线性规划模型。求解模型连续变量所用原始对偶内点法的收敛性能 取决于给 定初值与 最优运行 点的距离[19,20]。线性规划问题属于凸规划问题,其求解方法成熟,局部最优解即为全局最优解[21];分支定界法是一种在问题解空间树上逐步细分可行域的整数规划求解算法,具备全局寻优能力[22],与线性规划求解算法相结合被广泛应用于商业MIP求解软件, 如CPLEX。因此,将微电网日内调度计划模型线性化后再求解,不仅能高效稳定获得全局最优解,还调和了求解速度与精度的矛盾。
为此,本文提出了一种适用于微电网日内调度计划的MIP模型,引入反映蓄电池充放电过程的辅助变量,有效计及了蓄电池充放电循环次数与老化成本。在现有微电网经济调度模型的基础上,建立了考虑电压幅值的线性化潮流方程、基于解析几何的线性化支路容量、公共连接点功率交换和功率因数限制等约束模型。通过算例验证了所提模型的正确性。
1蓄电池充放电过程模型及老化成本
与传统电力系统相比,微电网的负荷规模和系统惯性较小,其运行易受分布式电源出力和负荷功率波动的影响,面临功率输出波动性强、潮流方向及大小变化频繁、继电保护整定困难等问题。储能技术的发展为解决这些问题提供了有效途径。其中, 蓄电池储能以其技术成熟、成本低廉和可靠性高的优势成为当前微电网应用最为广泛的储能技术。然而蓄电池寿命短的缺点同样不容忽视,因此如何量化并降低蓄电池老化成本是微电网经济调度运行所关心的问题。
蓄电池的使用寿命可表示为在保持输出一定容量的情况下所能进行的充放电循环次数。可见蓄电池充放电循环次数的计算是量化使用寿命的基础, 其关键在于蓄电池充放电过程建模。蓄电池有充电、放电、静止(即不充电且不放电)3种状态,以0-1整数变量us,t和vs,t分别表示蓄电池在时段t充电状态和放电状态,其充放电状态列于表1。
蓄电池时段t的状态满足:
蓄电池运行过程受充放电限值、电池容量、逆变器容量等条件约束,其老化成本与充放电循环次数有关。
1)充放电限值约束
式中:Pcsh,min和Pcsh,max分别为蓄电池最小、最大充电功率;Psdis,min和Psdis,max分别为蓄电池最小、最大放电功率;Pchs,t和Pdis,st分别为时段t的充、放电功率。
2)电池容量约束
式中:Es,t和Es,t-1分别为蓄电池时段t和时段t-1的容量;Eloss为蓄电池静止状态的单位时段能量损耗;ηch和ηdis分别为蓄电池的充电、放电效率;Ec为蓄电池额定容量;SOmiCn和SOmaCx分别为蓄电池的最小、 最大荷电状态。
3)充放电过程模型
蓄电池的一次充电过程指其从充电状态开始到下一次放电状态为止,一次放电过程指其从放电状态开始到下一次充电状态为止。为此,引入2个辅助变量表示充电和放电过程,如表2所示。表中: usp,t和vsp,t分别表示蓄电池在时段t的充电过程和放电过程。
充放电过程与充放电状态的关系可表示为:
式(6)表示蓄电池处于充电过程或放电过程; 式(7)和式 (8)表示初始 化充放电 过程;式 (9)至式(12)表示蓄电池所处的充放电过程不仅与当前时段充放电状态有关,还与上一时段所处的充放电过程紧密联系。
进一步引入0-1整数变量IsS,Wt来记录蓄电池充放电过程 的切换,即只有当ups,t-1=1,ups,t=0或ups,t-1=0,ups,t=1时,蓄电池才发生充放电过程的切换,则Isws,t须满足:
在日内调度计划周期T内蓄电池的充放电次数可表示为:
4)老化成本
蓄电池每充电、放电一次,称作一次充 放电循环。蓄电池老化成本量化为充放电循环次数与单位充放电循环成本之积,即
式中:Csc为单位充放电循环成本。
2日内调度计划的MIP模型
2.1目标函数
微电网日内调度计划的目标是在微电网满足正常运行约束的条件下,通过合理安排各可控单元的出力,使系统运行总成本最低。对微电网中的可再生能源发电设备如风机和光伏电池,其发电运行成本较小可忽略不计;柴油发电机的运行成本包括燃料成本、启动与停机成本以及维护成本[23];其他运行成本还包括:蓄电池老化成本、购售电费用和负荷削减费用[24]。因此,微电网日内调度计划的目标函数为:
式中:Cder,t为柴油发电机r的运行成本,其确定方法参考文 献 [23];Css,t为蓄电池s的老化成 本;为负荷削减费用,其中zlt为时段t可中断负荷l的运行状态(1表示切除,0表示运行),pL,lt和Plt分别为时段t可中断负荷l的单位功率经济损失和被切除有功功率;Cm,t= pg,tPPCC,t为并网运行时 微电网与 主网间的 购售电费 用,其中pg,t为时段t电力交易价格,PPCC,t为时段t与主网交换的有功功率,其为正数表示购电,为负数表示售电。关于式 (20)的线性化 处理方法 可参考文 献[25]。
2.2约束条件
2.2.1考虑电压幅值的线性化潮流约束
日内调度计划是提前30~60min根据最新运行信息对某一计划周期的日前调度计划作修正,其实质为考虑运行安全的最优潮流模型。潮流约束为日内调度计划模型的等式约束,本文采用基于极坐标的潮流模型。
式中:PGi和QGi分别为节点i的发电机有功和无功功率;PDi和QDi分别为节点i的负荷有功和无功功率;Vi和Vj分别为节点i和j的电压幅值;j∈i表示节点j与节点i直接相连;θij,Gij和Bij分别为节点i与节点j的相角差、电导和电纳;Gii和Bii分别为节点i自导纳的实部和虚部;Pij和Qij分别为支路i-j的有功和无功功率;Gi0和Bi0分别为支路i-j中节点i的对地电导和电纳。
提高电能质量、改善电压水平不仅是微电网经济调度的重要内容,还影响微电网中微电源和负荷的运行。因此,假定电压幅值为1.0(标幺值)的直流潮流模型[26]不能直接 应用于微 电网经济 调度。 为此,本文对潮流方程变量构成的单项式逐一进行线性近似处理。微电网供电半径小,满足0.95 ≤ Vi≤1.05,|θij| ≤40°条件[27],状态变量构成单项式原始值与近似值的最大偏差,如表3所示。
由表3可见,潮流方程单项式与近似式的最大偏差在3%以内,而传统的cosθij≈1.0最大偏差高达23.4%。 结合三角 函数公式cosθij=12sin2(θij/2)≈1- (θi2j/2),则式 (23)和式 (24)可化为:
注意到θi2j的存在使式(25)和式(26)不是线性方程,采用特殊排序集合2[28]对θi2j作线性化处理。 式(25)和式(26)转化为线性方程的同时,还保留电压幅值,有利于考虑电压幅值对微电网运行的影响。
节点电压幅值需满足:
式中:Vimin和Vimax分别为节点i的电压幅值下限和上限。
2.2.2基于解析几何的线性化支路容量约束支路i-j的传输容量须满足:
式中:Sij为支路i-j的传输容量。
从解析几何角度看,式(28)表示点(Pij,Qij)处于半径为Sij的圆内,如图1所示。若将圆周m等分,依次连结 各分点,获得圆内 接等m边形。 当m→∞时,点(Pij,Qij)在圆内等价于点(Pij,Qij)在圆内接等m边形内。
设A,B为圆内接等m边形相邻的两点,A,B的弧度角分别为α,β,则α=2πk/m,β=2π(k+1)/ m,k∈ [0,m -1],即点A坐标为 (Sijcosα, Sijsinα),点B坐标为(Sijcosβ,Sijsinβ),则等m边形任意一条边AB直线方程可表示为:
基于解析几何理论,式(28)可化为:
2.2.3公共连接点功率交换和功率因数限制约束
配电网对并网方式的微电网运行有一定要求, 即限定公共连接点(point of common couple,PCC) 的交换功率和功率因数,即
式中:PPmiCnC和PPmCaxC分别为PCC的有功功率交换最小值和最大值;QPCC,t为时段t时PCC功率交换的无功功率;λPCC为PCC的功率因数限值。
将式(32)化为:
对式 (33)中|PPCC,t|的线性化 处理可参 考文献[29]引入松弛变量处理。
综上,本文所提微电网日内调度计划模型的目标函数和约束条件均为线性方程,即所提模型为混合整数线性规划模型,可利用商业MIP求解软件进行求解。
3算例分析
以如图2所示的微电网为算例验证本文所提模型,该微电网的电源有小型柴油机、异步风机、光伏电池和蓄电池等,负荷包括重要负荷、可中断负荷和弹性负荷[30],线路型号为LJ_95。日内调度计划的时间跨度为4h,分为16个时段,每时段为15min。 具体选取某天14:00—18:00时段内的光伏、风电以及负荷功率短期预测值如图3所示。
柴油机组出力最小、最大限值分别为3kW和60kW;无功输出 功率的最 小、最大限值 分别为0.986kvar和19.72kvar;上爬坡和下爬坡速率分别为10kW/min和5kW/min;最大开、停机时间分别为3h和2h;蓄电池的ηch=ηdis=η,参数如表4所示,荷电状态初始容量取最小容量值,单位充放电循环成本为50元;微电网与主网的有功功率PPCC∈ [-160,160]kW,功率因数 限值为0.9,电价为0.8元/(kW·h)。
所提模型在GAMS平台上实现,并采用商业MIP求解器GAMS/CPLEX进行求解,以下所有算例的测试计算均在Intel CoreDuo i7-3770CPU @ 3.40GHz,16GB内存的Windows 7 64位PC机上进行。
3.1模型性能分析
为验证所提MIP的计算精度及速度,分别求解并网方式、孤岛方式及并网方式向孤岛方式切换情况的日内调度计划,并与基于GAMS/BONMIN求解的混合整数非线性规划(MINLP)模型进行比较。 情况1为并网方式;情况2为孤岛方式;情况3为并网方式向孤岛方式切换,微电网在时段1~8并网运行,时段9~16由于工程检修进入孤岛运行模式,时段13以后柴油机才能投入运行。3种情况的计算结果列于表5。表中:tc为计算时间。
由表5可以得出如下结论。
1)情况1和情况2采用MIP模型与MINLP模型的优化结果非常接近,以MINLP模型计算结果为参考值,MIP模型所获结果的相对误差值分别为0.002%和4.893%。
2)情况1和情况2采用MINLP模型所耗费的时间均大大高于MIP模型,且情况1比情况2求解快;情况3采用MIP模型计算耗时仅5s,而采用MINLP模型则无法快速收敛。这是由于3种情况模型的起作用约束集逐步递增,求解速度降低;MIP模型的收敛性好于MINLP模型。
3)将情况2的MIP模型所获的启停变量结果作为MINLP模型的初 值再次求 解,其结果为393.995元,与MIP模型求解的394.830元更为接近。可见,MINLP模型可能由于选取的 初值不在 最优运行点附近,收敛于局部最优解,而MIP模型能快速有效地收敛于全局最优解。
为验证时段数对模型求解的影响,图4绘出了不同时段数 的情况1和情况2分别采用MIP和MINLP模型的性能比较。由图4可看出:1情况1的MIP和MINLP模型优化结果相等;2情况2的MINLP模型在时段数为11,12和14时出现不收敛的情况,其余时段数的优化结果与MIP模型的较为相近;3MIP模型求解时间不随时段数显著增加, 而MINLP模型求解时间随时段数变化而变化。
3.2模型结果分析
对情况3的MIP模型计算结果作进一步分析, 各微电源出力、与主网交 换功率和 负荷功率 见附录A图A1,蓄电池的充放电状态及过程见附录A表A1。
由附录图A1可以看出,在时段1~8,微电网并网运行时主网对微电网送电,负荷功率由光伏、风电和主网提供,蓄电池处于充电状态;在时段9~16, 微电网孤岛运行,由于柴油机未投入运行,在时段9~12,光伏、风电和蓄电池提供的功率无法满足微电网负荷功率要求,需削减部分负荷;在时段13~ 16,柴油机投入运行,负荷功率由柴油机、光伏、风电和蓄电池提供。
由附录A表A1可以看出,2个蓄电池在计划周期内均只进行1次充放电切换,即微电网并网运行时蓄电池1和2均处于充电状态,孤岛运行时蓄电池1和2均放电以满足系统负 荷功率要求。可见,所提模型通过引入反映蓄电池充放电过程的辅助变量,能有效计及蓄电池充放电循环次数与老化成本,克服了蓄电池频繁充放电加剧老化的局限性。
3.3支路容量约束线性化分析
在基于解析几何的线性化支路容量约束中,圆内接多边形边数m是影响系统计算速度和精度的重要参数。m越大,圆内接多边形越逼近于圆,计算结果精度越高,但等效不等式约束方程增加导致模型求解速度降低。情况3的MIP模型含连续变量1 926个,离散变量284个,以下针对情况3的m取值作进一步讨论。表6列出了不同m取值的计算结果和时间。
由表6可见,随着边数m的增加,模型所含约束方程规模大幅增加,求解精度越来越高,而求解越来越耗时;当m≥64时,求解结果基本趋于不变,为此取m=64,可满足日内调度计划求解的精度要求, 还避免了不必要的时间开销。
4结论
本文提出了一种适用于微电网日内调度计划的MIP模型,主要结论如下:1与未经线性化的模型相比,所提模型获得的结果在偏差不大的前提下,快速稳定收敛于全局最优解,且不依赖于初值;2引入反映蓄电池充放电过程的辅助变量,能有效计及蓄电池充放电循环次数与老化成本,符合工程实际; 3基于解析几何的线性化支路容量约束,克服了现有线性化潮流模型仅考虑支路有功传输容量约束的局限性。后续研究将进一步拓展所提模型的应用范围,如建立多时间尺度微电网经济调度的统一MIP模型。
附录见本刊 网络版 (http://www.aeps-info. com/aeps/ch/index.aspx)。
摘要：为进一步调和微电网日内调度计划模型求解速度与精度的矛盾,提出了一种适用于微电网日内调度计划的混合整数规划模型。构建了蓄电池充放电过程模型,能有效计及充放电循环次数和老化成本;在现有微电网经济调度模型的基础上,建立了考虑电压幅值的线性化潮流方程、基于解析几何的线性化支路容量、公共连接点功率交换和功率因数限制等约束模型。通过算例验证所提模型,结果表明:1所提模型求解精度高,快速稳定收敛于全局最优解,且不依赖于初值;2蓄电池充放电过程模型符合工程实际,克服了现有模型中蓄电池频繁充放电加剧老化的局限性。
混合调度 篇6
遗传算法,粒子群算法,蚁群算法,人工鱼群算法等优化算法的出现对于求解约束、非线性和多极值的全局优化和多目标优化问题提供了新的解决方法,并且在社会生产各个领域得到广泛应用[1,2,3,4]。
混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)是2003年由Eusuff和Lansey提出的一种基于群体智能的生物进化算法[5]。算法具有概念简单、参数少、计算速度快、全局寻优能力强、易于实现等特点,近年来,该算法不断得到改进和应用[6,7,8,9,10]。
本文通过引入自适应因子,提出了一种改进的混合蛙跳算法,通过测试实验函数和优化电力系统经济调度问题,结果表明本文提出的改进算法较之基本混合蛙跳算法和文献[6-7]中的改进算法,具有更好的优化性能。
1 改进的混合蛙跳算法
1.1 自适应混合蛙跳算法(ISFLA)
ISFLA在更新过程中,青蛙个体能够记住自身前两次的更新步长和个体邻域的历史最优值,因而迭代过程中Pw(适应值最差个体)不仅向Pb(子群适应值最好个体)或Pg(全局适应值最好个体)学习,在延续上次更新的部分惯性步长的同时,还向记忆中的个体邻域历史最优值学习,随着迭代次数的增加,自适应因子对个体更新策略影响呈线性减弱趋势。这种更新策略加快了算法的收敛速度,扩大了个体的搜索区域,同时也保持了开发与探索的平衡,维持了种群的多样性,一定程度上扩展了算法的搜索能力。具体更新策略如下式。
式中:R1,R2,R3,R4是0~1之间的随机数;Dis是Pw的移动步长;Dis M是青蛙移动步长的上限;t是当前迭代次数;Tmax是总的迭代次数;W是权重因子;Ws和We是权重因子的初始值和结束值,本文中的取值分别是0.9和0.4;s为大于1的整数,取值范围[1,30]。图1为s分别等于3、5、10,Tmax=1000时,函数a的值的曲线图。
His(Pw)是Pw的个体邻域历史最优值。个体邻域结构如图2所示,在图中有P个存储体,标记为{C(i),i=1,2,…,P},按照初始化种群的适应值降序排列,自左至右存储相应个体迭代过程中的历史最优值。个体邻域指个体所对应存储体左右半径内的存储体集合,如:以C(3)为中心,半径为2的个体邻域集合是{C(j),j=1,2,3,4,5}。存储体采用循环结构,C(1)包含在C(P)的右邻域内,C(P)包含在C(1)的左邻域内。
1.2 测试标准函数蛙跳算法流程
Step1:设置相关参数,在定义域范围内随机产生P只青蛙,子群数为M,每个子群青蛙个数为N,全局信息交换迭代次数为T1,局部搜索迭代次数为T2。
Step2:计算每只青蛙的适应值,将所有青蛙按照目标函数值降序排序,随机分组。
Step3:执行式(2)、式(3),对每个子群重新排序,更新每个子群的Pw、Pb及整个种群的Pg。
Step4:判断局部搜索迭代次数是否达到T2,若未达到,返回Step3继续执行。
Step5:判断全局信息交换迭代次数是否达到T1或Pg是否达到要求的收敛精度。如果不满足,跳至Step2继续执行;如果满足,算法结束,输出Pg。
1.3 实验方法、结果及说明
1.3.1 实验设计
应用SFLA,文献[6-7]中的改进算法和ISFLA,对下面4个测试函数进行优化计算,并对其计算结果进行分析,以下4个测试函数均为求全局极小值,测试函数参数如表1所示,测试平台为VC++6.0,机器主频为P4(2.2 G),内存为2 G。
实验中算法具体参数设置:青蛙种群规模为200,子群数为20,每个子群中青蛙数为10,迭代进化次数为500,子群内更新迭代次数为10。ISFLA的个体邻域半径为1,各函数优化的参数和目标精度见表1。对以上4个测试函数分别采用SFLA,文献[6-7]中的改进算法、ISFLA进行极小值寻优,实验结果采用算法独立执行30次得到的平均值。
本文采用以下方式分析算法的优化性能:(1)固定迭代进化次数,算法收敛速度和精度分析;(2)固定收敛精度,算法迭代进化次数分析。
1.3.2 实验结果及分析
1)固定迭代进化次数,算法收敛速度和精度分析
实验结果如表2和图3~图6所示。由表2可以看出,ISFLA的平均优化结果明显好于基本SFLA和文献[6-7]中改进算法。ISFLA的运行时间与基本SFLA和文献[6]中的改进算法相当,但明显快于文献[7]中改进算法,另外ISFLA的标准差相对较小,表明改进算法具有更好的稳定性。
图3~图6是函数f1~f4采用四种算法运行30次后得到的平均值的进化曲线,在图3~图6中,使用函数平均极值的常用对数表示纵坐标的值,使用进化次数表示横坐标的值。从图中可以看出,ISFLA虽然在进化前期收敛速度较慢,但在中后期收敛速度明显快于其他三种算法。
2)固定收敛精度,算法迭代进化次数分析
4个测试函数分别采用基本SFLA、文献[6-7]中改进算法、ISFLA各自独立执行30次,达到表1中要求精度的迭代次数(最大迭代次数为500),如表3所示,其中,成功率等于达到要求精度的迭代次数与实验总次数(30)之比。从表3可以看出:ISFLA对4个函数达到93%~100%的成功率,改进算法明显高于其他三种算法。从达到固定优化精度的平均迭代次数、最小迭代次数和最大迭代次数三个指标来看,ISFLA都比其他三种算法整体上性能突出。以上结果说明ISFLA优化成功率高、收敛速度快,且具有较好的稳定性。
2 在电力系统经济调度问题中的应用
2.1 燃料成本目标函数
电力系统经济调度问题燃料成本的数学模型如式(5)[11]。
式中:Fcost为系统燃料成本费用;Z为系统内发电机数目;Pm为第m台发电机的有功功率;Fmcost(Pm)为第m台发电机的耗量特性。
1)普遍性描述
Fmcost(Pm)的二次函数近似表示为
式中,am,bm,cm为燃料成本系数。
2)发电机耗量曲线的阀点效应[12]
机组热运行测试过程中,发电机有功功率从最小值缓慢增加到最大值,通过对Pm、Fmcost(Pm)采样可获得机组的耗量曲线,通常将其表示为二次函数形式,如式(5)。然而汽轮机进汽阀突然开启时出现的拔丝现象在机组的耗量曲线上叠加了1个脉冲效果,即产生了阀点效应,如图7所示。
当考虑阀点效应时,耗量特性为
式中:Em为由阀点效应引起的耗量特性变化;am,bm,cm,gm,hm为系统参数;mPmin为第m台发电机的有功功率下限。
2.2 约束条件
调度过程中考虑两种约束条件:容量约束与平衡约束。
容量约束为
其中,Pmmin,Pmmax为第m台发电机的最小和最大有功功率输出。
平衡约束为
其中:PF为系统负荷;Ploss为有功网损。采用B系数法时,网损与发电机有功功率的关系为
式中:P为M维有功功率列向量;Bmj,B0m,B00为B系数,实际应用中可以每隔一段时间进行测量修正。
2.3 算例分析与结果说明
为了验证改进混合蛙跳算法的性能,本文以文献[12-13]的3机组6母线电力系统为例,分别讨论:a)忽略网损,忽略阀点效应;b)忽略网损,考虑阀点效应;c)考虑网损,考虑阀点效应三种情形下系统的负荷分配问题,并针对同一问题,使用ISFLA、文献[6-7]和SFLA进行优化求解,并与文献[14]中的标准PSO算法(SPSO)以及文献[15-16]中改进粒子群算法的结果进行比较研究。具体的参数为:发电机负载总负荷PD=500 MW,各发电机的耗量特性常数及有功功率容量约束见表4。
2.4 改进算法优化电力系统调度问题流程[14]
Step1:设置相关参数,青蛙总数为P,子群数为M,每个子群青蛙个数为N,全局信息交换迭代次数为T1,局部搜索迭代次数为T2。
Step2:根据不等式约束和等式约束在定义域范围内随机产生P只青蛙的前D-1维位置。
Step3:计算每个个体最后一维的位置,判断是否符合机组功率限定,若不符合转Step2。
Step4:根据式(6)~式(8)计算每只青蛙的适应值,将所有青蛙按照目标函数值降序排序,随机分组。
Step5:执行式(1)、式(2)对每个子群重新排序,更新每个子群的Pw、Pb及整个种群的Pg。
Step6:判断局部搜索迭代次数是否达到T2,若未达到,返回Step5继续执行。
Step7:判断全局信息交换迭代次数是否达到T1或Pg是否达到要求的收敛精度。如果不满足,跳至Step4继续执行;如果满足,算法结束,输出Pg。
计算网损的B系数如下[14]:
实验中算法具体参数设置:青蛙种群规模为50,子群数为10,每个子群中青蛙数为5,迭代进化次数为500,子群内更新迭代次数为5。ISFLA的个体邻域半径为1,试验次数为10,实验结果采用算法独立执行10次得到的最好值。表5和表7分别统计了各算法的最优解以及与其他参考文献中的最优解。
表5中,各种算法优化性能相近,但是ISFLA在10~20次之内找到最优解,而其他算法则在300~400次找到最优解[14],使用ISFLA求解该问题具有较快的收敛速度和精度。
从表6和表7中可以看出,ISFLA求解该问题得到的解均优于基本SFLA和文献[6-7],文献[14-16]中的解,且具有较快的收敛速度及较高的收敛精度。
4 结束语