一种集成多AGV柔性作业车间调度方法、装置及介质与流程

一种集成多agv柔性作业车间调度方法、装置及介质
技术领域
1.本发明涉及生产调度技术领域，尤其涉及一种集成多agv柔性作业车间调度方法、装置及介质。


背景技术：

2.近年来越来越高效的智能自动化生产方式受到社会的广泛关注。产品向着更加个性化、定制化方向发展，制造车间生产组织方式更加柔性化，从而使得调度问题变得更为复杂。柔性作业车间调度问题(flexible job shop scheduling problem，fjsp)考虑了机器柔性问题，即一个工序可由多个工位加工，是作业车间调度问题(job shop scheduling problem，jsp)的重要拓展。近年来agv在制造工厂和仓库、物流场景中得到了广泛的应用，提高了物流、制造过程中的自动化和柔性化。当前对于fjsp已有大量研究，而对于集成多agv的fjsp(fjsp
‑
ma)要少得多，尤其是考虑agv数量限制和多工序多工位的大规模问题，该问题的解空间更大，约束更多，更难求解，但是如果忽略这些客观条件，容易使加工计划与实际生产相违背。因此，求解集成多agv的fjsp问题得到的调度结果更加贴近实际情况，符合实际生产的需求，可以更科学地指导实际生产，进一步提高工厂的智慧化程度。
3.fjsp
‑
ma与fjsp问题类似，属于离散的组合优化问题，当前求解这一类问题主要方法是智能优化方法，其中应用最多且最为高效的是遗传算法与局部搜索算法的混合方法。遗传算法基于种群，全局搜索能力强，局部搜索能力弱，容易陷入局部最优解，与局部搜索算法的结合很好地弥补了这个缺点；遗传算法及其混合算法等传统方法利用种群机制保证了解的多样性，但是在计算过程中需要保存大量的个体解，并且需要在代表种群的矩阵中频繁存取每一个解，并进行大量选择、交叉、变异操作，这些操作具有一定的盲目性、计算资源开销较大。另外传统方法控制参数较多，在设计实现以及调试应用时不够方便。


技术实现要素：

4.为至少一定程度上解决现有技术中存在的技术问题之一，本发明的目的在于提供一种集成多agv柔性作业车间调度方法、装置及介质。
5.本发明所采用的技术方案是：
6.一种集成多agv柔性作业车间调度方法，包括以下步骤：
7.获取调度任务参数；
8.初始化算法参数，所述算法参数包括最大完工时间记忆库的大小h；
9.对集成多agv的柔性作业车间调度方案进行编码，初始化当前解x；
10.对当前解进行解码，获得最大完工时间f(x)，初始化记忆库中的值为当前解的最大完工时间；
11.执行带最大完工时间记忆库的变邻域局部搜索算法，直到算法终止；
12.在算法终止后，输出并保存最优的调度方案；
13.其中，所述最大完工时间记忆库用来引导算法的邻域变换方向；算法终止的条件
为：当前解的未改善次数达到预设最大值或迭代次数大于或等于最大迭代次数。
14.进一步地，所述执行带最大完工时间记忆库的变邻域局部搜索算法，包括：
15.生成当前解的邻域候选解y，对候选解进行解码，获得候选解最大完工时间f(y)；
16.如果候选解的最大完工时间大于当前解的最大完工时间，候选解未改善次数计数器加1，或者计数器置零；
17.如果候选解的最大完工时间小于最优解的最大完工时间，最优解替换为候选解，最优解的最大完工时间替换为候选解的最大完工时间；
18.设记忆库参照数h等于it除以h取余数；
19.如果候选解的最大完工时间f(y)小于记忆库中第h个数值，或者候选解的最大完工时间f(y)小于等于当前解的最大完工时间f(x)，则将当前解x替换为候选解y，并替换相应最大完工时间；
20.如果候选解的最大完工时间f(y)小于记忆库中第h个数值，则将记忆库中第h个数值替换为候选解的最大完工时间，更新记忆库；
21.it＝it 1，it为当前迭代次数。
22.进一步地，所述调度任务参数包括agv的数量、工件各工序对应机器表、各工件机器数量表、工件各工序对应加工时间表、装货/卸货点以及各机器间的运输时间表；
23.采用工序链和机器链双层编码方式对集成多agv的柔性作业车间调度方案进行编码，编码方式包括：
24.工序链的长度等于所有工件的工序之和，为各工件编号，工件号出现的顺序表示该工件工序间的先后加工顺序；
25.机器链的长度等于所有工件的工序之和，机器链中每一位用整数表示，依次按照工件和工件工序的顺序进行排列，每个整数表示当前工序选择的加工机器在可选机器集中的顺序编号。
26.进一步地，所述对当前解进行解码这一步骤中的解码方式为求解最大完工时间，求解过程中包括将编码转换为具体的调度工序、计算各个工序的对应的开始时间和完工时间、计算agv运输任务的具体信息。
27.进一步地，所述计算各个工序的对应的开始时间和完工时间，包括：
28.利用所述机器链求解工件各个工序的加工机器矩阵和各工序加工时间矩阵；
29.结合加工机器矩阵、加工时间矩阵以及预设的agv运输任务分配方法，计算各个工序的对应的开始时间和完工时间；
30.其中，所述预设的agv运输任务分配方法的分配规则为：针对调度过程的每一次运输任务在所有agv中，最先获取当前工序的工件的agv最先被分配。
31.进一步地，所述预设的agv运输任务分配方法，包括：
32.假设agv的数量为n，初始化一个n
×
2的动态的agv调度信息矩阵，矩阵第一列存储当前agv所在机器编号，第二列存储当前agv总运行时间。
33.进一步地，所述计算agv运输任务的具体信息，包括：
34.将所有agv的运输信息存储在多个矩阵中，每一个矩阵对应一个agv；
35.其中，所述运输信息为每一次运输任务的详细信息，详细信息包括：空载行程的起点工位和终点工位、空载行程的开始时间和结束时间、负载行程的起点工位和终点工位、负
载行程的开始时间和结束时间。
36.进一步地，还包括以下步骤：
37.根据最优的调度方案绘制甘特图。
38.进一步地，所述生成当前解的邻域候选解y，包括：
39.随机选择一个工序，为所述工序分配加工机器，修改对应的机器链上的编号；
40.在工序链中随机选择两个位置，交换其编码，即改变对应的工序顺序。
41.本发明所采用的另一技术方案是：
42.一种集成多agv柔性作业车间调度装置，包括：
43.至少一个处理器；
44.至少一个存储器，用于存储至少一个程序；
45.当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现上所述方法。
46.本发明所采用的另一技术方案是：
47.一种存储介质，其中存储有处理器可执行的程序，所述处理器可执行的程序在由处理器执行时用于执行如上所述方法。
48.本发明的有益效果是：本发明可以求解集成多agv的柔性作业车间调度方案，从而实现对机器工件和多agv的同时调度；其中变邻域局部搜索算法包含一个最大完工时间记忆库，直接利用最大完工时间来确定解的邻域变换方向，提高了算法的搜索速度。
附图说明
49.为了更清楚地说明本发明实施例或者现有技术中的技术方案，下面对本发明实施例或者现有技术中的相关技术方案附图作以下介绍，应当理解的是，下面介绍中的附图仅仅为了方便清晰表述本发明的技术方案中的部分实施例，对于本领域的技术人员而言，在无需付出创造性劳动的前提下，还可以根据这些附图获取到其他附图。
50.图1是发明实施例中一种集成多agv柔性作业车间调度方法的流程图；
51.图2是发明实施例中造车间机器布局示意图；
52.图3是发明实施例中调度方案编码方式示意图；
53.图4是发明实施例中运算结果甘特图；
54.图5是发明实施例中算法运算收敛曲线图。
具体实施方式
55.下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。对于以下实施例中的步骤编号，其仅为了便于阐述说明而设置，对步骤之间的顺序不做任何限定，实施例中的各步骤的执行顺序均可根据本领域技术人员的理解来进行适应性调整。
56.在本发明的描述中，需要理解的是，涉及到方位描述，例如上、下、前、后、左、右等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和
操作，因此不能理解为对本发明的限制。
57.在本发明的描述中，若干的含义是一个或者多个，多个的含义是两个以上，大于、小于、超过等理解为不包括本数，以上、以下、以内等理解为包括本数。如果有描述到第一、第二只是用于区分技术特征为目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量或者隐含指明所指示的技术特征的先后关系。
58.本发明的描述中，除非另有明确的限定，设置、安装、连接等词语应做广义理解，所属技术领域技术人员可以结合技术方案的具体内容合理确定上述词语在本发明中的具体含义。
59.如图1所示，本实施例提供一种集成多agv柔性作业车间调度方法，包括以下步骤：
60.s1、载入调度任务参数。
61.调度任务参数包括agv数量、工件各工序对应机器表、机器数量表、工件各工序对应加工时间表、装货/卸货点以及各机器间的运输时间表。
62.在本实施例中，调度任务参数具体包括2台agv小车、8台机器、6个待加工工件总共21个工序，6个工件的加工工序和各个机器对不同工序的加工时间如表1所示，装货/卸货点以及各机器间的运输时间表如表2所示，图2为该实例制造车间机器布局示意图；工件开始加工时，首先由agv从立体仓库中取出毛坯运到相应的机床加工，在该机床的本道工序完成后由agv运送到其他机床加工，等该工件所有的工序加工完成之后，由agv运回立体仓库。
63.表1
[0064][0065][0066]
表2
[0067][0068]
s2、设置算法参数。
[0069]
算法参数包括最大完工时间记忆库的大小h、最大迭代次数max_iteration、当前
解未改善最大次数系数max_no_improve；h的取值要根据问题规模调试得到，本实例中h取100，max_iteration取100000，max_no_improve取0.02，这两个参数一般在可求解问题的前提下取小值。
[0070]
s3、对集成多agv的柔性作业车间调度方案进行编码，初始化当前解x。
[0071]
对调度方案进行编码，初始化当前解x和最好解bestx；并初始化算法运行参数，即迭代次数计数器it初始化为1，候选解未改善次数计数器初始化为0。
[0072]
初始化时需要将一组集成多agv的柔性作业车间调度方案用一串整数编码来表示，每一串编码代表一个解，编码方式采用工序链和机器链双层编码方式，如图3所示，具体描述如下：
[0073]
工序链的长度等于所有工件的工序之和，工序链中为各工件编号，工件编号为整数，工件号出现的顺序表示该工件工序间的先后加工顺序，即被调度的先后顺序；
[0074]
机器链的长度等于所有工件的工序之和，机器链中每一位用整数表示，依次按照工件和工件工序的顺序进行排列，每个整数表示当前工序选择的加工机器在可选机器集中的顺序编号。
[0075]
当前解是随机生成的，即解的机器链部分的每个位置的整数为对应工序的可选加工机器集上随机选择的序号；工序链部分为所有工序加工顺序随机排列。最优解初始时等于当前解。
[0076]
s4、对当前解进行解码，获得最大完工时间f(x)，初始化记忆库中的值为当前解的最大完工时间。
[0077]
步骤s4中解码方式为求解最大完工时间，采用主动解码，包含以下步骤s41
‑
s44：
[0078]
s41、首先对机器链解码，从左到右依次读取编码，转换成对应的加工机器矩阵和加工时间矩阵；
[0079]
s42、再对工序链解码，从左到右依次读取工序链整数编码，计算调度工序；
[0080]
s43、计算各个工序的对应的开始时间和完工时间；
[0081]
s44、计算agv运输任务的具体信息。
[0082]
在步骤s43中对于每一个工序，要先求两个时间：agv配送该工件到达指定工位的时间、该工序所在机器的上一道工序的完工时间，该工序的最早开始时间为这两个时间的较大值，这两个时间都可以通过读取机器链解码出来的加工机器矩阵和加工时间矩阵以及机器间运输时间矩阵得到；遍历所有工序即可获得各个工序的开始时间和完工时间以及对应的加工机器，同时可求得该调度方案的最大完工时间。
[0083]
步骤s44中的计算agv运输任务的具体信息，包括将所有agv的运输信息存储在多个矩阵中，每一个矩阵对应一个agv，其中包括每一次运输任务的具体信息：空载行程的起点和终点、空载行程的开始时间和结束时间、负载行程的起点和终点、负载行程的开始时间和结束时间。
[0084]
基于规则的agv运输任务分配方法，具体规则为最早完成最先被分配，即在当前工序分配agv的时刻，从所有agv中选择到达工件所在机器时间最短的那一台。
[0085]
基于规则的agv运输任务分配方法，包括以下步骤：
[0086]
假设agv的数量为n，首先初始化一个n
×
2的动态的agv调度信息矩阵，矩阵第一列存储当前agv所在机器编号，初始值为装卸货工位0，第二列存储当前agv总运行时间(包含
等待时间)，初始值为0。
[0087]
对于某一道工序，其负载行程可通过加工机器矩阵和机器间运输时间矩阵获得，确定每一道工序运输任务最优的agv的过程中只需要计算每一台agv空载行程获取工件的时间，用到的公式为：deadheadgetjobtime＝max(preoperationcompletiontime,agvavailabletime(j,1) deadheadtime)；式中deadheadgetjobtime为空载行程获取工件的时间，preoperationcompletiontime为该工件前一道工序的完工时间，j为agv编号，agvavailabletime(j,1)为agv完成上一个运输任务的时间，deadtime为空载行程的时长，该时长为agv从上一次停留工位到达当前工序所在工位的时间。
[0088]
s5、判断算法是否终止。只要候选解未改善次数未达到允许最大值并且迭代次数小于最大迭代次数，执行s6。
[0089]
s6、执行带最大完工时间记忆库的变邻域局部搜索算法。
[0090]
参照图5，步骤s6中的带最大完工时间记忆库的变邻域局部搜索算法包含以下步骤：
[0091]
s61、生成当前解的邻域候选解y，并对候选解进行解码得到候选解最大完工时间f(y)。
[0092]
步骤s61中当前解的邻域解生成方法，包括如下步骤：
[0093]
随机选择一个工序，重新为其分配加工机器，修改对应机器链上的编号；
[0094]
在工序链中随机选择两个位置，交换其编码，即改变对应的工序顺序。
[0095]
s62、如果候选解的最大完工时间f(y)大于当前解的最大完工时间f(x)，候选解未改善次数计数器idle_time加1，否则计数器置零。
[0096]
s63、如果候选解的最大完工时间f(y)小于最优解的最大完工时间f(bestx)，最优解bestx替换为候选解y，最优解的最大完工时间替换为候选解的最大完工时间。这里的最优解就是最后要求得到的结果，是算法搜索过程中当前最优调度方案的编码；当前解不一定是目前的最优解，因为可能会被更差的解替换。
[0097]
s64、记忆库参照数h等于it除以h取余数。
[0098]
s65、如果候选解的最大完工时间f(y)小于记忆库中第h个数值，或者候选解的最大完工时间f(y)小于等于当前解的最大完工时间f(x)，则将当前解x替换为候选解y，并替换相应最大完工时间。
[0099]
s66、如果候选解的最大完工时间f(y)小于记忆库中第h个数值，则将记忆库中第h个数值替换为候选解的最大完工时间，更新记忆库。
[0100]
s67、迭代次数计数器加1，it＝it 1。
[0101]
s7、输出最优序列编码并保存。
[0102]
s8、对最优的调度序列解码并绘制甘特图，如图4所示，其中包含各工序的开始时间和完工时间以及对应的加工机器，各个agv运输任务的开始时间和完工时间以及对应的工件，图中白色部分为agv空载行程，灰黑色部分为携带物料的负载行程。
[0103]
表3为本实施例方法与改进遗传算法在本实例上的测试结果，每个方法在该实例上测试15次，本实施例方法相比传统改进遗传算法计算速度提升了67％，并且取得了更高的精度，同时具有良好的稳定性。
[0104]
表3
[0105][0106]
综上所述，本实施例方法相对于现有技术，具有如下有益效果：本实施例方法可以求解集成多agv的柔性作业车间调度方案，从而实现对机器工件和多agv的同时调度。采用工序链和机器链双层编码来表示一种可行的调度方案，该编码方式可以避免非法解的产生和修复；利用一种简单高效的变邻域局部搜索算法与启发式规则结合来进行解的寻优，其中变邻域局部搜索算法包含一个最大完工时间记忆库，直接利用记忆库中不断减少的最大完工时间来确定解的邻域变换方向，邻域生成方式则对当前解数组进行微小变动，避免了传统方法对种群解对应的矩阵进行大量的存取和盲目随机操作，大大提高了算法的搜索速度；基于最早完成最早被分配的启发式规则，不损失求解精度的情况下可以提升算法的运行效率。另外，本算法实现起来较简单，只有一个控制参数h，方便调试应用。本方法克服了传统方法控制参数多、需要存储和操作大量的个体解、设计和实现起来困难的缺点，并且可以达到更高的求解速度和良好的求解精度。
[0107]
本实施例还提供一种集成多agv柔性作业车间调度装置，包括：
[0108]
至少一个处理器；
[0109]
至少一个存储器，用于存储至少一个程序；
[0110]
当所述至少一个程序被所述至少一个处理器执行，使得所述至少一个处理器实现如图1所示的方法。
[0111]
本实施例的一种集成多agv柔性作业车间调度装置，可执行本发明方法实施例所提供的一种集成多agv柔性作业车间调度方法，可执行方法实施例的任意组合实施步骤，具备该方法相应的功能和有益效果。
[0112]
本技术实施例还公开了一种计算机程序产品或计算机程序，该计算机程序产品或计算机程序包括计算机指令，该计算机指令存储在计算机可读存介质中。计算机设备的处理器可以从计算机可读存储介质读取该计算机指令，处理器执行该计算机指令，使得该计算机设备执行图1所示的方法。
[0113]
本实施例还提供了一种存储介质，存储有可执行本发明方法实施例所提供的一种集成多agv柔性作业车间调度方法的指令或程序，当运行该指令或程序时，可执行方法实施例的任意组合实施步骤，具备该方法相应的功能和有益效果。
[0114]
在一些可选择的实施例中，在方框图中提到的功能/操作可以不按照操作示图提到的顺序发生。例如，取决于所涉及的功能/操作，连续示出的两个方框实际上可以被大体上同时地执行或所述方框有时能以相反顺序被执行。此外，在本发明的流程图中所呈现和描述的实施例以示例的方式被提供，目的在于提供对技术更全面的理解。所公开的方法不限于本文所呈现的操作和逻辑流程。可选择的实施例是可预期的，其中各种操作的顺序被改变以及其中被描述为较大操作的一部分的子操作被独立地执行。
[0115]
此外，虽然在功能性模块的背景下描述了本发明，但应当理解的是，除非另有相反说明，所述的功能和/或特征中的一个或多个可以被集成在单个物理装置和/或软件模块中，或者一个或多个功能和/或特征可以在单独的物理装置或软件模块中被实现。还可以理
解的是，有关每个模块的实际实现的详细讨论对于理解本发明是不必要的。更确切地说，考虑到在本文中公开的装置中各种功能模块的属性、功能和内部关系的情况下，在工程师的常规技术内将会了解该模块的实际实现。因此，本领域技术人员运用普通技术就能够在无需过度试验的情况下实现在权利要求书中所阐明的本发明。还可以理解的是，所公开的特定概念仅仅是说明性的，并不意在限制本发明的范围，本发明的范围由所附权利要求书及其等同方案的全部范围来决定。
[0116]
所述功能如果以软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read
‑
only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
[0117]
在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。
[0118]
计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(ram)，只读存储器(rom)，可擦除可编辑只读存储器(eprom或闪速存储器)，光纤装置，以及便携式光盘只读存储器(cdrom)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。
[0119]
应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(pga)，现场可编程门阵列(fpga)等。
[0120]
在本说明书的上述描述中，参考术语“一个实施方式/实施例”、“另一实施方式/实施例”或“某些实施方式/实施例”等的描述意指结合实施方式或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施方式或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施方式或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施方式或示例中以合适的方式结合。
[0121]
尽管已经示出和描述了本发明的实施方式，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施方式进行多种变化、修改、替换和变
型，本发明的范围由权利要求及其等同物限定。
[0122]
以上是对本发明的较佳实施进行了具体说明，但本发明并不限于上述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换，这些等同的变形或替换均包含在本技术权利要求所限定的范围内。