基于粒子群算法和免疫记忆机制的批量计划方法

基于粒子群算法和免疫记忆机制的批量计划方法

0优化算法和标准rii技术和资源规划（mrp）是提高多品种小批量生产效率的有效方法。将成组技术和MRPⅡ有效地结合起来,利用零件之间的相似性制定分时段的批量计划,能够降低总的生产调整时间,提高企业的生产效率。基于成组单元有能力约束生产批量计划问题是在能力约束限制下,确定M个簇的N种不同的项目在给定计划范围T内的每一个时间段的批量,使得在整个计划范围内,项目总的调整费用(簇调整费用和项目调整费用)、库存保管费用和生产费用总和最小。求解有能力约束的生产批量计划问题是一个非常复杂的问题,它不但是一个应用上的难点,而且是一个理论上的难点,主要是由于在受资源约束的情况下,为了消除资源冲突,需要对项目、时间和数量这3维变量同时进行调整。文献证明了单个项目的单资源约束的生产批量计划问题属于NP-hard问题。求该类问题精确解的计算量将随问题规模的增加呈指数递增,因此精确算法只能求小规模问题,而专用启发式算法只能求解特定的生产批量计划问题。粒子群优化(ParticleSwarmOptimization,PSO)算法是Eberhard和Kennedy于1995年提出的一种新的进化算法,它源于对鸟群群体寻食运动行为研究结果的启发。由于PSO算法有收敛速度快、运算简单、易于实现等优点,一经提出立即引起了进化计算、计算机科学和管理科学领域学者们的广泛关注,并取得了大量的研究成果。这些研究成果大部分是对各类多维连续空间优化问题研究所取得的,但对离散优化问题中的应用研究成果还很少,只有少数学者进行了一些这方面的尝试。本文提出了用于求解基于成组单元有能力约束的生产批量计划问题的改进二进制PSO算法。1约化管理1根据基于成组单元有能力约束的生产批量计划问题的特点,本文做如下假设:①每个项目的提前期为1;②不允许缺货;③不允许加班。则问题的数学模型为:min(Ν∑i=1Τ∑t=1(ΡiQit+siYit+ΗiΙit)+Τ∑t=1Μ∑k=1SkΖkt)。(1)s.t.Ii,t-1+Qit-Iit=dit,(2)Ν∑i=1(aijYit+bijQit)+Μ∑k=1AkjΖkt≤Cjt;(3)Qit≤GYit;(4)∑i∈ΩkQit≤GΖkt;(5)Yit∈{0,1};(6)Zkt∈{0,1};(7)Qit≥0;(8)Iit≥0;(9)Ii0=IiT=0;(10)i=1,2,…,N,j=1,2,…,R,t=1,2,…,T,k=1,2,…,M。其中,N为生产项目总数,T为计划范围长度,R为可用资源数;G为非常大的正数;dit为项目i在t时间段的外部需求,Hi为单位时间单位库存费用,si为项目i的调整费用,Sk为第k簇的调整费用,Pi为项目i单位生产费用;aij为项目i上单位产品在第j个资源上的准备工时,bij为项目i上单位产品在第j个资源上的加工工时,Akj为第k簇在j个资源上需要的调整时间,Cjt为资源j在t时间段的可用能力。决策变量有:Qit为项目i在t时间段的生产数量,Yit为项目i在t时间段的生产调整变量,Zkt为第k簇在t时间段的生产调整变量,Iit为项目i在t时间段末的库存量。目标函数式(1)使得在整个计划范围内项目总的调整费用(簇调整费用和项目调整费用)、库存保管费用以及生产费用之和最小;约束式(2)表示满足需求的物流平衡方程;约束式(3)表示资源能力的限制;约束式(4)表示只有当生产数量大于0时才能发生调整费用和准备工时;约束式(5)表示当簇内只要有一个项目的生产数量大于0时,就会发生项目的簇调整费用;约束式(6)表示Y是0或1的调整变量;约束式(7)表示Z是0或1的调整变量;约束式(8)表示每个生产周期的生产数量为非负;约束式(9)表示不允许缺货;约束式(10)表示初始和结束周期的库存为0。2优化生产批量计划的二元pso算法标准PSO算法主要适用于连续空间函数的优化问题,Kennedy和Eberhard在1997年提出了二进制PSO算法,本文应用二进制PSO算法解决基于成组单元有能力约束的生产批量计划问题。2.1zkt、iiit和ld应用PSO算法解决基于成组单元带能力约束的生产批量计划问题,关键是如何编码。该问题是一个混合整数规划问题,决策变量Qit和Iit为连续整数变量,Yit和Zkt为0,1整数变量。因此,需要研究变量之间的关系和性质。定理1对于基于成组技术有能力约束的批量计划问题,如果Yit给定,i∈[1,N],t∈[1,T],则此问题的最优解Qit,Zkt和Iit可由Yit惟一确定,即Qit={0Yit=0t1∑m=tdimYit=1,t1=minp=t+1‚⋯‚Τ{p|Yip=1};(11)Ιit=t∑m=1Qim-t∑m=1dim;(12)Ζkt={0,∑i∈ΩkQit=0,1‚∑i∈ΩkQit≠0。(13)定理1的证明参见文献。对于基于成组单元有能力约束的生产批量计划问题PSO的编码采用如下策略:①只使用变量Yit为构造0,1编码的粒子;②利用定理1,由Yit通过式(11)、式(12)和式(13)来确定Qit,Zkt和Iit的值。具体的编码方案为:Xkh表示粒子群中的第h个粒子在进化的第k代的位置值。每一个Xkh表示成生产批量计划问题的一个解,Xhk=[xhitk]N×T,N为生产项目总数,T为计划范围长度。如果xhitk=0表示第h个粒子在进化第k代时,第i个项目在第t时间段不生产;否则,第i个项目在第t时间段生产。Vhk表示粒子群中的第h个粒子在进化的第k代的速度值,Vhk=[vhitk]N×T。2.2算法流程求解基于成组单元有能力约束的生产批量计划问题的二进制改进PSO算法的流程如下:(1)确定参数值确定种群规模H以及学习因子c1和c2,并令进化代数k=0。(2)速度2mx每个粒子的位置由式(14)随机生成,其中R(0,1)表示随机产生之间的随机数。xhit0={0,R(0,1)＜0.5；1‚R(0‚1)≥0.5。h=1,2,⋯,Η‚i=1‚2‚⋯‚Ν‚t=1‚2‚⋯‚Τ(14)每个粒子的速度由式(15)随机生成,其中vmax和vmin表示速度的最大和最小限制值。vhit0=vmin+R(0,1)(vmax-vmin)。(15)(3)pb药的计算计算粒子经历的最好位置和种群经历的最好位置,并更新记忆库。粒子的适应值可以由式(16)计算,其中G为1个充分大的正数。令PBhk表示第h个粒子进化k代所经历的最好位置,GBk表示整个种群进化k代所经历的最好位置。如果k=0,则PBh0=Xh0,否则PBhk可由式(17)计算。GBk可由式(18)计算,并将其存入记忆库。检查结束条件是否满足,满足则结束,否则继续。f(xhk)=(∑i=1Ν∑t=1Τ(ΡiQit+sixhitk+ΗiΙit)+∑t=1Τ∑Κ=1ΜSkΖkt)+G∑t=1Τ∑j=1R(max{0,∑i=1Ν(aijxhitk+bijQit)+∑k=1ΜAkjΖkt-Cjt})。(16)ΡBhk={ΡBhk-1,f(Xhk)＞f(ΡBhk-1)；Xhk,f(Xhk)≤f(ΡBhk-1)。(17)GBK=minPBhk,h=1,2,…,H。(18)(4)用存储库中的存储颗粒代替颗粒群中的适应值差的颗粒从记忆库中选择J个粒子,替换粒子群中那些适应值排在整个粒子群中后J位的粒子。(5)更新粒子的速度和位置为有效地更新粒子群中粒子的速度和位置,首先引入式(19)和式(20)。其中,式(19)的目的是使粒子的速度在最大最小速度范围之内,式(20)的目的是使结果值处于0和1之间。g(vhitk)={vmax,vhitk＞vmax；vhitk,vmin≤vhitk≤vmax；vmin,vhitk＜vmin。(19)h(vhitk)=11+(vmax-vhitkvhitk-vmin)2。(20)令k=k+1。由式(21),式(22)和式(23)来更新粒子的位置和速度,然后转(3)。Δvhitk-1=c1R(0,1)(PBhitk-1-xhitk-1)+c2R(0,1)(GBitk-1-xhitk-1);(21)vhitk=g(vhitk-1+Δvhitk-1);(22)xhitk={1,R(0,1)＜h(vhitk)；0‚R(0,1)≥h(vhitk)。(23)3优化算法仿真结果为了更好地说明算法的运行效果,本文用VB6.0为上文提到的算法编写了程序,选取文献和文献中的计算实例作为本文的仿真实例。文献和文献中的计算实例是一个6个工件、4个周期、2个簇的有约束成组生产批量计划问题,问题的参数数据如表1和表2所示。本文的二进制PSO算法的参数设置为:c1=c2=2,种群规模H=40,记忆更新粒子数J=2,最大进化代数50。本算法程序在IntelP41.7GHz,128M内存的计算机上独立运行50次,其中某一次的运行结果及目标函数收敛曲线如图1所示。50次的运行结果都达到了本文的最优值,平均耗时1s,平均进化代数10代。用二进制PSO算法求解仿真实例的计算结果如表3和表4所示。从表3和表4可以看出,在最优值方面,若不考虑能力约束,本文的改进二进制PSO算法优于文献和文献中的遗传算法;若考虑能力约束,本文的改进二进制PSO算法也优于文献的遗传算法(文献未计算有能力约束的情况)。而且本文算法在1s的时间内便找到了最优解,独立实验50次都找