基于改进算法的工艺规划与车间调度的双目标优化模型
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于改进算法的工艺规划与车间调度的双目标优化模型范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对工艺规划与车间调度的集成问题，一般考虑以加工时间、加工成本和加工质量为优化性能指标，而对能量消耗等环境影响因素考虑不足。本文建立了工艺规划与车间调度的数学模型，以完工时间和能量消耗为优化目标，通过设置权重系数来调节优化目标倾向。采用改进的混合模拟退火与遗传算法对问题进行求解，利用遗传算法的全局搜索速度快和模拟退火的突跳性强的特点，结合回火机制，有效地得到了完工时间和能量优化结果。最后，通过实例仿真表明该方法具有可行性。
中图分类号：TH166
文献标志码：A
文章编号：1005-2615（2015）01-0088-08
随着社会的发展，节能已成为大势所趋。企业要想提高竞争力，成本的节约无疑是非常关键的一环，能量消耗的减少，一方面有利于减小企业生产成本，另一方面有利于绿色环保。如果能够仅通过调度优化，在不改变技术、资源等需求的情况下，减少能量消耗，缩短完工时间，对提高企业的竞争力有着非常重要的意义。
在柔性制造提出之后，对工艺规划与车间调度集成的优化问题研究逐渐增多。高亮等论证了工艺规划与车间调度集成的必要性，分析了研究现状及发展趋势。田颖等对遗传算法求解工艺规划与调度集成做了研究。Li等用混合模拟退火与遗传算法对工艺规划进行了优化。他们的研究都是只针对单目标（完工时间）进行优化。当前，对于工艺规划与能量消耗的多目标优化问题研究较少。Liu等在混合流水车间内建立了能量模型，用自适应变异概率的改进遗传算法分别对能耗和完工时间进行优化，比较了两种不同优化目标下的能量消耗情况。Zhang等研究了柔性制造系统中的能量消耗与调度问题。Salido等建立了数学模型，分析了能量消耗、鲁棒性与完工时问之间的关系，提出了节约能量的3种途径：发明高效节能的生产机器、在产品设计阶段充分考虑节能减排、优化生产调度系统，指出第3种方法是最切实可行的“。Mouzon等建立了多目标数学规划模型探讨调度作业的问题，他们指出关闭一台非必要的加工机器，节省的能源消耗占总量的相关份额可能会增加80%。Bruzzone等提出了一种基于混合整数规划的调度算法，在保持原有的固定的工作分配和给定的排序柔性流水作业基上进行能源优化。这些研究都已经开始具备了能量节约因素，但是没有同时进行能量与完工时间的多目标优化。何彦等建立了能量优化与完工时间的双目标优化模型，用禁忌搜索算法对问题进行了求解。但足，他们的双目标模型中，每个工件只有一个工序，且可以在任意一台机器上加工，没有考虑工艺规划的因素。
本文在此基础上建立了工艺规划与车间调度的能量优化模型，采用一种基于模拟退火与遗传算法的混合算法，使用新的交叉方法，配合模拟退火及同火，求解完工时间与能量消耗的多目标优化，通过设置权重系数，使企业可以自由调节优化目标的倾向，以完工时间或是能量消耗为主，或者同时双目标优化。实验结果证明了方法的有效性。
l 问题描述
1.1 工艺规划与车间调度的数学模型
传统的车间调度中每个工件只有一条工艺路线，不能满足现代日益发展的柔性制造要求。在生产实际巾，每个工件可能有几种工艺路线，而每条工艺路线的工序又各不一样。把工艺路线的选择与车间调度同时进行优化，有利于缩短完工时间或达到其他优化目标，从而提高企业竞争力。为了建立数学模型，作如下假设：（1）每台机器一次只能进行一个工序的加工；（2）每台机器从空闲状态到加工状态的准备时间为O；（3）每个工件同时只能被一台设备加工；（4）每台机器从开机到该机器所有的加工任务完成，中间不关机；（5）每个工序的加工从开始到结束不允许被中断。
1.2 能量模型
根据假设，每台机器从任务开始，到本机器所有加工任务完成，一直在运转。在实际生产中，机器的切削能耗占总能耗的比例不大，为了方便建立，数学模型，采用空转功率来计算机器运转淌耗的能量。作如下符号定义：
PAi：机器i运转平均功率，即单位时平均消耗能量。
EAi：机器i运转消耗能量。
EA：所有机器运转消耗能量总和。
2 算法设计
本文提出的混合调度算法主要由遗传编码、遗传操作、模拟退火、模拟回火等模块组成，算法以迭代次数为收敛依据。在算法中，染色体采用分层编码的方式，遗传算法的变异模块用模拟退火代替，同时引入回火机制，既保留了遗传算法的寻优性，义具备模拟退火的突变性。算法流程如图1所示，设置回火代数为20。
算法步骤如下：
（1）基本参数输入，Jm，T，包含详细的工艺路线、加工机器、加工时间等信息；
（2）进行遗传算法操作，初始化种群；
（3）计算适应度值，判断是否满足迭代次数，否则继续；
（4）进行复制交叉、模拟退火、回火操作，产生新的种群，转步骤3；
（5）结束。
2.1 染色体编码及种群初始化
用遗传算法解决优化问题，对染色体的编码设计非常重要.既要包括工艺规划和车间调度的全部信息，又要有利于交叉变异。本文采用分层编码的方式，第一层为工艺选择，码长为工件个数，每个基因的值表示该序号工件选择的工艺路线序号；第二层编码为工序排列。码长为各工件机器矩阵t，，的列数和。以6工件为例，如第一层编码表示为3―2 2 1 3 3，表示1号工件采用第3条工艺路线，2号工件采用第2条工艺路线，3号工件采用第2条工艺路线。第二层编码：3-2-3-1-5-4-3-4-2-1-6-3-6-2-4-1-3-6-3-5-2-1-3-5.该层编码有7个3表示3号工件的7道工序，4个1表示1号工件的4道工序。结合第一层工艺编码，该染色体表示的加工顺序为N312N221N322N131N53lN411N323N412N222N132N631N324N632N223N413N133N325N633N326N532N224N134N327N533，其中，Nijk表示工件i的第j条工艺路线的第k道工序。这种编码的好处是每个个体的长度是一样的，有利于后续的交叉变异操作，而且交叉中不需要考虑各工件的加工工序约束关系。
2.2 适应度函数
在实际生产中，有时候交货期紧张，这个时候就需要完工时间最短，有时候交货期比较松，就可以能量消耗最少为目标。根据这一实际情况，对节能和完工时间的综合采用加权多目标综合方法，设置一个权重系数W来控制目标函数的倾向。由于能量和完工时间量纲的差异，且数值相差较大，不具有可比性，在加权之前需要对能耗和完工时间值作适当的处理，受启发，本文对两个目标进行去量纲处理。先对两个目标单独进行10次优化，取优化过程中出现的最大值Makespan（max），EA（max），最小值Makespan（min），EA（min）。去量纲后的目标函数可表示为
2.3 交叉
交叉是遗传算法进行寻优的重要环节。由于本文采取分层编码的方式，所以交叉也进行分层交叉。
在父代种群Chroml中随机选取两个染色体P1和P2作为父代，满叉概率后，进行分层交叉，如图2所示。工艺部分：分别从P1和P2中取出染色体的工艺部分P11和P21，进行普通的单点交叉，得到O11和021作为子代的工艺部分。工序部分：先取出父代染色体的工序部分P12和P22。根据工件个数n.将n的随机系列随机分为两块A和B，A中含有工件的数为（0.3-0.5）×N个，这样既能维持交叉产生新个体的多样性，又能充分继承父代的优良特性。以6工件为例，假设A=（2，5.6），B=（l，3，4），令Ol2 =P12，O22=P22，将O12中B工件位置置O，将P22中B工件依次填人O12中O的位置。同理，将022中A工件位置置0，将P12中A工件依次填入022中O的位置。将O11和012组合得到子代01，将021和组合得到子代02。将01和02放入子代种群Chrom2中。
对父代种群Chroml以及概率交叉后得到予种群Chrom2采取精英保留策略.即对Chroml和Chrom2进行全排列，取出较优的一半染色体组成新的种群Chrom，这样做的好处是既能得到交叉后的染色体的多样性，义不破坏父代种群中的优良个体。
2.4 变异
为了改善遗传算法容易陷入局部最优的缺点，本文采用模拟退火算法代替遗传算法中的变异模块，步骤如下：
（1）给定初始温度t0，在种群中随机取一个染色体，汁算目标值F。
（2）对染色体进行变异操作。工艺部分：随机取一个工件位置，随机取该工件的另一条工艺路线代替当前工艺路线。若当前工件只有一条工艺路线，则另取一个工件。工序部分：随机将两个基因值不同的工序位置进行交换，得到新的染色体，计算目标值F'，即F'-F=df，若dfO，即新染色体劣于原染色体，则概率接受新染色体。接受概率为cxp（-df/t）。
（3）更新温度t=t×q，q为降温系数。
2.5 回火机制
回火，就是连续多代小更新最优解时，人为地增加温度t的值，从而增大突变慨率。在算法运行的每一代中，以tempF记录、当前最优解，tempt记录当前温度，如果新种群最优解优于tempF，则更新tempF和tempt。本文设置回火代数为20，当连续20代不更新tempF时，令t=tempt，提高t的值，也就是提高突变慨牢。
3 算法仿真
目标函数值为0. 042 843。可以看出，不管是完工时间还是能量消耗，都不是单目标优化的最优值，但是目标函数最优。
（3）当w=0时，此时完工时间对目标函数值没有影响，相当于单一的能量优化。如图6所示，目标函数与能量消耗的变化曲线一致。最终的能量消耗值为617. 53，完工时间为37。由图7所示甘特图可以看出，在以能量消耗为单一目标优化的情况下，机器10由于能耗较大，并没有参与工作。
由图3可知，单纯的从车间调度与工艺规划的角度来看，本文的优化结果Makespan一27，优于的结果28，证明了本算法的可行性。图6中的能量消耗为617. 53，与图3中单一的完工时间优化所耗能量为796相比，能量的节约达到22. 5%。由以上结果可以看出，在权重系数W取值不同的结果下，目标函数的优化结果都不一样，企业在实际生产过程中，可以根据需求设置权重系数，在不影响交货期的情况下，最大限度地减少能量消耗。
4 实际案例
某车间需生产10个工件，每个工件有不同的工艺路线，共有加工设备10台，各设备在运转时所消耗的平均功率PU=[2.9，1.O，0.8，0.75，0.7，0. 65，0.95，1.7，0. 85，1.6] kW。加工数据如表l所示。
优化算法的参数设置和第3节一样，权重系数w=0：0.1：1.O，共11组，每组运行 20次，优化结果的完工时间和能量消耗各自取平均值。结果如表2所示。
在实际生产中，能量的消耗与完工时间是相互冲突的，一般情况下，二者不可能同时达到最优。从表2可以看出，随着权重系数的增大（即完工时间对目标函数的影响增大），完工时问逐步缩短，但是能量消耗逐渐增加。W=0时，只进行能量消耗优化，完工时间均值为4. 27 h，能耗均值为22. 406 5 kW.h；W=l时，只进行完工时n1J优化，完工时间均值为2. 925 h，能耗均值为30. 223 5 kW.h，比W=0时多消耗能量34.9%。
5 结束语
工艺规划与车间调度问题在企业生产中广泛存在，加上能量的优化，对企业提高竞争力有着极其重要的意义。本文在普通的遗传算法中，结合模拟退火算法，以及回火机制，有效地对工艺规划与车间调度中能量消耗和完工时间进行了优化。通过权重系数W的设置，可以帮助企业合理选择优化目标。从优化结果可以看出，在交货期不紧张的情况下，只需对生产调度进行改变，而不用增加其他任何支出，节能可以达到20%以上，为实际的企业生产提供了新的优化思路。