考虑客户满意度的模糊柔性作业车间调度优化方法

Fuzzy Flexible Job-shop Scheduling Optimization Approach Considering Customer Satisfaction

摘要

针对离散制造企业单件小批量、高定制化导致完工时间不确定、客户满意度差的问题，建立了以完工时间、平均及最小客户满意度为目标的模糊柔性作业车间调度模型，提出一种改进多目标进化算法对模型进行求解，引入基于种群分布的自适应交叉变异策略平衡全局及局部搜索。设计了基于满意度结构的知识驱动邻域搜索策略，通过调整关键路径的关键块与非关键块工序，以缩短完工时间、提高客户满意度。基于多组基准算例的对比分析结果验证了所提模型及算法的有效性。

Abstract

To address uncertain completion times and low customer satisfaction in discrete manufacturing with single-piece， small-batch， and highly customized production， this paper establishes a fuzzy flexible job-shop scheduling model that minimizes makespan， maximizes average customer satisfaction， and maximizes the minimum customer satisfaction. An improved multi-objective evolutionary algorithm is proposed， which incorporates an adaptive crossover-mutation strategy based on population distribution to balance global and local search， and a knowledge-driven neighborhood search strategy that exploits the structure of customer satisfaction. By adjusting critical and non-critical blocks on the critical path， the algorithm reduces makespan and enhances customer satisfaction. Comparative results on multiple benchmark instances confirm the effectiveness of the proposed model and algorithm.

Graphical abstract

关键词

模糊柔性作业车间调度 / 客户满意度 / 多目标优化 / 知识驱动邻域搜索

Key words

fuzzy flexible job-shop scheduling problem / customer satisfaction index / multi-objective optimization / knowledge-driven neighborhood search

0 引言

当前，以航空航天、汽车为代表的离散制造企业已从“以产品为中心”转向“以客户为中心”，客户满意度已成为其可持续发展的基石。离散制造企业车间生产高度柔性化及定制化，产品品种多、批量小、工艺过程复杂导致车间生产效率低、工件加工时间及完工时间难以准确估计^［1］。此外，工件完工时间与客户满意度之间存在协同优化冲突，而交货窗口提前或延后都会降低客户满意度^［2］，因此如何平衡生产效率与客户满意度已成为企业发展面临的核心问题。高效的车间调度是压缩制造提前期、确保承诺交货期的关键。因此，开展考虑客户满意度的模糊柔性作业车间调度优化方法研究已势在必行。

模糊柔性作业车间调度问题（fuzzy flexible job-shop scheduling problem， FFJSP）已被证明是NP-hard问题^［3］。目前，学者针对不同场景的FFJSP，在模型建立、算法求解领域开展了大量研究。模型建立领域，JIMÉNEZ TOVAR等^［4］采用线性加权和协同优化了完工时间与平均流程时间，李瑞等^［5］构建了以完工时间与机器负载为优化目标的FFJSP模型，LIU等^［6］构建了考虑总负载及最大机器负载的多目标FFJSP模型。在此基础上，DENG等^［7］引入能耗指标，将退化效应转化为模糊数内部的线性平移。LI等^［8］为更好捕捉复杂制造过程中加工时间的不确定性，引入区间二型模糊集来表征加工时间，建立了集成开关机策略的节能调度混合整数线性规划（mixed-integer linear programming， MILP）模型。CHEN等^［9］研究了设备加工速度可变的FFJSP，将加工时间表征为速度选择的动态函数。SUN等^［10］针对集成批量分割的FFJSP，采用具有非线性隶属度的L-R模糊数表征加工及装配时间。SOOFI等^［11］研究了考虑机器故障的双资源FFJSP，以所有故障场景的平均完工时间及最坏情况的完工时间加权和为混合目标函数，提出一种鲁棒模糊随机规划模型。WU等^［12］在生产调度的基础上引入AGV运输，以模糊数表征运输时间，构建了集成加工及运输的调度模型。ZHANG等^［13］采用对称三元随机数表征加工时间，设计了一种集成调度方案生成与瓶颈识别的分层模型，依据多场景性能指标动态识别瓶颈。上述研究多聚焦于生产系统的效率与资源利用，鲜有揭示调度方案与客户满意度间的制约机理。

为准确量化客户满意度与交付期望，MA等^［14］、YANG等^［15］将完工时间与交货期间的偏差转化为满意度损失以提高客户满意度。在此基础上，CHEN等^［2］引入设备维护约束，以区间数表征维护周期，构建了以完工时间、碳排放量、生产成本及客户满意度为目标的FFJSP模型。WANG等^［16］考虑作业插入，建立了协同优化完工时间、客户满意度及总能耗的FFJSP模型。ZHU等^［17］设计了一种基于完工时间相对交货期的延迟指数来表征客户交付期望，同时优化了完工时间、工作量及延迟指数。

求解算法方面，分支定界法、整数规划、约束规划等传统精确算法在求解大规模问题时难以在合理时间内求得满意可行解^［18］，以进化算法、群智能优化算法为代表的元启发式算法已成为求解FFJSP模型的主流方法^［9］。针对不同FFJSP的特点，学者们提出多种改进策略。唐红涛等^［19］采用非线性动态权重更新机制平衡全局与局部搜索。LI等^［20］提出了一种改进免疫算法，采用双向量局部搜索策略来提高搜索效率，并引入基于模拟退火算法的概率性接受劣解策略来避免早熟。PAN等^［21］提出了一种带有反馈机制的双种群进化算法，并基于历史种群信息动态评估个体质量并调整种群规模，以提升解集质量。LI等^［22］提出了一种基于成功/失败记忆的局部搜索策略，依据历史成功概率自主学习有效局部搜索操作，显著提高了搜索效率。GNANAVELBABU等^［23］将蒙特卡洛模拟融入多目标改进回溯搜索算法，增强不确定性的处理能力。FANG等^［24］设计了一种基于混沌与贪婪算法的混合初始化方法，提高了初始解质量。ZHANG等^［25］设计了一种基于分解的多目标进化算法，通过基于惩罚的边界交集分层评估与聚类自适应分解策略动态调整解集的选择压力及权重向量，增强Pareto前沿的逼近能力。

针对考虑客户满意度的FFJSP，目前存在满意度目标维度单一与满意度驱动的优化算子缺失的问题，难以有效提升客户满意度。基于此，本文针对考虑客户满意度的FFJSP，建立以完工时间、平均客户满意度及最小客户满意度为优化目标的数学模型，提出改进多目标进化算法（improved multi-objective evolutionary algorithm，IMOEA）进行求解，采用自适应交叉与变异概率以平衡算法前后期的搜索能力；设计知识驱动的邻域搜索策略，引入N8与客户满意度（CSI）邻域结构进行局部搜索，进一步提高客户满意度、缩短工件完工时间。最后，通过田口试验选取算法最优参数组合，并基于多组基准算例验证了算法的有效性。

1 问题描述及数学模型

1.1 问题描述

本文所研究的考虑客户满意度的FFJSP可描述如下：有n个工件需在m台机器上加工，机器M_k （k=1，2，…，m）可加工多道工序，其中，工件J_i （i=1，2，…，n）有N_i 道工序。工序的顺序是预先给定的，即后道工序必须在其前道工序完成后才能开始加工。工序加工时间以三角模糊数{\tilde{T}}_{\mathrm{1}}=(t_{\mathrm{1}},t_{\mathrm{2}},t_{\mathrm{3}})表示，其中，t₁、t₂、t₃分别为最乐观值即最优加工时间、最可能值即最可能加工时间、最悲观值即最差加工时间。工件交货期以梯形模糊数{\tilde{D}}_{\mathrm{1}}=(d_{\mathrm{1}},d_{\mathrm{2}},d_{\mathrm{3}},d_{\mathrm{4}})表示，其中，d₁、d₂、d₃、d₄分别为最早交货期、最理想交货期下限、最理想交货期上限及最晚交货期。图1给出的考虑客户满意度的FFJSP示例包含4个工件和3台机器。

考虑客户满意度的FFJSP基于如下假设：①初始调度时刻，所有机器均可用，所有工件均可被加工；②各工件相互独立，同一个工件的工序有先后关系；③机器开始工作后一直处于工作状态，直到完成分配的所有作业；④每道工序由不同机器完成的模糊加工时间不同且已知；⑤不考虑机器损坏、订单插入等特殊情况。

1.2 模型建立

模型中相关参数及含义如表1所示。

1.2.1 优化目标

最小化完工时间即所有工件的最大完工时间：

f_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}{\tilde{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}（1）

最大化平均客户满意度即指完工时间与交货期之间的符合程度：

f_{\mathrm{2}}=\mathrm{m}\mathrm{a}\mathrm{x}(\frac{\mathrm{1}}{n}{\displaystyle \sum _{i=\mathrm{1}}^n}{A}_i)（2）

A_i=\frac{area({\tilde{C}}_i\bigcap {\tilde{D}}_i)}{area{\tilde{C}}_i}（3）

式中：area{\tilde{C}}_i为模糊数{\tilde{C}}_i隶属度函数曲线下的面积；area({\tilde{C}}_i\bigcap {\tilde{D}}_i)为{\tilde{C}}_i与{\tilde{D}}_i交集的隶属度函数曲线下的面积。

最大化最小客户满意度：

f_{\mathrm{3}}=\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{m}\mathrm{i}\mathrm{n}(A_{\mathrm{1}},A_{\mathrm{2}},\cdots ,A_n)（4）

1.2.2 约束条件

{\tilde{s}}_{ij}+{\tilde{t}}_{ijk}={\tilde{f}}_{ij}\begin{array}{c}\end{array}\forall i,j,k（5）

{\tilde{f}}_{ij}\le {\tilde{s}}_{i(j+\mathrm{1})}\begin{array}{c}\end{array}\forall i,j,k（6）

{\tilde{f}}_{i(N_i)}\le {\tilde{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}\begin{array}{c}\end{array}\forall i,j,k（7）

{\tilde{s}}_{ij}+{\tilde{t}}_{ijk}\le {\tilde{s}}_{ph}+\tilde{M}(\mathrm{1}-Y_{ijphk})\begin{array}{c}\end{array}\forall i,j,k,p,h（8）

{\displaystyle \sum _{k=\mathrm{1}}^m}{x}_{ijk}=\mathrm{1}\begin{array}{c}\end{array}\forall i,j,k（9）

{\tilde{s}}_{ij},t_{ijk}\ge \mathrm{0}\begin{array}{c}\end{array}\forall i,j,k（10）

式（5）、式（6）约束各工序的先后顺序；式（7）表示每工件的完工时间必须小于总完工时间；式（8）表示一台机器一次只能完成一道工序；式（9）表示某一时刻的一道工序仅能在一台机器上完成。

1.3 三角模糊数的运算

本文所建FFJSP数学模型中的工序完成时间均以三角模糊数表示。求解前必须明确三角模糊数的运算规则即加法、比较和取大。对于三角模糊数{\tilde{\mathit{T}}}_{\mathrm{1}}=(t_{\mathrm{1}},t_{\mathrm{2}},t_{\mathrm{3}})与{\tilde{\mathit{T}}}_{\mathrm{2}}=(t_{{}_{\mathrm{1}}}^{\mathrm{*}},t_{{}_{\mathrm{2}}}^{\mathrm{*}},t_{{}_{\mathrm{3}}}^{\mathrm{*}})，加法运算规则为

{\tilde{\mathit{T}}}_{\mathrm{1}}+{\tilde{\mathit{T}}}_{\mathrm{2}}=(t_{\mathrm{1}}+t_{\mathrm{1}}^{\mathrm{*}},t_{\mathrm{2}}+t_{\mathrm{2}}^{\mathrm{*}},t_{\mathrm{3}}+t_{\mathrm{3}}^{\mathrm{*}})（11）

比较准则如下：

准则1 对于C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{1}})=(t_{\mathrm{1}}+\mathrm{2}{t}_{\mathrm{2}}+t_{\mathrm{3}})/\mathrm{4}，C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{2}})=(t_{\mathrm{1}}^{\mathrm{*}}+\mathrm{2}{t}_{\mathrm{2}}^{\mathrm{*}}+t_{\mathrm{3}}^{\mathrm{*}})/\mathrm{4}，若C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{1}})>C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{2}})，则{\tilde{\mathit{T}}}_{\mathrm{1}}>{\tilde{\mathit{T}}}_{\mathrm{2}}，反之，则。

准则2 对于C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{1}})=t_{\mathrm{2}},C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{2}})=t_{\mathrm{2}}^{\mathrm{*}}，C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{1}})=C_{\mathrm{1}}({\tilde{\mathit{T}}}_{\mathrm{2}})时，若C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{1}})>C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{2}})，则{\tilde{\mathit{T}}}_{\mathrm{1}}>{\tilde{\mathit{T}}}_{\mathrm{2}}，反之，则。

准则3 对于C_{\mathrm{3}}({\tilde{\mathit{T}}}_{\mathrm{1}})=t_{\mathrm{3}}-t_{\mathrm{1}},C_{\mathrm{3}}({\tilde{\mathit{T}}}_{\mathrm{2}})=t_{{}_{\mathrm{3}}}^{\mathrm{*}}-t_{{}_{\mathrm{1}}}^{\mathrm{*}}，C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{1}})=C_{\mathrm{2}}({\tilde{\mathit{T}}}_{\mathrm{2}})时，若C_{\mathrm{3}}({\tilde{\mathit{T}}}_{\mathrm{1}})>C_{\mathrm{3}}({\tilde{\mathit{T}}}_{\mathrm{2}})，则{\tilde{\mathit{T}}}_{\mathrm{1}}>{\tilde{\mathit{T}}}_{\mathrm{2}}，反之，则。

模糊数的近似取大规则如下：

{\tilde{\mathit{T}}}_{\mathrm{1}}\vee {\tilde{\mathit{T}}}_{\mathrm{2}}=\left\{\begin{array}{cc}{\tilde{\mathit{T}}}_{\mathrm{1}}& {\tilde{\mathit{T}}}_{\mathrm{1}}>{\tilde{\mathit{T}}}_{\mathrm{2}}\\ {\tilde{\mathit{T}}}_{\mathrm{2}}& \mathrm{其他}\end{array}\right.（12）

2 基于IMOEA的模型求解

2.1 算法设计

相较于传统FJSP，考虑客户满意度的FFJSP具有加工时间不确定、多目标耦合、目标量级差异大等特点，问题复杂度高，以进化算法与群智能优化算法为代表的元启发式算法是主要求解方式。第三代非支配排序遗传算法（NSGA-Ⅲ）基于参考点的选择机制能有效维持目标空间中的解集分布性，并通过归一化处理与参考点设定有效解决不同目标量级差异大的问题，确保所有目标在Pareto前沿进化过程中的收敛性^［26］。基于此，本文提出一种基于参考点的IMOEA对模型进行求解。首先，采用两段式整数编码表征FFJSP的解向量，基于贪婪解码将解向量中的编码值转化为具体的调度方案。然后，针对模型目标量级差异大的问题，引入基于参考点关联的自适应交叉与变异概率，并根据参考点的稀疏度与聚集度动态调整不同个体的交叉与变异概率，平衡算法的全局搜索能力与局部搜索能力。最后，根据问题特征设计基于N8与CSI邻域结构的知识驱动邻域搜索策略，通过有限次调整关键路径上的工序，实现精英个体周围解空间的精细化搜索，进一步缩短完工时间，提高客户满意度。算法总体流程如图2所示。

2.2 初始种群与编码解码

本文所提IMOEA采用随机初始化策略生成种群个体，基于两段式整数编码表征种群个体。每条染色体都由工序排序（OS）、机器选择（MS）两部分组成，其编码长度等于所有工件的工序总和。OS部分的元素值为工件的编号，同一编号在序列中出现的次数对应该工件的工序序号。MS部分的元素值为工件加工的机器编号。图1（甘特图）对应的编码如图3所示，OS部分的4个“4”表示工件4的第1-4道工序；MS部分的第一个“1”表示将工序O₄₁安排到机器M₁上完成。

2.3 自适应交叉与变异

2.3.1 交叉算子

交叉操作中，OS编码采用POX交叉算子，MS编码采用MPX交叉算子。

1）POX交叉算子具体步骤如下：①将所有工件号随机分到非空子集S₁、S₂；②在父代F₁中找到与S₁内的工件号相同的编码，将其复制到子代N₁的相同位置上；③在父代F₂中找到与S₂内的工件号相同的编码，按从左到右的顺序复制到子代N₁中的空余位置；④以同样操作生成子代N₂，具体操作如图4所示。

2）MPX交叉算子具体步骤如下：①生成一个长度为所有工序总和的0-1集合B；②若B集合中的某元素为1，则将父代F₁中对应位置的编码复制到子代N₁中的相同位置；③若B集合中某元素为0，则将父代F₂中对应位置的编码编复制到子代N₁中的相同位置；④以同样操作生成子代N₂，具体操作如图4所示。

2.3.2 变异算子

变异操作中，随机选取OS部分的2个编码并交换编码值；随机选取MS部分的两个工序并从对应候选机器中选择一台机器替代原有机器，如图5所示。

2.3.3 自适应机制

在求解考虑客户满意度的FFJSP时，固定的交叉与变异概率往往难以适应算法在进化过程中的种群变化。进化初期，交叉与变异概率过大可能破坏优质解，过小则会削弱种群的探索能力，使算法过早收敛到次优解。算法后期，种群多样性降低时，过小的变异概率可能会使算法陷入局部最优解。因此，为减小固定参数可能导致的误差，平衡算法的全局及局部搜索能力，采用自适应策略来动态调整交叉与变异概率。该策略根据种群在进化过程中的动态信息调整不同个体的交叉与变异概率，以适应不同进化阶段的需求。第\alpha个个体的交叉概率P_{\mathrm{c}}^{(\alpha )}与变异概率P_{\mathrm{m}}^{(\alpha )}分别为

P_{\mathrm{c}}^{(\alpha )}=\left\{\begin{array}{cc}{P}_{\mathrm{c}a}-\mathrm{0.4}{C}_{\alpha }& C_{\alpha }>\mathrm{0.25}\\ P_{\mathrm{c}i}& \mathrm{其他}\end{array}\right.（13）

C_{\alpha }=C_{i,\mathrm{n}\mathrm{u}\mathrm{m}}/Z

P_{\mathrm{m}}^{(\alpha )}=P_{\mathrm{m}i}+(P_{\mathrm{m}a}-P_{\mathrm{m}i})\frac{D_{\alpha }-D_{\mathrm{m}\mathrm{i}\mathrm{n}}}{D_{\mathrm{m}\mathrm{a}\mathrm{x}}-D_{\mathrm{m}\mathrm{i}\mathrm{n}}}（14）

D_{\alpha }=\frac{\mathrm{1}}{G}{\displaystyle \sum _{g=\mathrm{1}}^G}(||{\mathit{f}}_g-{\mathit{R}}_y{||-\mu )}^{\mathrm{2}}

\mu =\frac{\mathrm{1}}{G}||{\mathit{f}}_g-{\mathit{R}}_y||

||{\mathit{f}}_g-{\mathit{R}}_y||=\sqrt[]{{\displaystyle \sum _{h=\mathrm{1}}^H}(f_{g,h}-r_{y,h}{)}^{\mathrm{2}}}

式中：P_ci 、P_ca 分别为最小、最大交叉概率；C_i，num为参考点R_y 的关联个体数；Z为种群规模；P_mi 、P_ma 分别为最小、最大变异概率；D_α 为参考点 R_y 邻域稀疏程度；G为参考点 R_y 邻域内的个体数； f_g 为第g个体目标向量；μ为邻域距离均值；H为目标函数个数；f_g，h 、r_y，h 分别为个体目标向量与参考点向量在第h个目标维度的分量。

2.4 知识驱动的邻域搜索策略

为进一步探索问题局部解的空间，提出基于禁忌搜索（tabu search，TS）的知识驱动邻域搜索策略。将禁忌搜索算法作为搜索框架，在此基础上，基于问题特征设计CSI邻域结构及N8邻域结构，进一步缩短工件完工时间、提高客户满意度。

2.4.1 N8邻域结构

现有的N5、N6、N7邻域结构是基于关键路径与关键块的工序扰动策略，在关键块内进行扰动来缩短完工时间，但将关键块内的工序移到关键块外可能缩短原有调度方案的完工时间。为此，N8邻域结构^［27］考虑将关键块内的工序移到块外的情况，生成更多的邻域解，其有效性和工序移动后调度方案的可行性^［28］已经通过实验验证。

2.4.2 CSI邻域结构

CSI邻域结构引入基于客户满意度的扰动操作，针对满意度低的工件非关键块工序进行扰动，进一步提高客户满意度。CSI邻域结构具体步骤如下：

1）计算所有工件的客户满意度，并选择客户满意度最低的2个工件。

2）这两个工件的工序中随机选择一道非关键块工序。

3）对该非关键块工序进行双点交换扰动操作，即将该非关键块工序与另一工件的某非关键块工序进行交换。

4）对该非关键块工序进行插入扰动操作，即将该非关键块工序插入到另一工件的某非关键块工序后。

5）对该非关键块工序进行邻域扰动操作，即在一定窗口长度内进行工序反转。

如图6所示，对图3所示的初始编码进行CSI邻域算子扰动操作。初始调度方案的完工时间为（39，56，70），平均客户满意度为0.172，最小客户满意度为0.044，关键块为（O₁₁）、（O₁₂-O₂₁-O₂₂）、（O₂₃-O₄₂）、（O₄₃-O₄₄），进行3种扰动操作后的调度方案如图7～图9所示。双点交换扰动操作后，调度方案的完工时间不变，但平均客户满意度提高至0.34，最小客户满意度提高至0.212。交叉扰动操作后，调度方案的完工时间、最小客户满意度不变，但平均客户满意度提高至0.334。邻域反转扰动操作后，调度方案完工时间缩短至（39，50，65），平均客户满意度提高至0.344，最小客户满意度下降0.032。由此可见，CSI邻域结构能有效优化完工时间与客户满意度。

3 数值实验

3.1 实验设计

为评估所提模型及算法的有效性，本文选取FMK算例^［28］与Remanu算例^［29］进行验证。FMK算例包含有10组算例，最小规模算例的工件数为10，机器数为6，总工序数为55；最大规模算例的工件数为20，机器数为15，总工序数为240。Remanu算例包含8组算例，最小规模算例的工件数为5，机器数为4，总工序数为23；最大规模算例的工件数为20，机器数为15，总工序数为355。

所有实验均在配置为Intel i7-8565U CPU、8.00GB RAM的计算机上完成，编程语言为Python。所有算法均独立运行10次。

3.2 算法参数敏感性分析

算法参数的选择对其性能具有显著影响。通过前文算法描述可知，本文所提IMOEA的主要参数有总评估次数（种群数量与迭代次数的乘积）max F_e、局部搜索频率w、禁忌表长度T_l、邻域结构比例N_r，为探寻不同参数的取值变化对算法综合性能的影响，选取所有算例中处于中等规模的FMK06算例进行敏感性分析基于田口试验设计方法获取最优参数组合，将反转世代距离（IGD）

I(S,P^{\mathrm{*}})=\frac{\mathrm{1}}{|P^{\mathrm{*}}|}{\displaystyle \sum _{\kappa =\mathrm{1}}^{|P^{\mathrm{*}}|}}\underset{\tau \in \left\{\mathrm{1,2},...,\left|S\right|\right\}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sqrt[]{{\displaystyle \sum _{h=\mathrm{1}}^H}(s_{\tau ,h}-p_{\kappa ,h}{)}^{\mathrm{2}}}（15）

式中：S为算法求解解集；P^*为参考解集；|P^*|为参考点数目；τ为解集S中的索引；κ为参考解集P^*中参考点的索引；s_τ，h 为解集S中的第\tau个解在第h个目标维度上的函数值；p_κ，h 为解集P^*中的第κ个参考点在第h个目标维度上的函数值。

作为响应变量。IGD通过计算每个参考点到其最近解的距离均值来评价算法性能，值越小代表算法综合性能越好。

表2为一组四参数四水平L₁₆（4⁴）正交试验表，选取中等规模的FMK06算例进行寻优参数，在每个参数水平下独立运行10次，得到各组合下的平均响应值（表3）、平均响应值与等级（表4），各参数水平因子变化如图10所示。

通过表4与图10可发现，总评估次数max F_e对算法性能影响最大，且max F_e过小会影响算法收敛速度与搜索广度。参数T_l对算法的影响位于第二位，T_l较小会限制算法搜索范围，导致算法难以跳出局部最优解，T_l过大会导致算法响应迟滞。参数w对算法性能的影响位于第三，决定了算法全局探索与局部搜索的平衡点，局部搜索频率很小会导致算法早熟收敛，反之会导致局部搜索不足，优质解无法充分扩展。参数N_r对算法的影响最小，均衡的邻域结构比例可保证邻域多样性与协同优化，提升算法稳定性。基于以上分析，参数max F_e、w、T_l、和N_r分别设为62 500、10、15和0.4。

3.3 消融实验

为探究不同邻域算子对IMOEA搜索性能的影响，运用基于不同邻域算子的IMOEA对各基准算例进行求解。其中，IMOEA-1为无知识驱动的邻域搜索策略的IMOEA，IMOEA-2为基于N8邻域算子的知识驱动的邻域搜索策略的IMOEA，IMOEA-3为基于CSI邻域算子的知识驱动的邻域搜索策略的IMOEA。选取世代距离（GD）

G(S,P^{\mathrm{*}})=\frac{\mathrm{1}}{|S|}{\displaystyle \sum _{\tau =\mathrm{1}}^{|S|}}\underset{\kappa \in \left\{\mathrm{1,2},\dots ,|P^{\mathrm{*}}|\right\}}{\mathrm{m}\mathrm{i}\mathrm{n}}\sqrt[]{{\displaystyle \sum _{h=\mathrm{1}}^H}(s_{\tau ,h}-p_{\kappa ,h}{)}^{\mathrm{2}}}（16）

式中：|S|为解集S中解的数量。

与IGD来评估算法性能。采用Friedman秩和检验分析消融实验结果，以判断邻域算子对IMOEA影响的显著性。表5、表6分别展示了所有算法独立运行后所得指标的均值与统计结果。

由表5、表6可得，IMOEA与3种变体算法（IMOEA-1/2/3）的算法性能有显著差异。从收敛性与分布性综合表现上看，IMOEA在所有算例上的GD与IGD的均值均优于IMOEA-1/2，只在算例Remanu02上劣于IMOEA-3；IMOEA-2/3在绝大多数基准算例上均优于IMOEA-1。这表明N8与CSI邻域算子可提高算法搜索能力。由不同规模算例的GD与IGD可得，问题规模较小时，IMOEA在绝大多数算例上的指标均优于IMOEA-1/2/3；IMOEA-2/3的IGD与GD上无显著差异。这是因为问题规模较小时，解空间的复杂度有限，N8与CSI邻域算子均能充分探索解空间并快速收敛至最优解附近的解空间，在提升算法收敛性的同时维持解集在目标空间中的均匀分布。处理中大规模算例时，IMOEA在所有算例的GD与IGD均优于IMOEA-1/2/3，而IMOEA-2在绝大多数算例上获得结果优于IMOEA-3。其原因在于IMOEA采用知识驱动的邻域搜索策略，N8邻域算子通过对关键路径上关键块工序进行调整，确保算法能探索更广泛的解空间，而CSI邻域算子针对优质解进行精细化搜索，在逼近真实的Pareto前沿的同时维持更好的分布性。相比之下，IMOEA-2缺少CSI邻域算子去深度探索优秀解周围的空间，导致其指标劣于IMOEA。IMOEA-3受限于CSI邻域算子的强局部性，在中大规模问题中易陷于局部最优且搜索效率低，导致其整体性能劣于IMOEA-2。

3.4 算法有效性分析

为进一步验证所提IMOEA的有效性，选取多目标粒子群优化（MOPSO）^［30］算法、基于分解的多目标进化算法（MOEA/D）^［25］、量子启发进化算法（QIEA）^［31］、多目标教与学优化（MOTLBO）^［32］算法、基于分解的聚类分层估计进化算法（MOEA/DCH）^［25］进行对比。为进一步评价算法解集分布的均匀性，在GD与IGD的基础上引入间距指标（SP）：

P(S)=\sqrt[]{\frac{\mathrm{1}}{|S|-\mathrm{1}}{\displaystyle \sum _{\tau =\mathrm{1}}^{\left|S\right|}}(\overline{d}-d_{\tau }{)}^{\mathrm{2}}}（17）

d_{\tau }=\underset{\omega \in \left\{\mathrm{1,2},...,\left|S\right|\right\},\omega \ne \tau }{\mathrm{m}\mathrm{i}\mathrm{n}}\sqrt[]{{\displaystyle \sum _{h=\mathrm{1}}^H}(s_{\tau ,h}-s_{\omega ,h})}

式中：\omega为解集S内其他解的索引；d_τ 为第τ个解到解集S中最近邻解的欧几里得距离；\overline{d}为d_τ 的均值。

为公平起见，所有算法均设置相同的种群大小、迭代次数、编码解码策略。表7～表9给出了不同算法在各基准算例上的统计结果，各指标Friedman秩和检验结果如表10所示。图11、图12分别展示了IMOEA求解FMK02最优调度方案及帕累托前沿。

由表7～表10的统计结果可发现IMOEA与5种对比算法的性能有显著差异。从收敛性与分布性的综合表现上看，IMOEA在不同规模的基准算例上的GD与IGD均优于其他算法。从解集分布的均匀性上看，IMOEA在不同规模的基准算法上的SP同样优于对比算法，验证了算法的有效性。IMOEA采用交叉与变异概率自适应机制，依据种群信息动态调整交叉与变异概率，实现对精英个体的低扰动保护与非精英个体的多样性增强，在维持种群收敛稳定性的同时优化全局探索效率。在此基础上，知识驱动的邻域搜索策略针对不同目标维度，在精英个体附近的解空间进行局部搜索，进一步提升算法性能。此外，IMOEA在不同算例规模上展现良好的鲁棒性。相较之下，随着算例规模增大，其余算法的GD与IGD普遍劣化，算法性能受问题规模影响显著。鲁棒排序及合理资源分配能在动态生产环境中有效提高客户满意度，避免物料、设备及工艺参数波动导致的计划偏离，保障订单及时交付。此外，考虑多维度客户满意度的调度方法有助于引导生产资源向关键客户订单优化配置，在确保生产效率的同时维护客户稳定性，增强企业在不确定的市场环境中的交付及竞争优势，实现可持续发展。

4 结论

本文针对考虑客户满意度的FFJSP构建了以最小化模糊完工时间、最大化平均客户满意度、最大化最小客户满意度为优化目标的FFJSP模型，并提出一种IMOEA进行求解。该算法采用交叉与变异自适应概率满足不同进化阶段的需求；针对问题特性设计了基于N8及CSI结构的知识驱动邻域搜索策略，进一步提升算法的局部搜索能力。最后通过多组基准算例对算法的有效性进行验证，结果表明：对于不同规模的实例数据，IMOEA的收敛性、分布性以及解集分布均匀性均显著优于MOPSO、MOEA/D、QIEA、MOTLBO、MOEA/DCH。

未来工作将重点围绕以下方面：①在模型构建方面，考虑动态事件与资源约束，建立考虑多维度客户满意度的FFJSP模型，构建动态需求驱动的模糊调度决策范式；②在算法求解方面，通过融合深度强化学习与模糊推理技术，开发具有在线自适应能力的混合智能算法，并建立数字孪生赋能的虚实交互验证平台。

参考文献

[1] 祝正宇， 郭具涛， 吕佑龙， 等. 面向柔性作业车间生产调度的深度强化学习方法［J］. 中国机械工程， 2024， 35（11）： 2007-2014.

[2] ZHU Zhengyu， GUO Jutao， Youlong LYU， et al. Deep Reinforcement Learning Method for Flexible Job Shop Scheduling［J］. China Mechanical Engineering， 2024， 35（11）： 2007-2014.

[3] CHEN Zhaoming， ZOU Jinsong， WANG Wei. Digital Twin-oriented Collaborative Optimization of Fuzzy Flexible Job Shop Scheduling under Multiple Uncertainties［J］. Sādhanā， 2023， 48（2）： 78.

[4] DAUZÈRE-PÉRÈS S， DING Junwen， SHEN Liji， et al. The Flexible Job Shop Scheduling Problem： a Review［J］. European Journal of Operational Research， 2024， 314（2）： 409-432.

[5] JIMÉNEZ TOVAR M， ACEVEDO-CHEDID J， OSPINA-MATEUS H， et al. An Optimization Algorithm for the Multi-objective Flexible Fuzzy Job Shop Environment with Partial Flexibility Based on Adaptive Teaching–Learning Considering Fuzzy Processing Times［J］. Soft Computing， 2024， 28（2）： 1459-1489.

[6] 李瑞， 龚文引. 改进的基于分解的多目标进化算法求解双目标模糊柔性作业车间调度问题［J］. 控制理论与应用， 2022， 39（1）： 31-40.

[7] LI Rui， GONG Wenyin. An Improved Multi-objective Evolutionary Algorithm Based on Decomposition for Bi-objective Fuzzy Flexible Job-shop Scheduling Problem［J］. Control Theory & Applications， 2022， 39（1）： 31-40.

[8] LIU Zhenggang， LIANG Xu， HOU Lingyan， et al. Multi-strategy Dynamic Evolution-based Improved MOEA/D Algorithm for Solving Multi-objective Fuzzy Flexible Job Shop Scheduling Problem［J］. IEEE Access， 2023， 11： 54596-54606.

[9] DENG Libao， ZHU Yingjian， DI Yuanzhu， et al. Biased Bi-population Evolutionary Algorithm for Energy-efficient Fuzzy Flexible Job Shop Scheduling with Deteriorating Jobs［J］. Complex System Modeling and Simulation， 2024， 4（1）： 15-32.

[10] LI Rui， GONG Wenyin， LU Chao， et al. A Learning-based Memetic Algorithm for Energy-efficient Flexible Job-shop Scheduling with Type-2 Fuzzy Processing Time［J］. IEEE Transactions on Evolutionary Computation， 2023， 27（3）： 610-620.

[11] CHEN Xiaolong， LI Junqing， DU Yu. A Hybrid Evolutionary Immune Algorithm for Fuzzy Flexible Job Shop Scheduling Problem with Variable Processing Speeds［J］. Expert Systems with Applications， 2023， 233： 120891.

[12] SUN Mengke， CAI Zongyan， ZHANG Haonan. A Teaching-learning-based Optimization with Feedback for L-R Fuzzy Flexible Assembly Job Shop Scheduling Problem with Batch Splitting［J］. Expert Systems with Applications， 2023， 224： 120043.

[13] SOOFI P， YAZDANI M， AMIRI M， et al. Robust Fuzzy-stochastic Programming Model and Meta-heuristic Algorithms for Dual-resource Constrained Flexible Job-shop Scheduling Problem under Machine Breakdown［J］. IEEE Access， 2021， 9： 155740-155762.

[14] WU Rui， TIAN Zheng， LI Xixing， et al. Improved Discrete Particle Swarm Optimization Algorithm for Solving Fuzzy Flexible Job Shop Machines and Automated Guided Vehicles Fusion Scheduling Problem［J］. Engineering Applications of Artificial Intelligence， 2025， 160： 111951.

[15] ZHANG Cuilin， CHEN Jian， SANG Yaowen， et al. Integrated Ternary Scheduling and Execution Bottleneck Identification in Stochastic Job Shops［J］. Expert Systems with Applications， 2026， 296： 129183.

[16] MA Jing， LI Yan. Solution to IPPS Problem under the Condition of Uncertain Delivery Time［C］∥Smart Innovations in Communication and Computational Sciences. Singapore： Springer， 2019： 105-111.

[17] YANG M S， BA L， ZHENG H Y， et al. An Integrated System for Scheduling of Processing and Assembly Operations with Fuzzy Operation Time and Fuzzy Delivery Time［J］. Advances in Production Engineering & Management， 2019， 14（3）： 367-378.

[18] WANG Ziqing， LIAO Wenzhu， ZHANG Yaping. Rescheduling Optimisation of Sustainable Multi-objective Fuzzy Flexible Job Shop under Uncertain Environment［J］. International Journal of Production Research， 2024， 62（24）： 8904-8920.

[19] ZHU Zhenwei， ZHOU Xionghui. A Multi-objective Multi-micro-swarm Leadership Hierarchy-based Optimizer for Uncertain Flexible Job Shop Scheduling Problem with Job Precedence Constraints［J］. Expert Systems with Applications， 2021， 182： 115214.

[20] 梁志珍， 王晓佳. 双资源约束的柔性作业车间鲁棒调度方法［J］. 机械工程学报， 2024， 60（6）： 114-126.

[21] LIANG Zhizhen， WANG Xiaojia. Dual Resource Constraints Flexible Job Shop Robust Scheduling Method［J］. Journal of Mechanical Engineering， 2024， 60（6）： 114- 126.

[22] 唐红涛， 李悦， 王磊. 模糊分布式柔性作业车间调度问题的求解算法［J］. 华中科技大学学报（自然科学版）， 2022， 50（6）： 81-88.

[23] TANG Hongtao， LI Yue， WANG Lei. An Improved GWO Algorithm for Fuzzy Distributed Flexible Job Shop Scheduling Problem［J］. Journal of Huazhong University of Science and Technology （Nature Science Edition）， 2022， 50（6）： 81-88.

[24] LI Junqing， LIU Zhengmin， LI Chengdong， et al. Improved Artificial Immune System Algorithm for Type-2 Fuzzy Flexible Job Shop Scheduling Problem［J］. IEEE Transactions on Fuzzy Systems， 2021， 29（11）： 3234-3248.

[25] PAN Zixiao， LEI Deming， WANG Ling. A Bi-population Evolutionary Algorithm with Feedback for Energy-efficient Fuzzy Flexible Job Shop Scheduling［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2022， 52（8）： 5295-5307.

[26] LI Rui， GONG Wenyin， LU Chao. Self-adaptive Multi-objective Evolutionary Algorithm for Flexible Job Shop Scheduling with Fuzzy Processing Time［J］. Computers & Industrial Engineering， 2022， 168： 108099.

[27] GNANAVELBABU A， CALDEIRA R H， VAIDYANATHAN T. A Simulation-based Modified Backtracking Search Algorithm for Multi-objective Stochastic Flexible Job Shop Scheduling Problem with Worker Flexibility［J］. Applied Soft Computing， 2021， 113： 107960.

[28] FANG Jincheng， ZENG Afeng， ZHENG Shaofeng， et al. Improved Multiverse Optimization Algorithm for Fuzzy Flexible Job-shop Scheduling Problem［J］. IEEE Access， 2023， 11： 48259-48275.

[29] ZHANG Xuwei， LIU Shixin， ZHAO Ziyan， et al. A Decomposition-based Evolutionary Algorithm with Clustering and Hierarchical Estimation for Multiobjective Fuzzy Flexible Jobshop Scheduling［J］. IEEE Transactions on Evolutionary Computation， 2026， 30（1）： 2-15.

[30] 徐宜刚， 陈勇， 王宸， 等. 改进NSGA-Ⅲ求解高维多目标绿色柔性作业车间调度问题［J］. 系统仿真学报， 2024， 36（10）： 2314-2329.

[31] XU Yigang， CHEN Yong， WANG Chen， et al. Improving NSGA-Ⅲ Algorithm for Solving High-dimensional Many-objective Green Flexible Job Shop Scheduling Problem［J］. Journal of System Simulation， 2024， 36（10）： 2314-2329.

[32] XIE Jin， LI Xinyu， GAO Liang， et al. A New Neighbourhood Structure for Job Shop Scheduling Problems［J］. International Journal of Production Research， 2023， 61（7）： 2147-2161.

[33] PALACIOS J J， PUENTE J， VELA C R， et al. Benchmarks for Fuzzy Job Shop Problems［J］. Information Sciences， 2016， 329： 736-752.

[34] GAO Kai zhou， SUGANTHAN P N， PAN Quan ke， et al. An Improved Artificial Bee Colony Algorithm for Flexible Job-shop Scheduling Problem with Fuzzy Processing Time［J］. Expert Systems with Applications， 2016， 65： 52-67.

[35] GU Xiaolin， HUANG Ming， LIANG Xu. A Discrete Particle Swarm Optimization Algorithm with Adaptive Inertia Weight for Solving Multiobjective Flexible Job-shop Scheduling Problem［J］. IEEE Access， 2020， 8： 33125-33136.

[36] WU Xiuli， WU Shaomin. An Elitist Quantum-inspired Evolutionary Algorithm for the Flexible Job-shop Scheduling Problem［J］. Journal of Intelligent Manufacturing， 2017， 28（6）： 1441-1457.

[37] LEI Deming， SU Bin. A Multi-class Teaching–Learning-based Optimization for Multi-objective Distributed Hybrid Flow Shop Scheduling［J］. Knowledge-Based Systems， 2023， 263： 110252.

基金资助

辽宁省科技计划(2024JH2/102600216)

沈阳工业大学翔源学者青年项目(XLYCQNO3)