低碳目标下的柔性作业车间调度问题研究

党世杰，张国辉，钞宇飞



低碳目标下的柔性作业车间调度问题研究

党世杰1，张国辉1，钞宇飞2

摘要：针对柔性作业车间调度问题的特点，结合实际生产情况，建立低碳下的柔性作业车间调度问题模型，扩展了经典的柔性作业车间调度问题，使该问题更具现实意义。使用实际碳排放量为染色体编码，减少了以往遗传算法编码的转换，提高了编码和解码的效率，并使用了改进的遗传操作来提高遗传算法的效率。然后通过使用改进的遗传算法分析具体案例，得到了最优解，最后给出了机器最大碳排放量最低的调度方案，从而验证了所建模型的可行性及所提算法的有效性。

关键词：低碳遗传算法；柔性作业；车间调度

一、前言

柔性作业车间调度问题是经典作业车间调度问题的扩展，允许一道工序在可选机器集中任选一台机器进行加工，是典型的NP-Hard问题，是车间生产研究的重点问题之一。以往的柔性作业车间调度问题大多考虑最大完工时间[1-2]、机器负荷[3]、拖期[4]等，很少有文献从生产过程中碳排放量最小的角度去安排生产调度方案。

制造业消耗了大量能源，产生大量的温室气体，是碳排放的主要来源，对调度方案的中的碳排放量加以考虑有利于节能减排，降低生产成本，加大制造企业的成本优势。Tang等[5]考虑了柔性车间调度问题的能源消耗，并使用遗传模拟退火算法就行求解，但在大规模问题上的效果不理想。Liu等[6]使用遗传算法求解双目标柔性作业车间调度并取得了满意解。

本文建立了以低碳排放为目标的柔性作业车间调度模型，扩展了柔性作业车间调度问题，在遗传算法中对生产过程中的碳排放量直接进行编码，提高了编码和解码的效率。最后使用了遗传算法对问题进行求解，验证了所用算法在求解低碳目标下的柔性作业车间调度问题时的可行性和有效性。

二、低碳目标下的柔性作业车间调度问题的描述

低碳目标下的柔性作业车间调度问题需考虑三个子问题，即工序的加工机器、工序的加工顺序以及生产过程中的碳排放，是经典的作业车间调度问题的延伸。低碳目标下的柔性作业车间调度问题一般描述为：n个工件在m台机器上加工，每个工件由一道或多道工序构成，每道工序可在其可选机器集上选择一台机器加工，不同的工序在不同的机器上进行加工时的碳排放量可能相同也可能不同。调度目标是确定为工序选择最佳的加工机器，确定工序加工顺序，使生产过程中的碳排放量最小。表1所示的是4个工件在4台机器上加工的低碳目标下的柔性作业车间调度问题，如O11和M1对应的数字13表示工序O11在机器M1上加工时的碳排放量为13，“-”表示该工序不能在相应机器上加工。

低碳目标下的柔性作业车间调度问题的假设如下。

(1)某一工序在加工过程中不允许中断。

(2)不同工件之间没有加工顺序约束，同一工件的不同工序间有加工顺序约束。

(3)一台机器在同一时间只能加工某个工件的某一工序。

(4)为了保证加工过程的安全性，机器加工完一个工序，若下一工序仍为同一工件则继续加工，否则进行停机操作，当加工下一工件时重启机器进行加工。

本文的优化目标为：每个机器的最大碳排放量最小，即minCE=min(max(CEk)), 1≤k≤m，其中CE为碳排放量。

表1　低碳排放的柔性作业车间调度问题

三、遗传算法设计

遗传算法由美国Holland教授于1975年首先提出并被广泛用于函数优化、组合优化问题及生产调度问题等。本文使用了遗传算法求解低碳目标下的柔性作业车间调度问题，将生产过程中的碳排放量直接进行编码并优化求解。

1.编码和解码

编码和解码是运用遗传算法求解问题的关键步骤。柔性作业车间调度问题需要为每道工序选择合适的加工机器，然后确定加工顺序，因此本文设计的染色体由机器染色体和工序染色体构成。染色体编码如图1所示。

图1　染色体编码

在图1中显示了工件1的编码，工件2、3、4则依照此编码方式完成。图1中工件1加工部分可解码为工序O11在机器M4上加工，对应碳排放量为12；工序O12在机器M3上加工，对应碳排放量为11；工序O13在机器M2上加工，对应碳排放量为8；工序O14在机器M2上加工，对应碳排放量为12。该部分转化为机器顺序矩阵和碳排放量矩阵后为：

2.种群初始化

种群初始化即按照一定的方式生成初始可行解，初始解对整个算法的运行过程都有极大的影响。本文采用张国辉等[7]所使用的种群初始化方法来加快遗传算法的收敛速度。

3.遗传操作

(1)选择操作。通过使用选择操作可以使优良的个体得以保存下来，淘汰不适应环境的低劣个体来加快遗传算法的收敛性，提高算法效率。本文采用GOLDBERG等[8]提出的锦标赛法，目标值即是适应值，减少了目标值和适应值之间的转换，使操作更容易进行。

(2)交叉操作。针对染色体两段式特点，本文分别对机器染色体和工序染色体进行交叉操作，得到新染色体。当进行机器染色体交叉操作时采用两点交叉方式；工序染色体使用张超勇等[9]所提的POX交叉方式。通过使用交叉操作可以保留父代优良染色体，避免遗传算法陷入局部最优解。

(3)变异操作。该操作主要为了提高遗传算法的局部搜索能力，维持群体多样性，防止陷入局部最优解。机器染色体变异时，在基因串中随机选择一个位置，在此工序的加工机器集中任意选择一个与它不相等的整数，替换当前的基因，这样可以保证得到的解是可行的。工序染色体变异时，随机选择两个位置的基因后调换其位置，这种方法产生的解是合法解。

四、计算结果分析

遗传算法的程序采用Visual Studio 2012。程序在环境为P4 CPU、主频3.0GHz、内存4GB的个人电脑上运行，程序运行参数为：种群规模Ps=200，迭代次数G=100，交叉概率Pc=0.9，变异概率Pm=0.1。为了验证算法有效性，本文以表1为例进行计算，求得生产过程中每个机器最大碳排放量最低的调度方案，如图2所示，此时总碳排放量为153，然后可以按照该调度方案安排生产。

图2　每个机器最大碳排放量最低的调度方案

五、结语

本文通过对生产过程中每台机器的碳排放量最小为目标的柔性作业车间调度问题的描述，构建低碳目标下的柔性作业车间调度模型。基于基本的遗传算法，使用实际碳排放量为染色体编码，减少了以往编码方式的转换，提高了编码和解码的效率，并使用了改进的遗传操作来提高遗传算法的效率。然后使用了基于Visual Studio 2012的遗传算法程序对案例进行优化，得到了每台机器最大碳排放量最低的调度方案。最后给出了相应的调度甘特图。实验结果表明笔者提出的改进遗

传算法在求解低碳目标下的柔性作业车间调度问题时是可行的和有效的。

参考文献：

[1]张国辉,吴立辉.求解柔性作业车间调度的GATOC混合方法[J].计算机工程与应用，2015,51(23)：266-270.

[2]廖珊,翟所霞,鲁玉军.基于改进遗传算法的柔性作业车间调度方法研究[J].机电工程,2014,31(6):729-733.

[3]苏子林,车忠志,冯宝富.求解多目标柔性作业车间调度的改进遗传算法[J].鲁东大学学报(自然科学版),2015,31(4):380-384.

[4]项喧,陶守强,熊伟.结合仿真和遗传算法的生产调度多目标优化[J].系统仿真技术,2014,10(2):90-95.

[5]Tang D B, Dai M. Energy-efficient Approach to Minimizing the Energy Consumption in An Extended Job-shop Scheduling Problem[J]. Chinese Journal of MechanicalEngineering,2015,28(05):1-8.

[6]Liu Y, Tiwari A. An Investigation into Minimising Total Energy Consumption and Total Completion Time in a Flexible Job Shop for Recycling Carbon Fiber Reinforced Polymer[C]. The 22nd CIRP conference on Life Cycle Engineering,2015,29:722-727.

[7]张国辉,高亮,李培根,等.改进遗传算法求解柔性作业车间调度问题[J].机械工程学报,2009,45(7):145-151.

[8]GOLDBERG D E, DEB K. Acomparativeanalysisof selection schemes used in genetic algorithms[C].RAWLINSG,ed.FoundationsofGeneticAlgorithms,MorganKaufmann,1991:69-93.

[9]张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop 调度问题[J].中国机械工程,2004,15(23):83-87.

(2015CX009)；郑州航院大学生科技创新基金项目

(Y20150105))

(作者单位：1.郑州航空工业管理学院 管理工程学院；

2.中北大学 经济与管理学院)

(责任编校：裴媛慧，孙咏梅)

(基金项目：郑州航院研究生教育创新计划基金项目