面向绿色制造的柔性作业车间调度优化

臧维娜， 高国生

（石家庄铁道大学 机械工程学院，河北 石家庄 050043）

0 引言

绿色制造是一个综合考虑环境影响和资源消耗的现代制造模式，旨在减少制造业对环境的负面影响，提高其资源利用率［1］。近些年来，随着科技发展，制造业生产过程也发生了明显变化，最主要的特征即为生产规模大型化与生产过程连续化。在实施绿色制造的过程中，车间是最基本的生产单元，车间调度可以利用现有的资源（加工能力），满足被加工任务所需的各种约束（加工次序、所需机器等），使所有的任务能尽量按时完成（性能指标最小）［2］。柔性作业车间调度问题（Flexible Job－shop Scheduling Problem，FJSP）是生产系统中的核心问题之一，是对经典作业调度的一种扩展，在实际生产中，它允许每个工序在多个备选机器上加工，提高了加工灵活性，也增加了问题的复杂度，是更为复杂的NP－Hard问题。从实际生产角度来说，好的调度方案更符合生产需求，更适合生产的动态特性，从绿色制造角度来说，好的调度方案能减少资源消耗和环境污染，因此面向绿色制造的柔性车间调度研究具有重要的理论和实际应用价值。

目前，求解FJSP的常用算法有粒子群算法、蚁群算法、禁忌搜索和遗传算法等［3－7］。遗传算法具有鲁棒性好、计算性能稳定、通用性强等特点，在求解组合优化领域的非确定多项式问题上显示出较好的搜索能力，在车间调度问题中得到了很好的应用［8］。然而普通遗传算法存在消耗时间长、局部搜索能力较差且易早熟收敛等不足，为了克服上述缺陷，国内外学者们分别从算法编码、种群初始化、遗传操作、算法逻辑设计以及与其他算法融合等方面对算法进行改进。本文主要从种群初始化和遗传操作上对算法进行改进，并对优化目标进行了改善，弥补了遗传算法的不足，更适应面向绿色制造的柔性车间调度优化。

1 面向绿色制造的柔性作业车间调度模型

1.1 问题描述

面向绿色制造的柔性作业车间调度研究n个工件｛J1，J2，…，Jn｝在m 台机床｛W1，W2，…，Wm｝上加工，每个工件有一道或者多道工序，工件的工序顺序确定，每道工序的加工机床有多台可供选择，工序的加工时间、能源消耗以及对环境的污染程度都会因加工机床的不同而不同，调度的最终目标是给每道工序选择最优加工机床，确定每台机床的工序加工顺序和时间，使所期望的加工性能指标最优。此外，在加工过程中还需满足以下约束条件：

（1）同一台机床，同一个时间，只能加工一个工件；

（2）同一个工件，同一个时刻，只能在一台机床上加工；

（3）每一个工序一旦开始加工便不能中断；

（4）工件间无优先级限制，所有工件的加工准备时间为零；

（5）不同工件的工序间无先后约束，同一工件的工序间有先后约束。

1.2 调度目标

绿色制造需要综合考虑制造过程中的时间、质量、成本、资源消耗以及环境污染5个方面的影响，因此面向绿色制造的作业车间调度理应以这5项最优为目标。但在实际生产中，由于调度问题的复杂性，再加上5大目标间的相互联系，很难达到全面的最优，在此假设可选加工机床均能保证工件的加工质量，且忽略加工过程中所产生的生产成本差异，以时间、资源消耗和环境污染为调度目标。

1.2.1 时间t

多数文献都将最大完工时间最小作为作业车间调度的优化目标，但是在实际生产中，加工时间并非越短越好，最理想的状态应该是工件在其交货期内完成，提前完成会给企业增加仓储费用，延后完成会降低客户满意度，并且受到合同惩罚，因此调度的目标应是尽量使工件在交货期所在的时间段内完工。

1.2.2 资源消耗和环境影响

制造过程是将原材料加工成产品的过程，在这个过程中，必会造成资源价值和属性的改变，也就是说加工过程中必然会产生资源消耗和环境影响。文献［9］已用实例证明，同一工件会因加工机床不同而消耗不同资源。受调度方案所影响的资源消耗主要表现在电能消耗上，其他的物料消耗，包括原材料、切削液等主要在前期加工设计阶段决定，因此将电能消耗量定义为资源属性值；生产过程中会产生废气、废液、噪声等对环境造成影响，加工安全性也会对劳动者的身心健康造成危害，因此将这几方面的综合影响量定义为环境属性值。综上可知，面向绿色制造的作业车间调度问题应将这两方面的影响考虑其中，优化目标是将这两方面的影响尽量降到最低，两方面的数值进行量纲统一后，将其和称为可持续性指标值，则优化目标就变为可持续性指标值最高。

根据上述内容，为该调度模型定义变量如下：i代表工件序号，i＝1，2，…，n；k代表机床序号，k＝1，2，…，m；j代表工件的工序号；第i个工件的第j道工序可选机床集合为Mij，集合中元素的个数为mij；hi表示工件i的工序总数；tijk表示工件i的第j道工序在机床k上的加工时间，Ti表示加工完工件i的时间，ri，ei分别表示加工工件i的资源属性值和环境属性值（均为量纲统一后的数值），wr，we为其权重，REi表示可持续性指标值（如式（1）所示）；stij，enij分别表示工序i的第j道工序的起始和结束时间；［Si，Li］表示工件i的交货期，si，li分别为提前完工和延后完工的单位时间惩罚系数。

非交货期间完工都会对企业产生一定损失，因此需要进行惩罚，时间惩罚值用Pi表示（如式（2）所示），因此，将作业车间调度在时间方面的调度目标定为时间惩罚值最小，在资源消耗和环境影响方面的调度目标定为可持续性指标值最高，则总目标F如式（3）所示，其中P′i为量纲统一后的值，Wp、Wre为两分目标权重。

2 改进遗传算法求解面向绿色制造的柔性作业车间调度

2.1 基因编码

面向绿色制造的柔性作业车间调度问题，遗传算法的编码应由两部分组成，一部分是基于机床分配的编码，一部分是基于工序的编码。对于基于机床分配的编码，染色体的基因数等于所有工件工序的总数，基因用机床编号表示，如染色体［3 5 1 4 3 2 6 1 2］，第一数字3表示为第一道工序选择W3机床进行加工。对于基于工序的编码，染色体的基因数等于所有工件工序的总数，工序用工件序号表示，序号出现的次数即为该工件的工序号，如染色体［1 2 1 3 2 3 3 2 1］，数字1表示工件J1，3个数字1表示工件J1的3个工序。

2.2 种群初始化

在用遗传算法求解调度问题时，好的初始解可以加快算法的求解速度和质量，目前多数文献采用随机的初始化方法，初始解质量低，导致迭代次数增加，运算效率降低。Kacem等［10］提出了一种基于短用时策略与设备均衡策略的种群初始化方法，使种群质量大幅度提高。但是该方法强烈依赖于工件的排序顺序，并且这种单一的初始化方法也使得初始结果有一定的局限性，并不能保证算法的运算质量。Zhang等［11－12］提出了一种综合机器全局搜索（Global search，GS）、局部搜索（Local search，LS）和随机选择这3种方式的初始化方法，3种方式产生的初始解按一定比例共同组成初始种群，进一步提高了初始种群质量。本文将以此方法为基础，对此进行改进，以更适应于面向绿色制造的柔性车间调度问题。

原始方法均以机床负荷和加工时间为性能指标进行初始化，由于所期望的完工时间是在交货期内，完工时间过短和过长都会对企业造成损失，再考虑到一个工件的完工时间受到自身和其他工件的调度安排影响，直接将其限定在一个区间范围内是极其复杂的，所以将初始解的性能指标定为可持续性指标值和机床负荷这两方面上，两个指标随机参与初始化过程。

以某工程机械零部件制造企业3个工件、5台机床的作业调度进行研究，加工数据如表1所示。

表1 加工数据

用nijk，cijk，sijk分别表示噪声、拆卸回收性、安全性（均为量纲统一后的数值），wn，wc，ws分别表示其权重，则环境属性值如式（4）所示。

各权重值应根据企业实际加工标准来制定，在此将wn，wc，ws初步设为20%，50%，30%，式（1）中wr，we分别设为60%，40%。经过计算，可以得到表1中各加工方法的可持续性指标值，结果如表2所示。

表2 可持续性指标值

GS以深度优先进行搜索，两性能指标随机选择，可以选择可持续性指标值最大的工序所对应的机床，或者选择机床负荷最小的工序所对应的机床，选择完毕后更新未分配机床的其他工序所对应的该机床的加工负荷，如此循环，当所有工件工序的加工机床选择完毕后，将各机床加工负荷归零，进行下一组循环。由于绿色性优的机床可持续性指标值普遍偏高，每次以可持续性作为性能指标进行机床选择时，偏向于选择此种机床，易造成这些机床的加工负荷大幅度偏高，因此应避开选择加工负荷最高的工序所对应的机床。

具体操作过程如表3、表4所示，该示例以两个指标轮换着进行机床选择，先以可持续性为指标为工序选择机床，然后更新机床负荷（括号内数字），再以加工负荷为指标选择机床，并更新机床负荷，如此循环直到选择完毕。如表3所示，为第二个工件的第二道工序选择完机床后，更新机床负荷，下一步该以可持续性为指标进行机床选择，从表中可以看出，第3个工件的第三道工序选择三号机床时指标值最高，但选择后会造成机床负荷最高，因此应从其他可持续性指标值中进行选择，最终结果如表4所示。

表3 GS－1

表4 GS－2

LS以广度优先进行搜索，两性能指标随机选择，从第一个工件开始，一个工序选择机床完毕后只更新本工件的其他工序所对应的该机床的加工负荷，此工件所有工序选择机床完毕后，机床加工负荷归零，开始对下一个工件工序进行机床选择，如此循环，当所有工件工序的加工机床选择完毕后，将机床负荷归零，进行下一组循环，具体操作过程如表5所示。

表5 LS

初始化种群时仍需保留一定比例的随机搜索个体，目的是为了扩展搜索宽度，保持遗传基因的多样性。本文初始种群的60%采用全局搜索，30%采用局部搜索，10%采用随机产生的方法，多次试验测试比较结果表明，该比例组合所生成的初始解质量较优［13］。

该方法是按指标值的优劣作为选择顺序先后的标准，不依赖于工件的排序顺序，3种方法产生的种群共同组成初始种群，可有效保证种群质量，提高算法效率。

2.3 适应度函数与选择操作

在遗传算法中，适应度的高低是评价种群中染色体优劣的标准，适应度越高，则说明个体越优异，本文以式（3）作为适应度函数值来进行优化选择。选择操作是从种群中选择出优良个体，淘汰劣质个体，在此采用精英策略和GOLDBERG等［14］提出的锦标赛法进行选择，精英策略就是将种群中适应度高的个体直接复制到下一代中。锦标赛法的目标值就是适应值，相对于多数文献所应用的轮赌法来讲，免去了中间的转换，其具体操作步骤是从种群中随机选出3个个体，适应度值最高的复制到交叉池中，如此循环，直到满足所需数量。

2.4 交叉和变异

交叉操作是将两父代染色体中的基因进行交叉，以产生新的染色体，期望将优良的基因进行组合。将两种染色体分别进行交叉操作，基于机床分配的染色体采用两点交叉法，基于工序编码的染色体采用张超勇［15］提出的POX交叉算子。

基于机床分配的染色体的交叉操作流程为：选择两个父代染色体，再随机选择两个交叉点，将两父代染色体两交叉点内的基因进行互换，形成新的子代染色体。

基于工序编码的染色体的交叉操作流程为：将工件随机分为两个集合A1、A2，将父代染色体1／父代染色体2包含在A1中的工件复制给子代染色体1／子代染色体2，保留工件所在位置，将父代染色体2／父代染色体1包含在A2中的工件复制给子代染色体1／子代染色体2，保留工件顺序。具体实现过程如图1所示，其中A1＝｛J1，J3｝，A2＝｛J2，J4｝。

图1 POX法交叉示例

变异操作是为了保持种群多样性，避免早熟现象的产生，同时也可改善算法局部搜索能力。对机床染色体进行变异时，在染色体中随意选择一个基因，为该工序在其可选加工机床集中随意另选择一台机床，用其编号替代当前基因；对工序染色体进行变异时，在染色体中随意选择两个基因，交换其位置。以上这两种方式的变异操作均能保证新生解的可行性。

3 实例验证与结果分析

为了验证该算法的可行性与有效性，采用表1中的数据对3个工件5台机床的加工问题进行调度。利用MATLAB编写程序代码，令种群规模为40，迭代次数为30，交叉概率为0.7，变异概率为0.15。将提前完工和延后完工的单位时间惩罚系数均设为0.5，3个工件的交货期分别为：［19，20］、［15，16］、［19，20］，Wp、Wre分别设为0.7和0.3。为了更好的对算法进行验证，将该方法中初始种群的生成方法改为全部随机生成来进行比对，然后再去掉精英策略选择法进行对比，3种方法的运算结果如图2和表6所示，进行比对的数值均为每次迭代后种群中的适应度最高值。

表6 3种算法的运算结果

从运算结果可以看出，3种方法所得出的最优值相同，最优调度方案如图3所示，图中交叉线覆盖的区域为机器空余时间，3个工件的完工时间分别为：19.5、16、19.5。改进的遗传算法产生的初始种群中的最优值和最终结果的最优值已非常接近，该方法迭代7次后便出现最优解。初始种群若采用随机方法生成，种群质量差，迭代次数增加，精英策略可有效保留种群中的优良个体，加快收敛效率。

图2 各算法收敛比较图

图3 最优调度方案

4 结语

针对面向绿色制造的柔性作业车间调度问题，提出了一种改进的遗传算法来解决此问题。设定了新的调度目标，综合考虑了完工时间、环境影响、能量消耗对调度问题的影响，更加符合现代企业的生产需求。采用两种编码方式来描述调度方案，对初始种群做了调整，使种群个体更为优质，加快了算法的收敛效率。精英策略和锦标赛法的联合选择机制，保障了下一代个体的质量。两种编码采用不同方法进行交叉和变异，保证了新生解的可行性，最后通过实例验证了该算法的可行性和有效性。但是，本文所需解决的调度问题相对简单，迭代较小次数便能得出最优解，后期还需对复杂问题进行试验，测试该算法的计算效率、准确性等问题。

［1］刘飞，曹华军，张华.绿色制造的理论与技术［M］.北京：科学出版社，2005.

［2］陈伟.基于遗传算法的绿色制造车间调度方法研究［D］.武汉：武汉科技大学，2005.

［3］李丹，高立群，马佳，等.基于动态双种群粒子群算法的柔性工作车间调度［J］.东北大学学报：自然科学版，2007，28（9）：1238－1242.

［4］GAO J，SUN L Y，GEN M.A hybrid genetic and variable neighborhood descent for flexible job shop scheduling prob－lems［J］.Computers ＆ Operations Research，2008，35：2892－2907.

［5］SAISI－MEHRABAD M，FATTAHI P.Flexible job shop scheduling by tabu search algorithms［J］.The International Journal of Advance Manufacturing Technology，2007，32：563－570.

［6］张维存，郑丕谔，吴晓丹.蚁群遗传算法求解能力约束的柔性作业车间调度问题［J］.计算机集成制造系统，2007，13（2）：

333－337.

［7］王云，冯毅雄，谭建荣，等.柔性作业车间分批调度多目标优化方法［J］.浙江大学学报：工学版，2011，45（4）：719－726.

［8］赵诗奎，方水良，顾新建.柔性车间调度的新型初始机制遗传算法［J］.浙江大学学报：工学版，2013，47（6）：1022－1030.

［9］何彦，刘飞，曹华军，等.面向绿色制造的机械加工系统任务优化调度模型［J］.机械工程学报，2007，43（4）：27－33.

［10］KACEM I，HAMMADI S，BORNE P.Approach by localization and multi－objective evolutionary optimization for flexible job－shop scheduling problems［J］.IEEE Transactions on Systems，Man and Cybernetics，Part C：Applications and Reviews，2002，32（1）：1－13.

［11］ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job－shop scheduling problem ［J］.Expert Systems with Applications，2011，38（4）：3563－3573.

［12］张国辉，高亮，李培根，等.改进遗传算法求解柔性作业车间调度问题［J］.机械工程学报，2009，45（7）：145－151.

［13］蒋良宵.基于改进遗传算法的柔性作业车间调度问题［J］.现代计算机，2014，2：29－33.

［14］GOLDBERG D E，DEB K.A comparative analysis of selection schemes used in genetic algorithms［C］／／RAWLINS G，ed.Foundations of Genetic Algorithms.San Mateo：Morgan Kaufmann Publishers，1991：69－93.

［15］张超勇，饶运清，刘向军，等.基于POX交叉的遗传算法求解Job－Shop调度问题［J］.中国机械工程，2004，15（23）：2149－2153.