基于AM-GA算法的制造车间多目标调度优化

Multi-objective scheduling optimization for manufacturing workshop using an adjacency matrix-genetic algorithm

摘要

针对制造车间调度优化多目标的问题，构建了车间调度模型，提出了一种基于（Adjacency Matrix-Genetic Algorithm，AM-GA）算法的车间资源调度多目标优化新方法，该方法以遗传算法为基础框架，融合基于邻接矩阵定向匹配策略、多目标及改进基本位变异算子，通过与邻接矩阵的融合实现工艺路线的动态规划，该算法在针对车间多目标场景下的资源调度优化问题上，具有较好的可扩展性及全局搜索能力。最后，通过选取电子产品制造车间的数据进行试验对比，试验证明该方法能够较为高效准确地应对电子产品制造车间在多目标、多路径、多资源制造场景下的调度优化问题。

Abstract

Aiming at the multi-objective optimization problem of manufacturing workshop scheduling， a workshop scheduling model is constructed， and a novel multi-objective optimization method for workshop resource scheduling based on the Adjacency Matrix-Genetic Algorithm （AM-GA） is proposed.Taking the genetic algorithm as the basic framework， this method integrates the adjacency matrix-based directional matching strategy， multi-objective processing， and an improved basic bit mutation operator.The dynamic programming of process routes is realized through the integration with the adjacency matrix.The algorithm exhibits favorable scalability and global search capability in solving resource scheduling optimization problems under multi-objective workshop scenarios.Finally， experiments are carried out using data from an electronic product manufacturing workshop for comparative analysis.The results demonstrate that the proposed method can efficiently and accurately address the scheduling optimization problems in electronic product manufacturing workshops characterized by multi-objective， multi-route， and multi-resource manufacturing scenarios.

Graphical abstract

关键词

多目标 / 调度优化 / 遗传算法 / 多资源 / 邻接矩阵

Key words

multi-objective / scheduling optimization / genetic algorithm / multi-resource / adjacency matrix

在多变需求下，企业面临着生产制造链条长、制造要求变化多、计划目标满足难、制造要素品类多、工艺路径选择多、资源需求策划难等问题，目前依靠人工或简单的信息化手段已经难以满足需求的快速变化。对车间的计划调度模式进行数字化能力提升，是保证准时交付的关键，是高质量和低成本交付的重要要求和前提条件，对提升生产决策的及时性和准确性具有重要意义。

Bai等^［1］以最长完工时间为目标，分别研究了柔性开放车间调度问题的静态和动态问题，利用有界性假设证明了广义密集调度算法的渐近最优性。Zhuang等 ^［2］用序列对问题的解进行编码，使得算法能在大规模问题中取得最佳的求解效果。Coelho等^［3］从实验角度分析了大量的已有算法，并据此提出了一种能够适应大规模算例的三阶段算法。Yuan等^［4］在全局搜索中加入局部搜索方法，通过编码将连续域离散化，以平衡搜索的广度和深度。胡一凡等^［5］针对柔性装配作业车间调度问题，构建了基于多智能体的深度学习算法，充分挖掘高回报样本的价值。Wang等^［6］对柔性车间调度的多目标优化问题进行求解。Kardos等^［7］以最大完工时间、总拖期等为目标，对车间调度问题进行了研究。

综上所述，现有研究能够为解决复杂电子产品制造的调度优化问题提供新思路，如大多基于产线制造能力固定^［8］、工艺路径确定^［9］以及资源需求单一^［10］等情形，在针对多目标制造资源复杂电子产品生产制造场景时，难以高效全面地应对工艺路径复杂多变、订单量庞大以及资源需求种类多等融合的业务场景。本文以复杂电子产品制造车间调度优化为核心场景，提出了一种基于邻接矩阵-遗传算法（Adjacency Matrix-Genetic Algorithm， AM-GA）的制造车间多目标调度优化新方法，该方法充分考虑复杂电子产品多路径工艺路线的生产制造模式和车间各制造资源融合配置的需求，更加适用于多品种、变批量及定制化复杂电子产品的制造工艺链条长、工序种类多、作业场景多、资源需求复杂的生产制造场景。

1 问题描述及模型构建

1.1 问题描述

在复杂电子产品的制造过程中，工艺路线往往呈现出多路径网状关联^［11］的特性，如图1所示。这种多路径工艺路线指的是制造过程中存在多个并行和串行的工艺步骤，这些步骤之间通过特定的依赖关系相互连接，形成一个复杂的网络结构。为了描述和分析这种复杂的工艺关系，通常采用有向无环图^［12-13］（Directed acyclic graph，DAG）的形式进行定义。在多路径工艺路线^［14］中，每个节点代表一个具体的工艺步骤，而有向边则表示这些步骤之间的依赖关系，即某个工艺步骤必须在另一个工艺步骤完成后才能开始。这种网状结构能够清晰地展示工艺流程中的并行性和串行性，帮助识别关键路径和瓶颈环节，从而优化资源分配和提高生产效率。

复杂电子产品制造多资源调度问题^［15］是对车间人力资源、仪器设备和工位进行按需组合配置，该问题可描述为：某复杂电子产品制造车间一次性下发m个任务I_c=\{I_{\mathrm{1}},I_{\mathrm{2}},\dots ,I_m,c=\mathrm{1,2},\dots ,m\}，任务之间是相互独立的，每个任务有u道具有先后约束关系的工序J_f=\{J_{\mathrm{1}},J_{\mathrm{2}},\dots ,J_u,f=\mathrm{1,2},\dots ,u\}，根据工序资源需求为每道工序分配工位、仪器、执行时间和执行人员，所需工位、仪器和人员类型由资源需求决定，不同工序所需资源不同。为每个任务安排资源时，应该充分考虑任务交期和资源状态等因素。目标是在现有车间资源库的基础上，对m个任务u道工序进行排程，同时最优化既定的目标。

1.2 数学模型

复杂电子产品制造车间调度优化问题是一个典型的多目标优化问题^［16］，涉及了两大类目标：其一为提高任务的执行效率，即最小化任务完成总时间^［17］；其二为车间制造资源的工作负荷均衡，即最小化制造资源工作量的离散系数^［18］。数学模型中的目标函数F为：

\mathrm{m}\mathrm{i}\mathrm{n}F=\left\{F_{\mathrm{1}},F_{\mathrm{2}}\right\}={\omega }_{\mathrm{1}}{\psi }_{F_{\mathrm{1}}}+{\omega }_{\mathrm{2}}{\psi }_{F_{\mathrm{2}}}（1）

其中，{\omega }_{\mathrm{1}}\mathrm{、}{\omega }_{\mathrm{2}}为各项权重系数，{\omega }_i\ge \mathrm{0},i=\mathrm{1,2}，且{\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{2}}}{\omega }_i=\mathrm{1}；{\psi }_{F_i}为F_i(i=\mathrm{1,2})无量纲化之后的结果。目标F_{\mathrm{1}}和F_{\mathrm{2}}的定义如下。

1） 目标F_{\mathrm{1}}是在现有的资源条件下，通过合理分配资源和任务优化安排，使得项目总体完成时间最小^［19］。

F_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}{\displaystyle \sum _{c=\mathrm{1}}^b}{\displaystyle \sum _{f=\mathrm{1}}^u}Z{T}_{cf}（2）

2） 目标F_{\mathrm{2}}是最小化车间制造资源的工作负荷CV。车间制造资源的工作负荷表示人员、仪器和工位等三类资源的负荷情况，采用离散系数进行数学表达，表现为各类资源执行任务总时间的标准差与执行任务总时间均值的比值^［20］。离散系数越小，表明任务分配均衡合理，所以任务分配问题应尽量优化各类资源的工作负荷CV。

F_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}CV（3）

CV=\raisebox{1ex}{$\sigma $}\!\left/ \!\raisebox{-1ex}{$\mu $}\right.（4）

\mu ={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\frac{\mathrm{1}}{\left|O\right|}{\displaystyle \sum _{r=\mathrm{1}}^O}{\displaystyle \sum _{c=\mathrm{1}}^b}{\displaystyle \sum _{f=\mathrm{1}}^u}Z{T}_{cf}^o（5）

\sigma ={\displaystyle \sum _{i=\mathrm{1}}^{\mathrm{3}}}\sqrt[]{\frac{\mathrm{1}}{\left|O\right|}{\displaystyle \sum _{r=\mathrm{1}}^O}{\left({\displaystyle \sum _{c=\mathrm{1}}^b}{\displaystyle \sum _{f=\mathrm{1}}^u}Z{T}_{cf}^o-\mu \right)}^{\mathrm{2}}}（6）

其中，CV表示车间制造资源的工作负荷；\sigma表示人员执行任务总时间的标准差；\mu表示人员执行任务总时间的均值；i表示车间制造资源的类型，包括人员、仪器和工位；O表示资源个数；Z{T}_{cf}^o表示在资源O的操作下，任务I_c工序J_f的执行时间；Z{T}_{cf}^{}表示任务I_c工序J_f的执行时间。

综上所述，结合复杂电子产品制造车间调度优化问题描述，满足的约束条件及表达式如下：

{\displaystyle \sum _{c=\mathrm{1}}^b}{\displaystyle \sum _{f=\mathrm{1}}^u}{x}_{cft}^o\le \mathrm{1},t\in T（7）

S{T}_{cf}^o+Z{T}_{cf}^o\le S{T}_{vl}^o（8）

S{T}_{cf}^o+Z{T}_{cf}^o\le S{T}_{c(f+\mathrm{1})}^o（9）

Z{T}_{cf}^o\le T_{cf}^{}（10）

{\displaystyle \sum _{c=\mathrm{1}}^b}{\displaystyle \sum _{f=\mathrm{1}}^u}Z{T}_{cf}^o\le T_o（11）

{\displaystyle \sum _{f=\mathrm{1}}^u}{x}_{cft}^o\ge \mathrm{1},t\in T（12）

S{T}_{cf}^o\ge \mathrm{0}（13）

其中，Z{T}_{cf}^o表示在资源O的操作下，任务I_c工序J_f的执行时间；S{T}_{cf}^o表示在资源O的操作下，任务I_c工序J_f的开始时间；T_{cf}^{}表示任务I_c工序J_f的额定时间；T是时间的集合；x_{cft}^o为决策变量，表示在t时刻，任务I_c工序J_f由资源O来执行，则x_{cft}^o=\mathrm{1}，否则x_{cft}^o=\mathrm{0}；T_o为人员O的额定工作时间；Z_d^c为决策变量，表示任务I_c的紧急程度高于任务I_d，则Z_d^c=\mathrm{1}，否则Z_d^c=\mathrm{0}。此外，式（7）表示同一个资源在同一时刻最多执行一道工序；式（8）表示同一个资源必须当前工序执行结束才能执行下一工序；式（9）表示相同任务下的工序间具有紧前约束关系，即同一任务紧前工序执行结束才可以执行下一道工序；式（10）表示所有工序都在额定时间内完成；式（11）表示分派给执行人员的工作量不可超过额定工作时间；式（12）表示完成任务所需要的资源数量要大于1个；式（13）每项任务的开工时间大于0。

2 算法模型求解

2.1 遗传算法概述

遗传算法（Genetic Algorithm，GA）^［21］源于生物的进化机理，是仿照自然界中物种的进化机理而演变出来的一种智能搜索算法。原理是将实际问题抽象地表达为染色体的集合，并为每条染色体赋予一定的适应度值。通过对每条染色体的适应度值进行不断的计算，根据优胜劣汰的淘汰法则筛选出能够适应生存环境的染色体。将实际问题模拟成物种的演化过程，将染色体上的元素定义为基因的组合，并对它们进行复制、交叉和变异等操作，进而产生新的更优的染色体群体。不断地重复这样的操作，最终种群将会无限收敛到最优个体上，实现染色体解的寻优。GA 具有较强的稳健性和全局搜索能力，但其局部搜索能力较差^［22］，传统遗传算法在处理复杂工艺规划（如多路径工艺路线优化）时存在明显的局限性，具体如下。

1） 编码表达性与适应性不足^［23］：传统染色体编码（如二进制或顺序编码）难以有效描述具有多分支、多资源约束的工艺路线拓扑结构，导致解空间建模精度低。

2） 资源动态适配问题^［24］：现有方法通常将工艺路线与资源分配割裂处理，无法反映资源动态适配对工艺路径优化的影响，降低了方案的工程可行性。

针对上述问题，本文提出以下改进思路。

1） 基于邻接矩阵的多路径编码策略：将工艺路线抽象为图结构，通过邻接矩阵编码染色体基因位点，精准表征多分支路径的拓扑关系与工序衔接逻辑，提升解空间建模能力。

2） 资源-染色体融合的混合编码机制：在编码层引入资源标签维度，将人员、仪器、工位、工时等资源属性嵌入染色体基因序列，实现工艺路线与资源分配的同步优化，增强解的实际可操作性。

2.2 算法设计

2.2.1 算法流程

本文提出的基于AM-GA算法的制造车间多目标调度优化算法流程如图2所示，算法步骤如下。

Step1 获取所有待排程任务对应的工序运行逻辑、执行周期、资源需求（包括仪器、工位和人员）和资源库（包括仪器、工位和人员）。

Step2 根据工序运行逻辑构建邻接矩阵Sim。

Step3 进行染色体编码，并随机产生一定规模的初始种群，令n=1。

Step4 从种群中选取一条染色体，根据染色体的编码信息，按照邻接矩阵Sim的解析流程，得到待执行工序顺序。

Step5 按照基因位定向匹配策略对资源进行分配。

Step6 判断n是否满足阈值条件，若不满足，则n=n+1，执行下一步；否则跳转至Step12。

Step7 按照遗传算法进化规则，需要构建种群适应度函数F（i），并为每条染色体分配适应度值。

Step8 采用选择策略，从种群中随机选取设定比例的染色体进入下一步遗传操作。

Step9 从筛选出的染色体中每两条为一组，作为父代染色体，判断是否满足交叉条件，若满足，则进行交叉；否则对下一组染色体进行判断，直至遍历完成，构成新的子代种群，执行下一步。

Step10 在子代种群中逐条遍历染色体，判断是否满足变异条件，若满足，则进行变异；否则判断下一条染色体是否满足变异条件，遍历完成构成新的子代种群，执行下一步。

Step11 判断子代种群染色体与初始种群染色体个数差值h，从父代中选取适应度值F（i）高的h条染色体作为最优个体，不进行遗传操作，直接加入到新种群当中，转到Step5。

Step12 输出种群最优解，解码输出每道工序对应的人员、仪器、工位、开始结束时间。

2.2.2 染色体编码

本文拟采用整数编码^［25］的方式，每条染色体由“项目-任务-工序”的序列组合而成，工序之间具有固定的紧前约束关系。染色体编码规则如图3所示。

2.2.3 邻接矩阵构建

邻接矩阵（Adjacency Matrix，AM）^［26］是图论中一种基础的数据表示方法，通过二维矩阵描述图中顶点间的连接关系。邻接矩阵分为关系邻接矩阵和带权邻接矩阵^［27］，其行与列分别对应图的顶点，矩阵元素值标识顶点间是否存在边（无权图）或边的权重（带权图）。该结构以清晰的矩阵形式直观体现拓扑结构，并为基于矩阵运算的图算法（如路径计算或网络建模）提供了高效的理论与实现基础。邻接矩阵的关键在于它通过矩阵的行列索引的关系来描述顶点间的连接，是一种直观的表示方式。邻接矩阵定义为：

A[i,j]=\left\{\begin{array}{c}\mathrm{1},\mathrm{节点}i\mathrm{到节}\mathrm{点}j\mathrm{有弧}\mathrm{相连},\\ \mathrm{0},\mathrm{节点}i\mathrm{到节}\mathrm{点}j\mathrm{无弧}\mathrm{相连}\end{array}\right.（14）

本文所涉及的复杂电子产品的制造过程呈现多路径工艺路线网状关联的特点，其关联关系采用邻接矩阵的方式进行数学表达，构建过程及操作图解如图4和图5所示，算法步骤如下。

Step1 获取工序运行逻辑关系，设工序个数为k，从表中提取出工序号、输出工序和输入工序构成新的二维字符串矩阵。

Step2 将二维字符串矩阵转换成被计算机识别的数值矩阵形成一个新的矩阵E（k，3）。

Step3 生成一个k+1行、k列的零矩阵Sim，令j=1。

Step4 判断所有工序是否循环完毕，如果是，则邻接矩阵生成完毕，否则，判断输入工序是否为空，如果是，则将Sim第一行对应工序列幅值为1，否则，进入步骤Step5。

Step5 判断输出工序是否为空，如果是，则式j=j+1，进入步骤Step4，否则将Sim对应j+1行的输出工序列幅值为1。

2.2.4 适应度评价

适应度函数^［28］是体现遗传操作种群优良程度的指标，是判断子代种群个体好坏的依据，其函数值影响着染色体基因遗传到子代的几率及计算结果的收敛性和收敛速度。根据目标函数的不同，适应度函数的表达方式也不同，根据任务分配的优化目标，得到染色体i的适应度函数计算公式为：

F(x)=\frac{\mathrm{1}}{f\left(x\right)}（15）

其中，f_i\left(x\right)表示目标函数值。

2.2.5 基于AM的定向匹配策略

复杂电子产品制造过程普遍表现出多路径并行的网状工艺特征，可通过构建有向无环图（Directed Ayclic Graph，DAG）进行工艺特征的拓扑结构建模，其邻接矩阵做为表达工具，能够精确表征各工艺节点间的时序依赖关系。通过实施基于邻接矩阵的拓扑排序算法，可推导出满足工艺约束的最优工序序列。基于此拓扑排序过程，引入基于邻接矩阵的定向匹配策略实现对制造资源的最优配置。每个基因位对应DAG中的一个关键工序节点，其等位基因表征为该节点的人员（P）、仪器（E）、工位（S）与时间（T）多维度资源参数组合。通过邻接矩阵输出的工序拓扑顺序，可构建染色体基因位的动态编码。使制造资源在空间（工位）、时间（作业顺序）和物质（仪器和人员）三维度实现动态平衡。操作图解如图6所示。

基于邻接矩阵进行拓扑排序及进行人员（P）、仪器（E）、工位（S）与时间（T）多维度资源分配过程如图7所示，算法步骤如下。

Step1 读取邻接矩阵l行（初值为1）中非零元素对应个数n，并将非零对应列号放入数组K中。

Step2 如果n>1，则Q=Q+K（Q初值为0），在数组Q中随机选取列号j，Q=Q-j，l=j，将l存入S数组中；否则执行Step8。

Step3 读取工序l需求的仪器、工位和人员；

Step4 如果需要仪器，获取仪器需求类型，并分配满足需求的全部仪器；否则执行Step5。

Step5 如果需要工位，获取工位需求类型，并分配满足需求的全部工位；否则执行Step6。

Step6 如果需要人员，获取人员需求类型，并分配满足需求的全部人员，为该工序l分配开始和结束时间；否则执行Step7。

Step7 如果非零元素遍历完成，则结束资源分配操作，否则执行Step1。

Step8 提取数组K中元素j的非零项，保存至N中，如果S中包含全部N值，则执行Step2，否则K=0，执行Step2。

2.2.6 选择算子

选择操作^［29］主要是在一个种群中选出基因优良的个体，产生新的子代基因个体。主要是根据个体的适应度值的大小，以一定方式筛选出优良的遗传个体，由于每个个体具有不同的适应度值，导致每个个体被选中的概率也不相同。本文采用轮盘赌的方法进行选择，适应度值越大，表明该基因个体越好，被选中的概率也越大，轮盘赌选择的函数表达形式为：

P(i)=\frac{F(i)}{{\displaystyle \sum _{k=\mathrm{1}}^m}F(k)}（16）

式中，F(k)为第k个基因个体的适应度值，P(i)为第i个基因个体被选中的概率。

2.2.7 交叉算子

交叉操作又称重组^［30］，是模仿生物遗传进化的基因重组过程，按一定的交叉几率，将两个父代个体的一部分基因按一定的规则进行交换，而重新获得新个体的过程，每次交叉后，新产生个体的基本特征与父代相同，即保持了种群的多样性，又使得遗传算法的搜索能力得到大幅度的提升。本文采用顺序交叉算子，计算图解如图8所示。

2.2.8 变异算子

变异操作^［31］是将部分个体染色体基因串中的某些基因位进行突变，用其他符合要求的基因替换该位置，进而构成一条新的染色体序列。本文对基本位变异算子进行适应性改进，以一定概率在个体基因串中，随机选择一个或多个基因位，并对这些基因位的取值进行位轮换操作。通过引入新的遗传信息，维持种群的多样性，防止种群退化。其操作过程图解如图9所示。

3 实例验证

3.1 实例描述

以某复杂电子产品制造过程为实例，应用本文提出的基于AM-GA的车间制造资源调度优化方法，分别选取包含13道和11道工序的生产订单a和b，每个订单具有固定的紧前约束关系如图10和图11所示，从该企业中选取执行人员{\lambda }_k名，其中k=1，2，…，25，仪器{\mathrm{\epsilon }}_v台，其中v=1，2，…，46，可执行工位{\mathrm{\delta }}_m个，其中m=1，2，…，41，以该实验数据为例，其仪器、人员和工位需求如表1~表3所示。

3.2 算法参数确定

遗传算法的参数众多，其中代沟、交叉概率和变异概率对算法性能的影响最为突出，好的算法参数的选取能够显著提升遗传算法在具体问题当中的性能，加速寻优^［32］。其中代沟表示每一代中被替换的个体比例，通常取值范围［0.7，1.0］，交叉概率表示选中的父代个体进行交叉操作的概率，通常取值范围［0.8，1.0］，变异概率表示个体基因位发生变异的概率，通常取值范围［0.001，0.1］。本文通过正交试验设计，对遗传算法中的3个参数的不同组合进行性能验证，以最小收敛代数为核心评价指标。

试验设定种群规模为P=100和a，b车间的订单规模为D=5*5，最大迭代次数150次。参数及水平设置如表4所示。

试验共设计16组参数组合（L16（4⁵）正交表），覆盖各参数4个代表性水平，通过对所有组合的独立重复试验（每组运行10次，取平均收敛代数），得到正交试验结果如表5所示，迭代收敛曲线如图12所示。

由表5及图12分析对比可知，在本研究的问题场景中，当遗传算法的参数按照代沟G=0.9、交叉概率 P_c =0.97、变异概率 P_m =0.100的组合方式时，能够以最快的速度收敛至较优解，是兼顾效率与稳定性的最优参数组合。

3.3 仿真试验对比

车间订单规模和算法种群规模是调度优化算法的重要参数，其变化趋势往往会影响到问题求解的难度。本试验分别选取算法种群规模为P=100/150/200和a，b车间订单规模分别为为D=5*5/5*10/10*10两组算例，设定遗传算法代沟为G=0.9，交叉概率 P_c =0.97，变异概率 P_m =0.100，该算法设定以最大遗传代数为150作为结束条件，为验证本文算法性能，选择代理辅助遗传编程^［33］（Surrogate-assisted Genetic Programming，SA-GP）、混沌粒子群优化算法^［34］（Chaotic Particle Swarm Optimization，CPSO）、位变异遗传算法^［35］（Bit-Flip Mutation in GA，BFM-GA）、人工蜂群优化算法^［36］（Artificial Bee Colony Algorithm，ABC）与本文基于邻接矩阵的改进遗传算法（AM-GA）进行试验对比。

如图13表示出了SA-GP、CPSO、BFM-GA、ABC和AM-GA的迭代曲线图。同时对5种算法进行50次任务分配操作，选取并对比50次结果的算法指标平均值，得到如表6所示对比结果。

由表6和图13的分析对比结果可知，AM-GA在解决复杂多路径问题上实现了精度-效率的双重突破。

1） 相较于SA-GP算法，AM-GA通过邻接矩阵定向匹配策略直接建模多路径工艺路线的关联性，规避代理模型牺牲真实拓扑结构导致的局部最优问题，在同等条件下算法收敛代数平均降低33%，算法求解时间平均缩短25%。

2） 针对CPSO算法在复杂多路径问题中易破坏可行路径的连续性，AM-GA基于邻接矩阵编码天然保留路径节点的连接约束，实现迭代收敛代数平均减少35代。

3） 对比BFM-GA算法的变异策略易破坏邻接矩阵中已形成的可行路径，AM-GA通过位轮换变异操作与邻接矩阵相结合避免无效解，使目标函数值、执行时间、迭代收敛代数和算法求解时间都得到大幅提升。

4） 对于ABC算法因雇佣蜂-侦查蜂的分工机制需频繁重置状态增加计算开销，AM-GA通过对多路径工艺路线网状结构进行邻接矩阵拓扑排序，定向搜索可行解区域，提升搜索效率，实现算法求解时间平均缩短17%。

综上所述，通过采用基于邻接矩阵的改进遗传算法（AM-GA）能够使复杂电子产品车间制造资源的调度优化问题，在收敛速度、解的质量及时间成本上显著综合占优。

4 结论

本文在利用遗传算法解决复杂电子产品制造车间调度优化问题的基础上，引入基于邻接矩阵的基因位定向匹配策略以及改进基本位变异算子，提出并构建了一种基于AM-GA的车间制造资源调度优化新方法。实验结果证明，该方法充分考虑复杂电子产品多路径工艺路线的生产制造模式和车间制造资源的需求，能够较为高效准确地应对复杂电子产品制造车间在多目标制造资源场景下的调度优化难题，能够为企业的资源调度及任务分配提供参考。

参考文献

[1] Bai D， Zhang Z H， Zhang Q.Flexible open shop scheduling problem to minimize makespan［J］.Comput Oper Res， 2016， 67： 207-215.

[2] Zhuang Z， Huang Z， Lu Z， et al.An improved artificial bee colony algorithm for solving open shop scheduling problem with two sequence-dependent setup times ［J］.Procedia CIRP， 2019， 83： 563-568.

[3] Coelho J， Vanhoucke M.Going to the core of hard resource-constrained project scheduling instances［J］.Comput Oper Res， 2020， 121： 104976.

[4] Yuan Y， Xu H.Flexible job shop scheduling using hybrid differential evolution algorithms［J］.Comput Ind Eng， 2013， 65（2）： 246-260.

[5] Hu Y F， Zhang L P， Bai X.Deep reinforcement learning for flexible assembly job shop scheduling problem ［J］.J Huazhong Univ of Sci Tech （Natural Science Edition）， 2023， 51（2）： 153-160.

[6] 胡一凡， 张利平， 白雪，等.深度强化学习求解柔性装配作业车间调度问题［J］.华中科技大学学报（自然科学版）， 2023， 51（2）： 153-160.

[7] Wang J Z， Qu S H， Wang J， et al.Real-time decision support with reinforcement learning for dynamic flow-shop scheduling［C］//Smart Sys Tech 2017.Munich， Germany： VDE， 2017.

[8] Kardos C， Laflamme C， Gallina V， et al.Dynamic scheduling in a job-shop production system with reinforcement learning［J］.Procedia CIRP， 2021， 97： 104-109.

[9] Wang L， Hu X， Wang Y， et al.Dynamic job-shop scheduling in smart manufacturing using deep reinforcement learning［J］.Comput Netw， 2021， 190： 107969.

[10] Cai J， Lei D， Wang J， et al.A novel shuffled frog-leaping algorithm with reinforcement learning for distributed assembly hybrid flow shop scheduling［J］.Int J Prod Res， 2023， 61（4）： 1233-1251.

[11] Ling F P， Ji W X.Improved COOT algorithm to solve multi-objective FJSP［J/OL］.Computer Engineering and Applications.［2022-12-15］.

[12] de Campos A， Pozo A T R， Duarte E P.Parallel multi-swarm PSO strategies for solving many objective optimization problems［J］.J Parallel Distrib Comput， 2019， 126： 13-33.

[13] Günay E E， Kula U.A hybrid model for mix-bank buffer content determination in automobile industry ［J］.Eur J Ind Eng， 2020， 14（4）： 544.

[14] LI G L.Improved adaptive genetic algorithm for flexible job shop scheduling problem［J］.Scientific Journal of Economics and Management Research， 2022， 4（3）：77-88.

[15] Pezzella F， Morganti G， Ciaschetti G.A genetic algorithm for the flexible job-shop scheduling problem ［J］.Comput Oper Res， 2008， 35（10）： 3202-3212.

[16] Li X， Gao L.An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem［J］.Int J Prod Econ， 2016， 174： 93-110.

[17] Jia P H， Wu T.A hybrid genetic algorithm for solving FJSP［J］.Journal of Xian Polytechnic University，2020，34 （5） ：80-86.

[18] Tremblet D， Yelles-Chaouche A R， Gurevsky E， et al.Optimizing task reassignments for reconfigurable multi-model assembly lines with unknown order of product arrival［J］.J Manuf Syst， 2023， 67： 190-200.

[19] Rahman H F， Janardhanan M N， Nielsen I E.Real-time order acceptance and scheduling problems in a flow shop environment using hybrid GA-PSO algorithm［J］.IEEE Access， 2019， 7： 112742-112755.

[20] Habib Zahmani M， Atmani B.Multiple dispatching rules allocation in real time using data mining， genetic algorithms， and simulation［J］.J Sched， 2021， 24（2）： 175-196.

[21] Shi L， Zhan Z H， Liang D， et al.Memory-based ant colony system approach for multi-source data associated dynamic electric vehicle dispatch optimization ［J］.IEEE Trans Intell Transport Syst， 2022， 23（10）： 17491-17505.

[22] Urnauer C， Bosch E， Metternich J.Simulation-based optimization of sequencing buffer allocation in automated storage and retrieval systems for automobile production［C］//2019 Winter Simulation Conference （WSC）.National Harbor， MD， USA：IEEE， 2019： 1602-1611.

[23] Han B A， Yang J J.Research on adaptive job shop scheduling problems based on dueling double DQN［J］.IEEE Access， 2020， 8： 186474-186495.

[24] Cergibozan Ç， Tasan A S.Genetic algorithm based approaches to solve the order batching problem and a case study in a distribution center［J］.J Intell Manuf， 2022， 33（1）： 137-149.

[25] Ahmadian Fard Fini A， Rashidi T H， Akbarnezhad A， et al.Incorporating multiskilling and learning in the optimization of crew composition［J］.J Constr Eng Manage， 2016， 142（5）： 04015106.

[26] Kose Y， Cevikcan E， Ertemel S， et al.Game theory-oriented approach for disassembly line worker assignment and balancing problem with multi-manned workstations［J］.Comput Ind Eng， 2023， 181： 109294.

[27] Tan Y， Zhu G， Tian F， et al.Multi-objective optimization of T-shaped bilateral laser welding parameters based on NSGA-Ⅱ and MOPSO［J］.J Mater Sci， 2024， 59（21）： 9547-9573.

[28] Bajomo M， Ogbeyemi A， Zhang W.A systems dynamics approach to the management of material procurement for Engineering， Procurement and Construction industry［J］.Int J Prod Econ， 2022， 244： 108390.

[29] YounesSinaki R， Sadeghi A， Mosadegh H， et al.Cellular manufacturing design 1996-2021： A review and introduction to applications of industry 4.0 ［J］.Int J Prod Res， 2023， 61（16）： 5585-5636.

[30] Guo H， Liu J， Zhuang C.Automatic design for shop scheduling strategies based on hyper-heuristics： A systematic review［J］.Adv Eng Inform， 2022， 54： 101756.

[31] Fan J， Zhang C， Liu Q， et al.An improved genetic algorithm for flexible job shop scheduling problem considering reconfigurable machine tools with limited auxiliary modules［J］.J Manuf Syst， 2022， 62： 650-667.

[32] Choong S S， Wong L P， Lim C P.Automatic design of hyper-heuristic based on reinforcement learning ［J］.Inf Sci， 2018， 436： 89-107.

[33] Yu L Y， Hou Z Y， Cai Y P， et al. Parking path planning and tracking control methods by intelligent optimization algorithms［J］. Journal of Jiangsu University（Natural Science Edition）， 2025， 46（6）： 621-630.

[34] 于蕾艳， 侯泽宇， 蔡永鹏， 等.智能算法优化的泊车路径规划及跟踪控制方法［J］. 江苏大学学报（自然科学版）， 2025， 46（6）： 621-630.

[35] Zeiträg Y， Figueira J R， Horta N， et al.Surrogate-assisted automatic evolving of dispatching rules for multi-objective dynamic job shop scheduling using genetic programming［J］.Expert Syst Appl， 2022， 209： 118194.

[36] Petrović M， Vuković N， Mitić M， et al.Integration of process planning and scheduling using chaotic particle swarm optimization algorithm［J］.Expert Syst Appl， 2016， 64： 569-588.

[37] Wang M， Zhao B， Liu Y C， et al.Static task allocation for multi-machine cooperation based on multi-variation group genetic algorithm［J］.Transactions of the Chinese Society for Agricultural Machinery， 2021， 52（7）： 19-28.

[38] 王猛， 赵博， 刘春阳 等.基于多变异分组遗传算法的多机协同作业静态任务分配［J］.农业机械学报， 2021， 52（7）： 19-28.

[39] Zhang W， Zheng Y， Ahmad R.The integrated process planning and scheduling of flexible job-shop-type remanufacturing systems using improved artificial bee colony algorithm［J］.J Intell Manuf， 2023， 34（7）： 2963-2988.

基金资助

四川省重大科技专项(2020ZDZX0025)

四川省自然科学基金(2024NSFTD0048)