基于分解策略混合算法的DAJSP求解

A Hybrid Algorithm Based on Decomposition Strategy for DAJSP Solution

摘要

针对分布式装配作业车间调度问题（DAJSP），以最小化最大完工时间为目标，建立了混合整数线性规划（MILP）模型，提出了一种融合贪心策略的遗传-禁忌搜索算法（GTSAIGS）。将DAJSP分解为工件加工与产品装配的两阶段问题，在加工阶段采用启发式算法优化，针对装配阶段的调度问题设计了一种高效的贪心算法进行快速求解。40个算例的测试结果表明，相比于整体优化方法，GTSAIGS分解策略减少了计算耗时，提高了求解质量，进而验证了所提算法的有效性和优越性。

Abstract

This paper addresses the distributed assembly job-shop scheduling problem （DAJSP） by establishing a mixed-integer linear programming （MILP） model to minimize the makespan， and proposes a hybrid genetic-tabu search algorithm with a greedy strategy. The DAJSP is decomposed into two subproblems： job processing and product assembly. For the processing stage， a heuristic algorithm is applied； for the assembly stage， an efficient greedy algorithm is designed to provide a fast and effective scheduling solution. Experimental results on 40 instances show that， compared with a monolithic optimization method， the proposed decomposition strategy reduces computational time and improves solution quality， thereby validating its effectiveness and superiority.

Graphical abstract

关键词

分布式装配作业车间调度问题（DAJSP） / 最大完工时间 / 混合算法 / 贪心算法

Key words

distributed assembly job-shop scheduling / makespan / hybrid genetic-tabu search / greedy algorithm

0 引言

当前，企业间的合作生产日益普及，分布式制造已成为常见的生产模式。在汽车制造、航空航天和工程机械等行业，零部件常在不同地区的分布式工厂中生产，最后再运至总装厂进行最终装配。这种模式在充分利用不同地区生产成本和技术优势的同时也带来了跨地区工厂生产与装配协同调度的挑战。因此，研究分布式装配作业车间调度问题（distributed assembly job-shop scheduling problem，DAJSP）具有理论意义和应用价值。

DAJSP由工件分布式加工和产品装配两阶段组合而成。与作业车间调度问题（job-shop scheduling problem，JSP）相比，装配作业车间调度问题（assembly job-shop scheduling problem，AJSP）中的工件有多道工序，且工件须装配成最终产品。这一特性使得AJSP的优化需同时协调加工与装配阶段的时序约束。针对AJSP，已有研究提出了多种求解方法。对于柔性AJSP，ZHANG等^［1］提出的分布式蚁群优化算法可同时优化完工时间、总延迟时间和总工作量。SHI等^［2］提出一种将改进的扩展转移瓶颈程序和遗传算法相结合的混合算法来求解AJSP。李仲华等^［3］针对带外协的柔性AJSP，建立了以最小化最大完工时间为目标的模型，并采用改进鲸鱼动态调度算法求解。包含装配车间调度的产品综合调度优化问题中，基于工序约束链编码的遗传算法^［4］能准确体现产品各个工序之间的装配约束关系，且不会增加新的约束，保证了初始解空间的可行性和完备性，其有效性已被实验证明。

分布式作业车间调度问题（distributed job-shop scheduling problem，DJSP）是DAJSP的基础，主要研究工件在加工工厂间的分配以及各工厂内的加工顺序，以实现调度指标的最优。CHAOUCH等^［5］以最小化最大完工时间为目标，设计3个仿生算法来求解工件的工厂分配问题，并通过实验对比了三者的性能。在以最小化最大完工时间为目标的DJSP中，ŞAHMAN^［6］将机器负载排序机制和贪婪的启发式算法与离散斑点鬣狗算法相结合进行求解，取得了良好的结果。JIANG等^［7］提出一种基于分解的改进型多目标进化算法，并设计一种动态调整局部搜索算子利用率的选择策略，以最小化最大完工时间和总能耗为目标，对DJSP进行求解。WANG等^［8］提出一种解决DJSP的改进遗传算法，算法在工件分配工厂子问题中考虑个体间的相似性，在交叉过程中有效地平衡了解空间的探索和较优解基因保留的问题。

DJSP主要关注将一系列独立的工件分配到不同的工厂，并优化其在工厂内部的加工顺序，目标通常是最小化最大完工时间。DAJSP在此基础上增加了装配阶段，这意味着多个工件不再独立，而是构成最终产品的零部件，必须在各自完成加工后汇集到装配中心进行最终组装。在以最大完工时间为目标的研究中，DJSP需要平衡并缩短每个加工工厂的最大完工时间，以得到更优解。DAJSP的优化目标是包含装配工序在内的最大完工时间，单个工厂的最大完工时间影响其所关联的装配工序开工时间，进而影响最大完工时间。DAJSP的主要挑战在于引入了装配工序的齐套性约束，即一个产品的装配工序必须在其所有零部件都加工完成之后才能开始。这种约束使得分布在不同工厂、分属同一产品的各工件的调度彼此关联，形成耦合关系，增加了问题的复杂性。

目前，对DAJSP的研究尚处于起步阶段，研究也较少。TIAN等^［9］建立了以最小化最大完工时间为目标的DAJSP混合整数线性规划（mixed integer linear programming，MILP）模型，提出一种基于可变邻域搜索的遗传算法，采用三层编码表示DAJSP的3个决策过程，即将工件分配到工厂、确定每个工厂内的工序、确定产品的装配顺序。YANG等^［10］针对有转移、异构和柔性的DAJSP，以最小化最大完工时间和总能耗为目标，提出一种基于Q学习的改进型多目标遗传算法，并设计了2种交叉算子、4种变异算子和6种面向目标的邻域搜索算子，以增强算法的探索和开发能力。针对广泛存在带有车辆配送的DAJSP，杨绍文等^［11］以最小化运输和延迟惩罚总成本为优化目标，提出一种混合三维分布估计算法进行求解。

分析已有研究发现，现有DAJSP研究多将“工件分配—加工排序—装配排序”整体耦合优化，导致搜索空间大、装配阶段重复迭代耗时的问题。工件分配与加工调度确定后，装配可转化为带释放时间约束的单机排序问题，适合用规则快速求解。因此提出分解式混合算法，即在加工阶段采用“遗传算法全局搜索+禁忌搜索局部强化”提升解质量，在装配阶段采用贪心装配规则减少不必要迭代，从而在保证解质量的同时提高求解效率。

1 问题模型

1.1 问题描述

DAJSP是包含加工阶段和装配阶段的调度问题。在加工阶段，工件J₁、J₂、…、J_n 需在分布的多个工厂加工。每个工厂配置相同的机器M₁、M₂、…、M_m，且具有加工所有工件的能力。工件J_i 需按给定加工工艺路线在任一工厂的机器上依次完成若干工序。在装配阶段，一个装配工厂（仅有一台装配机器M_A）将工件装配为N_p 个不同的产品。研究假设工件在同一工厂内不同机器间的转移时间与跨工厂的运输时间忽略不计。

研究目标是确定工件的加工工厂分配、工序加工顺序和产品的装配顺序，以最小化最大完工时间C_max。此外，DAJSP有以下约束：所有机器从0时间开始可用；工件的加工应满足工艺路线约束；一台机器在同一时间最多完成一道工序；一道工序一旦在给定的机器上开始，则在完成之前不能中断；某一工件的所有工序应在一个工厂内完成。

表1所示为具有2个分布式加工工厂的DAJSP案例，案例包含产品P₁、P₂、P₃，其中，产品P₁由工件J₂、J₅、J₆组成，产品P₂由工件J₁、J₃、J₈组成，产品P₃由工件J₄、J₇组成。2个分布式加工工厂均配置机器M₁和M₂。表1给定了每个工件每道工序的加工机器和加工用时，以及每个产品的装配用时，表中空白表示该工序不在对应机器上加工。

1.2 数学建模

根据问题描述，建立MILP模型，其中，优化目标为

\mathrm{m}\mathrm{i}\mathrm{n}{C}_{\mathrm{m}\mathrm{a}\mathrm{x}}

约束条件为

\begin{array}{cc}{C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\ge C_p& \forall p\end{array}（1）

\begin{array}{cc}\sum _{f\in F}{X}_{i,f}=\mathrm{1}& \forall i\in I\end{array}（2）

\begin{array}{cc}{X}_{i,f}=X_{i,j,f}& \forall i\in I,j\in O_i,f\in F\end{array}（3）

\begin{array}{cc}{S}_{i,j+\mathrm{1}}\ge S_{i,j}+T_{i,j}& \forall i\in I,\forall j,j+\mathrm{1}\in O_i\end{array}（4）

S_{i,j}+T_{i,j}\le S_{i\mathrm{\text{'}},j\mathrm{\text{'}}}+L(\mathrm{1}-Y_{i,j,i\mathrm{\text{'}},j\mathrm{\text{'}}})+L(\mathrm{2}-X_{i,f}-X_{i\mathrm{\text{'}},f})

\forall i,i\mathrm{\text{'}}\in I,i\ne i\mathrm{\text{'}};\forall j,j\mathrm{\text{'}}\in O_i,k_{i,j}=k_{i\mathrm{\text{'}},j\mathrm{\text{'}}};\forall f\in F（5）

S_{i\mathrm{\text{'}},j\mathrm{\text{'}}}+T_{i\mathrm{\text{'}},j\mathrm{\text{'}}}\le S_{i,j}+L{Y}_{i,j,i\mathrm{\text{'}},j\mathrm{\text{'}}}+L(\mathrm{2}-X_{i,f}-X_{i\mathrm{\text{'}},f})

\forall i,i\mathrm{\text{'}}\in I,i\ne i\mathrm{\text{'}};\forall j,j\mathrm{\text{'}}\in O_i,k_{i,j}=k_{i\mathrm{\text{'}},j\mathrm{\text{'}}};\forall f\in F（6）

\begin{array}{cc}{C}_i\ge S_{i,j}+T_{i,j}& \forall i\in I,\forall j\in O_i\end{array}（7）

\begin{array}{cc}{A}_p\ge C_i& \forall i\in S_p,\forall p\in P\end{array}（8）

（9）

（10）

\begin{array}{cc}{C}_p=A_p+T_p& \forall p\in P\end{array}（11）

其中，式（1）为最大完工时间上界约束；式（2）为工件分配约束，确保每个工件必须且只能分配到一个工厂；式（3）为工序分配约束，确保同一工件的所有工序分配到同一工厂；式（4）为工件工艺路线约束，确保某工序必须在其紧前工序完成后才能开始加工，工件的首道工序无此约束；式（5）、式（6）为加工机器资源约束，确保同一机器上不同工序的加工时间不会重叠；式（7）为工件完工时间约束，确保一个工件的完工时间必须大于或等于其所有工序的完工时间；式（8）为装配齐套性约束，确保一个产品的装配必须在其所有工件完工后才能开始；式（9）和式（10）为装配机器资源约束，确保任意两个产品在装配机器上的装配时间不会重叠；式（11）计算产品完工时间。

模型相关符号如表2所示。

2 混合算法设计

本文提出一种融合贪心策略的遗传-禁忌搜索算法（genetic-tabu search algorithm incorporating greedy strategy，GTSAIGS）。GTSAIGS的核心思想是分解DAJSP，并为子问题匹配最合适的求解策略。加工阶段采用遗传算法与禁忌搜索相结合的方式进行求解。遗传算法在全局搜索中表现出色，能有效探索解空间，但局部搜索能力较弱，为提高解的质量，需结合问题特征进行局部优化。禁忌搜索算法专注于局部搜索，能有效与DAJSP的特征信息和邻域结构结合，引导搜索过程，减少搜索的盲目性，在局部范围内找到更优解。因此，将遗传算法与禁忌搜索算法相结合能很好平衡全局搜索与局部搜索，提高求得高质量解的能力。在装配阶段，基于贪心算法快速生成装配工序调度，并据此得到完整调度方案的最大完工时间C_max。通过3种算法的优势互补，混合算法在较短时间能求得DAJSP的高质量解。

2.1 遗传算法

2.1.1 编码和解码

遗传算法编码是将问题解的描述转化为算法可以处理的染色体的过程，现有DAJSP研究中的编码通常由工件的加工工厂分配、工序完成顺序和产品装配顺序三部分组成。研究发现，当工件的工厂分配和加工顺序确定后，装配阶段可依据加工结果通过贪心规则快速生成调度方案，因此本文在编码中不再显式表示装配顺序，且装配工序调度无需参与后续的交叉、变异等操作。因此，本文采用两层编码描述DAJSP解。第一层为工厂选择链，用于表示工件到工厂的分配；第二层为工序顺序链，用于表示工序完成顺序。在装配阶段，引入贪心算法来快速生成装配工序调度，简化编码且减少遗传操作与后续禁忌搜索中针对装配顺序的搜索开销。

图1所示为表1案例一个可行解的编码方案，其中，工厂选择链内的元素由1～N_f 的整数构成，位置i的整数f表示将工件J_i 分配到加工工厂f。图1中的工厂选择链表示工件J₂、J₃、J₅、J₆、J₈由工厂1中的机器加工，其余的工件由工厂2加工。工序顺序链采用基于工序的编码方式，用工件编号的重复出现次序隐式表示其各道工序的先后完成关系。链内元素由1～n的整数构成，链中第c个位置上的编号i表示工件J_i，若从左到右扫描至位置c时，编号i已出现j次，则该位置对应工件J_i 的第j道工序。结合工厂选择链并从左到右扫描工序顺序链，可确定各工序在对应加工工厂中的加工先后次序。例如，图1中的工序顺序链2→3→1→6→…表示加工顺序O_2，1→O_3，1→O_1，1→O_6，1→…。对于包含n个工件，每个分布式加工工厂具有m台机器的DAJSP，工序顺序链由n×m个整数组成，每个工件号i只能在染色体中出现m次。

在完成染色体编码设计后，初始化种群是遗传算法的起始步骤，随机编码可以最大限度地确保种群在算法初期就具备高度的多样性，实现对解空间的广泛覆盖，因此采用随机方式初始化种群。

解码是将染色体携带的编码信息转化为实际调度方案的过程。常见的解码方式有半主动解码和主动解码，半主动解码仅能保证工序按顺序尽可能早地开始，但无法改变工序的先后次序。主动解码通过搜索机器加工序列中间的空闲时段，在满足工艺约束的前提下，允许后续工序插空加工，在满足约束条件下的提前调度工序，压缩了机器的无效空闲时间。因此，本文采用主动解码方式，具体步骤如下：首先，根据工厂选择链将加工阶段划分为多个相互独立的工厂内JSP子问题。其次，依次读取工序顺序链，对于读取的某道工序，搜索其分配工厂内对应机器上的空闲时间窗，将该工序插入对应机器上满足加工耗时且不早于紧前工序完工时间的最早可行空闲时段内，从而确定所有工件的完工时间。最后，由贪心算法生成完整的调度方案，得到最大完工时间C_max。图2为图1示例编码解码得到的甘特图。

2.1.2 选择方法

遗传算法中，选择操作的作用是模拟自然界优胜劣汰的机制，引导种群向全局最优的方向搜索。为平衡算法的收敛速度与种群多样性，选择操作由两部分组成：首先采用精英保留策略直接复制部分最优个体；随后通过锦标赛选择补齐其余个体。首先选取父代种群中最优的一部分个体无条件复制到子代。然后从父代种群内随机抽取的部分个体中选出适应度最优的个体，并将其放入子代种群。重复此过程，直至子代种群的规模与父代种群相等。

2.1.3 交叉方法

交叉是决定遗传算法全局搜索能力的重要操作之一。某个个体具有较高适应度时，其基因序列中的某些片段通常表现良好。若这些优良片段在交叉过程中得到有效继承并与其他片段重新组合，就有可能产生适应度更高的后代，从而增强算法的全局搜索能力。

交叉算子的设计必须与染色体编码方式相匹配。由于本文采用的染色体编码由工厂选择链和工序顺序链两部分组成，为保证交叉后生成解的可行性，需针对两层编码的结构特点分别设计交叉方法^［12］。工厂选择链逻辑简单，易确保生成解的可行性，因此工厂选择链采用图3a所示的均匀交叉，即2个父代染色体元素以一定的概率进行交换。考虑工序顺序链的特点，采用JSP中常用的POX交叉法以继承父代的优良特征。如图3b所示，POX交叉首先将工件集随机划分为2个非空的子集Set₁和Set₂，随后将Parent1和Parent2中属于Set₁的工件分别复制到Children1和Children2中，并保留其在父代中的位置；再将Parent2和Parent1中属于Set₂的工件按照原有顺序分别填充至Children1和Children2的剩余空位中^［13］。这种交叉方式在保证解可行性的同时，实现了父代优良片段信息的传递与重组。

2.1.4 变异方法

变异是对染色体进行小幅扰动的操作，旨在保持种群的多样性，避免算法过早收敛。常见的变异方法有交换、插入和逆转等。如图4a所示，对工厂选择链采用单点随机变异，随机选中工厂选择链中的某一点，将该点的元素替换为其他可选工厂编号，实现了单个工件向其他工厂的转移。如图4b所示，对工序顺序链采用两点交换变异方式，随机选择工序顺序链中的两点并交换两点的值，实现了两道工序加工顺序的改变。

2.2 禁忌搜索

禁忌搜索算法在邻域搜索的基础上，通过设置禁忌表来避免解的重复搜索，并利用特赦准则允许某些被禁忌的优良解重新进入搜索过程。邻域结构、候选解生成和禁忌长度等因素是影响禁忌搜索算法性能的关键。

2.2.1 邻域结构

作为禁忌搜索算法的核心机制，邻域结构通过对当前解的局部扰动来生成邻域解集。为提高搜索效率并尽量减少无效及不可行的移动，邻域搜索通常作用于对目标函数值影响较大的关键工序。对于以最小化最大完工时间为目标的调度问题，这些关键工序位于当前调度方案对应析取图的关键路径上，因此需要借助析取图模型对关键路径进行分析。

JSP的析取图模型包含节点、连接弧和析取弧。节点对应工序，以及开始和结束虚拟节点；连接弧连接属于同一工件且相邻的两个工序；析取弧连接属于不同工件但在同一机器上完成的两个相邻工序^［14］。节点和弧可直观表示调度问题的工艺顺序约束和机器资源约束，将调度问题的求解转化为确定析取图中弧的去向。除了工艺约束和机器约束，DAJSP还需要考虑产品与工件之间的装配关系，为此，TIAN等^［9］在传统JSP析取图的基础上引入装配关系弧，设计了包含三类弧的DAJSP析取图模型，为后续关键路径识别及邻域结构设计提供图论基础。

如图5所示，析取图包含的虚拟节点O_begin、O_end表示调度的开始和结束。关键路径是从起点O_begin到汇点O_end的最长路径，以甘特图（图2）和图5所示的析取图模型为例，O_begin→O_2，1→O_2，2→O_5，1→O_5，2→P₁→P₃→P₂→O_end是关键路径。

关键路径由关键工序组成。某一工序是否为关键工序根据其最早开工时间和最晚开工时间判定，若工序O_i，j 满足r_{i,j}+t_{i,j}=C_{\mathrm{m}\mathrm{a}\mathrm{x}}，则该工序为关键工序，可将其加入关键路径，其中，r_i，j 为工序O_i，j 的头长度，为起点到节点O_i，j 的最长路径长度，可由染色体主动解码后得到；t_i，j 为工序的尾长度，为节点O_i，j 到汇点的最长路径长度与节点加工时间T_i，j 之和，通过对当前调度进行逆向分析得到，具体步骤如伪代码1所示：

关键块为关键路径上多个紧密相连的关键工序组成的块，如图2所示，O_2，2→O_5，1、P₁→P₃→P₂是关键块。

包含关键工序的工件为关键工件，包含关键工件的工厂为关键工厂。在工厂选择链中，针对关键工件的移动包括转移和互换两种方式。转移指将关键工件移到非关键工厂，一般移入完工时间最短的工厂，若所有工厂皆是关键工厂，则关键工件随机移到一个其他工厂。互换指选取一个关键工件，并从其他工厂中任选一个工件，将该其他工厂工件与选取的关键工件交换所属加工工厂。

工序顺序链的移动采用N7邻域结构。如图6所示，N7邻域结构的移动对象为关键块，移动操作包含关键块内的工序移动至块首之前或块尾之后，或将关键块的首工序或尾工序插入块内部。

2.2.2 禁忌搜索算法流程

结合析取图模型、工厂选择链、工序顺序链邻域结构，设计禁忌搜索算法，算法流程如伪代码2所示：

2.3 贪心算法

2.3.1 基本贪心算法

贪心算法在问题的每一步都做当前状态下最优的选择，并期望最终结果是最优。具有效率高、易于实现等优点，能在较短时间内获得令人满意的可行解。

2.3.2 基于贪心算法的装配工序调度

基于DAJSP的特性，当加工阶段的工件工厂分配与工序排序方案由启发式算法确定后，装配调度方案可由贪心策略快速求解。该方法无需对装配阶段进行编码，降低了编码复杂性，且装配阶段调度不需参与遗传算法和禁忌搜索的优化，缩短了算法的运行时间。

依据加工工序的调度结果，采用贪心算法生成装配工序调度方案的具体步骤如下：

1）初始化当前时间nowTime为0，将所有装配工序加入待调度产品列表waitlist，初始化装配工序调度序列assemblySchedule为空。根据加工工序的调度结果，将所有装配工序最早可开工时间设置为构成对应产品的所有工件的最大完工时间，并按最早可开工时间在waitlist中升序排列。

2）从waitlist中选择当前时间可开工的装配工序。若当前时间没有可开工的装配工序，则将nowTime更新为按最早可开工时间升序排列后的waitlist首元素的最早可开工时间。

3）在可选的待装配工序中选择装配时间最短的工序进行处理，并将所选工序加入assemblySchedule的末尾。装配完成后，更新当前时间为所选工序的完工时间，随后将该工序从waitlist中移除。

重复步骤2）和3），直至waitlist为空，最终求得完整的装配工序调度序列assemblySchedule。

表3所示为10个产品装配任务示例，为简便表示，直接给出每个产品的可开工时间和装配时间，采用贪心法生成装配工序调度。

表4所示为使用贪心算法对10个产品的装配工序进行调度的示例，“选择工序”这行内容对应本轮所选装配任务。

首先初始化数据，将当前时间nowTime设定为0，将所有装配工序放入待调度序列waitlist，根据可开工时间将工序升序排序，排序后的序列为P1→P8→P9→P3→P6→P5→P2→P4→P10→P7。随后，算法进入迭代循环：首先确定当前时间nowTime下的可开工工序，若无则将nowTime更新为waitlist中第一个工序的可开工时间；接着，在可选工序中选择装配用时最短的工序进行处理，将所选工序加入assemblySchedule最后位置，更新nowTime为该工序的完工时间，并将所选工序从waitlist中移除。重复此过程直至waitlist为空。最终得到的调度顺序为P1→P8→P9→P3→P6→P5→P10→P4→P7→P2。

3 算法总体框架与流程

本文提出的GTSAIGS基于分解策略，以工件完工时间作为解耦点，将DAJSP分解为工件加工调度和产品装配调度两阶段问题，两阶段通过工件完工时间与适应度值实现阶段间信息传递。

加工调度由遗传算法与禁忌搜索完成，通过全局搜索确定工件在各工厂的分配及加工顺序，随后对关键路径进行深度搜索以跳出局部最优。加工阶段的输出是所有工件的完工时间集合｛C_i ｝。装配调度采用贪心策略求解，将加工阶段输出的｛C_i ｝作为装配阶段的齐套性约束。贪心算法依据“当前可开工时间装配用时最短工序优先原则”快速生成装配调度方案，进而得到最终最大完工时间C_max，将C_max传递给主算法并作为染色体的适应度，指导种群进化。混合算法具体步骤如伪代码3所示：

4 实验测试

由于目前尚缺乏统一的DAJSP基准算例，本文采用文献［9］设计的一系列算例对算法进行评估。这一系列算例基于Ta01-Ta40设计，为每个算例新增产品数量、分布式加工车间的数量、每个产品的装配时间、工件和产品之间的包含关系，以适用于DAJSP。随后通过正交试验确定算法参数组合，并在此基础上开展对比实验与结果分析。

4.1 参数设置

正交试验在表5所列参数水平范围内进行，以确定算法的较优参数组合。实验基于DA09算例进行，采用相对偏差（RD）

D_{\mathrm{R}}=\frac{{\overline{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-C_{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}{C_{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}（12）

描述实验结果，其中，{\overline{C}}_{\mathrm{m}\mathrm{a}\mathrm{x}}、C_maxbest分别为参数组合运行5次获得的最大完工时间的平均值和最优值。

根据图7所示主效应图，分别比较popuSize、P_c和P_ER在不同水平下对应的D_R均值，优先选择能使D_R均值达到最小的参数水平作为候选组合。由图7可见，popuSize=50、P_c=0.9和P_ER=5%对应的D_R均值均处于各自因素的最优水平。算法中未参与正交试验的参数给定如下：遗传算法、禁忌搜索算法的最优解连续不更新迭代终止代数分别设为10和500；为避免早熟收敛，若连续5代最优适应度不改善，则将变异概率p_m 在当前值基础上增加0.05，直至上限0.50；禁忌表长度L_{\mathrm{t}\mathrm{u}\mathrm{b}\mathrm{u}}=\mathrm{10}+⌈\frac{n}{N_{f}m}⌉；锦标赛规模在2和3之间随机取值。所有算例均采用上述参数配置。

4.2 算法性能对比及部件有效性消融实验

对比算法选取遗传算法与禁忌搜索相结合的GATS。与本文方法不同，GATS采用三层编码，除工厂选择链和工序顺序链外，还包含产品装配顺序链。

在GATS中，产品装配顺序链同时参与交叉、变异和邻域移动，其中，装配顺序链的交叉算子和变异算子与工序顺序链相同，并在邻域搜索中采用N7邻域结构。

为保证对比的可解释性，本文设置两类参照：①CPLEX求解MILP模型获得的最优解，标记为MILP1；②文献［9］在相同算例上的结果（MILP2与GA‑VNS）作为外部对照。为进行深入分析各组件的有效性，设计了3种消融算法：遗传算法（GA）、融合贪心策略的遗传算法（GA-Grd）、GATS。

基于上述算例和参数的所有算法均使用MATLAB R2023a编程实现。实验在一台配置i5-9300H CPU、8GB RAM、Windows 10 64位操作系统的计算机上进行。为确保实验的公平性，所有算法均在完全相同的软硬件环境下运行，每个算例均重复运行20次以获取统计结果。结果按算例的产品数划分。见表6～表8，表中，best列表示各算法在20次运行中求得的最佳结果，average列表示各算法20次运行中求得的平均结果，time列表示各算法的平均耗时（s）。数值保留到小数点后两位。

根据实验结果，按产品数量分组对比了算法GTSAIGS和GATS的平均耗时和C_max平均结果，使用耗时减少率R_T和结果增加率R_R

R_{\mathrm{T}}=\frac{averageTim{e}_{\mathrm{G}\mathrm{A}\mathrm{T}\mathrm{S}}-averageTim{e}_{\mathrm{G}\mathrm{T}\mathrm{S}\mathrm{A}\mathrm{I}\mathrm{G}\mathrm{S}}}{averageTim{e}_{\mathrm{G}\mathrm{A}\mathrm{T}\mathrm{S}}}（13）

R_{\mathrm{R}}=\frac{average{C}_{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{G}\mathrm{A}\mathrm{T}\mathrm{S}}-average{C}_{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{G}\mathrm{T}\mathrm{S}\mathrm{A}\mathrm{I}\mathrm{G}\mathrm{S}}}{average{C}_{\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{G}\mathrm{A}\mathrm{T}\mathrm{S}}}（14）

表示混合算法的效率提升和结果优劣。

如图8所示，与GA和GATS相比，GTSAIGS在产品较多的算例求解时间上表现出明显的优势。如图8a所示，产品数量为2的15个算例中，GTSAIGS在9个算例上的计算耗时均有缩短，且最大完工时间的均值在8个算例中优于GATS求得的结果。图9a、图9b分别为算例DA02和DA03求得C_maxbest所用时间对比图（以GTSAIGS平均耗时为基准时间），产品较少导致GTSAIGS的时间优势不明显，两种算法求得C_maxbest所用时间相近。图8c所示的20个算例中，GTSAIGS在19个算例中均缩短了求解时间，且与GATS相比，最大完工时间的均值没有明显增大。图8b所示的5个算例中，GTSAIGS只有一个算例的C_max均值增大0.19%，在其余算例中的耗时都缩短。如图9c～图9f所示，两种算法在20次求得最优解的耗时对比中，GTSAIGS的耗时较GATS明显缩短。GTSAIGS求得DA35算例最优解的甘特图为图10。

4.3 结果分析

通过试验结果可知，采用CPLEX对DAJSP的MILP模型求解可得到问题的最优解，但巨大的计算耗时凸显了精确算法在求解此类NP-hard问题时的局限，证明了开发高效启发式算法的必要性。GATS和GTSAIGS在求解质量上均远远优于不包含禁忌搜索的GA和GA-Grd。对比结果显示，引入禁忌搜索可显著提高解质量；仅依遗传算法的全局搜索时，受限于局部搜索能力，难以找到高质量的解。

分解策略和贪心算法是算法设计的核心创新点，两项策略的有效性在不同规模的算例中得到验证。对比平均性能可发现GTSAIGS在大部分算例上的求解质量优于GA，且耗时更少。综合来看，贪心算法将装配阶段从迭代优化中剥离，使启发式算法能专注于工厂分配和加工排序，避免在更庞大解空间中的无效搜索。因此贪心策略在所提算法中实现了提质、增效的统一。

进一步发现，随着产品数量增加，GTSAIGS算法的耗时优势更为明显，同时大部分算例的C_max均值不劣于GATS，证明了GTSAIGS的可靠性和稳定性。深入分析可知，对比算法GATS采用传统的启发式算法求解装配工序的调度解，在每次禁忌搜索的迭代中，对装配机器上的关键块生成众多的邻域解，解码和生成邻域解等高耗时步骤的使用频率也随之增加，最终导致求解时间的延长。算法GTSAIGS基于分解策略，采用贪心算法独立求解装配工序调度解，消除了装配工序迭代优化的耗时，能快速求得装配阶段的调度方案，不仅降低了装配工序的求解时间复杂度，而且保证了结果的可靠性。

4.4 实例测试

为对所提算法的实际应用性能进行深入评估，本节采用不同算法对实际生产案例进行求解和对比。案例来自一家大型数控机床及自动化生产线制造商，其生产模式是典型的分布式生产与装配，该制造商在不同的工业园区有4个工厂，每个工厂的生产设备相同且均配备20台专用设备，包括重型数控加工中心、中型数控车床及铣床、轻型精密设备和检测装置。案例包含45个数控机床零部件，最终产品为8种不同型号的数控机床。该场景下的调度问题可建模为一个以最小化最大完工时间为目标的分布式装配作业车间调度问题。该问题包含45个工件、4个分布式加工工厂、每个工厂20台机器及8个产品（算例请参考：https：∥github.com/dqgo/DAJSP-instance）。分别采用GTSAIGS和其他算法对案例进行测试，各算法独立运行10次并求得结果的均值和最优值，MILP模型由CPLEX求解运行1次并记录求解时间，结果如表9所示。

4.5 管理启示

从计算复杂性视角看，生产调度中的加工阶段与装配阶段的决策特性存在显著差异。前者可行的分配与排序方案呈指数级增长，需要大量计算资源进行全局寻优。后者是在上游决策确定后的类单机调度问题，可高效确定一个较优解。基于本文对DAJSP的解耦问题、分层求解思想，为生产管理者提供以下决策建议：

（1）决策资源的分层配置。将复杂的优化资源集中用于加工阶段的生产计划与排序；在装配阶段实施简单高效的算法，如本文改进的贪心算法快速排程。这种模式不仅降低了现场管理的复杂性，还提高了调度系统的响应速度与稳定性。

（2）制造部门的决策解耦。将复杂的调度问题降维处理，允许企业管理者对不同部门进行独立的资源配置和优化。不同生产区域，如工厂、部门和产线都可独立进行生产计划，各生产单元的管理者可专注于内部资源的局部最优配置，做到单元内部最优调度。而后，与其他部门及上层管理者进行协同调度，在大规模的跨部门、产线和工厂的宏观角度下调整。这种分级管理模式不仅降低了现场管理的复杂度，还赋予了各部门应对突发扰动的灵活性，从而实现大规模复杂生产环境下的整体效益最大化。

5 结论

针对分布式装配作业车间调度问题提出了混合算法GTSAIGS，算法通过引入贪心算法将装配阶段从复杂的迭代优化中剥离，从而将遗传算法与禁忌搜索的搜索资源集中于更具组合爆炸特征的加工子问题，缩短装配阶段的优化迭代耗时。实验结果证实，分解策略应用的混合算法在保证解质量的同时，降低了计算复杂度，展现出优秀的求解性能。

下一步的研究包括设计更合理的邻域结构，提出面向工件跨工厂移动的快速评估方法，进一步提高算法计算速度，以及对包含节能的多目标DAJSP进行优化。

参考文献

[1] ZHANG Sicheng， LI Xiang， ZHANG Bowen， et al. Multi-objective Optimisation in Flexible Assembly Job Shop Scheduling Using a Distributed Ant Colony System［J］. European Journal of Operational Research， 2020， 283（2）： 441-460.

[2] SHI Fei， ZHAO Shikui， MENG Yue. Hybrid Algorithm Based on Improved Extended Shifting Bottleneck Procedure and GA for Assembly Job Shop Scheduling Problem［J］. International Journal of Production Research， 2020， 58（9）： 2604-2625.

[3] 李仲华， 唐红涛， 张伟. 基于改进鲸鱼动态调度算法求解带外协的柔性装配作业车间调度［J］. 机床与液压， 2024， 52（20）： 1-9.

[4] LI Zhonghua， TANG Hongtao， ZHANG Wei. Solving the Scheduling of Flexible Assembly Workshops with Outsourcing Cooperation Based on Improving Whale Dynamic Scheduling Algorithm［J］. Machine Tool & Hydraulics， 2024， 52（20）： 1-9.

[5] 石飞， 赵诗奎. 基于工序约束链编码的遗传算法求解产品综合调度问题［J］. 中国机械工程， 2017， 28（20）： 2483-2492.

[6] SHI Fei， ZHAO Shikui. Product Comprehensive Scheduling Problems Solved by Genetic Algorithm Based on Operation Constraint Chain Coding［J］. China Mechanical Engineering， 2017， 28（20）： 2483-2492.

[7] CHAOUCH I， DRISS O B， GHEDIRA K. A Modified Ant Colony Optimization Algorithm for the Distributed Job Shop Scheduling Problem［J］. Procedia Computer Science， 2017， 112： 296-305.

[8] ŞAHMAN M A. A Discrete Spotted Hyena Optimizer for Solving Distributed Job Shop Scheduling Problems［J］. Applied Soft Computing， 2021， 106： 107349.

[9] JIANG Enda， WANG Ling， PENG Zhiping. Solving Energy-efficient Distributed Job Shop Scheduling via Multi-objective Evolutionary Algorithm with Decomposition［J］. Swarm and Evolutionary Computation， 2020， 58： 100745.

[10] WANG Sihan， LI Xinyu， GAO Liang， et al. An Improved Genetic Algorithm for Distributed Job Shop Scheduling Problem［C］∥Intelligent Computing Theories and Application. Cham： Springer， 2021： 37-47.

[11] TIAN Shichen， ZHANG Chunjiang， FAN Jiaxin， et al. A Genetic Algorithm with Critical Path-based Variable Neighborhood Search for Distributed Assembly Job Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2024， 85： 101485.

[12] YANG Zhijie， HU Xinkai， LI Yibing， et al. A Q-learning-based Improved Multi-objective Genetic Algorithm for Solving Distributed Heterogeneous Assembly Flexible Job Shop Scheduling Problems with Transfers［J］. Journal of Manufacturing Systems， 2025， 79： 398-418.

[13] 杨绍文， 钱斌， 胡蓉， 等. 混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题［J］. 电子学报， 2024， 52（3）： 909-923.

[14] YANG Shaowen， QIAN Bin， HU Rong， et al. Hybrid Three-dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery［J］. Acta Electronica Sinica， 2024， 52（3）： 909-923.

[15] 王玉芳， 葛嘉荣， 缪昇， 等. 一种求解柔性作业车间的改进遗传算法［J］. 重庆理工大学学报（自然科学版）， 2021， 35（9）： 152-159.

[16] WANG Yufang， GE Jiarong， MIAO Sheng， et al. An Improve Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem［J］. Journal of Chongqing Institute of Technology， 2021， 35（9）： 152-159.

[17] 刘设，李佳欣，田志强，等 ．考虑客户满意度的模糊柔性作业车间调度优化方法［J/OL］.中国机械工程［2026-03-17］.

[18] LIU She， LI Jiaxin， TIAN Zhiqiang，et al. Fuzzy Flexible Job-shop Scheduling Optimization Approach Considering Customer Satisfaction［J/OL］. China Mechanical Engineering.［2026-03-17］.

[19] 周豪， 张超勇， 刘辉， 等. 改进Jaya算法求解混合流水车间调度问题［J］. 中国机械工程， 2024， 35（8）： 1462-1471.

[20] ZHOU Hao， ZHANG Chaoyong， LIU Hui， et al. Improved Jaya Algorithm for Solving HFSPS［J］. China Mechanical Engineering， 2024， 35（8）： 1462-1471.

基金资助

国家自然科学基金(52275490)

山东省自然科学基金(ZR2025MS766)

山东省科技型中小企业创新能力提升工程(2025TSGCCZZB0845)

中央引导地方科技发展资金(YDZX2024127)