考虑低碳的柔性作业车间分批调度方法

A Low-carbon Flexible Job Shop Scheduling Method with Lot Splitting

摘要

针对中小制造企业普遍采用的柔性作业生产模式，建立了包含碳排量、完工时间和制造成本的多目标分批调度模型，并采用改进NSGA-Ⅱ算法求解。为提高调度灵活性与求解效率，采用4层染色体编码方式。提出最大批次数搜索方法以确定合理的分批范围。采用改进的优先工序交叉（POX）算子以避免工序叠加产生的非法解。引入自适应变异算子，以动态调整变异概率、提高算法的全局搜索能力。公开算例和实际案例验证了算法的有效性和适用性。

Abstract

A multi-objective batch scheduling model integrating carbon emissions， makespan， and manufacturing cost is established to accommodate the flexible production mode commonly adopted by small and medium-sized manufacturing enterprises. An improved non-dominated sorting genetic algorithm （NSGA-Ⅱ） was proposed to solve the model. To enhance scheduling flexibility and solution efficiency， a four-layer chromosome encoding scheme was designed. A maximum batch number search method was developed to determine a reasonable batching range. Furthermore， an improved precedence operation crossover （POX） operator was introduced to prevent illegal solutions arising from operation overlap， while an adaptive mutation operator was employed to dynamically adjust the mutation probability and strengthen global search capability. The effectiveness and applicability of the proposed algorithm were validated through both benchmark instances and real-world industrial case studies.

Graphical abstract

关键词

四层编码 / 最大批次数搜索 / 改进优先工序交叉 / 自适应变异算子 / 低碳车间调度

Key words

four-layer encoding / maximum batch search / improved precedence operation crossover （POX） / adaptive mutation operator / low-carbon workshop scheduling

0 引言

生产调度是制造企业生产管理的核心，它通过对有限资源的合理安排，在给定的时间内以最优的性能完成预定的任务^［1］。近年来，考虑环境因素的柔性作业车间调度问题备受关注。黄海松等^［2］针对碳排放与作业时间耦合的柔性生产，构建了以碳排放和完工时间为目标的调度模型，提出的改进模拟退火算法采用随机位置和轮盘赌编码提高寻优速度。NING等^［3］建立了以最小化最大完工时间、机器总工作量、碳排放为目标的调度模型，采用改良的双链量子遗传算法优化加工流程，实现了车间的低碳调度。杨幸博等^［4］同时考虑最大完工时间、机器的负载及排碳量，建立了相应的多目标调度模型。孟磊磊等^［5］构建了考虑机器的空闲时间和空闲能耗的碳排放模型，并提出了针对机器开关状态的绿色调度模型。

柔性作业车间的工件通常是批量加工的^［6］，分批方式对优化目标的影响不可忽视^［7］，但当前对分批方法的研究较少。SANGROUDI等^［8］提出的自适应布谷鸟优化算法同时优化批量和调度方案，以最小化总生产成本、安装成本和延期成本。LI等^［9］构建了具有4个目标的模型，得到不同分批的混合流水车间调度方案。王全武等^［10］采用可变分批方法及改进的头脑风暴算法优化实际的车间调度。张奎等^［11］提出一种结合FR柔性分批结果与工序调度的双层编码方式来同时优化批次分割和工序调度。

已有的分批调度研究多采用工件分批先于工序调度的方式实现多目标优化。该方式虽在一定程度上减小算法的运行复杂度，但无法根据调度结果优化分批方案，不能得到调度最优解，且同时优化工件分批与工序调度虽能扩大调度结果的可行域，但存在计算量过大和遗传操作过程产生大量非法解的问题。鉴于此，本文在分析机加工车间碳排放来源的基础上，提出一种以碳排量、完工时间、制造成本为优化目标的低碳柔性作业车间分批调度（low-carbon flexible job-shop scheduling problem-lot splitting，LFJSP-LS）模型。针对分批规则缺乏柔性、双层编码无法适应复杂调度需求、算法易陷入局部早熟等问题，提出最大批次数搜索、四层编码方式、改进优先工序交叉（precedence operation crossover， POX），并引入自适应变异算子，为求解以低碳为优化目标的车间分批调度问题提供一种新思路。

1 低碳柔性作业车间的分批调度问题模型

1.1 机加工车间的碳足迹描述

机加工产生碳排放的来源多，不仅包括机床加工的直接排放，还包括生产原材料、能源和辅助物料的间接排放，因此有必要外延机加工过程的碳排放评估边界，如图1所示。

机加工的碳排放可大致分为能源碳排放和物料碳排放。机加工设备与车间辅助设施消耗电能的碳排放为能源碳排放。物料碳排放包括生产工件原材料与辅助物料，以及废弃物安全处理产生的碳排放。

1.2 低碳分批调度问题描述

低碳柔性作业车间分批调度问题可描述为：对于n种工件组成的工件集合J=｛J₁，J₂，…，J_n ｝，第i（i=1，2，…，n）种工件J_i 可分为P_i 个子批（每个子批的工件数量随机分配），且均需完成工序O_i1、O_i2、…、O_ip。在m台机床组成的机床集合｛M₁，M₂，…，M_m ｝中为工件的每道工序选定加工机床。LFJSP-LS的核心目标是通过有效的分批，确定最优的子批数量及每个子批的工件数量，并为每个子批选择合适的机床及加工顺序，实现调度目标的最优。

LFJSP-LS应满足以下假设条件：①所有机器在调度前为关机状态，不产生成本和排碳量；②一台机器在一个时段内只能加工一个子批的工件；③不考虑工件批次之间的运输时间和调整时间；④每个子批工件在加工中的优先级相同；⑤每个子批工件的加工不能中断；⑥工件的子批个数不大于该种工件的总数；⑦每个子批的工件数都必须是自然数，且子批工件数量的总和必须等于该种工件的总数。

1.3 多目标函数

综合考虑机加工过程中的环境因素、生产因素、经济因素，以碳排量、最大完工时间和制造成本为优化目标。

1.3.1 最小化最大完工时间

最大完工时间f₁指所有工件完成加工的最大时间，是最基本的优化指标。

1.3.2 最小化车间碳排放量

（1）机加工设备消耗电能的碳排量。本文分别计算切削和待机的电能消耗（二者之和为总电能消耗），再结合电能排放因子将电能消耗转化为碳排放量。机加工设备切削状态消耗电能的碳排量E_{\mathrm{m}}^{\mathrm{c}} 、待机状态下消耗电能的碳排量E_{\mathrm{m}}^{\mathrm{u}}分别为

E_{\mathrm{m}}^{\mathrm{c}}=F_{\mathrm{e}}{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{P}_k^{\mathrm{c}}{t}_{izjk}^{\mathrm{c}}{X}_{izjk}（1）

E_{\mathrm{m}}^{\mathrm{u}}=F_{\mathrm{e}}{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{P}_k^{\mathrm{u}}{t}_{izjk}^{\mathrm{u}}{X}_{izjk}（2）

式中：F_e为电能排放因子；P_k^{\mathrm{c}}、P_k^{\mathrm{u}}分别为机床的切削功率和待机功率；t_{izjk}^{\mathrm{c}}、t_{izjk}^{\mathrm{u}}分别为机床的切削时间和待机时间；X_{izjk}为0-1变量，加工时取1，反之取0。

（2）车间照明、排风等系统的碳排量。车间照明、排风等系统的碳排量E_L直接受所有工件全部完工时间t的影响：

E_L=F_eP_at（3）

式中：P_a为车间照明、排风等系统的额定功率。

（3）刀具磨损的碳排量。刀具磨损产生的碳排量为

E_{\mathrm{t}\mathrm{w}}=F_{\mathrm{e}}{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}\frac{t_{izjk}^{\mathrm{c}}{L}_k{X}_{izjk}}{t_k}（4）

式中：L_k 、t_k 分别为机床k的刀具研磨一次消耗的电能和研磨后恢复的使用寿命。

（4）废弃物处理的碳排量。主要由切削废屑和切削废液的安全处理产生的碳排量组成。切削废屑的安全处理产生的碳排量为

E_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{d}}=F_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{d}}{\displaystyle \sum _{i=\mathrm{1}}^n}{N}_i\mathrm{\Delta }{m}_i（5）

式中：F_removed为切削废屑处理的排放因子；N_i 、Δm_i 分别为工件J_i 的数量和加工前后的单个工件质量变化量。

切削废液的安全化处理产生的碳排量为

E_{\mathrm{c}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{t}}=F_{\mathrm{c}\mathrm{o}\mathrm{o}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{t}}{q}_V{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{t}_{izjk}^{\mathrm{c}}{X}_{izjk}（6）

式中：F_coolant为切削液处理的排放因子；q_V 为机床单位时间消耗的切削液体积。

则柔性作业车间最小碳排放量为

min f₂=min（E_{\mathrm{m}}^{\mathrm{c}}+E_{\mathrm{m}}^{\mathrm{u}}+E_L+E_tw+E_removed+E_coolant）（7）

1.3.3 最小化制造成本

机加工车间的制造成本包含机器加工成本C_p、原材料成本C_t和切削废弃物的处理成本C_f：

C_{\mathrm{p}}={\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{p}_{izjk}{t}_{izjk}{X}_{izjk}（8）

C_{\mathrm{t}}=p_{\mathrm{t}}V{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{t}_{izjk}^{\mathrm{c}}{X}_{izjk}（9）

C_{\mathrm{f}}=p_{\mathrm{F}}V{\displaystyle \sum _{k=\mathrm{1}}^m}{\displaystyle \sum _{i=\mathrm{1}}^n}{\displaystyle \sum _{z=\mathrm{1}}^{P_i}}{\displaystyle \sum _{j=\mathrm{1}}^{J_i}}{T}_{izjk}^{\mathrm{c}}{X}_{izjk}+p_{\mathrm{E}}{\displaystyle \sum _{i=\mathrm{1}}^n}{N}_i\mathrm{\Delta }{m}_i（10）

式中：p_izjk为工件i的第z批次的第j道工序在机床k的单位时间加工成本；V为机床单位时间内使用的切削液喷射体积；p_t、p_F分别为单位体积切削液的成本和安全化处理成本；p_E为单位质量废屑的安全化处理成本。

则柔性作业车间最小制造成本为

min f₃=min（C_p+C_t+C_ft）（11）

1.4 约束条件

LFJSP-LS模型的约束条件如下：①当前批次工序完成后，后续的子批工件才能开始加工；②每道工序的加工时间都必须不小于该道工序的切削时间；③所有工序的完工时间等于该工序的加工时间与开始时间之和；④任意机床在同一时段只能完成一个子批工件的一道工序；⑤每种工件的子批个数不超过最大批次个数，且同种工件各子批的批量之和必须等于该型号工件的总批量。

2 LFJSP-LS模型求解方法设计

LFJSP-LS模型需要同时优化碳排放量、完工时间、制造成本，不同目标间的相互制约使得很难使所有目标同时达到全局最优。LFJSP-LS具有工序分批、工序选择和机器选择的多重柔性。分批调度过程中，调度方案不仅受机器能力的限制，还受各个批次的数量、工序和机器选择的约束，进一步增加求解的复杂性。

每个分批方案及其工序调度与机器选择都需在庞大的解空间中寻找最优解。随着工件数和工序数的增大，解空间指数级增长，使传统调度算法易陷入局部最优，且难在合理时间内获得有效解。因此，需要设计合理的分批策略以缩小搜索空间，同时改进遗传算法以提高算法的全局搜索能力并避免早熟。生成多组非支配解后，为筛选出最优调度方案，引入层次分析（AHP）方法。通过主客观组合赋权，确定碳排放、完工时间和制造成本在多目标优化中的权重，使筛选出的调度方案更具实用性和适应性。

LFJSP-LS模型的求解步骤如下：首先，在最大批次数搜索方法得到的最大分批次数的约束下，采用一致分批方法随机得到多组分批结果；然后，根据分批结果对染色体进行编码，生成种群的每个个体，并通过改进NSGA-Ⅱ算法求解模型，得到多组最优解；最后，建立接收最优解集的调度池，并采用AHP模型输出最适合生产的调度方案。

2.1 分批方法设计

柔性作业车间分批调度的分批结果和工序调度相互制约，“先确定工件的分批方案、再优化工序调度” 的策略难以在满足多个目标需求的同时实现全局最优，降低了柔性作业车间分批调度的优化能力与实际可行性。因此，本文先采用一致分批方法生成多种分批方案，再对初始工序调度进行编码，生成初始解集，最后通过NSGA-Ⅱ得到最佳分批调度方案，如图2所示。此方法能实现工件分批与工序调度的同步优化，扩大了搜索空间，提高了调度方案的整体优化水平，但随机生成的过多子批会对算法的寻优速度和寻优质量产生不可忽略的影响。假设某个型号工件的个数为20，随机生成的最大批次个数p_max在15到20之间时，很多子批的工件数量为1，这种分批结果绝不可能是最佳的分批调度方案，且随机生成的p_max也无法根据多变的工件信息做出正确的判断。

针对一致分批方法的不足，本文设计了最大批次数搜索方法即在工序调度前分批工件来获取p_max。搜索p_max时只需要搜索出最佳调度的批次数量范围，不需要得出精确的最佳调度批次数量。均等分批、一致分批和可变分批中，均等分批方法直接平分工件，计算复杂度低，能显著缩短批次划分时间，有助于快速输出合理的p_max，避免延误生产。因此，本文在最大批次数的搜索过程中，采用均等分批策略划分工件的初始批次。首先，随机选择一种工件（每种工件有且仅被选一次）。然后，被选择型号工件的批次数加1并重新划分子批，其他种类的工件批次数量不变，得到一个调度结果。若最小化最大完工时间得到优化，则不断增加该种工件的批次数，直到调度目标不再变得更优。输出该种当前的批次数。保持已完成分批的分批个数不变，随机选取其他种类的工件重复上述操作，直到所有种类的工件都完成分批，得到每种工件的分批数。多次重复进行上述步骤，得到多组最优调度的分批个数，从中选取最大的分批数并设定为p_max。最大批次数搜索方法的流程如图3所示。

2.2 求解算法设计

2.2.1 编码设计

根据LFJSP-LS问题的特性，染色体编码采用四层编码的方式，其中，第一层对应工件子批数量（BD），第二层对应某批次下的工件数量（SWQ），第三层确定工件的加工顺序（OS），第四层对应各子批工序的机器选择（MS）。

图4所示为4台机器加工工件J₁～J₃（每种工件的数量都是10且都有2道工序）时的编码，其中，BD层编码的基因位次对应工件型号，基因位上的数字为对应工件的批次数量；SWQ编码基因位上的数字对应每个子批的工件数量；OS编码由两个整数组成，其中，第一个数表示工件型号，第二个数表示批次号；MS编码依次排列不同工件的批次和加工工序，基因位上的数字表示子批次的对应机床号。

四层编码可有效表达批次、批量、工序和机器选择，为后续工件分批和工序调度的同时优化奠定基础，但在优化时增加了复杂度，如SWQ层基因会随BD层基因的变化而变化，OS层基因在交叉时会因工序叠加产生非法解，变异操作更易陷入局部最优等问题。本文通过改进交叉操作、变异操作和解码来解决上述问题。

2.2.2 改进交叉操作

（1）BD层基因采用多点交叉操作。

（2）SWQ层基因采用交叉操作。若在BD层交换父代个体P₁、P₂的第n个基因的数值，则直接须交换SWQ层对应位置的基因，如图5所示。这可避免传统交叉方式下工件的批次数与每批的工件数量不对应产生的非法解。

（3）OS层基因的交叉操作。为防止交叉过程中的工序叠加产生的非法解，在OS层基因采用图6所示的改进POX算子，具体过程如下：①选择的父代个体P₁、P₂；②随机生成一个小于1的实数a，如果a小于交叉概率p_c，则将P₁在OS层基因的第n（初始值为1）个基因复制到相同位置的子代个体S₁中；③n←n+1；④重复步骤②、③，直到n等于P₁中的工序排序基因个数；⑤从父代个体P₂中寻找与子代个体S₁不相同的基因，并按位置顺序补充到S₁空余的基因位，形成完整的基因；⑥重复步骤②～⑤，补充子代个体S₁空余的基因位，生成新的子代个体。

（4）MS层基因采用多点交叉操作。

2.2.3 改进变异操作

为避免传统算法的早熟，本文增加了具有自适应变异的算子：

p_v=p_b2 ^γ

\gamma =\mathrm{e}\mathrm{x}\mathrm{p}(\frac{G}{G_{\mathrm{m}}-G})

式中：p_v为变异率；p_b为初始变异率；G为当前进化代数；G_{\mathrm{m}}为最大进化代数。

自适应变异算子的变异率会随进化代数的增加而逐渐减小，这有助于算法在初期通过较大的变异率扩大搜索范围，在后期通过较小的变异率细化搜索，提高求解精度。

BD层基因的变异会直接影响SWQ层基因的合法性，采用上述类似的变异调整机制保证合法解的产生，且不影响NSGA-Ⅱ算法的随机搜索能力。BD层基因的变异操作具体如下：①选择父代个体P₁；②随机生成一个小于1的实数b，如果b小于p_v，则将P₁的第n（初始值为1）个基因的数值（当前批次数）改为随机生成的正整数p（p与当前批次数不同且p≤p_max），产生新的子代个体S₁；③令n←n+1；④重复步骤②、③，直至遍历BD层所有基因。

2.2.4 解码

为防止产生非法解，先剔除无效基因、再按OS层基因的排列顺序进行解码。通过显隐性基因的判别方法剔除隐性基因：

OS层第j位基因pList［j］为隐性基因时

pList［j］>10i+cList［i］

式中：cList［i］为BD层第i位基因。

基因pList［j］为显性基因时

10i<pList［j］≤10i+cList［i］

解码时，首先根据BD层基因得到工序排序层的显性基因，如BD层第一位基因cList［1］=2，则OS层基因pList［j］必须为11或12。pList［j］=13不在该范围内，可判定为隐性基因，同时定义MS层的对应基因为隐性基因。对BD层的后续所有基因重复上述操作，筛选隐性基因。剔除全部隐性基因后，得到可行染色体。然后对照加工机器矩阵和加工时间矩阵，解码工序调度编码和机器编码，得到调度结果。

2.3 采用融合熵权法的层次分析模型筛选调度最优解

将改进NSGA-Ⅱ算法求解的解集存放到调度池后，采用AHP筛选最优解。AHP按照决策者主观意愿从调度池中选择调度方案缺乏依据，因此本文设计了融合熵权法的层次分析模型来解决多目标决策问题。AHP和熵权法的结合能同时考虑主客观因素，使决策更加全面、客观。本文将多目标LFJSP-LS的决策分为3层，对应的层次分析模型如图7所示。

目标i的组合权重为

w_i=\sqrt[]{{\alpha }_i{\beta }_i}/{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\sqrt[]{{\alpha }_i{\beta }_i}

式中：α_i 为AHP法得到的主观权重；β_i 为熵权法得到的客观权重。

通过组合权重确定目标之间的优先级，使决策更加合理。

3 仿真试验分析

3.1 算法有效性分析

采用4×6（4种工件、6台机床）的柔性车间批量调度问题实例^［12］验证遗传算法改进部分的有效性。实例中，每种工件的数量为8，每种工件都有3道工序且每道工序均可由多台机器完成。工件加工时间如表1所示。

改进NSGA-Ⅱ算法需设定的初始参数有种群规模N、进化次数E_n、交叉概率p_c、初始变异概率p_b。通过田口试验确定算法参数的最优设定值。每个参数设置4个水平，采用L₁₆（4⁴）正交表进行试验，每个参数组合独立运行10次。参数组合及其10次运行的完工时间均值\overline{t}如表2所示，参数水平变化如图8所示。

根据参数水平趋势确定改进NSGA-Ⅱ算法的最优参数组合：种群规模N=100，进化次数E_n=300，交叉概率p_c=0.8，初始变异概率p_b=0.015。

采用实验对比本文算法（方法1）、NSGA-Ⅱ整批调度算法（方法2）、基于双层编码的遗传算法分批调度方法^［11］（方法3）、基于改进遗传算法^［13］（方法4）的性能，对比方法的参数均采用设定的最优初始参数。方法1的子批数量为12，分批方案为［2，2，4，4］，其中，第1、2种工件均划分2批，子批工件数量分别为（6，2）、（1，7）；第3、4种工件均划分4批，子批工件数量分别为（3，1，1，3）、（2，2，1，3）；完工时间为69 min。方法2不分批，完工时间为136 min。方法3的子批数量为12，分批方案为［1，4，4，3］，其中，第1种工件不分批，第2种工件的子批工件数量为（2，4，1，1），第3种工件的子批工件数量为（2，2，1，3），第4种工件的子批工件数量为（3，3，2），完工时间为93 min。方法4的子批数量为12，分批方案为［3，3，3，3］，每种工件的子批工件数量均为（3，3，2），完工时间为71 min。

从完工时间上看，方法1相较方法2缩短49.3%，较方法3缩短25.8%，与方法4差距不大，但方法1迭代30次就已收敛，而文方法4在迭代76次后才收敛，这显示出方法1具有良好的收敛性。

3.2 案例分析

以某机加工车间为研究对象进行仿真，通过本文算法与常用算法的对比来验证实际性。8种工件J1～J8的工序均为平面钻中心孔（工序1）、车外圆（工序2）、粗磨（工序3）、搓丝（工序4）、滚齿（工序5）、研磨中心孔（工序6）和精磨（工序7），加工在6台机床上完成。工件的切削时间t₁、加工时间t₂、机器切削功率P（请扫码篇首处OSID二维码获取），其中，“-”表示机床不完成工序。机床的加工成本见表3，碳排放因子见表4，其他相关参数如表5所示。

将实际的加工数据和参数输入PyCharm程序，并采用本文算法、多目标粒子群优化（particle swarm optimization，PSO）算法^［14］和NSGA-Ⅱ整批调度算法进行仿真，得到各算法的完工时间、碳排量和制造成本的Pareto图（图9）。由图9可知，本文算法得到的Pareto解多样且分布均匀，表明本文算法具有良好的多样性。本文算法求解的Pareto非支配解最多，且多目标PSO算法的非支配解均被本文算法的非支配解支配，这表明本文算法在求解该问题时具有性能优势。

分析本文算法所求的Pareto解集（请扫文前的OSID二维码获取）可知，不同解在各目标下的优化效果不同，如解16（总批次17，完工时间8361 s，碳排量57.65 kg，制造成本1971.88元）与解47（总批次16，完工时间6331 s，碳排量64.32 kg，制造成本1943.68元）的加工时间几乎相等，但解16的碳排量更优，解47的制造成本更优。

采用基于融合熵权法的AHP模型筛选47组解，得到最佳调度解（方案24）的综合重要度0.249，对应的分批方案如表6所示，调度甘特图为图10，图中，O_{\mathrm{2,3}}表示工件的第二子批的第三道工序。

按照基于融合熵权法的AHP模型筛选NSGA-Ⅱ整批调度得到的13组解，AHP法得到的主观权重、熵权法得到的客观权重、二者的组合权重分别为0.422、0.379、0.199，对应调度甘特图为图11，综合重要度为0.262。

按照基于融合熵权法的AHP模型筛选多目标PSO算法得到的31组解，最佳调度解的AHP法得到的主观权重、熵权法得到的客观权重、二者的组合权重分别为0.588、0.286、0.126，最佳方案的调度甘特图为图12，分批方案如表7所示，综合重要度为0.274。

上述3种算法筛选出的最佳调度方案性能指标如表8所示。在完工时间方面，本文算法比NSGA-Ⅱ算法缩短22.1%，比多目标PSO算法缩短7.4%。在碳排放量方面，本文算法减少了机器运转和刀具磨损的碳排量，总碳排量比NSGA-Ⅱ算法减少9.6%，比多目标PSO算法减少6.3%。在制造成本方面，3种算法差距不大，但本文算法仍然表现最佳。

4 结语

针对柔性作业车间调度问题，从最小化最大完工时间、最小化碳排放量和最小化制造成本三个方面进行优化调度，建立了考虑低碳的柔性作业车间分批调度模型（LFJSP-LS）。为求解该模型，提出一种改进NSGA-Ⅱ算法，通过四层编码方式、改进交叉调整机制和自适应变异算子，成功解决了分批调度过程中产生大量非法解的问题。企业实例应用结果表明本文算法在完工时间、碳排放量和制造成本的表现更优，验证了算法的有效性和优越性。

实际车间的生产状态并不可能一直稳定，突发情况在机加工车间比较常见，因此需要研究针突发状况（机器故障、插单等）对机加工车间调度的影响，采取有效的调度方案调整保证生产的有序进行是下一步需要深入开展的研究。

参考文献

[1] 赵诗奎， 王林瑞， 石飞. 作业车间调度问题综述［J］. 济南大学学报（自然科学版）， 2016， 30（1）： 74-80.

[2] ZHAO Shikui， WANG Linrui， SHI Fei. A Review of Job Shop Scheduling Problem［J］. Journal of University of Jinan （Science and Technology）， 2016， 30（1）： 74-80.

[3] 黄海松， 刘凯， 初光勇. 改进模拟退火算法在柔性调度中的应用［J］. 组合机床与自动化加工技术， 2018（2）： 148-151.

[4] HUANG Haisong， LIU Kai， CHU Guangyong. Improved Simulated Annealing Algorithm for Low-carbon Flexible Job Shop Scheduling［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2018（2）： 148-151.

[5] NING Tao， HUANG Yiming. Low Carbon Emission Management for Flexible Job Shop Scheduling： a Study Case in China［J］. Journal of Ambient Intelligence and Humanized Computing， 2023， 14（2）： 789-805.

[6] 杨幸博， 罗国富， 宋俊杰， 等. 多目标柔性作业车间低碳调度研究［J］. 轻工学报， 2020， 35（6）： 93-99.

[7] YANG Xingbo， LUO Guofu， SONG Junjie， et al. Research on Low Carbon Scheduling of Multi-objective Flexible Job Shop［J］. Journal of Light Industry， 2020， 35（6）： 93-99.

[8] 孟磊磊， 张超勇， 肖华军， 等. 面向加工时间可控的柔性作业车间节能调度问题建模［J］. 计算机集成制造系统， 2019， 25（5）： 1062-1074.

[9] MENG Leilei， ZHANG Chaoyong， XIAO Huajun， et al. Mathematical Modeling of Energy-efficient Flexible Job Shop Scheduling Problem with Controllable Processing Times［J］. Computer Integrated Manufacturing Systems， 2019， 25（5）： 1062-1074.

[10] 尹家乐. 考虑制造成本的多目标柔性作业车间调度优化研究［D］. 杭州： 中国计量大学， 2021.

[11] YIN Jiale. Research on Multi-objective Flexible Job-shop Scheduling Optimization Considering Manufacturing Cost［D］. Hangzhou： China University of Metrology， 2021.

[12] HENNING G P， CERDÁ J. A Knowledge-based Approach to Production Scheduling for Batch Processes［J］. Computers & Chemical Engineering， 1996， 20： S1295-S1300.

[13] SANGROUDI H A， RANJBAR-BOURANI M. Solving a Flexible Job Shop Lot Sizing Problem with Shared Operations Using a Self-adaptive COA［J］. International Journal of Production Research， 2021， 59（2）： 483-515.

[14] LI Junqing， TAO Xinrui， JIA Baoxian， et al. Efficient Multi-objective Algorithm for the Lot-streaming Hybrid Flowshop with Variable Sub-lots［J］. Swarm and Evolutionary Computation， 2020， 52： 100600.

[15] 王全武， 徐震浩， 顾幸生. 基于头脑风暴算法的多处理机组合生产批量调度问题［J］. 华东理工大学学报（自然科学版）， 2022， 48（5）： 685-695.

[16] WANG Quanwu， XU Zhenhao， GU Xingsheng. Multi-processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm［J］. Journal of East China University of Science and Technology， 2022， 48（5）： 685-695.

[17] 张奎， 朱斌， 郭岳， 等. 基于双层编码的柔性作业车间分批调度研究［J］. 组合机床与自动化加工技术， 2020（9）： 167-170.

[18] ZHANG Kui， ZHU Bin， GUO Yue， et al. Research on Flexible Job Shop Batch Scheduling Based on Bi-level Coding［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2020（9）： 167-170.

[19] 王万良， 范丽霞， 徐新黎， 等. 多目标差分进化算法求解柔性作业车间批量调度问题［J］. 计算机集成制造系统， 2013， 19（10）： 2481-2492.

[20] WANG Wanliang， FAN Lixia， XU Xinli， et al. Multi-objective Differential Evolution Algorithm for Flexible Job-shop Batch Scheduling Problem［J］. Computer Integrated Manufacturing Systems， 2013， 19（10）： 2481-2492.

[21] 吴亮， 周学良， 冷杰武， 等. 基于改进遗传算法的柔性制造车间等量分批调度问题［J］. 湖北汽车工业学院学报， 2022， 36（4）： 61-67.

[22] WU Liang， ZHOU Xueliang， LENG Jiewu， et al. Equivalent Batch Scheduling Problem in Flexible Manufacturing Shop Based on Improved Genetic Algorithm［J］. Journal of Hubei University of Automotive Technology， 2022， 36（4）： 61-67.

[23] 赵文强. 基于工艺路线的作业车间节能分批调度研究［D］. 西安： 西安工程大学， 2019.

[24] ZHAO Wenqiang. Research on Energy-saving Batch Scheduling of Job Shop Based on Process Route［D］. Xi'an： Xi'an Polytechnic University， 2019.

基金资助

国家自然科学基金(52175257)

国家重点研发计划(2021 YFC3340400)

浙江省2021年度重点研发计划(2021C01053)