摘要
研究动态柔性作业车间调度问题(DFJSP)对有效控制生产过程, 提升企业经济盈利能力具有重要意义. 现有研究大多仅考虑机器选择柔性及动态生产场景, 但实际生产中还存在更复杂的工序顺序柔性问题. 在定制化装备制造等场景下, 作业加工工序可按工艺要求划分为若干组, 同组内工序无强制加工顺序约束, 不同组间则需遵循严格加工顺序. 这种工序顺序柔性的引入显著增加问题搜索空间复杂度, 导致求解时间大幅延长. 因此, 本文结合定制化装备制造车间的实际生产需求, 综合考虑机器选择柔性, 工序顺序柔性及新作业到达的动态特性, 提出动态多柔性作业车间调度问题(DMFJSP), 其优化目标为最小化平均流程时间. 为求解该问题, 本文提出一种基于个体简化的遗传规划(GP)方法, 通过引入动态终端节点频率分析个体结构复杂度, 并在适应度评估阶段设置惩罚函数引导种群进化, 进而简化个体结构, 缩短GP训练时间. 为验证所提方法的有效性, 本文在3种不同生产场景下开展测试, 结果表明, 该方法在保证求解质量的同时, 可显著缩短计算时间. 面对更大规模和复杂问题时, 其收敛速度快, 能在合理时间内找到满意解.
关键词
Abstract
Studying the dynamic flexible job-shop scheduling problem (DFJSP) is of great significance for effectively controlling production processes and enhancing enterprises’ economic profitability. Existing studies mostly only consider machine selection flexibility and dynamic production scenarios; however, a more complex issue of flexible process sequence exists in practical production. Specifically, in scenarios like customized equipment manufacturing, job processing operations can be divided into several groups according to process requirements. There are no mandatory processing sequence constraints apply to operations within the same group, whereas strict processing sequence constraints must be followed between different groups. The introduction of this flexible process sequence significantly increases the complexity of the problem’s search space, leading to a substantial extension of solution time. Therefore, by integrating the practical production needs of customized equipment manufacturing workshops, this paper comprehensively considers machine selection flexibility, flexible process sequence, and the dynamic characteristic of new job arrivals, and proposes the dynamic multiflexible job-shop scheduling problem (DMFJSP) with the optimization objective of minimizing the average flow time. To solve this problem, a genetic programming (GP) method based on individual simplification is proposed which analyzes the structural complexity of individuals by introducing dynamic terminal node frequency, and sets a penalty function during the fitness evaluation stage to guide population evolution―ultimately simplifying individual structures and reducing GP training time. To verify the effectiveness of the proposed method, tests are conducted under three different production scenarios. The results demonstrate that the method can significantly shorten computation time while ensuring solution quality; when addressing larger-scale and more complex problems, it exhibits fast convergence and can obtain satisfactory solutions within a reasonable time frame.
1 引言
随着信息通信技术发展，制造企业融合云制造 [1]、智能制造 [2] 及大数据 [3] 推进数字化转型. 柔性作业车间调度问题（flexible job-shop scheduling problem，FJSP）作为作业车间调度问题（JSP）的扩展，在车间调度领域应用广泛 [4] . 但当前研究多聚焦静态调度，并未考虑实际车间扰动，难以满足生产需求. 进而动态柔性作业车间调度问题（dynamic FJSP，DFJSP）成为研究热点 [5] . 新作业到达是实际生产中常见的动态事件 [6]，初始调度作业并非全部可用，新作业随时间陆续到达车间加工. 这种动态事件会显著增加调度不确定性与复杂性. 此外，现代制造企业为适配动态生产环境，依订单制定灵活工艺流程，在满足工艺约束的情况下，一些产品的加工工序具备工序顺序柔性，如定制化特种装备装配车间中，盾体、电气等部件装配可并行，但需在总装前完成. 此类调度问题更贴合实际生产，而 DFJSP尚未考虑工序顺序柔性，因此本文综合机器选择柔性与工序顺序柔性，研究动态多柔性作业车间调度问题（dynamic multi-flexible JSP，DMFJSP）.
针对新作业到达的DFJSP已有相关研究. Baykasoglu等 [7] 提出一种贪心随机自适应搜索策略，求解依赖序列相关准备时间的DFJSP; Lei等 [8] 采用图神经网络与多层感知器代理的层次强化学习框架，处理大规模DFJSP; Zhao等 [9] 结合注意力机制与策略强化学习算法求解DFJSP问题; Liu等 [10] 基于分布式分层双深度Q神经网络，通过奖励驱动学习车间信息与调度决策的映射以求解DFJSP.
上述针对新作业到达DFJSP的研究，均仅考虑工序的机器选择柔性，当前已有研究关注工序顺序柔性. 如Vital-Soto等 [11] 提出改进非支配排序遗传算法，求解考虑工序顺序柔性与工人分配的双资源约束FJSP; Zhang等 [12] 提出分布式蚁群算法，解决含工序顺序柔性的柔性装配作业车间调度问题; 胡瑞淇等 [13] 设计基于表达式树的工序顺序染色体编码，结合遗传算法求解工序顺序柔性作业车间调度问题; 魏光艳等 [14] 采用结合分布估计算法与邻域搜索算子的多维模因算法，求解分布式多柔性装配作业车间调度问题. 但上述研究均针对静态车间场景，未考虑新作业到达这类扰动因素.
现有研究尚未在动态作业车间中综合考虑机器选择柔性与工序顺序柔性，而该问题在制造企业生产中十分常见. 本文调度问题源自高端装备制造企业装配车间，车间内多工位可加工不同工序，作业每道工序可选多个工位. 产品装配分为部装与总装阶段，部装阶段无顺序约束可并行，需全部完工后方能进入总装. 总装通常含1–2道工序（如调试、厂验），需按序加工. 且产品装配作业随时间动态到达，新作业到达前不可预测. 该场景类似动态多柔性作业车间调度问题. 因企业面临高度定制化，复杂化生产任务，订单需求与优先级各异. 为满足其平衡工作负荷与成本控制的需求，本文以最小化平均流程时间目标，构建DMFJSP问题.
现有DFJSP求解方法主要分为启发式规则、元启发式方法与基于机器学习的方法. 启发式规则基于直观或经验逻辑制定，易理解实现. Xiong等 [15] 针对考虑批量释放与扩展技术优先约束的动态车间调度问题，基于松弛时间与动态比率提出4种调度规则，优化延迟相关指标; Oukil等 [16] 提出基于数据包络分析的多视角方法，解决多目标动态流水车间调度规则排名问题. 但启发式规则设计需丰富领域知识与大量试错成本，且缺乏全局优化能力，解质量难以保证 [17] . 元启发式方法可通过参数调整适配不同DFJSP，全局搜索能力强，还能结合多种策略提升搜索效率与解质量. 王艳等 [18] 提出改进多目标差分进化算法，求解以最小化能耗、完工时间与调度稳定性为目标的DFJSP; 张国辉等 [19] 结合事件驱动策略设计帝国竞争算法，求解考虑机器故障的DFJSP. 但元启发式方法迭代与计算量大，难以满足DFJSP的实时性需求[20] . 深度强化学习方法作为机器学习的一类，能随环境变化自动调整策略，通过试错反馈优化调度效果 [21] . Shi等 [22] 提出基于深度强化学习的智能调度方法，应用于离散自动化生产线; Song等 [23] 设计异构图神经网络，将操作选择与机器分配整合为复合决策求解FJSP. 但深度强化学习需手动设计适配动态问题的重调度规则，依赖复杂先验知识. 此外，众多学者采用遗传规划（genetic programming，GP）求解DFJSP [24]，相较于启发式规则与深度强化学习，GP可模仿自然选择和遗传机制，自动从候选规则中优化最佳规则，更适配复杂动态环境. 相较于元启发式算法，GP生成的演化规则计算简单，能快速响应动态事件. 因此，本文选用GP作为算法框架求解DMFJSP.
GP求解DFJSP的研究较多. Zhang等 [25] 提出协同进化遗传规划（cooperative co-evolution genetic programming with two sub-populations，CCGP），可同时优化机器选择与工序排序规则; Zhou等 [26] 采用双子树遗传规划（genetic programming with single population that a GP individuals contains two sub-trees，TTGP）方法，将两类规则编码于单个GP个体求解; Xu等 [27] 设计带存档的多子树遗传规划方法（CCGP with archive，CCAGP）解决DFJSP，通过存档存储进化潜力解以供后续迭代复用; Zhu 等 [28] 提出改进交叉算子的CCGP 方法（CCGP selects both two rules for crossover，and one rule and for swap，CCGP-C2S），在机器选择与工序排序规则上应用交叉，交换策略提升种群多样性. 上述研究多聚焦改善GP种群，却鲜少关注GP个体结构对算法性能的影响.
现有研究尚未关注DMFJSP，本文针对该问题提出个体简化的GP方法，该方法充分考虑机器选择、工序排序与工序顺序柔性3个子问题，通过适应度评估阶段的个体简化策略引导种群进化，在缩短算法计算时间的同时保证求解质量. 本文主要贡献如下:
1）研究一种动态多柔性作业车间调度问题，该问题考虑新作业到达、机器选择柔性与工序顺序柔性3类现实约束，以平均流程时间为优化目标，建立该问题的数学模型;
2）提出个体简化的GP方法求解该问题，通过评估动态终端节点频率引导种群进化方向，克服GP训练耗时久、收敛速度慢的缺点.
2 问题描述与建模
2.1 问题描述
DMFJSP除机器选择柔性外，还考虑工序顺序柔性，作业加工工序按工艺划分为若干组，同组工序无顺序约束，不同组需遵循严格加工顺序. 该问题可描述为: 生产车间内含 m台机器 M = {M1，M2，· · ·，Mm}，初始有n个作业 J = {J1，J2，· · ·，Jn}待加工，后续新作业J ′ ={}陆续到达，作业Ji含 Ni道加工工序O={}，其优先级层级为Ri ，优先级为r的工序共Ki，r道，同优先级工序无顺序约束，低优先级工序需待高优先级工序完工后进行，且每个作业有对应到达时间，优化目标为最小化平均流程时间，DMFJSP包含以下子问题: 1）作业的机器选择问题; 2）工序的排序问题; 3）工序间的优先级约束问题.
此外，为更好地表述问题，作如下假设:
1）所有作业的每道工序仅分配处理一次;
2）同一作业工序受优先级约束，不同作业工序间无优先级约束;
3）作业工序加工过程不可中断;
4）作业工序仅分配至适配机器加工;
5）每台机器0时刻均可用;
6）每台机器可加工多道工序，但同一时刻至多加工一道.
2.2 符号说明
为了更好的描述DMFJSP的数学模型，使用的符号和含义如表1所示.
2.3 数学模型
目标函数
(1)
其中式（1）表示最小化平均流程时间.
约束条件:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
其中: 式（2）表示所有作业的每道工序仅分配处理一次; 式（3）和式（4）表示作业最高优先级工序需在作业释放后进行; 式（5）表示同一作业中，低优先级组任意工序需待高优先级组所有工序完工后进行; 式（6）与式（7）表示同一优先级的任意两道工序可并行加工; 式（8）表示每道工序均分配至适配机器; 式（9）表示工序加工过程不可中断; 式（10）表示每台机器同一时刻仅能处理一道工序; 式（11）表示工序的开始时间，处理时间及完成时间均不小于0.
表1符号说明
Table1Symbol notation
3 算法描述
3.1 个体设计
GP 个体为树状结构，含节点与子树. 节点分为操作符节点与终端节点: 操作符节点含算数运算符，如 Add，Sub和Max; 终端节点用于表示车间生产状态，如 PT，OWT和NIQ. 因本文需考虑工序优先级约束，因此在终端节点中增加OP，OPR 和NPIQ 等与工序约束相关节点，以促使调度决策更多考虑优先级约束，间接影响决策演化结果. 表2列出了构建GP树所用终端节点与操作符节点功能.
表2GP个体节点及对应功能
Table2GP individual nodes and their corresponding functions
根据种群个体初始化方式不同，GP可划分为CCGP与TTGP. TTGP中，单个种群个体为一棵树，左、右子树分别对应机器选择与工序排序决策，两者在同一 GP个体中协同进化，如图1（a）所示. CCGP则将种群个体拆分为两棵独立树，分别对应机器选择与工序排序决策，两类规则独立进化，如图1（b）所示. 采用这两种方式创建新种群，可充分衡量不同种群个体类型对算法性能的影响.
3.2 个体适应度评估
运行时间是评价算法性能的重要指标. GP运行时，每次迭代需对种群所有个体进行适应度评估，作为超启发式算法，GP个体并非问题的解，而是求解问题的启发式规则，故其适应度评估需模拟数千个陆续到达的作业. 个体解码的调度策略参与机器选择与工序排序决策: 新作业到达或当前工序完成时，通过机器选择树计算候选机器排名以确定加工机器; 目标机器空闲时，通过工序排序树计算等待工序排名以确定下一道处理工序. 该过程中所有树节点需执行数十万次运算，导致计算耗时显著.
图1调度策略的编码表示
Fig.1Encoding representation of scheduling rules
为减少GP个体适应度评估耗时，本文提出个体简化策略（individual simplification policy，ISP）. ISP从两方面优化计算效率: 1）GP树节点含操作符节点与终端节点，操作符节点为加减乘除等浮点数运算，计算速度快，终端节点按参数是否随程序变化分为静态与动态终端节点. 静态终端节点参数预定义，如工序处理时间 PT、到期日 DD等，耗时较短. 动态终端节点需实时计算车间状态，耗时较长. 如工序等待时间 OWT、同优先级剩余工序数OPR等; 2）相同复杂度的 GP个体，动态终端节点越多，高耗时动态节点占比越高，运行时间越长，故引入动态终端节点计算耗时占比，量化个体的相对计算开销. 具体而言，ISP通过惩罚函数控制动态终端节点占比，将其融入适应度计算. 惩罚函数设计需考虑了以下3个关键因素: 1）动态终端节点占比: 计算动态节点数与总节点数比例; 2）计算耗时权重: 为不同动态节点分配权重以反映耗时差异; 3）惩罚力度: 结合前两者设置，确保高动态节点在子代选择中处于劣势. ISP的优势在于从基因层面优化，一方面，动态终端节点中部分冗余节点的计算信息对GP个体核心决策无额外增益，用非冗余节点替代后，既能保留关键决策信息，又能保障种群进化中解质量稳定; 另一方面，通过量化其耗时占比，搭配惩罚函数控制动态节点数量，显著降低适应度评估耗时. 改进后的适应度计算公式如下所示:
(12)
其中: ωF为惩罚函数在原适应度中占比，bi为第i种动态终端节点运行时间占所有动态节点运行时间的比例，numdynamic 为个体树中所有动态终端节点总数，numi为个体树中第i种动态终端节点个数.
3.3 种群进化
种群个体经适应度评估后，更新精英个体. 父代个体通过锦标赛选择从当前种群中筛选产生（参考文献 [29]，比赛规模设置为3），再通过交叉，变异算子繁殖子代. 交叉算子采用单点交叉，在两父代个体中各随机选取一个节点，交换对应子树形成子代. 变异算子随机选取父代个体的一个节点作为突变点，用随机生成的子树替换该节点子树. TTGP个体进化方式有特殊性，其两种调度规则编码于同一棵树，故交叉、变异算子需选择相同类型的子树节点. 交叉时从两父代中随机选取同类型子树节点，交换子树生成子代; 变异时随机选择父代子树节点，用随机子树替换该节点为根的子树.
图2给出 TTGP 交叉与变异算子的示例. 交叉时，随机选取两个个体tree1（机器选择规则为PT*（NIQOPR））和tree2（机器选择规则为NOR+DD），两者从同类型GP 树中选取子树Subtree1与Subtree2，交换后子代机器选择规则分别为PT*（NOR+DD），NIQ-OPR. 变异时，随机选取个体tree1（机器选择规则为 PT*（NIQOPR）），用随机生成的新子树替换其随机选定的子树 Subtree1，子代机器选择规则变为PT*（OWT+TIS）. 种群进化完成后，将保留的精英个体混入新生子代，再经锦标赛法筛选出与原父代种群数量一致的个体，形成新种群.
3.4 算法流程
根据上述算法描述，整个算法的流程图如图3所示.
图2TTGP交叉和变异方式
Fig.2Crossover and mutation techniques in TTGP
图3改进后的GP框架和个体适应度评估过程
Fig.3Improved GP framework and individual fitness evaluation process
算法的具体步骤如下:
步骤 1 初始化GP种群. 设置个体最大深度为6，采用随机初始化方式分别生成CCGP和TTGP种群个体;
步骤 2 个体适应度评估（包含以下子步骤）:
2.1 判断是否有新批次到达，若有新批次到达，初始化本批次工序集合，否则跳转至步骤2.6;
2.2 选择高优先级工序放入待调度集合;
2.3 对于所有待调度集合工序，判断是否需要选择机器: 若需要，则应用机器选择决策计算候选机器排名并确定加工机器，否则直接进入下一步;
2.4 判断当前机器是否需要选择工序: 若需要，则应用工序排序决策计算等待工序排名并确定加工工序，否则直接进入下一步;
2.5 判断本批次所有待调度工序是否完成: 若已完成，则进入下一步，否则跳转至步骤2.2;
2.6 判断所有批次工序是否完成: 若已完成，则根据个体在该场景表现计算适应度，否则跳转至步骤2.1;
步骤 3 更新精英个体: 判断种群中是否有个体适应度优于精英存档中个体，若有则更新精英存档;
步骤 4 判断是否达到最大迭代次数，若未达到，通过锦标赛选择从当前种群筛选父代，执行交叉与变异生成子代种群，并将精英个体插入子代，返回步骤2重新进行适应度评估;
步骤 5 若达到最大迭代次数，输出适应度最优的个体，该个体的调度规则作为最终用于动态场景的决策规则.
4 实验及分析
4.1 实验设置
本实验中，仿真模型参数在一定范围内随机生成. 具体范围如表3所示. 作业到达时间依据机器利用率确定. 假设新作业到达车间遵循泊松过程，平均到达时间间隔计算如下:
(13)
其中: t为作业平均到达时间间隔，为作业工序平均处理时间， np为作业平均工序数量，u为机器利用率，m为机器数量. 作业到达时间间隔由指数分布E（1/t）计算. 交货期设为作业加工时间与交货期宽裕度系数的乘积.
为确保测量起始即获稳态性能，将初始1000个作业设为预热任务，性能评估从第1001个作业开始，至第6000个作业完成，其统计信息用于适应度计算. 此外，作业工序优先级层级（operation priority size，Ops）设为不同等级，Ops越大，加工难度越高，作业工艺流程越复杂. GP算法种群进化的相关参数设置如表4所示. 其中，种群大小与精英个体数量经多次测试确定为适配值，种群初始化采用完全生成法与成长生成法结合的Ramped half-and-half方式 [30]，50%个体为最大深度，其余个体深度服从U[2，6]，确保种群中兼具简单与复杂树结构. 其余参数设置参考文献 [31] .
表3仿真模型参数设置
Table3Setting parameters in simulation models
表4GP算法参数设置
Table4Setting parameters in the GP algorithm
实验分训练阶段与测试阶段，训练阶段每次迭代通过评估相同动态场景进化调度规则，测试阶段使用表现最优的调度规则实时响应动态事件. 新作业到达时，该最优调度规则会根据车间信息进行决策，从而保证重调度的实时性. 最终以30次测试的平均适应度值作为本次训练结果，独立运行30次，取测试阶段平均适应度值评估算法性能. 需注意，ISP修正适应度值仅用于种群进化，评估算法性能仍用原适应度值，以保证对比实验适应度值范围一致. 此外，ISP需计算各动态终端节点占总运行时间的比例，表5列出各动态终端节点10次独立的时间（单位: ms）均值及占比. Ops 增加会显著提升问题求解难度. 为探究ISP对GP算法的影响，本文按Ops=3，4，5设置3个生产场景，将CCGP，TTGP分别结合ISP形成CCGP-ISP，TTGP-ISP，验证ISP在不同GP个体构建场景下的表现.
4.2 参数校验
ISP中惩罚函数占比ωF控制种群个体简化程度.占比过小则无法充分引导种群进化，易出现更多高耗时动态终端节点; 占比过大则会过度简化个体，导致其失去复杂性与表达能力. 本节探究不同ωF对CCGPISP，TTGP-ISP 性能的影响. 具体设置 ωF = 0.1，0.2，0.3，0.4共4种配置，在3种生产场景中实验，每次迭代取最优个体，在同一场景下测试30次，以平均适应度值表征该代种群性能.
表5动态节点运行时间平均值及占比统计
Table5Statistics of average running time and proportion for dynamic nodes
不同ωF对CCGP-ISP的影响如图4所示（横轴为时间，纵轴为平均适应度值）.3种场景中均呈现ωF增大时收敛后平均适应度值先减再增的趋势，其中 ωF = 0.3时不仅最终适应度值最优，且算法收敛更快，如图5（TTGP-ISP平均适应度曲线）所示，ωF = 0.3在所有场景中同样表现最优，故CCGP-ISP与TTGP-ISP均选取ωF = 0.3作为算法配置.
图4CCGP不同惩罚函数占比配置在3种生产场景中相同训练时间下独立运行30次得到的平均适应度曲线
Fig.4Average fitness curves for CCGP using different proportions of penalty functions in three production scenarios, derived from 30 independent runs with identical training duration
图5TTGP不同惩罚函数占比配置在3种生产场景中相同训练时间下独立运行30次得到的平均适应度曲线
Fig.5Average fitness curves for TTGP using different proportions of penalty functions in three production scenarios, derived from 30 independent runs with identical training duration
4.3 实验结果及分析
为测试CCGP-ISP，TTGP-ISP性能，本文将其与现有改进GP算法CCAGP [27]，CCGP-C2S [28] 对比，以验证ISP策略有效性. 采用显著性水平为0.05的Wilcoxon秩和检验，基于3个生产场景下30次独立运行结果检验算法性能，以“−”，“+”和“≈”分别表示结果优于、差于和相近于对比算法.
表6给出不同算法在3种生产场景下30次独立运行的训练时间均值，标准差及Wilcoxon秩和检验置信区间. 结果显示，CCGP-ISP在3个场景中训练时间均值均最优，TTGP-ISP在Ops=4，5的场景中优于原始算法. 随问题规模从Ops=3扩大至Ops=5，ISP算法的时间优势更显著. 结果表明，使用ISP可有效缩短GP训练时间. 此外，工序优先级层级对训练时间影响显著，层级越高，工序越多，工艺越复杂，所需训练时间越长，这一点在所有场景中均成立. 而简单场景下ISP算法与原始算法表现相近，可能因简单场景中GP个体结构不复杂，两类种群个体差异较小.
图6为不同算法在3种场景下30次独立运行的最优适应度小提琴图. Ops=3的场景中，CCAGP和CCGPC2S最优适应度值集中于较低区间，ISP算法与原始算法分布区间基本重合; Ops=4场景中，TTGP-ISP分布区间更低且中位数显著低于其他算法; Ops=5场景中，ISP算法与其余算法适应度分布基本持平. 结果表明，ISP通过减少动态终端节点计算冗余，简化个体结构的同时保留机器选择与工序排序的核心决策信息，不影响GP全局搜索能力. 且复杂场景中ISP可减少冗余节点对种群进化的干扰，使算法聚焦于工序优先级约束等关键因素，进而获得更优解. 表7给出不同算法在3种场景下30次独立运行的最优适应度均值，标准差及 Wilcoxon秩和检验置信区间. 结果显示，3种场景中ISP算法与同类种群算法性能无统计学差异，仅 Ops=4场景中ISP算法存在一定优势; 其余场景下各算法性能整体处于相近水平. 综上，ISP能在减少训练时间的同时，实现与原始算法相似甚至更好的性能. 理论上，ISP仅降低个体计算复杂度，不影响种群质量. 可能原因在于，计算复杂动态终端节点在性能评估中的作用不优于静态节点，减少其频率反而利于优化.
表6不同算法在3种生产场景中独立运行30次得到的训练时间平均值、标准差以及Wilcoxon秩和检验置信区间
Table6The mean of training time (in minutes) , standard deviation, and confidence intervals from Wilcoxon rank-sum test for different algorithms over 30 independent runs in three production scenarios
图6不同算法在3种生产场景中独立运行30次得到的最优适应度小提琴图
Fig.6Violin plots of optimal fitness for different algorithms over 30 independent runs in three production scenarios
为进一步分析算法在相同训练时间下的性能，参考文献 [32] 的实验方法，因不同算法每次迭代耗时不同，无法通过迭代次数衡量算法相同时间内的性能. 每个场景设置大部分算法均能完成训练的基准时间，Ops = 3为51 min，Ops = 4为150 min，Ops = 5为 300 min，分别对应17个、50个和100个等间隔采样点（间隔3 min），以离采样点最近一代种群的适应度值作为该采样点的算法性能表现，通过30次独立运行获取各采样点平均适应度值以衡量算法性能. 图7为不同算法在3种场景相同训练时间下的平均适应度曲线.结果显示，相同训练时间内，Ops=3，4场景中ISP算法收敛速度略占优势; Ops=5场景中，TTGP-ISP表现更突出，且3种场景下ISP算法在种群进化早期均能获得更优适应度值.
综上，实验结果证明了在GP中使用ISP的有效性. 使用ISP可以通过简化个体结构缩短计算时间，从而提升算法效率. 此外，使用ISP不会影响种群生成个体的质量，在所有情况下表现都不会更差，在部分情况下可以实现更好的性能. 在相同的训练时间下收敛速度更快，在较短的时间内可以找到更优的结果.
表7不同算法在3种生产场景中独立运行30次得到的最优适应度平均值、标准差以及Wilcoxon秩和检验置信区间
Table7The mean of optimal fitness, standard deviation, and confidence intervals from Wilcoxon rank-sum test for different algorithms over 30 independent runs in three production scenarios
图7不同算法在3种生产场景中的相同训练时间下独立运行30次得到的平均适应度曲线
Fig.7Average fitness curves for different algorithms over 30 independent runs under identical training time in three production scenarios
5 结论
本文研究动态多柔性作业车间调度问题，为有效解决该问题，提出个体简化的遗传规划方法，从动态终端节点计算耗时与数量占比两方面，分析其对个体适应度评估耗时的影响，通过惩罚函数削弱动态终端节点占比高的个体在子代选择中的优势，进而缩短 GP计算时间. 为验证该方法有效性，本文在3个生产场景下对比6种算法，结果显示，该方法在不影响GP 性能的同时，显著缩短其计算时间. 在此基础上，后续研究将从问题与算法两方面展开: 1）本文基于ISP的 GP方法仅验证了单目标优化问题，未来可在GP中引入多目标优化框架以优化多个目标，此外，未来将研究其如何更好适应订单变更，设备故障等动态生产环境; 2）通过代理辅助模型替代部分适应度评估过程，减轻计算负担，提升GP在更复杂问题中的计算速度.