易变质产品批量计划与作业排序集成优化

易变质产品批量计划与作业排序集成优化

1多层生产计划问题批发计划和运营顺序的整合和优化一直是生产计划领域的研究热点，这对降低成本、缩短生产周期、提高生产效率具有重要意义。现有研究中,有很多仅是单独针对批量计划或单独针对作业排序问题的。文献总结了在确定性环境下各种批量计划的模型及其求解算法。文献在不确定环境下求解柔性自动化车间的随机生产计划和控制问题。然而不同层次的生产计划之间是紧密联系的,为了能有效地组织生产,不同层次的计划无论在制定阶段还是在实施阶段都必须要进行有效的沟通,相互之间并不是孤立的。因此,近年来,在批量计划和作业排序研究的基础上,多层生产计划问题吸引了大量学者的研究兴趣。目前,对于多层生产计划问题的建模,最具有普遍性的建模方法是基于时段的建模方法,即将整个规划周期分成若干个时段,每个时段都有需求,前面时段生产的产品,如果满足了需求之后还有剩余,可以以库存方式来满足后面的需求,优化的对象为各个时段的批量安排和作业安排。然而,以上研究的多层生产计划问题都没有考虑到产成品的变质。事实上,现实生活中存在着大量的易变质产品,例如牛奶、蔬菜、水果、肉食、鲜花、药品等等。这些产品较高的变质率影响了管理者的生产决策。Ghare和Schrader首先对常数变质率和需求率的易变质产品进行了探讨。在随后的数十年中,许多学者如Nahmias、Papachristos、余玉刚、文晓巍、Teng等对易变质产品的相关问题进行了深入的研究,但绝大多关于易变质品的研究仅是局限于库存阶段,并未涉及到生产方面,该文正是基于这一点,提出了结合易变质产品的批量计划和作业排序集成优化设计模型。由于问题的复杂性,目前关这方面研究文献基本上没有,是一个尚待研究的新课题,而此类生产问题在现实中却是大量存在的。如食品加工厂需要针对外界需求对多种食品进行加工,而生产周期中产生的库存可能发生变质造成损耗。在分析现有的批量计划与作业排序集成优化的模型上针对易变质产品提出了新的模型并进行了相应的分析研究。2模型a:加工顺序某食品加工厂有单机加工中心,在整个有限计划周期内将要生产N种不同食品,经数据统计分析,每个周期内,N种食品库存的平均变质率分别为θi(变质的食品取整)。计划周期均分为T个时段,每种食品i在机器上的加工时间已知(pi不同),机器从生产食品i调整到生产食品j(i,j=1,2,…,N;i≠j)需要相关的调整时间τij。每种食品i在每个时段t的需求量dit已知,并且各时段食品允许缺货。生产者的各种原材料能够及时得到补充,且原材料变质率为0。食品产出后变质成本分别δi(变质成本δi远小于缺货成本)。要求解每个时段t每种食品i的批量xit及其加工顺序st,使得库存费用、缺货费用、加班费用与变质费用之和最小。生产能力约束通过时间来体现,每个时段的时间长度有限。在有限的生产能力条件下,需要安排每种食品在各个时段的计划生产量。如果后面时段的生产能力不足,且前面生产能力有剩余,允许提前生产一部分食品来保证后面的需求,但需要支付库存费用;允许加班或者缺货,但需要支付相应的加班费用和缺货费用,整个周期内加班时间存在上限,用于最后优化结果的检验。此外还需对对机器上的食品加工顺序做出安排。机器从一种食品加工状态调整到另外一种食品加工状态,需要不同的机器调整时间。因此食品加工顺序直接影响着批量计划层的批量安排,批量计划和作业排序之间互相制约。另外,初始库存为零,在整个计划周期内每种食品的总产量等于总需求与总变质量之和。以上问题可以用如下模型表示:其中,决策变量为:xit:时段t内食品i的计划批量;st:时段t内不同食品的加工顺序;模型参数包括:T:整个计划周期分成的时段数量;At:每个时段的时间长度,即可用工时;A:整个计划周期内加班时间上限;τij:机器从生产食品i调整为生产食品j的调整时间;θi:食品i的变质率;Iit:时段t末食品i的库存量;li:单位食品i的缺货费用;δi:单位食品i的变质费用;o:单位时间的加班费用;dit:时段t内食品i的需求量;χit:时段t内食品i的变质量;hi:单位食品i的库存费用。3基于邻域的进化框架传统遗传算法只考虑生物之间的竞争,没有考虑生物之间协作的可能,在运算过程中极易陷入局部最优。而协同进化算法在遗传算法等进化算法基础上,考虑了种群与环境之间、种群与种群之间在进化过程中的协调,将种群中个体的适应度通过与其他种群中个体的一系列合作作用并根据其对目标问题解决的贡献度来决定的协同进化,可在一定程度上弥补遗传算法的缺陷。采用协同遗传进化算法,即采用协同进化算法和遗传算法并行混合搜索框架。混合种群包括两类种群,一类为采用协同进化算法进化的排序子种群P(1)和批量子种群P(2),另一类为采用遗传算法进化的公共种群P(3),通过引入迁移算子,把协同进化算法和遗传算法有机联系起来,充分发挥两种算法的优势,使得每代子种群协同进化过程中获得的最好“完整解个体”(同时包含批量与排序信息)能够保留到公共种群中进一步进化,从而保证较好的进化模式不会因为协同进化的动态性能而被较早淘汰。同时,算法采用了基于邻域的进化策略以加强种群多样性,并根据问题特点设计了有效的交叉和变异算子,提高搜索性能。排序子种群P(1)、批量子种群P(2)都采用二维的正方形格栅结构,NP[k]ij(k=1,2)代表3×3的邻域,该邻域包含个体(i,j)及其他在种群P(k)内的8个邻域个体。基于邻域的进化框架具体步骤如下:(1)随机选择进化中心(i,j),确定3×3的邻域NP[k]ij(k=1,2,3)。(2)在邻域范围内依次对两类种群进行局部进化,对子种群邻域内的个体协同进化。(3)通过改变进化中心(i,j)的位置重复上述过程,直到满足终止准则。基于种群的进化策略容易使好的个体模式快速繁衍,布满整个种群,从而造成种群陷入局部最优,而这种基于邻域的进化策略,每轮进化过程中,各种遗传操作只是作用在每个种群某个3×3的邻域内,新生成的个体也仅仅能够影响与其相邻的部分个体,从而鼓励不同区域的个体向不同的方向发展,较好地保证种群的多样性。3.1编码形式和启动3.1.1初始模拟加工如果考虑N种产品和T个时段,排序部分的编码形式本应该为S=[sit]N×T,然而除去第一个时段外,每个时段机器的初始加工状态为上个时段末机器的加工状态,而上个时段末的机器加工状态直接影响当前时段初的机器调整时间,因此在每个时段初都把上个时段末机器的加工工序当作机器的初始虚工序,代表机器的初始加工状态,所以排序部分的个体编码形式修正为S=[sit](N+1)×T,其中sit为时段t内第i道加工的工序所对应的产品类别号,每个时段除初始虚工序外,初始排序基因sit均随机生成(不重复)。3.1.2基因中心qt的初始化如果考虑N种产品和T个时段,批量部分的编码形式应该为Q=[qit]N×T,第i行基因qit代表产品i在各个时段的计划批量(也即xit),每个基因qit的初值按照如下步骤生成:步骤1qit在[0.75dit,1.25dit]中随机产生,并取整数,dit为时段t内产品i的需求量。步骤2对Q作修复,以满足式(2)约束。对于每一种产品i,按照式(7)计算总需求与总变质产品之和减去总计划产量的值Δi:若Δi≥-qiT则更新qiT为qiT+Δi,前T-1个时段产品i的计划批量保持不变;若Δi<-qiT则重新生成初始批量部分。3.2遗传操作的计费3.2.1选择父节点选择算子采用基于适应值的轮盘赌方法,用于选择执行交叉操作的父代个体,适应值越高的个体被选中的概率越大。3.2.2交叉处理(1)fps的边界信息①先利用F2的边界信息;②如果F2的边界信息无法利用,则利用F1的边界信息;③如果F1,F2的边界信息都无法利用,则在还未安排的产品种类中随机选择。子代个体S2排序基因生成方式类似。3.3批量部分和排序部分进行变异操作对群体中的每个个体以一个较低的概率来进行,同样分为批量部分和排序部分两部分分别进行。类似于交叉操作,公共种群P(3)的个体变异操作也是批量部分和排序部分基因各自同时进行的。3.4各进化个体的迁移在基于邻域的进化过程中,子种群中的个体协同进化,而协同进化的动态性能无法保证适应值高的个体能较长时间地保留下来,因此,算法设计了一种迁移算子,把所得到的最好的“完整解个体”保留到公共种群的邻域中,取代邻域中最差的完整解个体,这种迁移过来的“完整解个体”是当前代子种群中的进化个体与共生伙伴的最好“结合”,同时包含批量与排序信息。这种迁移算子有助于保留子种群之间相互作用所产生的较好的进化模式,使其可以沿着较好的方向进一步进化,同时,由于这些高性能的完整解个体来自于公共种群之外,能够增加其多样性,因此也有助于避免遗传算法陷入局部最优,从而提升算法的整体性能。3.5子种群完整解的选择对于子种群P(1)和P(2)的个体来说,它们只是代表源问题的部分解,因此在评价子种群P(1)和P(2)的个体时需要为其选择共生伙伴,从而与被评价个体组成完整解个体。共生伙伴的选择方式有很多种,算法采用方式为在子种群邻域内随机选择共生伙伴。得到完整解个体以后,就可以带入目标函数中求出相应的目标函数值,并按照式(8)计算其适应值。fit(xi)=mj∈aRx{f(xj)}-f(xi),R为评价群体(8)3.6邻域n[q]ij的协同进化上面讨论了算法的关键技术,整个算法流程如下。步骤1初始化生成3个种群P(k)(k=1,2,3)。P(1)代表排序子种群,P(2)代表批量子种群,P(3)为公共种群。步骤2对每个种群中的初始个体进行适应值评估。对于子种群P(1)和P(2)中的个体,评价时选取另一种群中与其序号相同(即处在同一位置)的个体作为共生伙伴;对于公共种群P(3)中的个体,则直接进行评估。确定最优适应值fbest。步骤3随机选择进化中心(i,j),构造邻域NP[k]ij(k=1,2,3)。设置q=1。步骤4基于邻域NP[q]ij的混合种群协同进化。步骤4.1采用基于适应值的轮盘赌方法在邻域NP[q]ij内选择交叉的父代个体,运用交叉算子产生两个子代个体,同时用新生的子代个体取代邻域NP[q]ij内的两个最差个体。步骤4.2根据变异概率对邻域NP[q]ij内的个体执行变异操作。步骤4.3对新生成的个体进行适应值评估。对于子种群邻域内的新生个体,评估时共生伙伴在另一子种群邻域内随机选择;对于公共种群邻域内的新生个体,则直接进行评估。如果新生的子代个体适应值高于最优适应值fbest,则更新最优适应值fbest。步骤4.5令q←q+1,如果q≤3(种群数量),则返回步骤4;否则进入步骤5。步骤5利用迁移算子,把排序子种群P(1)和批量子种群P(2)邻域NP[q]ij(q=1,2)内的个体在进化时所获得的最好完整解个体迁移到公共种群P(3)邻域NPij内,并取代NPij内的最差个体。步骤6如果满足终止准则,则算法结束;否则返回步骤3,开始新一轮进化。4调整时间及算法性能分析由于此类问题没有标准算例可供参考,为验证算法的有效性,参照相关文献做法根据问题特点设计了如下算例:某食品加工工厂生产5种易变质食品,生产计划周期为5周。工厂初始库存为0,每种食品每周的需求量已知,在整个计划期内,产出量等于需求量与变质量之和。在每个周期内,上一周期的库存会以概率θi发生变质。单位食品的库存费用,变质费用,缺货费用、生产线的调整时间、加班费用均随机生成。当然缺货成本要高于变质成本,这样库存的存在才有意义。数值仿真实验的模型参数如下:需求矩阵D={dit}N×T中的元素dit在50~100之间随机生成;食品i的加工时间pi在1~10之间随机生成,机器调整时间sij在5~20之间随机生成;时段长度A分别为1700,允许最长加班时间为500;食品i的变质率在0.1~0.2间随机生产,食品i的单位库存费用hi在2~4随机生成;食品i的单位变质费用hi在2~4随机生成;每种食品的单位缺货费用li在40~60之间随机生成,单位时间加班费用o=5。混合协同进化算法的参数如下:每个种群规模为100,交叉概率0.8,变异概率0.2,最大进化代数为5000,对算例独立运行10次,分析其算法性能,同时给出了最优解相对于初始解在各项指标上的改进比例。改进比例的计算方式为(初始解——最优解)/初始解。运算结果见表1。为了进一步验证该文采用的协同进化遗传算法(HybridCoevolutionaryGeneticAlgorithm,HCGA)的搜索性能,采用传统的遗传算法(GeneticAlgorithm,GA)作为对比算法。HCGA与GA的区别在于:在整个算法框架上,GA采用的是单种群优化,即只产生并优化完整种群。为体现算法对比的公平性,两种算法在遗传操作和进化参数上保持一致,两种算法同样独立运行10次,对比其进化结果。表2对比了两种算法的进化结果,该算法无论平均值还是最好值都获得了比遗传算法更好的结果,从标准偏差上看,算法的进化结果落在相对较小的范围内,显示了较强的稳健性。此外在运行时间上,GA所花费的时间几乎是HCGA的2.5倍左右。从整体上来说,协同进化遗传算法在算法性能上和单纯遗传算法相比得到很大的改进。图1显示了HCGA算法、GA算法在该问题上分别的进化过程。在进化初始阶段,算法收敛速度比遗传算法慢,这是因为算法采用基于邻域的进化策略,算法初期需要一定的进化过程来遍历整个种群,从而不断提高种群整体的进化质量。在进化的中后期,“贪婪”的遗传算法逐步陷入局部最优,很难找到更好的解,而算法在整个进化过程中不断地找到更好的解,最终获得了比遗传算法更好的解,这主要得益于迁移算子使得协同进化算法和遗传算法优势互补,从而显示了较强的寻优能力。5算法性能测试针对一类加工易变质产品并带有器调整时间的加工车间提出了批量计划与作业排序的集成优化模型,根据问题建立一种混合整数规划模型,并设计