Flexible job shop scheduling considering transportation and machine pre-maintenance
-
摘要: 航空制造业的快速发展，对高效率和低能耗生产模式的需求愈发迫切。通过综合分析考虑运输和预维护的航空复合材料柔性作业车间调度问题，建立了以最小化完工时间、瓶颈机器负载和总能耗为目标的模型，提出了一种基于种群质量的非支配排序遗传算法(nondominated sorting genetic algorithm II，NSGA-II)。采用启发式初始化方法产生高质量的初始种群，对个体进行分组进化：对优质种群进行局部搜索，深度挖掘种群的最优个体；中等种群通过交叉变异和机器负载操作改变自身部分基因来挖掘最优解；劣质种群则通过学习机制获取优质个体的优秀基因，提升个体优良率。通过测试算例与对比算法的比较验证了所提算法的有效性。最后，将算法应用于实际的航空制造系统，实现了实际生产活动的调度，验证了算法的可行性。Abstract: The rapid development of the aviation manufacturing industry has increased the demand for high-efficiency and low-energy modes of consumption and production. Here, a modeling and analysis approach was employed to address the green scheduling issues of an aerospace flexible job shop regarding transportation and pre-maintenance. Additionally, a model was established to minimize the completion time, bottleneck machine workload, and total energy consumption. Further, non-dominated sorting genetic algorithm II based on population quality was proposed to resolve the issues. Furthermore, heuristic initialization was employed to generate high-quality initial populations, and individuals were grouped to evolve. Thereafter, local search operations were conducted to comprehensively explore the optimal individuals. For the populations classified as moderate, crossover and mutation combined with machine load operations were applied to alter portions of their genetic makeup and achieve optimal solutions. Employing a learning mechanism, the inferior populations acquired superior genes from elite individuals to enhance their overall quality. Subsequently, the effectiveness of the proposed algorithm was verified by comparing it with those of other algorithms on test examples. Finally, the algorithm was applied to a real aerospace composite material manufacturing system to schedule actual production activities, thereby verifying its feasibility.
-
随着生产规模的扩大和产品种类的多样化，航空企业在追求最小化完工时间的同时，还需尽可能降低生产能耗，以满足低碳制造的行业要求[1-2]。在实际航空复合材料生产中，由于机器磨损和老化，故障不可避免地发生，严重影响生产效率和产品质量。本研究在考虑工件运输时间的同时，引入机器预维护机制，在故障发生前进行预防性维护，以降低其对生产流程的影响。
在现有考虑运输时间的多目标柔性作业车间调度问题(flexible job-shop scheduling problem, FJSP)研究中，多数研究假设机器持续可用，未考虑机器可靠性及维修等因素对生产过程的影响。因此，本研究将机器的预维护(preventive maintenance, PM)纳入考量，以提升生产调度的准确性和稳定性。吴秀丽等[3]研究了考虑机器预防性维修的FJSP，设计了一种超启发式文化基因算法进行求解。李聪波等[4]为减少实际FJSP过程中由机床故障导致的加工中断，提出一种启发式框架下的调度算法进行求解。Wocker等[5]提出了一个混合整数模型，同步优化柔性作业车间调度与维护活动分配，并开发了集成式局部搜索算法求解该问题。虽然这些研究考虑了预维护对FJSP的影响，却忽略了运输时间和能源消耗。在实际生产中，尤其是在大规模生产和长距离运输的情况下，运输能耗可能会成为生产过程中的主要能耗。Nikolaos等[6]提出了一种基于分组的分解方法，将整个问题分解为更小的子问题，求得能耗更低的可行解。Meng等[7]提出了一种高效的混合蛙跳算法以解决考虑能耗的分布式柔性作业车间调度问题。王凌等[8]建立了考虑运输时间的分布式绿色FJSP模型，提出了一种考虑运输时间的协同群智能算法进行求解。Jiang等[9]研究了考虑总能耗的带运输时间的FJSP，并设计了一种改进的动物迁移优化算法进行求解。需指出的是，实际生产中机器故障与维修会引发生产中断和延误，进而影响完工时间及能耗等指标。
鉴于上述背景，本文针对航空复合材料生产车间的具体特征和需求，引入机器预维护机制，以完工时间、瓶颈机器负载和能耗为优化目标，对考虑运输和预维护的柔性作业车间调度问题(flexible job-shop scheduling problem with transportation time and pre-maintenance, FJSPTP)展开研究。由于FJSP是一种典型的NP(nondeterministic polynomial time)难问题[10]，其精确解在多项式时间内通常不可得，因此启发式与元启发式算法（如遗传[11]、蚁群[12]、粒子群[13]、灰狼[14]算法等）成为实际应用中寻求可行解的主要方法。这些算法能够在合理的时间内找到足够好的解，满足实际应用的需求。为此，本文提出一种基于种群质量的非支配排序遗传算法(non-dominated sorting genetic algorithm II based on population quality, PQNSGA-II)求解该模型。最后，通过测试算例和实例分析，验证PQNSGA-II算法求解FJSPTP的有效性。
1. 问题描述及数学模型
1.1 问题描述
FJSPTP描述为：给定n个工件在m台机器上加工，每个工件包含若干道工序，每道工序都可以在多台机器上进行加工，工序间的转移需要考虑机器间的运输时间，该时间取决于机器间距和所运输工件的特性。每台机器需进行Vk次预维护计划，预维护时间由机器的可靠性函数
$ R\left( t \right) $ 及可靠性阈值$ R\mathrm{_{th}\mathit{\mathit{ }}} $ 确定，维护期间机器不可加工工件。假设运输资源充足，且机器间运输时间已知。调度目标为最小化最大完工时间、总能耗和瓶颈机器负载。此外，还需满足以下约束：1)所有工件均在0时刻可以被加工；
2)不同工件工序之间相互独立，同一工件工序之间存在先后约束；
3)每个工件在加工过程中不能被中断；
4)机器故障率服从Weibull分布，随着时间的推移，机器的寿命逐渐减少，故障率逐渐增加；
5)在完成一道工序后，机器可靠性降至阈值时，立即执行预防性维护，假设每台机器初始役龄为0。
1.2 机器预维护
为描述机器运行中的故障特征，采用Weibull分布来描述初始机器故障规律模型，定义故障发生率为[15]
$$ \lambda(t)=\left(\frac{t}{\eta}\right)^{\beta-1} \frac{\beta}{\eta},\qquad t>0 $$ (1) 式中：
$ t $ 为机器运行时间(役龄)；$ \beta $ 为形状参数，决定了函数的形状变化；$ \eta $ 为尺度参数，影响故障率分布曲线的放缩变换。参数$ \beta $ 与$ \eta $ 可以根据设备故障的历史数据获得，并且不随时间改变。根据机器役龄计算可靠性函数
$ R(t) $ ：$$ R(t) = {{\mathrm{e}}^{ - \left(\tfrac{t}{n}\right)}}^{\beta } $$ (2) 通常在执行完预维护后，机器的故障率以及潜在的故障风险均会降低，因此本文设计机器老化因子
$ a $ 来描述预维护后的机器状态。引入预维护和老化因子$ a $ 的故障率$ \lambda_{v} $ 调整为$$ \lambda_{v}(t)=\lambda(t)-a^{\left(t-t_{\mathrm{PM}}\right)/\eta} $$ (3) 式中：
$ t $ 为当前机器的役龄；$ t\mathrm{_{PM}} $ 为预维护的时间点；v为第v次预维护；$ a $ 为反映机器老化的因子，由于$0 < a < 1$ ，预维护以后故障率降低，意味着预维护有助于降低机器的故障率。随着$ t $ 的增加，指数部分也会增加，表示随着$ t $ 的增长，预维护的效果会逐渐减弱，机器故障率上升。综上分析，构建一个两阶段可靠性模型：
$$ R(t)=\left\{\begin{array}{l}\mathrm{e}^{-\left(\tfrac{t}{\eta}\right)^{\beta}}, \;\;\; t\leqslant t_{\mathrm{PM}} \\ R(t)\cdot\mathrm{e}^{-a\cdot\left(\tfrac{t-t_{\mathrm{PM}}}{\eta}\right)^{\beta}}, \;\;\; t > t_{\mathrm{PM}}\end{array}\right. $$ (4) 在此模型中，在
$ t\leqslant t\mathrm{_{PM}} $ 时，故障率服从常规Weibull分布，可靠性函数不受预维护影响。在$ t > t\mathrm{_{PM}} $ 时，在执行完预维护以后通过引入老化因子调整故障率，使机器在预维护之后恢复到新的状态。但随着时间的推移，预维护效果可能会逐渐削弱，机器将依照其固有的老化过程渐进。通过分析历史维修记录，确定机器的可靠性阈值。当$ R(t) < R_{\mathrm{th}} $ 时会进行预维护，这种两阶段可靠性模型的设计，使得设备在不同役龄阶段呈现不同的故障特性，既能降低故障发生概率，又能通过提高设备可靠性来保障生产效率。1.3 数学模型
为便于描述，FJSPTP模型符号定义如表1所示。
表 1 符号定义Table 1 Symbol definitions符号 定义 n 工件总数 m 机器总数 hi 工件号为i的工序数 i 工件序号, i=1,2,···,n j 工序序号, j=1,2,···, hi k,e 机器序号, k,e=1,2,···,m J 所有工件集合 M 所有机器集合 Ji 第i号工件 Mk 第k台机器 Oij 工件i的第j道工序 Mij Oij可选机器集 Pijk Oij于Mk的加工时间 Tke 工件从机器k到机器e运输时间 $T_{{\mathrm{PS}}_{kv}} $ Mk第v次预维护的开始时间 $ T_{{\mathrm{PE}}_{kv}} $ Mk第v次预维护的结束时间 $T_{{\mathrm{PM}}_{kv}} $ Mk第v次预维护的维护时间 Sij Oij加工开始时间 Cij Oij加工结束时间 Ci Ji完成时间 E 总能耗 EP 加工能耗 EI 空载能耗 ET 运输能耗 $ e_{p_k} $ Mk单位加工能耗 $e_{i_k} $ Mk单位空载能耗 $e_{t_k} $ Mk单位运输能耗 Vk Mk的预维护次数 Cmax 总加工完成时间 Xijk 0−1决策变量，当Oij选择在Mk上加工，
则Xijk=1，否则Xijk=0Yijxyk 0−1决策变量，当Oij在Oxy之前在Mk加工时，则Yijxyk=1，否则Yijxyk=0 Zike 0−1决策变量，当工件i从Mk运输到Me时，
则Zike =1，否则Zike =0L 一个很大的正数 本文以最小化最大完工时间、总能耗及瓶颈机器负载为优化目标：
$$ \min f=\left\{f_{1}, f_{2}, f_{3}\right\} $$ (5) 并以此建立调度优化模型如下。
1)最小化最大完工时间，该目标用于描述工件加工效率，是评价生产效率的重要指标：
$$ f_1=\min C_{\max }=\min \left(\max _{1 \leq i \leq n} C_i\right) $$ (6) 2)最小化总能耗，随着全球温室效应加剧，制造业的能耗问题备受关注。在实际柔性车间生产过程中，总能耗包括机器加工能耗、空载能耗和运输能耗，总能耗、机器的加工能耗、空闲能耗和运输能耗分别表示为
$$ f_{2}=E_{\min }=\min ( E_{\mathrm{P}}+ E_{\mathrm{T}}+ E_{\mathrm{I}}) $$ (7) $$ E_{\mathrm{P}}=\sum_{i=1}^n \sum_{j=1}^{h_i} \sum_{k=1}^m e_{p_k} \times p_{i j k} \times X_{i j k} $$ (8) $$ E_{\mathrm{I}}=\sum_{i=1}^n \sum_{j=1}^{h_i} \sum_{i'=1}^n \sum_{j^{\prime}=1}^{h_i} \sum_{k=1}^m e_{i_k} \times\left(S_{i j k}-C_{g h k}\right) \times Y_{i j i^{\prime} j^{\prime} k} $$ (9) $$ E_{\mathrm{T}}=\sum_{i=1}^n \sum_{k=1}^m \sum_{e=1}^m t_e \times t_{k e} \times Z_{i k e} $$ (10) 3)最小化瓶颈机器负载，瓶颈机器是加工过程中承载最大负载的机器。由于长时间高负载运行容易导致机器故障，为了减少机器的PM次数，需要平衡机器的负载以降低机器故障率：
$$ f_3=\min \left(\max _{1 \leq k \leq m} \sum_{i=1}^n \sum_{j=1}^{h_i} P_{i j k} X_{i j k}\right) $$ (11) 约束条件：
$$ S_{i j k}+P_{i j k} \leq S_{i^{\prime} j^{\prime} k}+L\left(1-Y_{i j i^{\prime} j^{\prime} k}\right) $$ (12) $$ C_{i(j-1) k} \leq S_{i j k}+L\left(1-Y_{i j i^{\prime} j^{\prime} k}\right) $$ (13) $$ \sum_{k=1}^{m} X_{ijk}=1 $$ (14) $$ S_{i j} \geq 0, C_{i j} \geq 0 $$ (15) $$ S_{ijk} \geq T_{{\mathrm{PE}}_{kv}}, C_{ijk} \leq T_{{\mathrm{PS}}_{k v}} $$ (16) $$ T_{{\mathrm{PE}}_{kv}} \geq T_{{\mathrm{PS}}_{kv}}+ T_{{\mathrm{PM}}_{kv}} $$ (17) $$ C_{i j k}=S_{i j k}+\sum_{i=1}^n \sum_{j=1}^{n_i} \sum_{k=1}^m\left(X_{i j k} P_{i j k}+\tau_{i j k} T_{{\mathrm{PM}}_{k v}}\right) $$ (18) 式(12)～(13)表示同一时间一台机器只能加工一道工序；式(14)表示在同一时刻一道工序只能由一台机器加工；式(15)表示任意工序的开始和完成时间均为非负的；式(16)表示每台机器上不能同时进行工件加工和PM操作；式(17)表示PM操作的时间约束，PM要有足够的时间在计划内进行维护；式(18)表示一道工序要经过预维护与加工操作才算完成。
2. 基于种群质量的NSGA-II算法
2.1 算法总体流程
PQNSGA-II(基于种群质量的NSGA-II)算法的整体流程如图1所示：1)采用混合初始化规则，以提高初始种群质量并维持种群多样性；2)基于个体质量对种群进行分组，优质种群采用基于关键机器的变邻域搜索策略，深度挖掘优质种群最优解；3)中等种群进行交叉变异和负载平衡操作，充分发挥每个个体的搜索能力；4)劣质种群通过向优质种群学习，实现优秀基因的重组，提高种群解的多样性。
图 1 PQNSGA-II算法流程Fig. 1 Flow chart of PQNSGA-II algorithm
下载:
全尺寸图片
2.2 基于个体质量的种群分组机制
利用非支配排序等级进行个体选择可能无法精确区分具有相同等级但不同性状的个体。因此，本文引入了一个量化指标，即个体质量，来评价处于同一等级的个体之间的差别。本文设计了一种基于个体质量的种群分组机制，该分组机制不仅基于非支配排序等级，也考虑到了个体之间的综合质量差异，从而使选择过程更加精确，选择过程中也有效区分不同等级的个体，提高在复杂问题求解过程中的效率，具体操作如下。
1)首先确定种群中每个个体等级
$ R(i) $ ，根据等级计算超过该等级的个体数$ H_{i-1} $ ：$$ H_{i-1}=\sum_{j=1}^{R(i)-1} N_j $$ (19) 式中
$ N_{j} $ 是等级为$ j $ 的个体数量。2)计算个体
$ {i} $ 的质量$ Q(i) $ ，其公式为$$ Q(i)=N-N_{i}-H_{i-1} $$ (20) 式中：
$ {i} $ 为个体在种群中的索引，$ N $ 为种群规模，$ N_{i} $ 为与个体$ {i} $ 在同一等级的个体数，$ H_{i-1} $ 为所有高于个体$ {i} $ 等级的个体数。3)基于所构建的
$ Q(i) $ 对个体进行分组，按照个体质量从高到低被分为优质种群、中等种群和劣质种群，确保该分组结果反映个体质量差异。2.3 编码和解码
根据问题特征设计了4层编码方式，分别为工序排序(operation sequence, OS)、机器选择(machine selection, MS)、运输时间选择(transportation time selection, TS)和预维护选择(preventive maintenance selection, PS)。每层编码长度为工序的总数。OS编码值表示工件号，同编码值出现次数即为工序号。MS表示对应工序所选机器集中的加工机器，按照
$ J_{1}-J_{2}-J_{3}-J_{4} $ 排列。TS表示上一道工序和此工序的加工机器之间的运输时间，运输时间矩阵已知。PS由0和1组成，同样也与OS的序列一一对应，1代表该工序完成后立即进行PM操作，0则表示没有PM操作。编码方式如图2所示。
图 2 编码示意Fig. 2 Schematic diagram of encoding下载:
全尺寸图片
编码过程建立了工序与机器间的映射关系，确定了各工序对应的加工时间、运输时间以及PM操作安排，进而推导出工序的开始和结束时间。解码过程则将编码映射转换为可行的调度方案。高效合理的解码能够确保工序与机器的最佳匹配，避免资源浪费，提高资源利用率，最终有效缩短工件完工时间。本文设计了一种考虑运输时间和机器预维护的贪婪解码方式(greedy decoding approach considering transportation and pre-maintenance, GDTP)，读取OS中依次加工的工件号，以及每道工序选择的机器序号，将工序安排在机器上，采用插空式的方法将工件向左插入机器空闲时间，从而提高机器使用率。
2.4 混合初始化
本文设计了一种考虑加工时间和机器负载的混合初始化方法(hybrid initialization method, HIM)。MS采用GLR[16]方法进行初始化，包括全局选择(global selection, GS)、局部选择(local selection, LS)和随机选择(random selection, RS)，同时还考虑了机器负载平衡。针对GS从全局角度分配工序到机器上，考虑当前可用机器的负载水平，选择当前负载最小的机器进行工序分配，避免产生负载过大的机器。LS通过在每个工件可选机器集内进行选择，尽可能达到局部的机器负载均衡。RS通过随机分配工序到可选机器，促进初始种群的多样性。OS编码是随机生成的。TS编码根据对应MS的编码生成。通过前3层编码的初始化，根据工件工序在各机器上的加工顺序，由式(4)计算加工后的可靠性，并与可靠性阈值比较，若低于阈值则需要PM，否则不需要PM，生成0或1序列构成PS编码。该混合初始化方法生成的初始种群质量高且具备多样性，还考虑了机器负载平衡，为算法提供了良好的起点。
2.5 优质种群局部搜索策略
优质种群局部搜索策略(dominant population local search strategy, DPLS)通过邻域搜索操作挖掘优质个体周围的可能解，找到更优的调度方案，帮助优质个体跳出局部最优。本文针对OS层和MS层分别进行操作，具体操作如下。
1) OS邻域搜索策略
关键路径上的工序调整对最终解的质量具有显著影响，定义OS的邻域操作为基准交换，关键路径产生邻域解的方法在调度上已得到了成功的应用[17-20]，对提取的关键路径执行以下基准。
基准1 若首关键块包含两道及以上工序，交换其末尾相连的两道工序；
基准2 若尾关键块包含两道及以上工序，交换其块首相连的两道工序；
基准3 若中间关键块包含三道及以上工序，交换块首和倒数第二道工序，交换块尾和第二道工序；
基准4 若交换过程中两道工序为同一工件的不同工序，则不进行交换。
2) MS邻域搜索策略
关键机器通常指负载最大的机器，承担了最多任务的机器，即瓶颈机器。这是因为当一个或少数几个机器负载过高时，它们可能成为系统整体性能的瓶颈，限制了任务完成的速度和效率。减少瓶颈机器的负载，可以降低机器故障率，提升整个调度的效率和可持续性。为了加强算法的寻优能力，为算法设计基于关键机器的邻域搜索策略，具体过程如下。
步骤1：计算各机器负载，从负载最大的机器上随机选择一道工序，并将其重新分配至该工序的可选机器集中的另一台机器。
步骤2：计算通过这种方式得到的新解，并将其与当前解进行比较。如果新解能够在目标空间中支配旧解，即在所有目标上新解要么更优要么不劣于旧解，新解就会取代旧解。该搜索策略聚焦在种群中具有支配表现的个体，旨在改善优质解，从而提高算法的收敛速度和种群质量。
2.6 中等种群全局搜索操作
在染色体的OS、MS、TS和PS的4层编码结构中，OS和MS是显性基因参与交叉和变异操作，而TS和PS是隐性基因不参与操作，但会随显性基因变化更新调整。因此，中等种群的交叉和变异操做主要针对OS层和MS层进行：OS层的交叉操作，采用改进优先工序交叉(improved precedence operation crossover，IPOX)[21]方法，而MS层则采用多点交叉(multiple points crossover，MPX)方法。中等种群的OS层和MS层采用不同变异方式，OS变异采用两点插入变异方式对工序层进行变异，操作步骤如图3所示，具体操作如下：1)随机选取两个位置
$ l_{1} $ 和$ l_{2} $ ，$ l_{1} $ 位于$ l_{2} $ 之前；2)将$ l_{2} $ 及其后面的编码插入到$ l_{1} $ 后，从而实现两点插入变异。
图 3 OS变异图Fig. 3 OS variant下载:
全尺寸图片
这种变异方式增加了染色体的多样性，提高了算法的搜索效率。随机选择不同的位置进行插入，在搜索空间中探索更多的解空间，从而增强算法的全局搜索能力。只插入两个位置之间的编码，保证变异后的染色体不是非法解。
对于MS的变异操作，本文设计了基于外部档案引导的机器负载平衡策略(external-archive guided machine load balancing strategy, EGMLBS)。该策略根据外部档案中所有当前最优解的机器负载情况，通过工序转移的方法，从而平衡各机器负载，更加精准地引导当前搜索阶段的局部探索，提高算法的搜索效率。
2.7 劣质种群学习策略
本文设计一种劣质种群学习策略来提高搜索效率，让劣质个体从优质个体中学习优良基因，从而提高劣质个体的优良程度。优质个体的OS和MS具有较高的优秀基因，劣质个体通过学习这些信息，能更快地找到全局最优解。学习策略的操作过程如图4所示，具体操作步骤如下：
图 4 劣质种群学习策略Fig. 4 Learning strategies for inferior populations下载:
全尺寸图片
1)选择优质种群父代P1，劣质种群父代P2，在P1、P2上随机选择两个交叉点r1和r2；
2)将P1在交叉点r1和r2之间的基因位直接复制到子代C2对应的基因位中，将P2中r1和r2之外的基因位保留到C2中；
3)对生成的C2进行非法值检查，若子代C2中某个工件的某个工序出现的次数超过该工件的总工序数，则从剩余可加工的工序中随机选择一个替换非法基因位。
劣质种群学习策略使劣质个体能更好地继承优质体优良基因，保持种群多样性，加快求解全局最优解的速度，提高种群解的质量。
3. 实验分析
3.1 算例生成与参数设置
为测试PQNSGA-II算法的性能，本文运行环境为AMD Ryzen 7处理器（主频2.9 GHz）、16 GB内存及Windows 10操作系统。通过正交试验确定最优参数组合：种群数量200、迭代次数100、交叉概率0.8、变异概率0.2。
综合考虑预维护的车间生产特性，拓展标准算例以验证改进策略和算法的有效性。此外，对某复合材料制造企业的生产数据进行整理，提取5个不同规模的生产车间的实例，验证算法求解实际生产问题的能力。通过对Brandimarte[22]的FJSP算例(K-data)进行拓展，生成了10组测试算例。其中，机器之间的运输时间Tke
$ \in $ (0,5] h，$ {e_{p_k}} \in [10,15]{\text{ kW}} $ ，$ {e_{i_k}} \in [1,3]{\text{ kW}} $ ，$ e_{t_k} = 3{\text{ kW}} $ ，${R_{{\mathrm{th}}}} = 0.95$ 。3.2 策略有效性分析
为了验证PQNSGA-II算法改进策略的有效性，采用控制变量法进行排列组合，得到了如表2所示的8种算法（分别采用了HIM、EGMLBS和DPLS策略的不同组合）。通过比较这些算法的性能，验证改进策略的有效性。
表 2 选择不同策略的8种算法Table 2 Eight algorithms for different selected strategies策略 PQNSGA-NO PQNSGA-H PQNSGA-E PQNSGA-D PQNSGA-HE PQNSGA-HD PQNSGA-ED PQNSGA-II HIM — √ — — √ √ — √ EGMLBS — — √ — √ — √ √ DPLS — — — √ — √ √ √ 注：“√”表示当前算法选择该策略，“—”表示当前算法无该策略。 将8种算法分别独立运行20次，取每次迭代的并集的Pareto非支配解集作为求解前沿线。计算各算法在迭代过程中采用反世代距离（inverse generational distance, IGD）[23]平均值，绘制出收敛曲线如图5所示。
图 5 8种算法IGD收敛曲线Fig. 5 IGD convergence curves of eight algorithms下载:
全尺寸图片
如图5所示，种群在第1代分化明显，使用HIM策略的算法均表现出更好的IGD值，说明HIM策略能生成更高质量的初始解，为算法提供了较高的搜索起点。对比PQNSGA-NO和PQNSGA-E可见，PQNSGA-E在整个迭代过程中的IGD值明显低于PQNSGA-NO，这说明EGMLBS策略对个体质量的提升效果显著，根据外部档案中当前最优解的机器负载信息进行负载平衡操作，增强了算法的搜索能力。进一步比较PQNSGA-NO和PQNSGA-D曲线可以发现，PQNSGA-NO的IGD值在37代之前与PQNSGA-D差距不明显，但在迭代后期显著高于PQNSGA-D，这表明DPLS策略在迭代后期发挥了作用，帮助算法跳出局部最优，找到更优解。在PQNSGA-D基础上融合全局搜索策略EGMLBS的PQNSGA-ED明显优于PQNSGA-D，说明全局搜索策略EGMLBS有效地提高了解集的质量，为算法获取更高的搜索起点，充分发挥了局部搜索能力。由此可见，DPLS和EGMLBS两种策略相互促进，明显提升了算法性能。结合所有策略的PQNSGA-II在整个迭代过程中IGD值都是最小的，具有最优的性能，表明3种改进策略相互促进。比较PQNSGA-II和PQNSGA-HD，前者的IGD值明显优于后者，说明EGMLBS在算法中扮演着关键的角色，显著提高了算法的整体性能。
采用因素方差分析(analysis of variance, ANOVA)[24]验证各算法设计策略的显著性。将IGD和超体积（hypervolume, HV）[25]值作为响应变量，使用8种算法分别求解，ANOVA分析结果如表3所示（其中，F值反映策略对响应变量的影响程度，F值越大说明该策略的作用越大；P值反映策略对响应变量的显著性影响，若P小于0.05则说明该策略对响应变量的变异贡献显著）。
表 3 ANOVA方差分析结果Table 3 ANOVA analysis of variance results策略 以HV为响应变量 以IGD为响应变量 F P F P HIM 9.1018 0.0393 4.3425 0.1056 EGMLBS 98.0658 0.0006 75.9829 0.0010 DPLS 15.1600 0.0176 8.4065 0.0441 注：加粗为指标达到最优。 表3结果显示，EGMLBS策略在HV和IGD两个指标上都达到了最大的均方值和F值，表示该策略对算法影响程度最大，且P值远低于0.05，说明了EGMLBS策略具有显著性，在优化过程中起到了关键作用。相比之下，HIM策略的均方值和F值最小，说明此策略相对其他两种策略对算法影响最小。然而，HIM策略在HV指标上P<0.05，表明其在增强算法多样性上有效；在IGD指标上P>0.05，意味着在逼近最优前沿解集时HIM策略不具有显著性。这说明HIM策略在初始化阶段产生高质量和多样化的解集，使种群覆盖更广泛的搜索空间，但在提升解集与参考前沿接近程度上，需要结合其他策略来增强IGD指标。DPLS策略在HV和IGD指标上的均方值和F值均适中，这说明了DPLS策略可以提高解的多样性，有助于生成接近最优前沿的解集合。特别地，其在IGD指标上，P值接近于临界值0.05，表明DPLS策略作为一种局部搜索策略，帮助算法跳出局部最优，影响较为显著。
3.3 算法性能验证
为了进一步验证算法的有效性，将PQNSGA-II算法与群智能体算法中的混合人工蜂群算法(hybrid artificial bee colony algorithm, HABC)[26]、多目标优化算法中的Jaya算法[27]、基于自然选择原理的多目标遗传(multiple objective genetic algorithm, MOGA)[28]和基于社会模型演化的帝国竞争算法(imperial competition algorithm, ICA)[29]进行比较，其中，ICA和Jaya未采用启发式的局部搜索策略，会导致算法在后期搜索乏力而陷入局部最优。采用反世代距离IGD(DIG)、超体积HV(VH)和贡献率（contribution rate, CR）(RC)[30]指标对算法的多样性、收敛性和分布性等性能进行了综合评价。
1) IGD用于衡量算法所得的近似解集与真实Pareto前沿之间的接近程度。DIG值越小，表明算法找到的解集不仅覆盖了真实前沿，而且分布得也足够均匀。其公式为
$$ D_\mathrm{IG}=\frac{\displaystyle\sum_{\bar{r} \in P_{\mathrm{F}}^*} d^{\prime} \bar{r}}{N} $$ (21) 式中：
$P_{\mathrm{F}}^* $ 为Pareto前沿解集，$ {d{'}}\bar r = {\text{mi}}{{\text{n}}_{\bar q \in P_{\mathrm{F}}}}\left| {\bar r - \bar q} \right| $ 为$P_{\mathrm{F}}^* $ 上的点$ \bar r $ 到最终解集PF中个体$ \bar q $ 的最小欧氏距离，N为非支配解的个数。2) VH用于度量算法在目标空间中所能达到的解的多样性和覆盖面积。VH值越大表明解集的质量和多样性越好，算法的综合性能较好。其公式为
$$ { {V_{\mathrm{H}} = }}{\mathrm{volume}}\left( {\bigcup_{i{{= 1}}}^{P_{\mathrm{F}}} {{u_i}} } \right) $$ (22) 式中
$ {u_i} $ 是在得到的PF中的一个解和参考点之间形成的超立方体。3) RC指算法求得的解集中能够“覆盖”真实Pareto前沿的比例，RC越大说明算法寻优能力越好，其公式为
$$ {{R_{\mathrm{C}}}} = \frac{{\left| {\left\{ {X\left| {X \in P_{\mathrm{F}}\& X \in P_{\mathrm{F}}^* } \right.} \right\}} \right|}}{{\left| {P_{\mathrm{F}}^* } \right|}} $$ (23) 式中：
$P_{\mathrm{F}}^* $ 是对比算法生成的非支配解集，收集所有对比算法的PF，取并集后重新进行非支配排序，获得最优前沿解集$P_{\mathrm{F}}^* $ 。表4给出了各算法在类比航空复合材料生产问题的仿真算例中的对比结果。
表 4 5种算法的IGD、HV和CR对比结果(测试算例)Table 4 Comparison results of five algorithms of IGD, HV, and CR (test case)算例 指标 Jaya MOGA ICA HABC PQNSGA-II TPMK01 IGD 0.1159 0.2110 0.2847 0.0749 0.0570 HV 0.8381 0.6808 0.7443 0.8746 0.8842 CR 0 0 0 0.3750 0.6250 TPMK02 IGD 0.0766 0.1983 0.4745 0.0235 0.0068 HV 0.8854 0.7604 0.6792 0.9724 0.9777 CR 0 0 0 0.0769 0.9231 TPMK03 IGD 0.2136 0.4358 0.3127 0.1072 0.1898 HV 0.8362 0.7411 0.7658 0.8767 0.9399 CR 0.0556 0 0 0.3611 0.5833 TPMK04 IGD 0.1044 0.1778 0.3402 0.1061 0.0009 HV 0.9039 0.8531 0.7360 0.9326 0.9565 CR 0.0938 0 0 0 0.9063 TPMK05 IGD 0.1183 0.0498 0.3540 0.0952 0.0198 HV 0.8984 0.9290 0.7396 0.9044 0.9698 CR 0.0435 0.2174 0 0 0.7391 TPMK06 IGD 0.1755 0.4294 0.5171 0.2603 0.1384 HV 0.8128 0.6700 0.5970 0.7650 0.8691 CR 0.0909 0.1132 0.0682 0.1136 0.6818 TPMK07 IGD 0.0575 0.0455 0.2806 0.0563 0.0399 HV 0.9189 0.8520 0.7546 0.9171 0.9391 CR 0.0690 0 0 0.2759 0.6552 TPMK08 IGD 0.1865 0.1795 0.1554 0.1574 0.0212 HV 0.8542 0.8564 0.8864 0.9053 0.9331 CR 0.0333 0.0333 0 0.2677 0.6661 TPMK09 IGD 0.6201 0.5262 0.4991 0.5290 0.1022 HV 0.5102 0.5669 0.7111 0.5578 0.8658 CR 0.1071 0.0769 0.0577 0.1346 0.6346 TPMK10 IGD 0.2030 0.4173 0.4747 0.3486 0.1314 HV 0.9370 0.7433 0.7011 0.7699 0.9643 CR 0.0962 0 0 0.1714 0.7714 注：粗体表示指标达到最优。 从表4中的CR指标可以看出，PQNSGA-II算法在所有测试算例中均取得最优值，体现了其解集在非支配排序上的优势。这是因为算法在初始化阶段考虑了加工时间和机器负载，不仅有效地生成了高质量的初始种群，还通过随机化机器编码增强了种群的多样性，进而提升了算法的全局探索能力，使解集均匀地分布在Pareto前沿上。除TPMK03算例外，PQNSGA-II算法的IGD指标均小于其他4种算法，表明PQNSGA-II算法的变异操作和机器负载平衡策略避免了算法陷入局部最优，同时基于关键机器的邻域搜索策略进一步提高了调度方案的搜索效率，确保其解集更紧密地逼近真实Pareto前沿。10个算例中PQNSGA-II算法的HV指标均为最优值，可见PQNSGA-II算法的搜索效率明显高于其他算法，这是由于全局搜索操作融合了父代优秀的基因，获得更高质量的子代，增强目标空间解的多样性，拓展了前沿面的覆盖面积，进一步增强了算法的性能。
3.4 实例分析
为进一步验证PQNSGA-II算法求解实际案例的有效性，通过整理分析某航空复合材料制造企业生产车间的数据，提取5个应用实例(TPHK01～TPHK05)的加工信息，表5给出了实例TPHK01的加工信息，包括工件名称、工序名称及其加工时间。表6则提供了机器相关能耗、维护时间以及机器之间的运输时间，其中单位运输能耗为3 kW。
表 5 实例TPHK01加工信息Table 5 Processing information of TPHK01 instance工件 工序1 工序2 工序3 工序4 工序5 工序6 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 J1 车外圆 10，M1
16，M2铣键槽 15，M3
14，M4镗孔 8，M6 车槽 8，M1
9，M2车端面 6，M1
4，M2检验 6，M7 J2 镗孔 5，M6 数控车 6，M5 铣键槽 2，M3
2，M4车端面 10，M1
9，M2铣平面 6，M3
8，M4车外圆 8，M1
12，M2J3 铣平面 6，M3
5，M4钳 4，M9 检验 4，M7 数控车 3，M5 镗孔 4，M6 车外圆 5，M1
6，M2J4 车外圆 4，M1
5，M2数控车 6，M5 车槽 6，M1
8，M2铣键槽 8，M3
6，M4镗孔 3，M6 铣平面 6，M3
4，M4J5 热处理 8，M8 车外圆 5，M1
5，M2车槽 14，M1
12，M2车端面 8，M1
6，M2铣平面 9，M3
8，M4— — J6 车端面 10，M1
8，M2铣键槽 8，M3
10，M4铣平面 6，M3
8，M4钳 5，M9 车槽 6，M1
9，M2数控车 5，M5 J7 车槽 9，M1
8，M2镗孔 3，M6 车外圆 5，M1
5，M2数控车 3，M5 检验 6，M7 车端面 2，M1
3，M2J8 车槽 12，M1
11，M2车端面 6，M1
5，M2镗孔 6，M6 铣平面 12，M3
10，M4铣键槽 8，M3
7，M4热处理 4，M8 表 6 机器相关信息及运输时间Table 6 Machine information and transportation time能耗/维护时间/运输时间 变量名 M1 M2 M3 M4 M5 M6 M7 M8 M9 能耗/kW $e_{p_k} $ 12.5 13.0 12.0 12.0 14.0 13.5 11.8 12.0 12.5 $e_{i_k} $ 1.5 1.0 2.75 1.75 2.0 1.5 1.2 1.0 1.5 维护时间 $T_{\mathrm{PM}} $ 3.0 5.0 4.0 5.0 3.0 6.0 7.0 4.0 4.0 机器到机器之间的
运输时间/hM1 0 2.6 2.2 3.0 4.8 2.6 2.8 3.3 3.1 M2 3.0 0 1.2 3.6 3.2 3.7 1.8 2.3 3.6 M3 4.5 2.1 0 2.2 3.9 4.7 4.6 2.8 4.8 M4 2.4 2.0 3.9 0 3.3 4.2 4.1 3.9 3.9 M5 2.8 2.3 3.9 2.9 0 2.9 4.5 4.5 2.6 M6 4.9 1.6 4.5 2.4 2.8 0 2.1 3.9 4.3 M7 1.2 2.4 3.3 4.2 3.6 2.7 0 1.1 1.5 M8 4.9 1.5 1.3 4.1 3.1 4.9 3.7 0 1.2 M9 1.8 4.5 4.7 3.7 2.5 5.0 1.5 2.8 0 采用PQNSGA-II算法求解TPHK01实例，得到最佳的调度方案甘特图如图6所示。图中采用统一颜色标识同一工件的所有工序：每个工序块上方的数字表示工件编号，下方数字表示工序编号；黄色区块表示机器间运输时间，红色区块标注'PM-'表示当前机器需要预维护。
图 6 TPHK01实例甘特图Fig. 6 Gantt chart of TPHK01 instance下载:
全尺寸图片
分别采用HABC[18]、Jaya[19]、MOGA[20]、ICA[21]和PQNSGA-II算法求解实际生产调度实例，对比结果如表7所示。从表7可以看出，PQNSGA-II算法在IGD、HV和CR指标上均为最优，说明PQNSGA-II在求解实际生产车间调度问题上具有明显优势。从CR指标可以看出，PQNSGA-II对非支配前沿的贡献度在5个实例上最高，说明基于种群划分的搜索策略和针对不同种群的局部搜索策略充分挖掘了解空间，提升了算法的寻优能力。PQNSGA-II算法最优的IGD和HV指标说明算法在搜索过程中能够搜索到更多的非支配解，具有更优的多样性和收敛性。应用实例结果表明提出的PQNSGA-II算法具有优异性能，可有效地求解实际生产调度问题。
表 7 5种算法的IGD、HV和CR对比结果(实例)Table 7 comparison results of IGD, HV and CR of the five algorithms (real-world case)实例 指标 Jaya MOGA ICA HABC PQNSGA-II TPHK01 IGD 0.7110 0.7333 0.7467 0.0779 0.0163 HV 0.5524 0.5328 0.5255 0.9031 0.9920 CR 0 0 0 0.4375 0.5625 TPHK02 IGD 0.4444 0.5453 0.4809 0.2248 0 HV 0.6666 0.6251 0.6588 0.7845 0.9909 CR 0 0 0 0 1 TPHK03 IGD 0.7281 0.6110 0.7105 0.1941 0 HV 0.5596 0.6301 0.6333 0.8864 0.9952 CR 0 0 0 0 1 TPHK04 IGD 0.7418 0.8103 0.7035 0.1264 0.0140 HV 0.5517 0.5360 0.5544 0.9615 0.9897 CR 0 0 0 0.2727 0.7273 TPHK05 IGD 0.4048 0.8936 0.9212 0.1311 0.0414 HV 0.6550 0.3632 0.3497 0.9040 0.9757 CR 0.06667 0.0333 0 0.1000 0.8000 注：加粗为指标达到最优。 4. 结束语
为降低机器故障对生产流程的影响，本文提出机器预维护机制，对机器进行预维护，建立了考虑运输时间和机器预维护的柔性作业车间调度模型，调度目标包括最小化最大完工时间、瓶颈机器负载和总能耗。提出一种PQNSGA-II算法，利用种群分组来解决此类问题，通过4层编码方式和贪婪解码方式，均衡加工时间和机器负载的初始化方式，针对不同分组的种群采取针对性优化策略，发挥不同种群个体的搜索能力；设计交叉变异、基于外部档案引导的机器负载平衡和基于关键机器的邻域搜索策略来提高算法的寻优能力。通过标准算例验证改进策略的有效性，实验结果表明所提算法能够有效解决此类问题，进一步应用在航空复合材料生产实例中，实验结果表明PQNSGA-II算法在实例优化中的有效性。
-
图 1 PQNSGA-II算法流程
Fig. 1 Flow chart of PQNSGA-II algorithm
下载:
全尺寸图片
图 2 编码示意
Fig. 2 Schematic diagram of encoding
下载:
全尺寸图片
图 3 OS变异图
Fig. 3 OS variant
下载:
全尺寸图片
图 4 劣质种群学习策略
Fig. 4 Learning strategies for inferior populations
下载:
全尺寸图片
图 5 8种算法IGD收敛曲线
Fig. 5 IGD convergence curves of eight algorithms
下载:
全尺寸图片
图 6 TPHK01实例甘特图
Fig. 6 Gantt chart of TPHK01 instance
下载:
全尺寸图片
表 1 符号定义
Table 1 Symbol definitions
符号 定义 n 工件总数 m 机器总数 hi 工件号为i的工序数 i 工件序号, i=1,2,···,n j 工序序号, j=1,2,···, hi k,e 机器序号, k,e=1,2,···,m J 所有工件集合 M 所有机器集合 Ji 第i号工件 Mk 第k台机器 Oij 工件i的第j道工序 Mij Oij可选机器集 Pijk Oij于Mk的加工时间 Tke 工件从机器k到机器e运输时间 $T_{{\mathrm{PS}}_{kv}} $ Mk第v次预维护的开始时间 $ T_{{\mathrm{PE}}_{kv}} $ Mk第v次预维护的结束时间 $T_{{\mathrm{PM}}_{kv}} $ Mk第v次预维护的维护时间 Sij Oij加工开始时间 Cij Oij加工结束时间 Ci Ji完成时间 E 总能耗 EP 加工能耗 EI 空载能耗 ET 运输能耗 $ e_{p_k} $ Mk单位加工能耗 $e_{i_k} $ Mk单位空载能耗 $e_{t_k} $ Mk单位运输能耗 Vk Mk的预维护次数 Cmax 总加工完成时间 Xijk 0−1决策变量，当Oij选择在Mk上加工，
则Xijk=1，否则Xijk=0Yijxyk 0−1决策变量，当Oij在Oxy之前在Mk加工时，则Yijxyk=1，否则Yijxyk=0 Zike 0−1决策变量，当工件i从Mk运输到Me时，
则Zike =1，否则Zike =0L 一个很大的正数 表 2 选择不同策略的8种算法
Table 2 Eight algorithms for different selected strategies
策略 PQNSGA-NO PQNSGA-H PQNSGA-E PQNSGA-D PQNSGA-HE PQNSGA-HD PQNSGA-ED PQNSGA-II HIM — √ — — √ √ — √ EGMLBS — — √ — √ — √ √ DPLS — — — √ — √ √ √ 注：“√”表示当前算法选择该策略，“—”表示当前算法无该策略。 表 3 ANOVA方差分析结果
Table 3 ANOVA analysis of variance results
策略 以HV为响应变量 以IGD为响应变量 F P F P HIM 9.1018 0.0393 4.3425 0.1056 EGMLBS 98.0658 0.0006 75.9829 0.0010 DPLS 15.1600 0.0176 8.4065 0.0441 注：加粗为指标达到最优。 表 4 5种算法的IGD、HV和CR对比结果(测试算例)
Table 4 Comparison results of five algorithms of IGD, HV, and CR (test case)
算例 指标 Jaya MOGA ICA HABC PQNSGA-II TPMK01 IGD 0.1159 0.2110 0.2847 0.0749 0.0570 HV 0.8381 0.6808 0.7443 0.8746 0.8842 CR 0 0 0 0.3750 0.6250 TPMK02 IGD 0.0766 0.1983 0.4745 0.0235 0.0068 HV 0.8854 0.7604 0.6792 0.9724 0.9777 CR 0 0 0 0.0769 0.9231 TPMK03 IGD 0.2136 0.4358 0.3127 0.1072 0.1898 HV 0.8362 0.7411 0.7658 0.8767 0.9399 CR 0.0556 0 0 0.3611 0.5833 TPMK04 IGD 0.1044 0.1778 0.3402 0.1061 0.0009 HV 0.9039 0.8531 0.7360 0.9326 0.9565 CR 0.0938 0 0 0 0.9063 TPMK05 IGD 0.1183 0.0498 0.3540 0.0952 0.0198 HV 0.8984 0.9290 0.7396 0.9044 0.9698 CR 0.0435 0.2174 0 0 0.7391 TPMK06 IGD 0.1755 0.4294 0.5171 0.2603 0.1384 HV 0.8128 0.6700 0.5970 0.7650 0.8691 CR 0.0909 0.1132 0.0682 0.1136 0.6818 TPMK07 IGD 0.0575 0.0455 0.2806 0.0563 0.0399 HV 0.9189 0.8520 0.7546 0.9171 0.9391 CR 0.0690 0 0 0.2759 0.6552 TPMK08 IGD 0.1865 0.1795 0.1554 0.1574 0.0212 HV 0.8542 0.8564 0.8864 0.9053 0.9331 CR 0.0333 0.0333 0 0.2677 0.6661 TPMK09 IGD 0.6201 0.5262 0.4991 0.5290 0.1022 HV 0.5102 0.5669 0.7111 0.5578 0.8658 CR 0.1071 0.0769 0.0577 0.1346 0.6346 TPMK10 IGD 0.2030 0.4173 0.4747 0.3486 0.1314 HV 0.9370 0.7433 0.7011 0.7699 0.9643 CR 0.0962 0 0 0.1714 0.7714 注：粗体表示指标达到最优。 表 5 实例TPHK01加工信息
Table 5 Processing information of TPHK01 instance
工件 工序1 工序2 工序3 工序4 工序5 工序6 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 名称 时间/h，机器 J1 车外圆 10，M1
16，M2铣键槽 15，M3
14，M4镗孔 8，M6 车槽 8，M1
9，M2车端面 6，M1
4，M2检验 6，M7 J2 镗孔 5，M6 数控车 6，M5 铣键槽 2，M3
2，M4车端面 10，M1
9，M2铣平面 6，M3
8，M4车外圆 8，M1
12，M2J3 铣平面 6，M3
5，M4钳 4，M9 检验 4，M7 数控车 3，M5 镗孔 4，M6 车外圆 5，M1
6，M2J4 车外圆 4，M1
5，M2数控车 6，M5 车槽 6，M1
8，M2铣键槽 8，M3
6，M4镗孔 3，M6 铣平面 6，M3
4，M4J5 热处理 8，M8 车外圆 5，M1
5，M2车槽 14，M1
12，M2车端面 8，M1
6，M2铣平面 9，M3
8，M4— — J6 车端面 10，M1
8，M2铣键槽 8，M3
10，M4铣平面 6，M3
8，M4钳 5，M9 车槽 6，M1
9，M2数控车 5，M5 J7 车槽 9，M1
8，M2镗孔 3，M6 车外圆 5，M1
5，M2数控车 3，M5 检验 6，M7 车端面 2，M1
3，M2J8 车槽 12，M1
11，M2车端面 6，M1
5，M2镗孔 6，M6 铣平面 12，M3
10，M4铣键槽 8，M3
7，M4热处理 4，M8 表 6 机器相关信息及运输时间
Table 6 Machine information and transportation time
能耗/维护时间/运输时间 变量名 M1 M2 M3 M4 M5 M6 M7 M8 M9 能耗/kW $e_{p_k} $ 12.5 13.0 12.0 12.0 14.0 13.5 11.8 12.0 12.5 $e_{i_k} $ 1.5 1.0 2.75 1.75 2.0 1.5 1.2 1.0 1.5 维护时间 $T_{\mathrm{PM}} $ 3.0 5.0 4.0 5.0 3.0 6.0 7.0 4.0 4.0 机器到机器之间的
运输时间/hM1 0 2.6 2.2 3.0 4.8 2.6 2.8 3.3 3.1 M2 3.0 0 1.2 3.6 3.2 3.7 1.8 2.3 3.6 M3 4.5 2.1 0 2.2 3.9 4.7 4.6 2.8 4.8 M4 2.4 2.0 3.9 0 3.3 4.2 4.1 3.9 3.9 M5 2.8 2.3 3.9 2.9 0 2.9 4.5 4.5 2.6 M6 4.9 1.6 4.5 2.4 2.8 0 2.1 3.9 4.3 M7 1.2 2.4 3.3 4.2 3.6 2.7 0 1.1 1.5 M8 4.9 1.5 1.3 4.1 3.1 4.9 3.7 0 1.2 M9 1.8 4.5 4.7 3.7 2.5 5.0 1.5 2.8 0 表 7 5种算法的IGD、HV和CR对比结果(实例)
Table 7 comparison results of IGD, HV and CR of the five algorithms (real-world case)
实例 指标 Jaya MOGA ICA HABC PQNSGA-II TPHK01 IGD 0.7110 0.7333 0.7467 0.0779 0.0163 HV 0.5524 0.5328 0.5255 0.9031 0.9920 CR 0 0 0 0.4375 0.5625 TPHK02 IGD 0.4444 0.5453 0.4809 0.2248 0 HV 0.6666 0.6251 0.6588 0.7845 0.9909 CR 0 0 0 0 1 TPHK03 IGD 0.7281 0.6110 0.7105 0.1941 0 HV 0.5596 0.6301 0.6333 0.8864 0.9952 CR 0 0 0 0 1 TPHK04 IGD 0.7418 0.8103 0.7035 0.1264 0.0140 HV 0.5517 0.5360 0.5544 0.9615 0.9897 CR 0 0 0 0.2727 0.7273 TPHK05 IGD 0.4048 0.8936 0.9212 0.1311 0.0414 HV 0.6550 0.3632 0.3497 0.9040 0.9757 CR 0.06667 0.0333 0 0.1000 0.8000 注：加粗为指标达到最优。 -
[1] WU Mingliang, YANG Dongsheng, ZHOU Bowen, et al. Adaptive population NSGA-III with dual control strategy for flexible job shop scheduling problem with the consideration of energy consumption and weight[J]. Machines, 2021, 9(12): 344. [2] LI Yibin, HUANG Weixing, WU R, et al. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem[J]. Applied soft computing, 2020, 95: 106544. [3] 吴秀丽, 张志强, 赵宁, 等. 超启发式文化基因算法优化生产与预维修集成调度问题[J]. 计算机集成制造系统, 2019, 25(8): 1885−1896. WU Xiuli, ZHANG Zhiqiang, ZHAO Ning, et al. Production scheduling and preventive maintenance plan optimization with hyper-heuristics memetic algorithm[J]. Computer integrated manufacturing systems, 2019, 25(8): 1885−1896. [4] 李聪波, 王睿, 寇阳, 等. 考虑设备预维护的柔性作业车间调度节能优化方法[J]. 机械工程学报, 2021, 57(10): 220−230. doi: 10.3901/JME.2021.10.220 LI Congbo, WANG Rui, KOU Yang, et al. Energy saving optimization method of flexible job shop scheduling considering preventive maintenance[J]. Journal of mechanical engineering, 2021, 57(10): 220−230. doi: 10.3901/JME.2021.10.220 [5] WOCKER M M, OSTERMEIER F F, WANNINGER T, et al. Flexible job shop scheduling with preventive maintenance consideration[J]. Journal of intelligent manufacturing, 2023, 35(4): 1−23. [6] NIKOLAOS R, LI An, ZHANG An, et al. Novel approach to energy-efficient flexible job-shop scheduling problems[J]. Energy, 2022, 238: 121773. [7] MENG Leilei, REN Yaping, ZHANG Biao, et al. MILP modeling and optimization of energy-efficient distributed flexible job shop scheduling problem[J]. IEEE access, 2020, 8: 191191−191203. [8] 王凌, 王晶晶. 考虑运输时间的分布式绿色柔性作业车间调度协同群智能优化[J]. 中国科学: 技术科学, 2023, 53(2): 243−257. doi: 10.1360/SST-2021-0355 WANG Ling, WANG Jingjing. A cooperative memetic algorithm for the distributed green flexible job shop with transportation time[J]. SCIENTIA SINICA technologica, 2023, 53(2): 243−257. doi: 10.1360/SST-2021-0355 [9] JIANG Tianhua, ZHU Huiqi, LIU Lu, et al. Energy-conscious flexible job shop scheduling problem considering transportation time and deterioration effect simultaneously[J]. Sustainable computing: informatics and systems, 2022, 35: 100680. [10] 柳冬, 宋豫川, 杨云帆, 等. 机器故障的柔性加工与装配作业车间分批联合调度算法[J]. 智能系统学报, 2022, 17(3): 556−567. LIU Dong, SONG Yuchuan, YANG Yunfan, et al. Batch scheduling algorithm for flexible machining and assembly job shop when the machine breaks down[J]. CAAI transactions on intelligent systems, 2022, 17(3): 556−567. [11] SUN Wei, PAN Ying, LU Xiaohong, et al. Research on flexible job-shop scheduling problem based on a modified genetic algorithm[J]. Journal of mechanical science and technology, 2010, 24(10): 2119−2125. [12] WU J, WU G D, WANG J J. Flexible job-shop scheduling problem based on hybrid aco algorithm[J]. International journal of simulation modelling, 2017, 16(3): 497−505. [13] NOUIRI M, BEKRAR A, JEMAI A. Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns[J]. Computers & industrial engineering, 2017, 112: 595−606. [14] ZHOU K, TAN C H, ZHAO Y, et al. Research on solving flexible job shop scheduling problem based on improved GWO algorithm SS-GWO[J]. Neural processing letters, 2024, 56(1): 288−298. [15] ADIRI I, FROSTIG E, KAN A H G R. Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs[J]. Naval research logistics (NRL), 1991, 38(2): 261−271. [16] 常建涛, 史尊博, 符博峰, 等. 一种多品种变批量柔性作业车间调度方法[J]. 电子机械工程, 2022, 38(5): 60−64. CHANG Jiantao, SHI Zunbo, FU Bofeng, et al. A scheduling method for multi-variety variable batch flexible job shop[J]. Electro-mechanical engineering, 2022, 38(5): 60−64. [17] ASADZADEH L. A local search genetic algorithm for the job shop scheduling problem with intelligent agents[J]. Computers & industrial engineering, 2015, 85: 376−383. [18] WANG L, WANG S Y, LIU M. A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem[J]. International journal of production research, 2013, 51(12): 3574−3592. [19] MOKHTARI H, HASANI A. An energy-efficient multi-objective optimization for flexible job-shop scheduling problem[J]. Computers & chemical engineering, 2017, 104: 339−352. [20] 赵文超, 郭鹏, 王海波, 等. 改进樽海鞘群算法求解柔性作业车间调度问题[J]. 智能系统学报, 2022, 17(2): 376−386. ZHAO Wenchao, GUO Peng, WANG Haibo, et al. Improved slap swarm algorithm for scheduling of flexible job shop[J]. CAAI transactions on intelligent systems, 2022, 17(2): 376−386. [21] 张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004(23): 83−87. ZHANG Chaoyong, RAO Yunqing, LIU Xiangjun, et al. An improved genetic algorithm or the Job-Shop scheduling problem[J]. China mechanical engineering, 2004(23): 83−87. [22] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of operations research, 1993, 41(3): 157−183. doi: 10.1007/BF02023073 [23] BOSMAN P A N, THIERENS D. The balance between proximity and diversity in multiobjective evolutionary algorithms[J]. IEEE transactions on evolutionary computation, 2003, 7(2): 174−188. doi: 10.1109/TEVC.2003.810761 [24] KHARE A, AGRAWAL S. Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness[J]. Computers & industrial engineering, 2019, 135: 780−792. [25] WHILE L, HINGSTON P, BARONE L, et al. A faster algorithm for calculating hypervolume[J]. IEEE transactions on evolutionary computation., 2006, 10(1): 29−38. doi: 10.1109/TEVC.2005.851275 [26] WANG Y F, GE J R, MIAO S, et al. Application of hybrid artificial bee colony algorithm based on load balancing in aerospace composite material manufacturing[J]. Expert systems with application, 2023, 215: 119375. doi: 10.1016/j.eswa.2022.119375 [27] 张洪亮, 徐公杰, 鲍蔷, 等. 考虑运输时间和机器预维护的柔性作业车间绿色调度[J]. 计算机集成制造系统, 2024, 30(9): 3111−3124. ZHANG Honliang, XU Gonjie, BAO Qiang, et al. Flexible job-shop green scheduling considering transportation time and machine preventive maintenance[J]. Computer integrated manufacturing systems, 2024, 30(9): 3111−3124. [28] WANG H, SHENG B, LU Q, et al. A novel multi-objective optimization algorithm for the integrated scheduling of flexible job shops considering preventive maintenance activities and transportation processes[J]. Soft computing, 2021, 25(4): 1−27. [29] LI M, LEI D. An imperialist competitive algorithm with feedback for energy-efficient flexible job shop scheduling with transportation and sequence-dependent setup times[J]. Engineering applications of artificial intelligence, 2021, 103: 104307. doi: 10.1016/j.engappai.2021.104307 [30] ZITZLER E. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach[J]. IEEE transactions on evolutionary computation, 1999, 3(4): 257−271. doi: 10.1109/4235.797969
