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

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


背景技术：

2.针对传统的作业车间调度问题研究，其在求解过程中往往不考虑工件/物料在设备之间流 转过程，或者将转移时间假设为某一固定值的运输时间。然而，在实际生产制造系统中，产 品生产制造过程中与工件/物料关联的搬运活动所产生的物料搬运成本通常占产品制造成本 的15％～70％，并且通常需要占用25％的人力资源、55％的工厂空间和87％的生产时间，因此在 制定车间生产调度计划时考虑物料/工件在各设备之间的流转所带来的影响也就显得尤为重 要了。
3.在以纯电力自动导引小车(automatic guided vehicle,agv)为主要自动物料储运设备 的智能制造车间制定调度计划时，不仅需要考虑工件在加工设备上的处理过程，还需要考虑 工件在车间各网络运输节点(含加工设备、上/下料口以及物料中心仓库等非加设备辅助节点) 之间的流转过程。而在实际生产制造系统中，受设备采购成本、车间布局设计和车间实际运 作等因素影响，由agv等搬运设备构建的物料储运系统所能提供的运输能力有限，无法保证 所有搬运任务在生成时刻(完成加工任务等待转序)即可得到来自agv的响应。那么，如何 在有限运输能力约束场景下制定合理的联合调度方案使制造系统既能取得较优的加工效率， 又能降低agv的运输消耗(提升agv的长期服务能力)就成为亟待解决的关键问题。


技术实现要素：

4.针对上述缺陷，本发明的目的在于提出有限运输能力约束的作业车间多目标调度方法， 在有限运输能力约束场景下制定合理的联合调度方案，既能使制造系统具有较优的加工效 率，又能降低agv的运输消耗。
5.为达此目的，本发明采用以下技术方案：
6.有限运输能力约束的作业车间多目标调度方法，包括以下步骤：
7.步骤a1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；
8.步骤a2：确定作业车间的多目标调度场景的调度参数和先决条件；
9.步骤a：基于步骤a1和a2，构建具有运输资源和加工设备资源双重约束的多目标车间调 度模型；
10.步骤b：基于多目标莫因算法解析多目标车间调度模型；
11.步骤c：根据解析结果获取最优的最小化最大完工时间和最小化agv总运输时间，根据 最优的最小化最大完工时间和最小化agv总运输时间输出作业车间的多目标调度方案。
12.其中，步骤b包括通过求解mo-jspmh问题以解析多目标车间调度模型，包括：针对 mo-jspmh问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略。
13.优选的，在所述步骤a中，包括基于公式(1)和公式(2)构建调度模型：
14.f1＝minc
max
ꢀꢀꢀꢀ
(1)
[0015][0016]
其中，f1为最小化最大完工时间的目标函数，f2为最小化agv总运输时间的目标函数；
[0017]
在所述步骤a中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：
[0018]cmax
≥f
i(n+1)
ꢀꢀꢀꢀ
(3)
[0019]fij
≥d
ij
+p
ij
ꢀꢀꢀꢀ
(4)
[0020]
p
i0
＝0，p
i(m+1)
＝0
ꢀꢀꢀꢀ
(5)
[0021]di(j+1)
≥f
′
ij
ꢀꢀꢀꢀ
(6)
[0022][0023]d′
ij
≥f
ij
ꢀꢀꢀꢀ
(8)
[0024][0025][0026][0027][0028][0029][0030][0031][0032][0033][0034]
δ
ij，lq
+δ
lq，ij
＝1
ꢀꢀꢀꢀ
(19)
[0035]cpl
＝v
pl
ꢀꢀꢀꢀ
(20)。
[0036]
优选的，所述步骤b中运用所述多目标模因优化算法进行解析包括以下步骤：
[0037]
b1.对多目标莫因算法中的参数进行设置，包括设置种群规模、迭代次数、交叉算子、 变异算子和邻域搜索算子；
[0038]
b2.采用工序和加工装备结合的方式编码，并进行种群初始化：设置inter-no
＝0，
通过 编码的随机生成方法与启发式规则方法相结合的方式生成个个体，共同组成初始种群 p(inter_no)；
[0039]
b3.基于交叉算子对种群进行交叉操作，生成含个个体的新种群p
cross
(inter_no)；
[0040]
b4.基于变异算子对交叉后的种群进行变异操作，生成含个个体的新种群 p
mut
(inter_no)；
[0041]
b5.将经过交叉变异操作后生成的新种群与父代种群进行合并操作，生成一个新的种群 p
child
(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：随机选择关键路径工序集合中的一个工序o
ij
；
[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]
在本实施例中，首先构建具有运输资源和加工设备资源双重约束的多目标车间调度模型， 其次，针对具有运输资源和加工设备资源双重约束的多目标车间调度模型提出了一种多目标 模因优化算法，基于所研究调度问题特征设计相应的编码、解码方法，并进行交叉、变异算 子动作和选择策略的设计，得到最优的最小化最大完工时间(c
max
)和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]
在本发明的描述中，除非另有说明，“多个”的含义是两个或两个以上。
[0079]
在本发明的描述中，需要说明的是，除非另有明确的规定和限定，术语“安装”、“相连”、
ꢀ“
连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可 以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是 两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发 明中的具体含义。
[0080]
下面结合图1至图6和表1、表2描述本发明实施例的有限运输能力约束的作业车间多 目标调度方法，包括以下步骤：
[0081]
步骤a1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；
[0082]
步骤a2：确定作业车间的多目标调度场景的调度参数和先决条件；
[0083]
步骤a：基于步骤a1和a2，构建具有运输资源和加工设备资源双重约束的多目标车间调 度模型；
[0084]
步骤b：基于多目标莫因算法解析多目标车间调度模型；
[0085]
步骤c：根据解析结果获取最优的最小化最大完工时间和最小化agv总运输时间，根据 最优的最小化最大完工时间和最小化agv总运输时间输出作业车间的多目标调度方案。
[0086]
其中，步骤b包括通过求解mo-jspmh问题以解析多目标车间调度模型，包括：针对 mo-jspmh问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略。
[0087]
具体的，针对有限运输能力约束的作业车间多目标调度问题，本发明提出一种多目标模 因优化算法(multi-objective memetic algorithm,moma)对问题进行求解。首先，构建具 有运输资源和加工设备资源双重约束的多目标车间调度模型。其次，针对具有运输资源和加 工设备资源双重约束的多目标车间调度模型提出了一种多目标模因优化算法，基于所研究调 度问题特征设计相应的编码、解码方法，并进行交叉、变异算子动作和选择策略的设计，得 到最优的最小化最大完工时间(c
max
)和agv总运输时间，根据上述两个条件对车间调度方 案进行调整，实现agv调度策略的优化，使得制造系统能够取得较优的加工效率，又能达到 降低agv的运输消耗的效果。
[0088]
具体的，本方案首先基于实际生产车间构建有限运输能力约束的作业车间的多目标调度 场景。如图1所示为某一考虑有限运输能力约束的作业车间简图，该作业车间由加工区、中 转仓库和小车停车场三个区域构成，其中加工区域承担原材料/零部件的加工作业，由多个功 能各异的加工单元(每个加工单元均包括加工设备和前/后物料缓存区)和导
向路径已知的运 输轨道组成；中转仓库则作为原材料、零部件和半成品等物资的存储区域，负责车间物料的 集散工作；小车停车场为闲置(车间对运力的需求小于运输系统所能提供的运力)运输设备 的存放地点。而工件在此作业车间的作业过程可描述为：基于工件的工艺约束，由小车将工 件搬运到加工区域的指定加工单元进行加工操作，在完成加工操作后依然由小车进行转运工 作(运输至下一工序的指定设备/中转仓库)，直至完成工件在该车间所有工序加工任务后， 再运输至中转仓库进行存储操作。
[0089]
进一步的，有限运输能力约束的作业车间的多目标调度场景的调度参数具体可描述为： 有一待加工的工件集合j＝{1，2，...，n}，每个工件有nj道工序待加工，每道工序均由唯一指定 加工设备m，m∈m＝{1，...，m}进行加工，并由r台agv组成的搬运设备集合r＝{1，2，...，r}负 责工件在各节点(加工设备集合和中转仓库)间的转运操作，调度的优化目标为最小化最大 完工时间(c
max
)和最小化总运输时间。
[0090]
进一步的，本方案中对作业车间的多目标调度问题在以下先决条件下进行优化：(1)初 始时刻(可视为决策时刻)时，所有加工设备和agv小车均处于空闲状态；(2)agv在各节 点之间的搬运路线均基于最短路径原则进行规划，各agv在执行搬运任务过程中互不干扰； (3)agv负责从上一工序加工设备的缓存区中承接相应的工件，并将其运送至下一工序的缓 存区；(4)忽略工件从缓存区装载到agv的时间消耗和工件从agv卸载到缓存区的时间消耗； (5)agv在任意运输节点之间的搬运耗时仅与节点之间的距离和agv的运输速度相关，且不 考虑运输过程中出现故障等特殊情况；(6)agv任意两节点之间的搬运距离满足三角不等式 原则，即t
ij
＜t
ik
+t
kj
，也意味着采用中转运输比直达运输需要产生更大的消耗；(7)每台 agv在同一时刻仅可为一个工件提供搬运服务，且该搬运服务具有不可中断性，且不考虑agv 发生故障的情况；(8)每台加工设备在同一时刻仅可进行一个工件的加工操作，且工件在设 备上的加工具有不可中断性，且不考虑加工设备发生故障的情况；(9)不同工件之间没有关 联约束，但对同一工件而言必须先完成其前一道工序的加工，才可以进行后一工序的加工操 作；(10)加工设备处理工件的准则为先到先服务，即依据工件到达加工设备的先后顺序进行 排序加工；(11)所有待加工的工件在初始时刻均位于中转仓库。
[0091]
优选的，在所述步骤a中，包括基于公式(1)和公式(2)构建调度模型：
[0092]
f1＝minc
max
ꢀꢀꢀꢀ
(1)
[0093][0094]
其中，f1为最小化最大完工时间的目标函数，f2为最小化agv总运输时间的目标函数；
[0095]
在所述步骤a中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：
[0096]cmax
≥f
i(n+1)
ꢀꢀꢀꢀ
(3)
[0097]fij
≥d
ij
+p
ij
ꢀꢀꢀꢀ
(4)
[0098]
p
i0
＝0，p
i(m+1)
＝0
ꢀꢀꢀꢀ
(5)
[0099]di(j+1)
≥f
′
ij
ꢀꢀꢀꢀ
(6)
[0100][0101]d′
ij
≥f
ij
ꢀꢀꢀꢀ
(8)
[0102][0103][0104][0105][0106][0107][0108][0109][0110][0111][0112]
δ
ij，lq
+δ
lq，ij
＝1
ꢀꢀꢀꢀ
(19)
[0113]cpl
＝v
pl
ꢀꢀꢀꢀ
(20)。
[0114]
具体的，公式(1)至公式(20)中各参数为：工件编号：i，l；加工设备编号：m
l
；p/d 口编号：m0；搬运设备编号：rs，rk；任务工序编号：o
ij
，o
lq
；工件i的释放任务：o
i0
；工件i 的回收任务：o
i(n+1)
；工序o
ij
的加工时间：p
ij
；agv将物料从设备p输送到设备l的装载耗时：c
pl
；agv从设备p输送到设备l的空载耗时：v
pl
；一个极大数值：h；任务工件集合， j＝{j1，j2，...，jn}；加工设备集合，m＝{m1，m2，...，mm}；搬运设备集合，r＝{r1，r2，...，rk}； 工件i的加工任务集合，ji＝{o
i1
，o
i2
，...，o
in
}；t
ij
：将工件i从工序o
ij
加工设备上运输到工序 o
i(j+1)
加工设备的运输任务；d
ij
：工序任务o
ij
在机器上的开始加工时间；f
ij
：工序任务o
ij
在 机器上的任务完工时间；d
′
ij
：运输任务t
ij
的开始搬运时间；f
′
ij
：运输任务t
ij
的搬运完成时间；
[0115][0116][0117][0118]
前agv的agv设备替换原agv；最后，得到变异更新后的子代个体。
[0144]
优选的，所述步骤b1中对邻域搜索算子的设置包括以下步骤：
[0145]
步骤1：随机选择关键路径工序集合中的一个工序o
ij
；
[0146]
步骤2：为工序重新选择agv运输设备，为了避免无效选择，新选择的运输设备不可为 原搬运设备。
[0147]
具体的，通过以下方式检索调度方案的关键路径：以加工工序o
ij
为基准，通过公式(21) 至公式(23)确定工序o
ij
的最早开工时间s
earliest
(o
ij
)、最晚开工时间s
latest
(o
ij
)，当 s
earliest
(o
ij
)＝s
latest
(o
ij
)时工序o
ij
为关键工序链中工序之一。
[0148][0149][0150][0151]
其中，c
earliest
(po
ij
)为工件i中先于o
ij
操作的工序，为机器k中先于o
ij
操 作的工序，s
latest
(so
ij
)为工件i中晚于o
ij
操作的工序，为机器k中晚于o
ij
操作的 工序。
[0152]
优选的，所述步骤b2中，包括获取基于工件的拓展双链式编码方案，所述扩展双链式编 码方案包括两部分：工件排序层和agv运输层。
[0153]
具体的，如图5所示，工件排序层(js)的基因数值表示对应的工件编号，而从左至右 工件的累计出现频次数表示工件对应的工序号；agv运输层(ts)的编码与通过工件编码表 示的工序信息一一对应，基因数值代表被指派执行对应工序搬运任务的agv设备号。考虑到 调度问题中需要参与调度决策制定的生产资源有加工设备和agv运输设备两类，且可以通过 agv“先将工件搬运到加工设备”这一动作描述实现工件在加工设备上排序的隐性表达：先进 行搬运操作的工件，对目标加工设备具有优先占用权。因此，本研究采用基于工件的拓展双 链式编码方案。如图5所示，工件排序层基因片段的数字信息表示工件号，通过出现频次隐 性表示当前工件编号的第几道工序，如第一个1表示工件1的第一道工序o
11
，第二个1表示 工件1的第二道工序o
12
，并以此类推。agv运输层中基因层的数值表示被指派于将工件搬运 到工序设备的agv编号，如第二个位置上数字2表示编号2的agv小车将工件3搬运至加工 设备m3处(通过表2检索获取关联信息)，并以此类推。
[0154]
如表1和表2所示，分别为bilge所提测试案例集合之一的各节点搬运时间矩阵信息表 和工件加工工艺路径信息表，其中表1中数字表示两节点间需要花费的运输时间，如表1中 第一行的数值12表示从l/u运输的m4设备的运输耗时，表中其余数值均依此类推。参考文 献bilge u.，ulusoy g.a time window approach to simultaneous scheduling of machines
ꢀꢀ
and material handling system in an fms[j].operations research，199543(6)：1058—1070.
表1
[0155]
优选的，所述步骤b2中运用启发式规则方法生成初始解，具体包括5种初始解生成方法， 分别为4种启发式规则初始解生成策略和一种基于mneh算法的启发式规则；4种启发式规则 初始解生成策略为：rule1：将agv最早搬运完成策略与工序最早开工策略进行组合；rule2： 将agv最小无效运输时间策略与工序最早开工策略进行组合；rule3：将agv最小无效运输时 间策略与工序最早完工时间策略进行组合；rule4：将agv最早搬运完成策略与工序最早完工 时间策略进行组合。
[0156]
具体的，启发式动态决策算法框架如下表所示，为以加工任务(任务开工时间和任务完 工时间)和搬运任务(搬运任务完工时间和无效搬运时间)为辅助决策变量，进行动态决策 的算法流程伪代码，通过在算法流程伪代码的第10行的agv选择策略和第13行任务选择策 略分别嵌入不同的选择策略从而组成4个不同的启发式规则：
[0157][0158]
mneh算法流程如下表所示，其通过在传统neh调度决策过程中嵌入agv最早释放优先选 择策略，实现算法基于问题的适应性改进，同时以c
max
值为排序方案选择指标，进行最终的 排序方案的选择。
[0159]
[0160][0161]
通过嵌入具有较高求解质量效应的初始解生成策略，可以提升mo-ma算法对有效解空间 的搜索效率，降低mo-ma的搜索时间，保证算法在有限时间内的求解质量；尤其是在大规模 问题场景中，相较于无前置优质基因的搜索，具有优质方案基因继承的优化算法对有限的搜 索时间具有更高的利用率。
[0162]
9、根据权利要求8所述的有限运输能力约束的作业车间多目标调度方法，其特征在于： 所述启发式规则随机使用，具体使用步骤如下：
[0163]
c1.根据初始种群解码，产生工件工序；
[0164]
c2.根据工序，从左至右，确定该工序是否需要agv运输，是的话，继续，否则转步骤 c3；
[0165]
c21.确定当前空闲agv的数量及位置，选择调度规则，指定搬运的agv；
[0166]
c22.移动所选择的agv从当前位置到工件点取件，再到加工点；
[0167]
c23.到达加工点后，放下工件，停在加工点处，不妨碍其他agv运行；
[0168]
c3.判断是否为最后一道工序，是的话，完成agv分配，否则返回步骤c2。
[0169]
具体的，在完成编码后，还需对其进行解码以得到目标值，在解码过程中需要考虑到工 件的工艺约束，工序、加工设备和agv的不可间断性和独占性。以图5中的工序o
11
和工序o
21
为例，其均为对应工件的首道工序，但受到指派服务该工序的搬运agv和加工设备均为同一 设备影响，基于编码信息工序o
21
需要放在工序o
11
后进行搬运及加工。
[0170]
解码步骤如下：
[0171]
步骤1：从工件排序层(js)左侧开始进行基因片段提取，并将其转换成对应的工序o
ip
；
[0172]
步骤2：通过映射关系，从工件加工路径信息表中获取工序o
ip
的加工设备m
ip
、前序工 序o
i(p-1)
的加工设备m
i(p-1)
和工序o
ip
的加工时间并通过agv运输层基因片段映射得到 承运agv；
[0173]
步骤3：通过前向检索得到当前agv的释放时间和承运agv的释放位置节点da以 及加工设备m
i(p-1)
的位置节点计算agv的空载运输时间通过公式(24)得到 agv到达加工设备m
i(p-1)
的时间
[0174][0175]
步骤4：通过工件加工信息得到工件完成工序的释放时间并根据公式(25)判 断工件的开始承运时间并通过当前位置节点和目标节点计算agv的装载运 输时间通过公式(26)计算得到agv到达加工设备m
ip
的时间并同步更新当前 agv的释放时间
[0176][0177][0178]
步骤5：通过对加工设备进行前向检索得到加工设备完成排在工序o
ip
前加工任务的释放 时间并根据公式(27)判断工序的最早开工时间并基于工序的加工时间更 新工件i的完工时间
[0179][0180]
步骤6：如果工件排序层(js)中的所有基因均已进行解码，则结束解码程序；反之， 返回步骤1。
[0181]
如图6所示，为在图5编码情况下的解码结果。
[0182]
根据本发明实施例的有限运输能力约束的作业车间多目标调度方法的其他构成等以及操 作对于本领域普通技术人员而言都是已知的，这里不再详细描述。
[0183]
在本说明书的描述中，参考术语“实施例”、“示例”等的描述意指结合该实施例或示例 描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明 书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、 结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
[0184]
尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本 发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的 范围由权利要求及其等同物限定。

技术特征：
1.有限运输能力约束的作业车间多目标调度方法，其特征在于：包括以下步骤：步骤a1：根据实际生产车间构建有限运输能力约束的作业车间的多目标调度场景；步骤a2：确定作业车间的多目标调度场景的调度参数和先决条件；步骤a：基于步骤a1和a2，构建具有运输资源和加工设备资源双重约束的多目标车间调度模型；步骤b：基于多目标莫因算法解析多目标车间调度模型；步骤c：根据解析结果获取最优的最小化最大完工时间和最小化agv总运输时间，根据最优的最小化最大完工时间和最小化agv总运输时间输出作业车间的多目标调度方案；其中，步骤b包括通过求解mo-jspmh问题以解析多目标车间调度模型，包括：针对m0-jspmh问题特征设计编码、解码方案，执行交叉、变异算子操作，获取初始解以生成策略。2.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：在所述步骤a中，包括基于公式(1)和公式(2)构建调度模型：f1＝min c
max
ꢀꢀꢀꢀ
(1)其中，f1为最小化最大完工时间的目标函数，f2为最小化agv总运输时间的目标函数；在所述步骤a中，构建调度模型还包括设置约束条件，约束条件包括公式(3)至公式(20)：c
max
≥f
i(n+1)
ꢀꢀꢀꢀ
(3)f
ij
≥d
ij
+p
ij
ꢀꢀꢀꢀ
(4)p
i0
＝0，p
i(m+1)
＝0
ꢀꢀꢀꢀ
(5)d
i(j+1)
≥f
′
ij
ꢀꢀꢀꢀ
(6)d
′
ij
≥f
ij
ꢀꢀꢀꢀ
(8)(8)(8)(8)(8)(8)(8)(8)(8)
δ
ij，lq
+δ
lq，ij
＝1
ꢀꢀꢀꢀ
(19)c
pl
＝v
pl
ꢀꢀꢀꢀ
(20)。3.根据权利要求1所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b中运用所述多目标模因优化算法进行解析包括以下步骤：b1.对多目标莫因算法中的参数进行设置，包括设置种群规模、迭代次数、交叉算子、变异算子和邻域搜索算子；b2.采用工序和加工装备结合的方式编码，并进行种群初始化：设置inter_
no
＝0，通过编码的随机生成方法与启发式规则方法相结合的方式生成个个体，共同组成初始种群p(inter_no)；b3.基于交叉算子对种群进行交叉操作，生成含个个体的新种群p
cross
(inter_no)；b4.基于变异算子对交叉后的种群进行变异操作，生成含个个体的新种群p
mut
(inter_no)；b5.将经过交叉变异操作后生成的新种群与父代种群进行合并操作，生成一个新的种群p
child
(inter_no)，其个体数量为b6.对合并种群中的重复个体进行去重处理，对因为去重处理移除的个体，采用随机生成方法与启发式规则相结合的方式新生成等数量的个体进行群体填充，得到新种群b7.随机从种群中选择一定数量的个体，对此部分的个体进行邻域搜索，得到新的种群b8.对种群进行非支配排序和拥挤距离计算，并通过inter_no＝inter_no+1更新已迭代次数；b9.根据非支配排序和拥挤度计算的结果，采用锦标赛选择策略从种群中选取个个体，构成进入下一次迭代的父代种群p(inter_no)；b10.对迭代次数进行判断：当inter_no＞inter_max，输出种群p(inter_no)，否则返回步骤b3。4.根据权利要求3所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对交叉算子的设置包括以下步骤：b11：从父代种群中随机的选择两个父代个体p1和p2，作为执行交叉操作的起点；b12：基于映射关系，对工件排序层和agv运输层进行关联位置匹配，检索得到父代染色体p1和p2同一位置且基因片段相同的索引位，保留相邻位置也满足位置与基因片段均相同的基因点位，并将其分别保留到子代c1和c2中；b13：以染色体长度为基数n，随机生成一个1～n之间的数值为交叉基因位点n
g
，将父代染色体p1和p2中在n
g
位置前的基因分别继承到子代染色体c1和c2的对应位置上；b14：分别对父代染色体p1和c2、p2和c1中工件排序层未被继承基因进行顺序缺失，提取得到缺失基因序列，随后以左向右为导向将缺失基因序列中的基因进行缺位基因非重复插
入操作；b15：提取子代一和子代二的染色体作为当次交叉操作的子代结果。5.根据权利要求3所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对变异算子的设置包括以下步骤：获取需要参与变异操作判断的种群；基于变异概率逐个判断种群个体是否进行变异操作，当满足概率变异要求时以1/2概率选择进行工件排序层级变异或agv运输层级变异；将经过变异操作后的新个体和未经变异的个体进行合并组成新的种群。6.根据权利要求3所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b1中对邻域搜索算子的设置包括以下步骤：步骤1：随机选择关键路径工序集合中的一个工序o
ij
；步骤2：为工序重新选择agv运输设备，为了避免无效选择，新选择的运输设备不可为原搬运设备。7.根据权利要求3所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b2中，包括获取基于工件的拓展双链式编码方案，所述扩展双链式编码方案包括两部分：工件排序层和agv运输层。8.根据权利要求3所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述步骤b2中运用启发式规则方法生成初始解，具体包括5种初始解生成方法，分别为4种启发式规则初始解生成策略和一种基于mneh算法的启发式规则；4种启发式规则初始解生成策略为：rule1：将agv最早搬运完成策略与工序最早开工策略进行组合；rule2：将agv最小无效运输时间策略与工序最早开工策略进行组合；rule3：将agv最小无效运输时间策略与工序最早完工时间策略进行组合；rule4：将agv最早搬运完成策略与工序最早完工时间策略进行组合。9.根据权利要求8所述的有限运输能力约束的作业车间多目标调度方法，其特征在于：所述启发式规则随机使用，具体使用步骤如下：c1.根据初始种群解码，产生工件工序；c2.根据工序，从左至右，确定该工序是否需要agv运输，是的话，继续，否则转步骤c3；c21.确定当前空闲agv的数量及位置，选择调度规则，指定搬运的agv；c22.移动所选择的agv从当前位置到工件点取件，再到加工点；c23.到达加工点后，放下工件，停在加工点处，不妨碍其他agv运行；c3.判断是否为最后一道工序，是的话，完成agv分配，否则返回步骤c2。

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


技术研发人员：彭乘风 廖勇 李翔
受保护的技术使用者：湘南学院
技术研发日：2022.01.28
技术公布日：2022/7/5