遗传算法求解低碳柔性车间生产调度问题

张国辉，党世杰

(郑州航空工业管理学院 管理工程学院, 郑州 450015)



遗传算法求解低碳柔性车间生产调度问题

张国辉，党世杰

(郑州航空工业管理学院 管理工程学院, 郑州 450015)

低碳生产方式已成为当前各国所认可的生产方式，是可持续发展的必然要求。从满足最大完工时间最小和生产碳排放量最小角度出发，构建低碳车间调度模型。使用改进的遗传算法对有低碳需求的车间生产方式进行求解，在求解过程中对初始解生成机制和遗传算子进行改进，提高算法收敛速度。实验结果证明提出的改进遗传算法在求解车间低碳生产调度中是可行的。

低碳；遗传算法；柔性作业车间调度；优化

0 引言

先进的制造方式能减少碳排放并节约能源，是可持续发展和低碳制造实施的关键环节。车间调度技术在保证产品质量和控制生产成本的同时，能够优化加工方案，减少能源消耗量，降低制造过程中的碳排放。

柔性作业车间调度问题(Flexible Job Shop Scheduling Problem, FJSP)扩展了传统的作业车间调度问题，更贴近生产，然而，计算难度急剧增加，传统的优化方法已不能满足求解的需要。许多学者使用智能算法求解柔性作业车间调度问题，例如：遗传算法[1]、粒子群优化算法[2]、侦查包围搜索算法[3]以及蚁群算法[4]等。其中有部分学者将碳排放量作为优化目标之一，通过使用有效的调度方案减少能源消耗，增加企业效益。蒋增强等[5]在考虑设备状态-能耗分布曲线的低碳策略基础上，使用改进的NSGA-II算法求解多目标调度模型。Liu等[6]使用改进的遗传算法求解双目标柔性作业车间调度，减少了加工时的能源消耗并缩短了完工时间。Miguel等[7]依据加工速度和能耗的关系，建立了以能耗及最大完工时间为目标的柔性车间调度模型。Tang等[8]使用遗传模拟退火算法对小规模和大规模两种问题进行求解，得出了小规模问题比大规模问题的能效提升效果显著的结论。

本文以某制造企业的一个生产加工车间为例，建立了以最大完工时间和碳排放量为目标的柔性作业车间调度模型，最后利用改进的遗传算法进行求解，验证了所提遗传算法在求解有低碳需求的生产调度车间的可行性和有效性。

1 低碳排放目标下柔性作业车间调度问题模型

为实现节能减排，降低碳排放，缩短最大完工时间，本文对低碳排放目标下FJSP建立了数学模型。

为了便于描述FJSP，本文定义以下变量和参数：

n为工件总数；

m为机器总量；

h为机器序号，h= 1，2，3，…，m；

i为工件序号，i= 1，2，3，…，n；

Oij为第i个工件的第j道工序；

tijh为工序Oij在机器h上的加工时间；

Cmax为最大完工时间；

f(x)为决策者根据目标权重选择的生产方案；

E为碳排放量；

FJSP问题则可以描述为有m台加工机器加工n个工件，每个工件有i个工序，每个工序可以在h台可选机器上任选一台进行加工，最大完工时间和碳排放量因加工机器和工序顺序的不同而不同，通过合理的调度方案可以有效的减少生产过程中的能源消耗和加工时间浪费。

本文以最大完工时间和碳排放量为目标，目标函数如下：

(1)最大完工时间最小:

minCmax=min(max{Ci|i=1,2,…,n})

(1)

(2)碳排放量最小:

(2)

分别对两个函数赋以权重α、β，得到：

minf(x)=α·Cmax+β·E

(3)

假设在FJSP问题中，存在一个可选方案集S，则方案集中的一个方案s投影到轴C和轴E后，分别乘以各自的权重，比较所有的方案，数值越大的方案对决策者的效用越低，故数值最小的f(x)的即是所选择的方案，如图1所示。

图1 调度可选方案集

约束条件为：

(1)工序先后约束

tij≤ti(j+1)

(4)

(2)加工机器约束

(5)

(3)资源约束

tijh≤tglh∪Rijglh=1

(6)

2 改进遗传算法求解FJSP问题

2.1 编码和解码

两段式编码方式是为了解决FJSP问题的两个子问题，工序染色体部分用来解决工序排序问题，机器染色体部分用来解决机器选择问题。本文在编码和解码时使用张国辉等[9]所提出的方法来提高种群初始解的质量，加快遗传算法的收敛速度。

2.2 初始解的产生

本文采用两段式编码方式，工序染色体部分随机产生，改进了机器染色体部分生成机制。即在生成工序染色体后，在每道工序上随机选择两个加工机器，然后在[0,1]区间上产生一个随机数λ，若λ>0.8，选择加工时间较短的机器，其他情况则选择加工时间较长的机器作为该工序的加工机器。

2.3 遗传操作

遗传操作主要包括选择操作、交叉操作、变异操作。选择操作使用锦标赛选择方法，该方法随机性强，有利于筛选出适应性强的个体。针对工序染色体和机器染色体使用不同的交叉方式，在进行交叉操作和变异操作时分别根据每段染色体的特点进行相应的操作。

(1)机器染色体交叉操作

在机器染色体交叉操作时使用MPX[10]交叉方式，随机产生一条染色体且与机器染色体长度相同，该染色体上的基因只能是0和1。对比该染色体和机器染色体，若该随机染色体为0的位置则保留父代染色体上相应的基因，否则交换父代染色体的位置，经过变换后产生两条新的合法子代染色体。

(2)工序染色体交叉操作

在该操作中使用张超勇等[11]提出的POX交叉操作。将所有的工件分为两个集合，记为工件集1和工件集2，生成两个长度与原染色体相同的空白子代染色体，然后在第一个子代染色体的位置保留工件集1对应的基因，在第二个子代染色体中保留集合2的位置，依照剩余染色体保留它们的顺序填充到子代染色体。

(3)机器染色体变异操作

机器染色体变异时，在机器染色体随机选择一个基因，然后从对应工序上的加工机器集中再随机选择一台其他的加工机器并作为该工序的加工机器，这种变异方式能够保证变异后的机器染色体仍是合法解。

(4)工序染色体变异操作

当进行工序染色体变异时，随机选择两个不为同一工件的工序，交换两者的位置后得到一条新的染色体。根据工序染色体编码的特点，该变异操作避免产生非法解，同时增加了种群多样性。

2.4 计算流程

改进后的遗传算法计算流程可以描述为：

步骤1：参数设置。设定种群规模、交叉概率、变异概率等参数;

步骤2：种群初始化。利用提出的初始化方法对种群进行初始化，产生新种群;

步骤3：评价种群中的每个染色体个体的适应度值，若满足结束条件，则输出最优解并结束运行，否则进入步骤4;

步骤4：更新种群。对种群个体执行锦标赛选择，对满足条件的染色体个体执行交叉操作和变异操作，得到新种群;

步骤5：返回步骤3。

3 实例仿真实验

某制造车间生产过程可以简化为一个8个工件在7台机器上加工的柔性作业车间调度问题。在对车间生产进行调度时，方案的决策者希望生产过程中完工时间和车间碳排放两个目标都得以优化。该制造车间的加工数据如表1所示，表中第1列表示工件号，第2列表示每个工件的工序，第3～7列表示可选择的加工机器，有数字的代表对应的机器可以被选择，例如工序O11不可以在机器M1上加工，可以在机器M2上加工，且加工时间为16，碳排放量为1.7。

表1 加工车间简化后的FJSP问题

算法采用Visual Studio 2012编程，运行环境为P4 CPU，主频2.3GHz，内存2G的个人计算机。其中多目标遗传算法的主要参数设置如下：种群规模P=200，交叉概率Pc=0.8，变异概率Pm=0.05。使用改进的遗传算法求解该FJSP实例，得到的结果如表2所示。表2中，分别对三种情况下的完工时间和碳排放量之间的权重进行优化求解，这几个解之间是非支配解的关系。当完工时间的权重比较大时，获得调度方案完工时间最小，然而碳排放量明显高；当完工时间的权重比较小时，获得调度方案碳排放量最低，而完工时间会比较长。

表2 不同权重下的目标值

在选取方案时，根据决策者对实际情况的了解，选取一个调度方案为其执行方案。本文给出了当目标权重相同时的甘特图，如图2所示，其中最大完工时间是66，生产碳排放量是677.4，右上角的数字代表该工序在机器上加工时的碳排放量。如图2所示的在机器M1上有两个加工工序O31、O22，它们的加工时间分别为18、17，对应的碳排量分别为39.6、44.2。

图2 调度甘特图

4 结论

通过对有低碳生产要求的柔性车间调度问题的描述，构建以最大完工时间最小和碳排放量最小为目标函数的调度模型。提出了改进的遗传算法以提高算法收敛速度，改进了遗传算法初始解生成机制和优化了选择、交叉、变异操作等。然后以企业车间生产实际案例为应用背景进行优化，得到了不同权重下的调度方案。最后给出了两个目标权重相似的方案调度甘特图，实验结果表明提出的改进遗传算法在求解车间低碳生产方式是可行的。

[1] 李运霞, 杜娟, 孙王路. 基于多种群遗传算法的路径柔性车间调度问题[J]. 组合机床与自动化加工技术, 2014(3): 152-155.

[2] 刘韵, 胡毅, 罗企, 等. 一种解决柔性车间作业调度问题的粒子群优化算法[J]. 组合机床与自动化加工技术, 2015(12): 144-147.

[3] 刘韵, 胡毅, 房超, 等. 解决柔性车间作业调度问题的侦查包围搜索算法[J]. 组合机床与自动化加工技术, 2015(11): 124-128.

[4] 武福, 张治娟. 一种求解柔性作业车间调度问题的混合智能算法[J]. 组合机床与自动化加工技术, 2013(5): 130-133.

[5] 蒋增强, 左乐. 低碳策略下的多目标柔性作业车间调度[J]. 计算机集成制造系统, 2005, 21(4): 1023-1031.

[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] Salido M A, Escamilla J, Giret A, et al. A genetic algorithm for energy-efficiency in job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2015: 1-12.

[8] Tang D B, Dai M. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2015, 28(5): 1-8.

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

[10] 刘琼, 张超勇, 饶运清, 等. 改进遗传算法解决柔性作业车间调度问题[J]. 工业工程与管理, 2009, 14(2): 59-66.

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

(编辑 李秀敏)

Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem with Low Carbon

ZHANG Guo-hui，DANG Shi-jie

(School of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China)

Low carbon production mode has become the current accepted production mode, it is also the inevitable requirement of sustainable development. Low carbon flexible job shop scheduling model is built to meet the target of minimum makespan and producing carbon emissions. An improved genetic algorithm is proposed to solve the workshop production mode with low carbon requirements, in the process of solving, the initial solution and genetic operator are improved to enhance the algorithm convergence speed. Finally, the experimental results show that the proposed improved genetic algorithm is feasible in solving low carbon production scheduling.

low carbon; genetic algorithm; flexible job shop scheduling; optimization

1001-2265(2016)11-0141-04

10.13462/j.cnki.mmtamt.2016.11.038

2015-12-29；

2016-01-27

国家自然科学基金(61203179); 河南省高校科技创新人才支持计划资助(14HASTIT006); 河南省高等学校青年骨干教师资助计划(2014GGJS-105); 航空科学基金(2014ZG55016);郑州航院研究生教育创新计划基金(2015CX009)；河南省软科学项目(JYB2013034)

张国辉(1980—)，男，河南新乡人，郑州航空工业管理学院副教授，博士，研究方向为工业工程，(E-mail)zgh09@zzia.edu.cn。

TH16;TG506

A