有限运输能力约束的作业车间多目标调度方法

摘要

本申请涉及作业车间调度的技术领域，尤其是涉及有限运输能力约束的作业车间多目标调度方法,包括：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；确定作业车间的多目标调度场景的调度参数和先决条件；构建具有运输资源和加工设备资源双重约束的多目标车间调度模型；基于多目标莫因算法解析多目标车间调度模型；根据解析结果获取最优的最小化最大完工时间和最小化AGV总运输时间，根据最优的最小化最大完工时间和最小化AGV总运输时间输出作业车间的多目标调度方案；本发明在有限运输能力约束场景下制定合理的联合调度方案，既能使制造系统具有较优的加工效率，又能降低AGV的运输消耗。

权利要求

1.有限运输能力约束的作业车间多目标调度方法，其特征在于：包括以下步骤：步骤A1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；

步骤A2：确定作业车间的多目标调度场景的调度参数和先决条件；

步骤A：基于步骤A1和A2，构建具有运输资源和加工设备资源双重约束的多目标车间调度模型；

步骤B：基于多目标模因算法解析多目标车间调度模型；

步骤C：根据解析结果获取最优的最小化最大完工时间和最小化AGV总运输时间，根据最优的最小化最大完工时间和最小化AGV总运输时间输出作业车间的多目标调度方案；

其中，步骤B包括通过求解M0‑JSPMH问题以解析多目标车间调度模型，包括：针对MO‑JSPMH问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略；

在所述步骤A中，包括基于公式(1)和公式(2)构建调度模型：f1＝minCmax (1)

其中，f1为最小化最大完工时间的目标函数，f2为最小化AGV总运输时间的目标函数；

在所述步骤A中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：Cmax≥fi(n+1) (3)

fij≥dij+pij (4)

pi0＝0，pi(m+1)＝0 (5)

di(j+1)≥f′ij (6)

d′ij≥fij (8)

δij，lq+δlq，ij＝1 (19)

Cpl＝Vpl (20)

其中，工件编号：i，l；加工设备编号：Ml；P/D口编号：M0；搬运设备编号：rs，rk；任务工序编号：Oij，Olq；工件i的释放任务：Oi0；工件i的回收任务：Oi(n+1)；工序Oij的加工时间：pij；AGV将物料从设备p输送到设备l的装载耗时：Cpl；AGV从设备p输送到设备l的空载耗时：Vpl；一个极大数值：H；任务工件集合，J＝{J1，J2，...，Jn}；加工设备集合，M＝{M1，M2，...，Mm}；搬运设备集合，R＝{r1，r2，...，rk}；工件i的加工任务集合，Ji＝{Oi1，Oi2，...，Oin}；Tij：将工件i从工序Oij加工设备上运输到工序Oi(j+1)加工设备的运输任务；dij：工序任务Oij在机器上的开始加工时间；fij：工序任务Oij在机器上的任务完工时间；d′ij：运输任务Tij的开始搬运时间；f′ij：运输任务Tij的搬运完成时间；

其中，式(1)和式(2)分别表示调度问题的优化目标为最小化和最小化总运输时间；式(3)表示值为所有工件经过加工返回P/D口时间的最大值；式(4)和(5)表示任务在加工过程中不可被中断，其中(4)表示工件完工时间的更新，式(5)表示工件从P/D口出及进站均不需要花费额外的时间；式(6)‑(8)用于保证任务工件在完成加工和搬运操作后可以尽快的进入到搬运和加工状态，式(6)表示工件开始加工时间受运输到达时间制约；式(7)和(8)表示工件需等待完成加工方可执行运输操作；式(9)‑(11)表示加工设备处理加工任务具有唯一性：同一时刻一台设备仅可处理一个工件，一个工件同一时刻仅可被一台设备加工；其中式(12)表示搬运任务仅可被一台AGV服务；式(13)‑(19)表示执行搬运任务的唯一性：同一时刻一台AGV仅可处理一个搬运任务，一个搬运任务也仅可由一台AGV服务；式(20)表示问题不考虑装载和空载之间的运输时间偏差；

所述步骤B中运用所述多目标模因优化算法进行解析包括以下步骤：b1.对多目标模因算法中的参数进行设置，包括设置种群规模、迭代次数、交叉算子、变异算子和邻域搜索算子；

b2.采用工序和加工装备结合的方式编码，并进行种群初始化：设置inter‑no＝0，通过编码的随机生成方法与启发式规则方法相结合的方式生成 个个体，共同组成初始种群P(inter_no)；

cross

b3.基于交叉算子对种群进行交叉操作，生成含 个个体的新种群P (inter_no)；

mut

b4.基于变异算子对交叉后的种群进行变异操作，生成含 个个体的新种群P (inter_no)；

b5.将经过交叉变异操作后生成的新种群与父代种群进行合并操作，生成一个新的种child群P (inter_no)，其个体数量为

b6.对合并种群中的重复个体进行去重处理，对因为去重处理移除的个体，采用随机生成方法与启发式规则相结合的方式新生成等数量的个体进行群体填充，得到新种群b7.随机从种群中选择一定数量的个体，对此部分的个体进行邻域搜索，得到新的种群b8.对种群进行非支配排序和拥挤距离计算，并通过inter_no＝inter_no+1更新已迭代次数；

b9.根据非支配排序和拥挤度计算的结果，采用锦标赛选择策略从种群中选取 个个体，构成进入下一次迭代的父代种群P(inter_no)；

b10.对迭代次数进行判断：当inter_no＞inter_max，输出种群P(inter_no)，否则返回步骤b3。

2.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对交叉算子的设置包括以下步骤：

b11：从父代种群中随机的选择两个父代个体P1和P2，作为执行交叉操作的起点；

b12：基于映射关系，对工件排序层和AGV运输层进行关联位置匹配，检索得到父代染色体P1和P2同一位置且基因片段相同的索引位，保留相邻位置也满足位置与基因片段均相同的基因点位，并将其分别保留到子代C1和C2中；

b13：以染色体长度为基数N，随机生成一个1～N之间的数值为交叉基因位点Ng，将父代染色体P1和P2中在Ng位置前的基因分别继承到子代染色体C1和C2的对应位置上；

b14：分别对父代染色体P1和C2、P2和C1中工件排序层未被继承基因进行顺序缺失，提取得到缺失基因序列，随后以左向右为导向将缺失基因序列中的基因进行缺位基因非重复插入操作；

b15：提取子代一和子代二的染色体作为当次交叉操作的子代结果。

3.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对变异算子的设置包括以下步骤：获取需要参与变异操作判断的种群；基于变异概率逐个判断种群个体是否进行变异操作，当满足概率变异要求时以1/2概率选择进行工件排序层级变异或AGV运输层级变异；将经过变异操作后的新个体和未经变异的个体进行合并组成新的种群。

4.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对邻域搜索算子的设置包括以下步骤：

步骤1：随机选择关键路径工序集合中的一个工序Oij；

步骤2：为工序重新选择AGV运输设备，为了避免无效选择，新选择的运输设备不可为原搬运设备。

5.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b2中，包括获取基于工件的拓展双链式编码方案，所述拓展双链式编码方案包括两部分：工件排序层和AGV运输层。

6.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b2中运用启发式规则方法生成初始解，具体包括5种初始解生成方法，分别为4种启发式规则初始解生成策略和一种基于MNEH算法的启发式规则；4种启发式规则初始解生成策略为：Rule1：将AGV最早搬运完成策略与工序最早开工策略进行组合；Rule2：将AGV最小无效运输时间策略与工序最早开工策略进行组合；Rule3：将AGV最小无效运输时间策略与工序最早完工时间策略进行组合；Rule4：将AGV最早搬运完成策略与工序最早完工时间策略进行组合。

7.根据权利要求6所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述启发式规则随机使用，具体使用步骤如下：

c1.根据初始种群解码，产生工件工序；

c2.根据工序，从左至右，确定该工序是否需要AGV运输，是的话，继续，否则转步骤c3；

c21.确定当前空闲AGV的数量及位置，选择调度规则，指定搬运的AGV；

c22.移动所选择的AGV从当前位置到工件点取件，再到加工点；

c23.到达加工点后，放下工件，停在加工点处，不妨碍其他AGV运行；

c3.判断是否为最后一道工序，是的话，完成AGV分配，否则返回步骤c2。

说明书

有限运输能力约束的作业车间多目标调度方法

技术领域

[0001] 本发明涉及作业车间调度的技术领域，特别是有限运输能力约束的作业车间多目标调度方法。

背景技术

[0002] 针对传统的作业车间调度问题研究，其在求解过程中往往不考虑工件/物料在设备之间流转过程，或者将转移时间假设为某一固定值的运输时间。然而，在实际生产制造系统中，产品生产制造过程中与工件/物料关联的搬运活动所产生的物料搬运成本通常占产
品制造成本的15％～70％，并且通常需要占用25％的人力资源、55％的工厂空间和87％的
生产时间，因此在制定车间生产调度计划时考虑物料/工件在各设备之间的流转所带来的
影响也就显得尤为重要了。

[0003] 在以纯电力自动导引小车(Automatic Guided Vehicle,AGV)为主要自动物料储运设备的智能制造车间制定调度计划时，不仅需要考虑工件在加工设备上的处理过程，还
需要考虑工件在车间各网络运输节点(含加工设备、上/下料口以及物料中心仓库等非加设
备辅助节点)之间的流转过程。而在实际生产制造系统中，受设备采购成本、车间布局设计和车间实际运作等因素影响，由AGV等搬运设备构建的物料储运系统所能提供的运输能力
有限，无法保证所有搬运任务在生成时刻(完成加工任务等待转序)即可得到来自AGV的响
应。那么，如何在有限运输能力约束场景下制定合理的联合调度方案使制造系统既能取得
较优的加工效率，又能降低AGV的运输消耗(提升AGV的长期服务能力)就成为亟待解决的关
键问题。

发明内容

[0004] 针对上述缺陷，本发明的目的在于提出有限运输能力约束的作业车间多目标调度方法，在有限运输能力约束场景下制定合理的联合调度方案，既能使制造系统具有较优的
加工效率，又能降低AGV的运输消耗。

[0005] 为达此目的，本发明采用以下技术方案：

[0006] 有限运输能力约束的作业车间多目标调度方法，包括以下步骤：

[0007] 步骤A1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；

[0008] 步骤A2：确定作业车间的多目标调度场景的调度参数和先决条件；

[0009] 步骤A：基于步骤A1和A2，构建具有运输资源和加工设备资源双重约束的多目标车间调度模型；

[0010] 步骤B：基于多目标模因算法解析多目标车间调度模型；

[0011] 步骤C：根据解析结果获取最优的最小化最大完工时间和最小化AGV总运输时间，根据最优的最小化最大完工时间和最小化AGV总运输时间输出作业车间的多目标调度方
案。

[0012] 其中，步骤B包括通过求解MO‑JSPMH问题以解析多目标车间调度模型，包括：针对MO‑JSPMH问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略。

[0013] 优选的，在所述步骤A中，包括基于公式(1)和公式(2)构建调度模型：

[0014] f1＝minCmax (1)

[0015]

[0016] 其中，f1为最小化最大完工时间的目标函数，f2为最小化AGV总运输时间的目标函数；

[0017] 在所述步骤A中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：

[0018] Cmax≥fi(n+1) (3)

[0019] fij≥dij+pij (4)

[0020] pi0＝0，pi(m+1)＝0 (5)

[0021] di(j+1)≥f′ij (6)

[0022]

[0023] d′ij≥fij (8)

[0024]

[0025]

[0026]

[0027]

[0028]

[0029]

[0030]

[0031]

[0032]

[0033]

[0034] δij，lq+δlq，ij＝1 (19)

[0035] Cpl＝Vpl (20)。

[0036] 优选的，所述步骤B中运用所述多目标模因优化算法进行解析包括以下步骤：

[0037] b1.对多目标模因算法中的参数进行设置，包括设置种群规模、迭代次数、交叉算子、变异算子和邻域搜索算子；

[0038] b2.采用工序和加工装备结合的方式编码，并进行种群初始化：设置inter‑no＝0，通过编码的随机生成方法与启发式规则方法相结合的方式生成 个个体，共同组成初始种群P(inter_no)；
cross

[0039] b3.基于交叉算子对种群进行交叉操作，生成含 个个体的新种群P (inter_no)；

[0040] b4.基于变异算子对交叉后的种群进行变异操作，生成含 个个体的新种群Pmut(inter_no)；

[0041] b5.将经过交叉变异操作后生成的新种群与父代种群进行合并操作，生成一个新child
的种群P (inter_no)，其个体数量为

[0042] b6.对合并种群中的重复个体进行去重处理，对因为去重处理移除的个体，采用随机生成方法与启发式规则相结合的方式新生成等数量的个体进行群体填充，得到新种群

[0043] b7.随机从种群中选择一定数量的个体，对此部分的个体进行邻域搜索，得到新的种群

[0044] b8.对种群进行非支配排序和拥挤距离计算，并通过inter_no＝inter_no+1更新已迭代次数；

[0045] b9.根据非支配排序和拥挤度计算的结果，采用锦标赛选择策略从种群中选取 个个体，构成进入下一次迭代的父代种群P(inter_no)；

[0046] b10.对迭代次数进行判断：当inter_no＞inter_max，输出种群P(inter_no)，否则返回步骤b3。

[0047] 优选的，所述步骤b1中对交叉算子的设置包括以下步骤：

[0048] b11：从父代种群中随机选择两个父代个体P1和P2，作为执行交叉操作的起点；

[0049] b12：基于映射关系，对工件排序层和AGV运输层进行关联位置匹配，检索得到父代染色体P1和P2同一位置且基因片段相同的索引位，保留相邻位置也满足位置与基因片段均相同的基因点位，并将其分别保留到子代C1和C2中；

[0050] b13：以染色体长度为基数N，随机生成一个1～N之间的数值为交叉基因位点Ng，将父代染色体P1和P2中在Ng位置前的基因分别继承到子代染色体C1和C2的对应位置上；

[0051] b14：分别对父代染色体P1和C2、P2和C1中工件排序层未被继承基因进行顺序缺失，提取得到缺失基因序列，随后以左向右为导向将缺失基因序列中的基因进行缺位基因非重复插入操作；

[0052] b15：提取子代一和子代二的染色体作为当次交叉操作的子代结果。

[0053] 优选的，所述步骤b1中对变异算子的设置包括以下步骤：获取需要参与变异操作判断的种群；基于变异概率逐个判断种群个体是否进行变异操作，当满足概率变异要求时
以1/2概率选择进行工件排序层级变异或AGV运输层级变异；将经过变异操作后的新个体和
未经变异的个体进行合并组成新的种群。

[0054] 优选的，所述步骤b1中对邻域搜索算子的设置包括以下步骤：

[0055] 步骤1：随机选择关键路径工序集合中的一个工序Oij；

[0056] 步骤2：为工序重新选择AGV运输设备，为了避免无效选择，新选择的运输设备不可为原搬运设备。

[0057] 优选的，所述步骤b2中，包括获取基于工件的拓展双链式编码方案，所述拓展双链式编码方案包括两部分：工件排序层和AGV运输层。

[0058] 优选的，所述步骤b2中运用启发式规则方法生成初始解，具体包括5种初始解生成方法，分别为4种启发式规则初始解生成策略和一种基于MNEH算法的启发式规则；4种启发
式规则初始解生成策略为：Rule1：将AGV最早搬运完成策略与工序最早开工策略进行组合；
Rule2：将AGV最小无效运输时间策略与工序最早开工策略进行组合；Rule3：将AGV最小无效运输时间策略与工序最早完工时间策略进行组合；Rule4：将AGV最早搬运完成策略与工序
最早完工时间策略进行组合。

[0059] 优选的，所述启发式规则随机使用，具体使用步骤如下：

[0060] c1.根据初始种群解码，产生工件工序；

[0061] c2.根据工序，从左至右，确定该工序是否需要AGV运输，是的话，继续，否则转步骤c3；

[0062] c21.确定当前空闲AGV的数量及位置，选择调度规则，指定搬运的AGV；

[0063] c22.移动所选择的AGV从当前位置到工件点取件，再到加工点；

[0064] c23.到达加工点后，放下工件，停在加工点处，不妨碍其他AGV运行；

[0065] c3.判断是否为最后一道工序，是的话，完成AGV分配，否则返回步骤c2。

[0066] 上述技术方案包括以下有益效果：

[0067] 在本实施例中，首先构建具有运输资源和加工设备资源双重约束的多目标车间调度模型，其次，针对具有运输资源和加工设备资源双重约束的多目标车间调度模型提出了
一种多目标模因优化算法，基于所研究调度问题特征设计相应的编码、解码方法，并进行交叉、变异算子动作和选择策略的设计，得到最优的最小化最大完工时间(Cmax)和AGV总运输时间，根据上述两个条件对车间调度方案进行调整，实现AGV调度策略的优化，使得制造系统能够取得较优的加工效率，又能达到降低AGV的运输消耗的效果。

附图说明

[0068] 图1是本发明的考虑有限运输能力约束的作业车间简图；

[0069] 图2是本发明的多目标模因优化算法流程图；

[0070] 图3是本发明的SBOX交叉过程示意图：(a)父代染色体相同基因标记，(b)切点位置标识与基因继承，(c)缺失基因填充；

[0071] 图4是本发明的SWAP变异过程示意图：(a)工序排序层(JS)变异操作，(b)AGV运输层(TS)变异操作；

[0072] 图5是本发明的双链式染色体编码方式示意图；

[0073] 图6是本发明的解码结果示例图。

具体实施方式

[0074] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附
图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

[0075] 在本发明的描述中，需要理解的是，术语“纵向”、“横向”“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限
制。此外，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征，用于区别描述特征，无顺序之分，无轻重之分。

[0076] 在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。

[0077] 在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。

[0078] 下面结合图1至图6和表1、表2描述本发明实施例的有限运输能力约束的作业车间多目标调度方法，包括以下步骤：

[0079] 步骤A1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；

[0080] 步骤A2：确定作业车间的多目标调度场景的调度参数和先决条件；

[0081] 步骤A：基于步骤A1和A2，构建具有运输资源和加工设备资源双重约束的多目标车间调度模型；

[0082] 步骤B：基于多目标模因算法解析多目标车间调度模型；

[0083] 步骤C：根据解析结果获取最优的最小化最大完工时间和最小化AGV总运输时间，根据最优的最小化最大完工时间和最小化AGV总运输时间输出作业车间的多目标调度方
案。

[0084] 其中，步骤B包括通过求解MO‑JSPMH问题以解析多目标车间调度模型，包括：针对MO‑JSPMH问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略。

[0085] 具体的，针对有限运输能力约束的作业车间多目标调度问题，本发明提出一种多目标模因优化算法(Multi‑Objective Memetic Algorithm,MOMA)对问题进行求解。首先，构建具有运输资源和加工设备资源双重约束的多目标车间调度模型。其次，针对具有运输
资源和加工设备资源双重约束的多目标车间调度模型提出了一种多目标模因优化算法，基
于所研究调度问题特征设计相应的编码、解码方法，并进行交叉、变异算子动作和选择策略的设计，得到最优的最小化最大完工时间(Cmax)和AGV总运输时间，根据上述两个条件对车间调度方案进行调整，实现AGV调度策略的优化，使得制造系统能够取得较优的加工效率，又能达到降低AGV的运输消耗的效果。

[0086] 具体的，本方案首先基于实际生产车间构建有限运输能力约束的作业车间的多目标调度场景。如图1所示为某一考虑有限运输能力约束的作业车间简图，该作业车间由加工区、中转仓库和小车停车场三个区域构成，其中加工区域承担原材料/零部件的加工作业，由多个功能各异的加工单元(每个加工单元均包括加工设备和前/后物料缓存区)和导向路
径已知的运输轨道组成；中转仓库则作为原材料、零部件和半成品等物资的存储区域，负责车间物料的集散工作；小车停车场为闲置(车间对运力的需求小于运输系统所能提供的运
力)运输设备的存放地点。而工件在此作业车间的作业过程可描述为：基于工件的工艺约
束，由小车将工件搬运到加工区域的指定加工单元进行加工操作，在完成加工操作后依然
由小车进行转运工作(运输至下一工序的指定设备/中转仓库)，直至完成工件在该车间所
有工序加工任务后，再运输至中转仓库进行存储操作。

[0087] 进一步的，有限运输能力约束的作业车间的多目标调度场景的调度参数具体可描述为：有一待加工的工件集合J＝{1，2，...，n}，每个工件有nj道工序待加工，每道工序均由唯一指定加工设备m，m∈M＝{1，...，m}进行加工，并由r台AGV组成的搬运设备集合R＝{1，
2，...，r}负责工件在各节点(加工设备集合和中转仓库)间的转运操作，调度的优化目标为最小化最大完工时间(Cmax)和最小化总运输时间。

[0088] 进一步的，本方案中对作业车间的多目标调度问题在以下先决条件下进行优化：(1)初始时刻(可视为决策时刻)时，所有加工设备和AGV小车均处于空闲状态；(2)AGV在各
节点之间的搬运路线均基于最短路径原则进行规划，各AGV在执行搬运任务过程中互不干
扰；(3)AGV负责从上一工序加工设备的缓存区中承接相应的工件，并将其运送至下一工序
的缓存区；(4)忽略工件从缓存区装载到AGV的时间消耗和工件从AGV卸载到缓存区的时间
消耗；(5)AGV在任意运输节点之间的搬运耗时仅与节点之间的距离和AGV的运输速度相关，且不考虑运输过程中出现故障等特殊情况；(6)AGV任意两节点之间的搬运距离满足三角不
等式原则，即Tij＜Tik+Tkj，也意味着采用中转运输比直达运输需要产生更大的消耗；(7)每台AGV在同一时刻仅可为一个工件提供搬运服务，且该搬运服务具有不可中断性，且不考虑AGV发生故障的情况；(8)每台加工设备在同一时刻仅可进行一个工件的加工操作，且工件
在设备上的加工具有不可中断性，且不考虑加工设备发生故障的情况；(9)不同工件之间没有关联约束，但对同一工件而言必须先完成其前一道工序的加工，才可以进行后一工序的
加工操作；(10)加工设备处理工件的准则为先到先服务，即依据工件到达加工设备的先后
顺序进行排序加工；(11)所有待加工的工件在初始时刻均位于中转仓库。

[0089] 优选的，在所述步骤A中，包括基于公式(1)和公式(2)构建调度模型：

[0090] f1＝minCmax (1)

[0091]

[0092] 其中，f1为最小化最大完工时间的目标函数，f2为最小化AGV总运输时间的目标函数；

[0093] 在所述步骤A中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：

[0094] Cmax≥fi(n+1) (3)

[0095] fij≥dij+pij (4)

[0096] pi0＝0，pi(m+1)＝0 (5)

[0097] di(j+1)≥f′ij (6)

[0098]

[0099] d′ij≥fij (8)

[0100]

[0101]

[0102]

[0103]

[0104]

[0105]

[0106]

[0107]

[0108]

[0109]

[0110] δij，lq+δlq，ij＝1 (19)

[0111] Cpl＝Vpl (20)。

[0112] 具体的，公式(1)至公式(20)中各参数为：工件编号：i，l；加工设备编号：Ml；P/D口编号：M0；搬运设备编号：rs，rk；任务工序编号：Oij，Olq；工件i的释放任务：Oi0；工件i的回收任务：Oi(n+1)；工序Oij的加工时间：pij；AGV将物料从设备p输送到设备l的装载耗时：Cpl；AGV从设备p输送到设备l的空载耗时：Vpl；一个极大数值：H；任务工件集合，J＝{J1，J2，...，Jn}；加工设备集合，M＝{M1，M2，...，Mm}；搬运设备集合，R＝{r1，r2，..，rk}；工件i的加工任务集合，Ji＝{Oi1，Oi2，...，Oin}；Tij：将工件i从工序Oij加工设备上运输到工序Oi(j+1)加工设备的运输任务；dij：工序任务Oij在机器上的开始加工时间；fij：工序任务Oij在机器上的任务完工时间；d′ij：运输任务Tij的开始搬运时间；f′ij：运输任务Tij的搬运完成时间；

[0113]

[0114]

[0115]

[0116]

[0117]

[0118] 具体的，式(1)和式(2)分别表示调度问题的优化目标为最小化Cmax和最小化总运输时间；式(3)表示Cmax值为所有工件经过加工返回P/D口时间的最大值；式(4)和(5)表示任务在加工过程中不可被中断，其中(4)表示工件完工时间的更新，式(5)表示工件从P/D口出及进站均不需要花费额外的时间；式(6)‑(8)用于保证任务工件在完成加工和搬运操作后
可以尽快的进入到搬运和加工状态，式(6)表示工件开始加工时间受运输到达时间制约；式(7)和(8)表示工件需等待完成加工方可执行运输操作；式(9)‑(11)表示加工设备处理加工任务具有唯一性：同一时刻一台设备仅可处理一个工件，一个工件同一时刻仅可被一台设
备加工；其中式(12)表示搬运任务仅可被一台AGV服务；式(13)‑(19)表示执行搬运任务的唯一性：同一时刻一台AGV仅可处理一个搬运任务，一个搬运任务也仅可由一台AGV服务。式(20)表示问题不考虑装载和空载之间的运输时间偏差。

[0119] 优选的，所述步骤B中运用所述多目标模因优化算法进行解析包括以下步骤：

[0120] b1.对多目标模因算法中的参数进行设置，包括设置种群规模、迭代次数、交叉算子、变异算子和邻域搜索算子；

[0121] b2.采用工序和加工装备结合的方式编码，并进行种群初始化：设置inter‑no＝0，通过编码的随机生成方法与启发式规则方法相结合的方式生成 个个体，共同组成初始种群P(inter_no)；
cross

[0122] b3.基于交叉算子对种群进行交叉操作，生成含 个个体的新种群P (inter_no)；

[0123] b4.基于变异算子对交叉后的种群进行变异操作，生成含 个个体的新种群Pmut(inter_no)；

[0124] b5.将经过交叉变异操作后生成的新种群与父代种群进行合并操作，生成一个新child
的种群P (inter_no)，其个体数量为

[0125] b6.对合并种群中的重复个体进行去重处理，对因为去重处理移除的个体，采用随机生成方法与启发式规则相结合的方式新生成等数量的个体进行群体填充，得到新种群

[0126] b7.随机从种群中选择一定数量的个体，对此部分的个体进行邻域搜索，得到新的种群

[0127] b8.对种群进行非支配排序和拥挤距离计算，并通过inter_no＝inter_no+1更新已迭代次数；

[0128] b9.根据非支配排序和拥挤度计算的结果，采用锦标赛选择策略从种群中选取 个个体，构成进入下一次迭代的父代种群P(inter_no)；

[0129] b10.对迭代次数进行判断：当inter_no＞inter_max，输出种群P(inter_no)，否则返回步骤b3。

[0130] 具体的，如图2所示，为MO‑MA算法的总体流程框架，MO‑MA算法是通过将进化算法(Evolutionary Algorithm，FA)框架与特定问题相结合的一种邻域搜索方法，从而实现针对问题的全局搜索和局部挖掘：通过编码随机生成多个初始种群，并且通过在算法中嵌入
启发式规则，以生成具有较高质量的初始解方案，为算法在搜索的初始阶段提供优质的基
因片段，共同组成优质的初始种群；在生成父代种群后，分别通过交叉和变异操作生成新的子代种群，然后将子代和父代种群进行去重合并，并在组合种群中随机选取一部分个体进
行邻域搜索。

[0131] 本实施例中，在b9中使用二进制的锦标赛选择策略，将个体数量为N的种群随机的等分为来个体数量为 的两个竞争种群，随后从两种群中分别随机的选择一个个体进行“竞争”：优先选择支配解等级低的个体，若两个体等级在同一水平，则选择其中拥挤度值大的个体；最终，基于此个体选择策略可生成一个 个体数量的种群。因为受设备算力和问题自身难度限制，不能无限制地增加种群内个体的数量，同时过高的种群规模也容易导致群体
类个体的多样性降低，因此，选择合理的策略能够保证搜索过程中群体搜索能力与挖掘能
力的平衡。

[0132] 优选的，所述步骤b1中对交叉算子的设置包括以下步骤：

[0133] b11：从父代种群中随机的选择两个父代个体P1和P2，作为执行交叉操作的起点；

[0134] b12：基于映射关系，对工件排序层和AGV运输层进行关联位置匹配，检索得到父代染色体P1和P2同一位置且基因片段相同的索引位，保留相邻位置也满足位置与基因片段均相同的基因点位，并将其分别保留到子代C1和C2中；

[0135] b13：以染色体长度为基数N，随机生成一个1～N之间的数值为交叉基因位点Ng，将父代染色体P1和P2中在Ng位置前的基因分别继承到子代染色体C1和C2的对应位置上；

[0136] b14：分别对父代染色体P1和C2、P2和C1中工件排序层未被继承基因进行顺序缺失，提取得到缺失基因序列，随后以左向右为导向将缺失基因序列中的基因进行缺位基因非重复插入操作；

[0137] b15：提取子代一和子代二的染色体作为当次交叉操作的子代结果。

[0138] 具体的，步骤b12如图3(a)所示，步骤b13如图3(b)所示，步骤b14如图3(c)所示；交叉操作的实质是模拟父代染色体的基因交换过程，使子代从父代染色体中继承部分优秀基因。为了提升父代种群中的高质量基因片段遗传到子代种群，且考虑到双链式染色体编码
的中工序任务与搬运任务具有一定的关联性，故而在进行染色体交叉时需要考虑搬运任
务。本实施例中选择了综合性能表现更优的SBOX交叉作为本研究算法最终的交叉算子。

[0139] 优选的，所述步骤b1中对变异算子的设置包括以下步骤：获取需要参与变异操作判断的种群；基于变异概率逐个判断种群个体是否进行变异操作，当满足概率变异要求时
以1/2概率选择进行工件排序层级变异或AGV运输层级变异；将经过变异操作后的新个体和
未经变异的个体进行合并组成新的种群。

[0140] 具体的，工件排序层(JS)变异算子的设计过程如图4(a)所示，首先，随机选取需要进行变异操作个体中的两个非同工件编号的工件排序层基因片段；随后，通过将被选择的基因片段进行互换操作；最后，得到变异更新后的子代个体。

[0141] AGV运输层(TS)变异算子的设计过程如图4(b)所示，首先，随机选择需要进行变异操作个体中的一个AGV运输层基因片段；随后，从可用AGV搬运设备集中随机选择一台非当
前AGV的AGV设备替换原AGV；最后，得到变异更新后的子代个体。

[0142] 优选的，所述步骤b1中对邻域搜索算子的设置包括以下步骤：

[0143] 步骤1：随机选择关键路径工序集合中的一个工序Oij；

[0144] 步骤2：为工序重新选择AGV运输设备，为了避免无效选择，新选择的运输设备不可为原搬运设备。

[0145] 具体的，通过以下方式检索调度方案的关键路径：以加工工序Oij为基准，通过公式Earliest Latest(21)至公式(23)确定工序Oij的最早开工时间S (Oij)、最晚开工时间S (Oij)，当
Earliest Latest
S (Oij)＝S (Oij)时工序Oij为关键工序链中工序之一。

[0146]

[0147]

[0148]

[0149] 其中，CEarliest(POij)为工件i中先于Oij操作的工序， 为机器k中先于Latest
Oij操作的工序，S (SOij)为工件i中晚于Oij操作的工序， 为机器k中晚于Oij
操作的工序。

[0150] 优选的，所述步骤b2中，包括获取基于工件的拓展双链式编码方案，所述拓展双链式编码方案包括两部分：工件排序层和AGV运输层。

[0151] 具体的，如图5所示，工件排序层(JS)的基因数值表示对应的工件编号，而从左至右工件的累计出现频次数表示工件对应的工序号；AGV运输层(TS)的编码与通过工件编码
表示的工序信息一一对应，基因数值代表被指派执行对应工序搬运任务的AGV设备号。考虑到调度问题中需要参与调度决策制定的生产资源有加工设备和AGV运输设备两类，且可以
通过AGV“先将工件搬运到加工设备”这一动作描述实现工件在加工设备上排序的隐性表
达：先进行搬运操作的工件，对目标加工设备具有优先占用权。因此，本研究采用基于工件的拓展双链式编码方案。如图5所示，工件排序层基因片段的数字信息表示工件号，通过出现频次隐性表示当前工件编号的第几道工序，如第一个1表示工件1的第一道工序O11，第二个1表示工件1的第二道工序O12，并以此类推。AGV运输层中基因层的数值表示被指派于将工件搬运到工序设备的AGV编号，如第二个位置上数字2表示编号2的AGV小车将工件3搬运至
加工设备M3处(通过表2检索获取关联信息)，并以此类推。

[0152] 如表1和表2所示，分别为Bilge所提测试案例集合之一的各节点搬运时间矩阵信息表和工件加工工艺路径信息表，其中表1中数字表示两节点间需要花费的运输时间，如表
1中第一行的数值12表示从L/U运输的M4设备的运输耗时，表中其余数值均依此类推。参考
文献Bilge U.,Ulusoy G.A time window approach to simultaneous scheduling of 
machines andmaterial handling system in an FMS[J].Operations Research,199543
(6):1058‑1070.

[0153]

[0154] 表1

[0155]

[0156] 表2

[0157] 优选的，所述步骤b2中运用启发式规则方法生成初始解，具体包括5种初始解生成方法，分别为4种启发式规则初始解生成策略和一种基于MNEH算法的启发式规则；4种启发
式规则初始解生成策略为：Rule1：将AGV最早搬运完成策略与工序最早开工策略进行组合；
Rule2：将AGV最小无效运输时间策略与工序最早开工策略进行组合；Rule3：将AGV最小无效运输时间策略与工序最早完工时间策略进行组合；Rule4：将AGV最早搬运完成策略与工序
最早完工时间策略进行组合。

[0158] 具体的，启发式动态决策算法框架如下表所示，为以加工任务(任务开工时间和任务完工时间)和搬运任务(搬运任务完工时间和无效搬运时间)为辅助决策变量，进行动态
决策的算法流程伪代码，通过在算法流程伪代码的第10行的AGV选择策略和第13行任务选
择策略分别嵌入不同的选择策略从而组成4个不同的启发式规则：

[0159]

[0160]

[0161] MNEH算法流程如下表所示，其通过在传统NEH调度决策过程中嵌入AGV最早释放优先选择策略，实现算法基于问题的适应性改进，同时以Cmax值为排序方案选择指标，进行最终的排序方案的选择。

[0162]

[0163]

[0164] 通过嵌入具有较高求解质量效应的初始解生成策略，可以提升MO‑MA算法对有效解空间的搜索效率，降低MO‑MA的搜索时间，保证算法在有限时间内的求解质量；尤其是在大规模问题场景中，相较于无前置优质基因的搜索，具有优质方案基因继承的优化算法对
有限的搜索时间具有更高的利用率。

[0165] 优选的，所述启发式规则随机使用，具体使用步骤如下：

[0166] c1.根据初始种群解码，产生工件工序；

[0167] c2.根据工序，从左至右，确定该工序是否需要AGV运输，是的话，继续，否则转步骤c3；

[0168] c21.确定当前空闲AGV的数量及位置，选择调度规则，指定搬运的AGV；

[0169] c22.移动所选择的AGV从当前位置到工件点取件，再到加工点；

[0170] c23.到达加工点后，放下工件，停在加工点处，不妨碍其他AGV运行；

[0171] c3.判断是否为最后一道工序，是的话，完成AGV分配，否则返回步骤c2。

[0172] 具体的，在完成编码后，还需对其进行解码以得到目标值，在解码过程中需要考虑到工件的工艺约束，工序、加工设备和AGV的不可间断性和独占性。以图5中的工序O11和工序O21为例，其均为对应工件的首道工序，但受到指派服务该工序的搬运AGV和加工设备均为同一设备影响，基于编码信息工序O21需要放在工序O11后进行搬运及加工。

[0173] 解码步骤如下：

[0174] 步骤1：从工件排序层(JS)左侧开始进行基因片段提取，并将其转换成对应的工序Oip；

[0175] 步骤2：通过映射关系，从工件加工路径信息表中获取工序Oip的加工设备Mip、前序工序Oi(p‑1)的加工设备Mi(p‑1)和工序Oip的加工时间 并通过AGV运输层基因片段映射得到承运AGV；

[0176] 步骤3：通过前向检索得到当前AGV的释放时间 和承运AGV的释放位置节点a
D以及加工设备Mi(p‑1)的位置节点 计算AGV的空载运输时间 通过公式(24)得到
AGV到达加工设备Mi(p‑1)的时间

[0177]

[0178] 步骤4：通过工件加工信息得到工件完成工序的释放时间 并根据公式(25)判断工件的开始承运时间 并通过当前位置节点 和目标节点 计算AGV
的装载运输时间 通过公式(26)计算得到AGV到达加工设备Mip的时间 并同步更新
当前AGV的释放时间

[0179]

[0180]

[0181] 步骤5：通过对加工设备进行前向检索得到加工设备完成排在工序Oip前加工任务的释放时间 并根据公式(27)判断工序的最早开工时间 并基于工序的加工时间
更新工件i的完工时间

[0182]

[0183] 步骤6：如果工件排序层(JS)中的所有基因均已进行解码，则结束解码程序；反之，返回步骤1。

[0184] 如图6所示，为在图5编码情况下的解码结果。

[0185] 根据本发明实施例的有限运输能力约束的作业车间多目标调度方法的其他构成等以及操作对于本领域普通技术人员而言都是已知的，这里不再详细描述。

[0186] 在本说明书的描述中，参考术语“实施例”、“示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

[0187] 尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。