基于改进算法的工艺规划与车间调度的双目标优化模型

黄志清;唐敦兵;戴敏

【摘 要】针对工艺规划与车间调度的集成问题,一般考虑以加工时间、加工成本和加工质量为优化性能指标,而对能量消耗等环境影响因素考虑不足.本文建立了工艺规划与车间调度的数学模型,以完工时间和能量消耗为优化目标,通过设置权重系数来调节优化目标倾向.采用改进的混合模拟退火与遗传算法对问题进行求解,利用遗传算法的全局搜索速度快和模拟退火的突跳性强的特点,结合回火机制,有效地得到了完工时间和能量优化结果.最后,通过实例仿真表明该方法具有可行性. 【期刊名称】《南京航空航天大学学报》 【年(卷),期】2015(047)001 【总页数】8页(P88-95)

【关键词】工艺规划与车间调度;能量消耗;模拟退火;遗传算法 【作 者】黄志清;唐敦兵;戴敏

【作者单位】南京航空航天大学机电学院,南京,210016;南京航空航天大学机电学院,南京,210016;南京航空航天大学机电学院,南京,210016 【正文语种】中 文 【中图分类】TH166

随着社会的发展，节能已成为大势所趋。企业要想提高竞争力，成本的节约无疑是非常关键的一环，能量消耗的减少，一方面有利于减小企业生产成本，另一方面有利于绿色环保。如果能够仅通过调度优化，在不改变技术、资源等需求的情况下，

减少能量消耗，缩短完工时间，对提高企业的竞争力有着非常重要的意义。 在柔性制造提出之后，对工艺规划与车间调度集成的优化问题研究逐渐增多。高亮等论证了工艺规划与车间调度集成的必要性，分析了研究现状及发展趋势［1］。田颖等对遗传算法求解工艺规划与调度集成做了研究［2］。Li等用混合模拟退火与遗传算法对工艺规划进行了优化［3］。他们的研究都是只针对单目标（完工时间）进行优化。当前，对于工艺规划与能量消耗的多目标优化问题研究较少。Liu等在混合流水车间内建立了能量模型［4］，用自适应变异概率的改进遗传算法分别对能耗和完工时间进行优化，比较了两种不同优化目标下的能量消耗情况。Zhang等研究了柔性制造系统中的能量消耗与调度问题［5］。Salido等建立了数学模型，分析了能量消耗、鲁棒性与完工时间之间的关系，提出了节约能量的3种途径:发明高效节能的生产机器、在产品设计阶段充分考虑节能减排、优化生产调度系统，指出第3种方法是最切实可行的［6］。Mouzon等建立了多目标数学规划模型探讨调度作业的问题，他们指出关闭一台非必要的加工机器，节省的能源消耗占总量的相关份额可能会增加80%［7］。Bruzzone等提出了一种基于混合整数规划的调度算法，在保持原有的固定的工作分配和给定的排序柔性流水作业基础上进行能源优化［8］。这些研究都已经开始具备了能量节约因素，但是没有同时进行能量与完工时间的多目标优化。何彦等建立了能量优化与完工时间的双目标优化模型，用禁忌搜索算法对问题进行了求解［9］。但是，他们的双目标模型中，每个工件只有一个工序，且可以在任意一台机器上加工，没有考虑工艺规划的因素。 本文在此基础上建立了工艺规划与车间调度的能量优化模型，采用一种基于模拟退火与遗传算法的混合算法，使用新的交叉方法，配合模拟退火及回火，求解完工时间与能量消耗的多目标优化，通过设置权重系数，使企业可以自由调节优化目标的倾向，以完工时间或是能量消耗为主，或者同时双目标优化。实验结果证明了方法的有效性。

1.1 工艺规划与车间调度的数学模型

传统的车间调度中每个工件只有一条工艺路线，不能满足现代日益发展的柔性制造要求。在生产实际中，每个工件可能有几种工艺路线，而每条工艺路线的工序又各不一样。把工艺路线的选择与车间调度同时进行优化，有利于缩短完工时间或达到其他优化目标，从而提高企业竞争力。为了建立数学模型，作如下假设:（1）每台机器一次只能进行一个工序的加工；（2）每台机器从空闲状态到加工状态的准备时间为0；（3）每个工件同时只能被一台设备加工；（4）每台机器从开机到该机器所有的加工任务完成，中间不关机；（5）每个工序的加工从开始到结束不允许被中断。

根据以上假设，为建立工艺规划与车间调度集成的数学模型，定义符号如下: N:工件数量。

Ni:第i个工件的工艺路线数目。

Nij:第i个工件的第j条工艺路线的工序数。 Oijk:工件i的第j条工艺路线的第k道工序。

sijk:工件i的第j条工艺路线的第k道工序在对应机器上加工的开始时间。 tijk:工件i的第j条工艺路线的第k道工序在对应机器上加工的加工时间。 cijk:工件i的第j条工艺路线的第k道工序在对应机器上加工的完工时间。 M:加工机器数。

建立 机 器 矩 阵 J，其 中 J=的数值表示工件i的第j条工艺路线的第k道工序的加工机器序号，Oijk=0表示该工艺没有这个工序。

i=1，…，n，tijk的数值表示工件i的第j条工艺路线的第k道工序的加工时间，tijk=0表示该工艺没有这个工序。当Oijk=0时，必有tijk=0。 令机器l运转时间为Ol，则整个制造系统的完工时间表述为 1.2 能量模型

根据假设，每台机器从任务开始，到本机器所有加工任务完成，一直在运转。在实际生产中，机器的切削能耗占总能耗的比例不大，为了方便建立数学模型，采用空转功率来计算机器运转消耗的能量。作如下符号定义: PAi:机器i运转平均功率，即单位时间平均消耗能量。 EAi:机器i运转消耗能量。 EA:所有机器运转消耗能量总和。 则机器l消耗能量表示为 系统总消耗能量

本文提出的混合调度算法主要由遗传编码、遗传操作、模拟退火、模拟回火等模块组成，算法以迭代次数为收敛依据。在算法中，染色体采用分层编码的方式，遗传算法的变异模块用模拟退火代替，同时引入回火机制，既保留了遗传算法的寻优性，又具备模拟退火的突变性。算法流程如图1所示，设置回火代数为20。 算法步骤如下:

（1）基本参数输入，Jm，T，包含详细的工艺路线、加工机器、加工时间等信息； （2）进行遗传算法操作，初始化种群；

（3）计算适应度值，判断是否满足迭代次数，否则继续；

（4）进行复制交叉、模拟退火、回火操作，产生新的种群，转步骤3； （5）结束。

2.1 染色体编码及种群初始化

用遗传算法解决优化问题，对染色体的编码设计非常重要，既要包括工艺规划和车间调度的全部信息，又要有利于交叉变异。本文采用分层编码的方式，第一层为工艺选择，码长为工件个数，每个基因的值表示该序号工件选择的工艺路线序号；第二层编码为工序排列。码长为各工件机器矩阵Ji的列数和。以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道工序。结合第一层工艺编码，该染色体表示的加工顺序为

N321→N221→N322→N131→N531→N411→N323→N412→N222→N132→N631→N324→N632→N223→N413→N133→N325→N633→N326→N532→N224→N134→N327→N533，其中，Nijk表示工件i的第j条工艺路线的第k道工序。这种编码的好处是每个个体的长度是一样的，有利于后续的交叉变异操作，而且交叉中不需要考虑各工件的加工工序约束关系。 2.2 适应度函数

在实际生产中，有时候交货期紧张，这个时候就需要完工时间最短，有时候交货期比较松，就可以能量消耗最少为目标。根据这一实际情况，对节能和完工时间的综合采用加权多目标综合方法，设置一个权重系数W 来控制目标函数的倾向。由于能量和完工时间量纲的差异，且数值相差较大，不具有可比性，在加权之前需要对能耗和完工时间值作适当的处理，受文献［10］的启发，本文对两个目标进行去量纲处理。先对两个目标单独进行10次优化，取优化过程中出现的最大值Makespanmax，EAmax，最小值Makespanmin，EAmin。去量纲后的目标函数可表示为 2.3 交叉

交叉是遗传算法进行寻优的重要环节。由于本文采取分层编码的方式，所以交叉也进行分层交叉。

在父代种群Chrom1中随机选取两个染色体P1和P2作为父代，满足交叉概率后，进行分层交叉，如图2所示。工艺部分:分别从P1和P2中取出染色体的工艺部分P11和P21，进行普通的单点交叉，得到O11和O21作为子代的工艺部分。工

序部分:先取出父代染色体的工序部分P12和P22。根据工件个数n，将n的随机系列随机分为两块A和B，A中含有工件的数为（0.3-0.5）×n个，这样既能维持交叉产生新个体的多样性，又能充分继承父代的优良特性。以6工件为例，假设A=（2，5，6），B=（1，3，4），令O12=P12，O22=P22，将O12中B工件位置置0，将P22中B工件依次填入O12中0的位置。同理，将O22中A工件位置置0，将P12中A工件依次填入O22中0的位置。将O11和O12组合得到子代O1，将O21和组合得到子代O2。将O1和O2放入子代种群Chrom2中。 对父代种群Chrom1以及概率交叉后得到子种群Chrom2采取精英保留策略［11］，即对Chrom1和Chrom2进行全排列，取出较优的一半染色体组成新的种群Chrom，这样做的好处是既能得到交叉后的染色体的多样性，又不破坏父代种群中的优良个体。 2.4 变异

为了改善遗传算法容易陷入局部最优的缺点，本文采用模拟退火算法代替遗传算法中的变异模块，步骤如下:

（1）给定初始温度t0，在种群中随机取一个染色体，计算目标值F。

（2）对染色体进行变异操作。工艺部分:随机取一个工件位置，随机取该工件的另一条工艺路线代替当前工艺路线。若当前工件只有一条工艺路线，则另取一个工件。工序部分:随机将两个基因值不同的工序位置进行交换，得到新的染色体，计算目标值F′，即F′-F=d f，若d f＜0，则以新染色体代替当前染色体；若d f＞0，即新染色体劣于原染色体，则概率接受新染色体。接受概率为exp（-d f/t）。 （3）更新温度t=t×q，q为降温系数。 2.5 回火机制

回火，就是连续多代不更新最优解时，人为地增加温度t的值，从而增大突变概率。在算法运行的每一代中，以temp F记录当前最优解，temp t记录当前温度，如

果新种群最优解优于temp F，则更新temp F和temp t。本文设置回火代数为20，当连续20代不更新temp F时，令t=temp t，提高t的值，也就是提高突变概率。

由于目前尚无工艺规划与能量优化的标准实例，本文模拟问题的工艺规划部分来自于文献［12］的例子:10个工件在10台机器上加工，每个工件有不同的工艺路线，各工艺路线对应不同的工序和加工机器，各工序对应的加工机器及加工时间已知。能量优化部分，假定各机器的空载功率为PU=［2.4 3.36 2.0 1.77 2.2 7.5 2.0 1.77 2.2 7.5］。令权重系数为W，迭代次数为100，种群大小为100，代沟为1，交叉概率0.8，初温t0=-500×（（max（Obj（V））-min（Obj（V）））/log（0.8）），Obj（V）为初始种群各个体的目标函数值。根据权重系数的变化情况，运行结果如下:

（1）当W=1时，能量消耗不参与优化，相当于单一的完工时间优化。运行结果如图3所示，其中图3（a～c）分别表示目标函数、完工时间、能量消耗的收敛情况。从图中可以看出，它们在迭代40次后均能实现快速的收敛，其中完工时间最优值为27，能量消耗值为796。同时，由程序运算可获得最优工艺路线S=（2 1 1 2 2 2 3 1 2 2）和对应工序排列P=（1 5 1 9 5 7 4 8 1 7 1 4 2 4 6 9 3 5 5 2 1 5 6 1 10 10 2 1 3 5 4 1 2 10 1 9 8 8 3 7 2 9 5 3 1 6 4）。进一步，给出W 等于1时车间调度与工艺规划甘特图，如图4所示。

（2）当W=0.5时，此时为双目标优化，完工时间和能量消耗同时影响着目标函数，如图5所示。最终的优化结果为:完工时间29，能量消耗为703，目标函数值为0.042 843。可以看出，不管是完工时间还是能量消耗，都不是单目标优化的最优值，但是目标函数最优。

（3）当W=0时，此时完工时间对目标函数值没有影响，相当于单一的能量优化。如图6所示，目标函数与能量消耗的变化曲线一致。最终的能量消耗值为617.53，

完工时间为37。由图7所示甘特图可以看出，在以能量消耗为单一目标优化的情况下，机器10由于能耗较大，并没有参与工作。

由图3可知，单纯的从车间调度与工艺规划的角度来看，本文的优化结果Makespan=27，优于文献［11］的结果28，证明了本算法的可行性。图6中的能量消耗为617.53，与图3中单一的完工时间优化所耗能量为796相比，能量的节约达到22.5%。由以上结果可以看出，在权重系数W取值不同的结果下，目标函数的优化结果都不一样，企业在实际生产过程中，可以根据需求设置权重系数，在不影响交货期的情况下，最大限度地减少能量消耗。

某车间需生产10个工件，每个工件有不同的工艺路线，共有加工设备10台，各设备在运转时所消耗的平均功率PU=［2.9，1.0，0.8，0.75，0.7， 0.65，0.95，1.7，0.85，1.6］k W。加工数据如表1所示。

优化算法的参数设置和第3节一样，权重系数W=0∶0.1∶1.0，共11组，每组运行20次，优化结果的完工时间和能量消耗各自取平均值。结果如表2所示。 在实际生产中，能量的消耗与完工时间是相互冲突的，一般情况下，二者不可能同时达到最优。从表2可以看出，随着权重系数的增大（即完工时间对目标函数的影响增大），完工时间逐步缩短，但是能量消耗逐渐增加。W=0时，只进行能量消耗优化，完工时间均值为4.27 h，能耗均值为22.406 5 k W·h；W=1时，只进行完工时间优化，完工时间均值为2.925 h，能耗均值为30.223 5 k W·h，比W=0时多消耗能量34.9%。

工艺规划与车间调度问题在企业生产中广泛存在，加上能量的优化，对企业提高竞争力有着极

其重要的意义。本文在普通的遗传算法中，结合模拟退火算法，以及回火机制，有效地对工艺规划与车间调度中能量消耗和完工时间进行了优化。通过权重系数W 的设置，可以帮助企业合理选择优化目标。从优化结果可以看出，在交货期不紧张

的情况下，只需对生产调度进行改变，而不用增加其

他任何支出，节能可以达到20%以上，为实际的企业生产提供了新的优化思路。

【相关文献】

［1］ 高亮，李新宇.工艺规划与车间调度集成研究现在及展望［J］.中国机械工程，2011，22（8）:1001-1007. Gao Liang，Li Xinyu.Current researches on integrated process planning and scheduling［J］.China Mechanical Engineering，2011，22（8）:1001-1007.

［2］ 田颖，江平宇，周光辉，等.基于遗传算法的工艺规划与调度集成方法［J］.西安交通大学学报，2006，40（9）:1041-1044. Tian Ying，Jiang Pingyu，Zhou Guanghui，et

al.Integration of process planning and scheduling with genetic algorithm［J］.Journal of Xi＇an Jiao Tong University，2006，40（9）:1041-1044.

［3］ Li W D，Mc Mahon C A.A simulated annealingbased optimization approach for integrated process planning and scheduling［J］.International Journal of Computer Integrated Manufacturing，2007，20（1）: 80-95.

［4］ Liu Xiang，Zou Eengxing，Zhang Xiangping.Mathematical model and genetic optimization for hybrid flow shop scheduling problem based on energy consumption［C］//Control and Decision Conference. USA:IEEE，2008:1002-1007.

［5］ Zhang Liping，Li Xinyu，Gao Liang，et al.Dynamic scheduling model in EMS by considering energy consumption and schedule efficiency［C］//Computer Supported Cooperative Work in Design（CSCWD），IEEE 16th International Conference on.USA: IEEE，2012:719-724.

［6］ Salido M A，Escamilla J，Barber E，et al.Energyaware parameters in job-shop scheduling problems［C］//GREEN-COPLAS 2013:IJCAI 2013 Workshop on Constraint Reasoning，Planning and Scheduling Problems for a Sustainable Euture.Beijing，China:IJCAI-13，2013:44-53.

［7］ Mouzon G，Yildirim M B，Twomey J.Operational methods for minimization of energy consumption of manufacturing equipment［J］.International Journal of Production Research，2007，45（18/19）:4247-4271.

［8］ Bruzzone A A G，Anghinolfi D，Paolucci M，et al. Energy-aware scheduling for improving manufacturing process sustainability:A mathematical model for flexible flow shops［J］.CIRP Annals-Manufacturing Technology，2012，61（1）:459-462.

［9］ He Yan，Liu Eei，Cao Huajun，et al.A bi-objective model for job-shop scheduling problem to minimize both energy consumption and makespan［J］.Journal of Central South University of Technology，2005，12（2）:167-171.

［10］曹华军，刘飞，何彦.机械加工系统节能降噪型综合任务分配模型及其应用［J］.机械工程学报，2006，42（5）:97-102. Cao Huajun，Liu Eei，He Yan.Integrated taskassigning model of energy saving and noise reduction in the maching systems and its application［J］.Chinese Journal of Mechanical Engineering，2006，42（5）:97-102.

［11］林棻，王伟，张尧文，等.基于非劣排序遗传算法的三代轮毅轴承多目标优化［J］.南京航空航天大学学报，2013，45（6）:865-871. Lin Een，Wang Wei，Zhang Yaowen，et al.Multiobjective optimization for third generation wheel hub bearing based on NSGA-II［J］.Journal of Nanjing University of Aeronautics&Astronautics，2013，45（6）:865-871. ［12］Mohammadi G，Karampourhaghghi A，Samaei E.A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing［J］.International Journal of Production Research，2012，50（18）: 5063-5076.