一种基于动态规划和vns的装备供应链调度方法和系统

1.本发明涉及供应链调度技术领域，具体涉及一种基于动态规划和vns的装备供应链调度方法和系统。


背景技术：

2.随着装备制造业的发展，装备的制造过程也变得更加复杂，设备磨损、供应链服务水平等众多因素可能会对装备制造的效率产生重大影响。
3.在装备制造过程中，往往存在着批处理过程。批处理又可以分为平行批处理和连续批处理，在平行批处理中，一个批次的所有工件都可以同时处理，它的加工时间由一个批次处理中加工时间最大的工件决定；连续批处理中，工件须一个接一个加工，它的加工时间是所有工件实际加工时间的总和。
4.在针对连续批处理的最小最大完工时间的求解问题上，可以采取元启发式算法进行求解。其中，vns(variable neighborhood search，变邻域搜索)算法是一种常用的启发式算法，其利用各种动作邻域结构向不同方向进行搜索，使得算法能够在搜索广度和深度上取得一种很好的平衡效果。
5.但是，vns算法的性能取决于邻域结构的设计，当面对情形复杂的问题，现有的变邻域搜索算法存在无法于短时间内得出近似最优解或得出的近似最优解的求解质量较差。
6.因此，亟需一种基于vns的装备供应链调度方法，在保证近似最优解的求解质量的基础上，以缩短求解过程的时间。


技术实现要素：

7.(一)解决的技术问题
8.针对现有技术的不足，本发明提供了一种基于动态规划和vns的装备供应链调度方法和系统，解决了现有技术中无法在短时间内获得质量较优的近似最优解的技术问题。
9.(二)技术方案
10.为实现以上目的，本发明通过以下技术方案予以实现：
11.在本发明的第一方面，提供了一种基于动态规划和vns的装备供应链调度方法，所述方法包括：
12.s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；t
max
表示最大迭代次数，a表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数、it表示迭代次数；
13.s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码；
14.s3、判断it＜t
max
是否成立，若是，则转步骤s4；若否，则转步骤s10；
15.s4、判断it＜ix是否成立，若是，则转步骤s5；若否，则转步骤s6；
16.s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至步骤s7；
17.s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1；
18.s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的最大完工时间；
19.s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量；
20.s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转步骤s3；若否，则直接转步骤s3；times表示每次迭代过程中的最大搜索次数；
21.s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。
22.可选的，所述基于第一启发式算法对调度方案中的v2进行更新的过程包括：
23.s101、基于动态规划算法，获取机器mk中的工件分批方案并令其中，b
[z][k]
表示机器mk上第z个批次，表示机器mk上的批次总数量；nk表示分配至机器m
[k]
的工件数量；
[0024]
s102、判断z＞1是否成立，若是，则转至步骤s103；若否，则转到步骤s107；
[0025]
s103、判断是否成立，若是，则令r0＝1，是否成立，若是，则令r0＝1，转至步骤s104；若否，则令z＝z-1，转至步骤s102；其中，c表示每个批次中工件的最大容量；表示机器mk上第z个批次的工件数量；p0表示第r0个工件开始加工前该机器累计加工时间；表示第l个工件在机器mk上的基础加工时间；
[0026]
s104、判断s104、判断是否成立；若是，则将j
[k][r0]
设置在批次中工件j
[k][r2]
的加工顺序之后，并转至步骤s101；若否，则转到步骤s105；其中，表示第a0个工件在机器mk上第r0个位置进行加工的基础加工时间；b表示工件加工的恶化系数；
[0027]
s105、判断r2＜n
seq
是否成立；若是，则令r2＝r2+1，转至步骤s104；若否，则令并转至步骤s106；
[0028]
s106、判断r0＜r1是否成立；若是，则令r0＝r0+1，转至步骤s104；若否，则令z＝z-1，转至步骤s102；
[0029]
s107：更新机器mk上工件的加工优先级，输出机器mk的分批方案，并向机器mk的下一个机器m
k+1
执行步骤s101-s107，直到全部机器均输出分批方案，作为更新后的v2。
[0030]
可选的，基于第二启发式算法对调度方案中的v2部分进行更新的过程包括：
[0031]
s201、基于动态规划算法，获取机器mk中的工件分批方案并令z＝1，并令z＝1，其中，表示机器mk上第z0个批次的释放时间；
[0032]
s202、判断z≤z0是否成立；若是，则转至步骤s203；若否，则转至步骤s205；
[0033]
s203、判断是否成立；若是，则转至步骤s204；若否，则令z＝z+1，转至步骤s202；其中，表示机器mk上第z个批次的完工时间；
[0034]
s204、将所述机器mk中属于批次的所有工件，基于工件的基础加工时间进行非递减排列，并令z0＝z-1，z＝1，转至步骤s202；
[0035]
s205：将同一批次内的工件根据基础加工时间进行非递减排列，以更新机器mk中工件的加工优先级，并基于运行动态规划算法得到机器mk新的分批方案，并向机器mk的下一个机器m
k+1
执行步骤s201-s205，直到全部机器均输出分批方案，作为更新后的v2。
[0036]
可选的，所述基于动态规划算法，获取机器mk中的工件分批方案，包括：
[0037]
s401、设定当r＝0时，f(r)
[k]
＝0，且max{r-c，0}≤l≤r-1；其中，f(r)
[k]
表示在工件加工顺序确定后，仅考虑机器m
[k]
中前r个工件加工的最短完工时间，0≤r≤nk，nk表示分配至机器m
[k]
的工件数量；其中，r表示工件的顺序；
[0038]
s402、遍历r，并基于预设公式s402、遍历r，并基于预设公式以得到最小的f(r)
[k]
对应的r，l的数值，分别作为r
′
和l
′
；其中，表示机器mk上第l+1个批次的释放时间；θ表示设置时间的恶化系数；
[0039]
s403、判断r
′
＝nk是否成立，若是，则转至步骤s404，若否，则转至步骤s402；
[0040]
s404、若l
′
＜r
′‑
1，则将第l
′
+1个工件至第r
′
个工件设置于的同一个批次，令r
′
＝l
′
，并更新对应l
′
的值，转至步骤s405；若l
′
＝r
′‑
1，则将第r
′
个工件设置于一个新的批次，令r
′
＝l
′
，并更新对应l
′
的值，转至s405；
[0041]
s405、若l
′
＝0，则转至步骤s406；若否，则转至步骤s404；
[0042]
s406：输出机器mk中的工件分批方案和完工时间f(nk)
[k]
；其中，f(nk)
[k]
与的数值相同，表示机器m
[k]
的完工时间。
[0043]
可选的，所述邻域结构包括邻域结构1；其中，所述邻域结构1应用于调度方案的v1部分，用于从完工时间最大的机器中随机挑选一个工件转移到其他机器进行加工；
[0044]
所述邻域结构1的计算过程包括：
[0045]
s501、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；
[0046]
s502、随机生成1个随机整数rand1；其中，1≤rand1≤n；
[0047]
s503、若则随机生成1个随机整数rand2；若否，则转至步骤s502；其中，1≤rand2≤m，表示在v1′
中工件所属机器的序号；
[0048]
s504、判断rand2≠i是否成立；若是，则令以对v1′
进行更新，并结束；若否，则转至s503。
[0049]
可选的，所述邻域结构还包括邻域结构2：其中，所述邻域结构2应用于调度方案的v1部分，用于将完工时间最大的机器中的一个工件与其他机器中的一个基础加工时间更小的工件进行交换；
[0050]
所述邻域结构2的计算过程包括：
[0051]
s601、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；
[0052]
s602、随机生成1个随机整数rand3；其中，1≤rand3≤n；
[0053]
s603、判断是否成立；若是，则随机生成1个随机整数rand4；若否，则转至步骤s602；其中，1≤rand4≤m，表示在v1′
中工件所属机器的序号；
[0054]
s604、判断是否成立；若是，且则以对v1′
进行更新并结束；若否，则转至s603，其中，表示序号为rand4的工件的基础加工时间。
[0055]
可选的，所述邻域结构还包括邻域结构3：其中，所述邻域结构3应用于调度方案的v1部分，用于将随机挑选的一部分编码进行逆转；
[0056]
所述邻域结构3的计算过程包括：
[0057]
s701、令v1′
＝v1；
[0058]
s702、随机生成两个整数rand5和rand6；其中，1≤rand5，rand6≤n；
[0059]
s703、判断rand5＝rand6是否成立，若是，则转至步骤s702；若否，则转至步骤s703；
[0060]
s704、判断rand5＞rand6是否成立，若是，则sw＝rand5，rand5＝rand6，rand6＝sw；若否，则转至步骤s702；
[0061]
s705、令ac＝0；其中，表示对(rand
6-rand5+1)/2进行向下取整后的数值；
[0062]
s706、令s706、令
[0063]
s707、判断ac＜y是否成立，若是，则转至步骤s706；若否，则对v1′
进行更新并结束。
[0064]
可选的，所述邻域结构还包括邻域结构4：其中，所述邻域结构4应用于调度方案的v1部分和v2部分；
[0065]
当所述邻域结构4应用于调度方案的v1部分时，以随机挑选两个工件进行交换，并将任意一个工件分配到随机机器上；该处理过程包括：
[0066]
s801、令v1′
＝v1；
[0067]
s802、随机生成两个整数rand7和rand8；其中，1≤rand7，rand8≤n；
[0068]
s803、令
[0069]
s804、随机生成一个整数rand9和一个整数rand
10
；其中，1≤rand9≤n，1≤rand
10
≤m；
[0070]
s805、令以对v1′
进行更新并结束。
[0071]
当邻域结构4应用于调度方案的v2部分时，随机挑选两个工件，以0.5的概率对加工优先级进行交换；该处理过程包括：
[0072]
s901、令v2′
＝v2；
[0073]
s902、随机生成两个整数rand
11
和rand
12
，并随机生成一个小数rand
13
；其中，1≤rand
11
，rand
12
≤n，0＜rand
13
＜1；
[0074]
s903、判断rand
13
＞0.5是否成立，若是，则若否，则转至步骤s809；其中，表示在编码v2′
中优先级为的工件所对应机器的序号；
[0075]
s904、输出v2′
。
[0076]
可选的，所述v＝{v1，v2}中，
[0077]v1
＝(v1，v2，v3，...，vn)，且v2＝(v
n+1
，v
n+2
，v
n+3
，...，v
2n
)；其中，v1，v2，v3，...，vn表示为1至m中的随机整数；vj的数值表示第j个工件分配至序号为vj的机器；v
n+1
，v
n+2
，v
n+3
，...，v
2n
表示处于1至n的整数，且均不相同，v
n+j
表示第j个工件的加工优先级，所述加工优先级越低则表示对应的工件越先进行加工；1≤j≤n。
[0078]
在本发明的第二方面，提供了一种基于动态规划和vns的装备供应链调度系统，所述系统包括：
[0079]
第一获取模块，用于执行步骤s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；t
max
表示最大迭代次数，aa表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数、it表示迭代次数；
[0080]
第一更新模块，用于执行步骤s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码；
[0081]
第一判断模块，用于执行步骤s3、判断it＜t
max
是否成立，若是，则转第二判断模块执行步骤s4；若否，则转第二获取模块执行步骤s10；
[0082]
第二判断模块，用于执行步骤s4、判断it＜ix是否成立，若是，则转第一搜索模块执行步骤s5；若否，则转第二搜索模块执行步骤s6；
[0083]
第一搜索模块，用于执行步骤s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至第三判断模块执行步骤s7；
[0084]
第二搜索模块，用于执行步骤s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1；
[0085]
第三判断模块，用于执行步骤s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的最大完工时间；
[0086]
第四判断模块，用于执行步骤s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量；
[0087]
第五判断模块，用于执行步骤s9、判断time＞times是否成立；若是，则令it＝it+
1，time＝1，转第一判断模块执行步骤s3；若否，则直接转第一判断模块执行步骤s3；times表示每次迭代过程中的最大搜索次数；
[0088]
第二获取模块，用于执行步骤s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。
[0089]
(三)有益效果
[0090]
本发明提供了一种基于动态规划和vns的装备供应链调度方法和系统。与现有技术相比，具备以下有益效果：
[0091]
本发明提供了一种基于动态规划和vns的装备供应链调度方法和系统，该方法包括：s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；s3、判断it＜t
max
是否成立，若是，则转步骤s4；若否，则转步骤s10；s4、判断it＜ix是否成立，若是，则转步骤s5；若否，则转步骤s6；s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至步骤s7；s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1；s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转步骤s3；若否，则直接转步骤s3；s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。
[0092]
基于上述处理，本发明首先通过编码确定加工工件的分配以及加工顺序，并根据动态规划算法来确定每个机器上工件的组批方式，通过变邻域搜索算法迭代寻找到最优值，其中，当变邻域搜索算法迭代到一定次数后，两种启发式算法与变邻域搜索算法结合运行对当前最优解进行寻优，从而使得在搜索效率和求解质量之间达到很好的平衡，不仅提高了前期求解的收敛速度，也保证了后期迭代过程中能深度寻找最优解，使得在保证近似最优解的求解质量的基础上，进一步缩短了求解过程的时间。
附图说明
[0093]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0094]
图1为本发明提供的一种基于动态规划和vns的装备供应链调度方法的流程示意图；
[0095]
图2为本发明提供的一种编码解码过程的流程示意图；
[0096]
图3为本发明提供的一种基于动态规划和vns的装备供应链调度系统的架构图。
具体实施方式
[0097]
为使本发明实施例的目的、技术方案和优点更加清楚，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的
实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0098]
在传统的调度问题中，为了方便求解，往往会把实际问题进行简化，只考虑了很简单的情形。比如在考虑恶化效应时，往往就考虑简单的恶化，并没有对恶化的原因、恶化的情形进行更深程度的研究。实际生产过程中每个生产环节发生恶化效应的原因并不相同。
[0099]
同时，企业制造生产过程中往往需要考虑到各零部件的仓储水平，工件动态到达的情况，为企业管理者的决策生产计划带来新的困难。在传统的研究中，往往只考虑单一情况，与实际的生产情况存在非常大的出入，导致所得出的求解算法在实际的生产过程中的实际效果较差。由于装备制造的情形多样且动态变化，在同时考虑多种影响生产的因素中，传统的调度算法并不能给出一个良好且稳定的结果。
[0100]
此外，在研究方法上，对于np-hard问题，可以采取元启发式算法进行求解。变邻域搜索算法是一种常用的启发式算法，它可以利用各种动作邻域结构向不同方向进行搜索，使得算法能够在搜索广度和深度取得一种很好的平衡。但是，变邻域算法的性能也取决于邻域结构的设计，当面对情形复杂的问题，变邻域搜索算法可能无法在短时间内得出近似最优解。
[0101]
动态规划算法是一种求最优解的方法，应用动态规划的思想，可以得到的最优解或者局部最优解。但是当问题规模变大时，就会导致求解时间过长无法在规定时间给出最优解。因此在实际生产中，要根据研究问题提出相应的求解思路，有必要去选择一个好的算法，或者结合不同方法，以求在搜索效率和所得解的质量之间达到一个很好的平衡。
[0102]
本技术实施例中的技术方案为解决上述技术问题，总体思路如下：
[0103]
为了解决上述问题，本技术实施例通过提供一种基于动态规划和vns的装备供应链调度方法和系统，通过编码确定工件的分配以及加工顺序，再根据动态规划算法来确定每个机器上工件的组批方式，然后通过变邻域搜索算法迭代来寻找到最优值，其中当变邻域搜索算法迭代到一定次数后，两种启发式算法与变邻域搜索算法结合运行对当前最优解进行寻优，从而使得在搜索效率和求解质量之间达到很好的平衡，既提高了前期算法的收敛速度，也保证了后期迭代过程中能深度寻找最优解，使得在保证近似最优解的求解质量的基础上，缩短了求解过程的时间。
[0104]
为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。
[0105]
参见图1，图1为本发明提供的一种基于动态规划和vns的装备供应链调度方法的流程图。如图1所示，该方法包括：
[0106]
s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；t
max
表示最大迭代次数，a表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数、it表示迭代次数。
[0107]
s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码。
[0108]
s3、判断it＜t
max
是否成立，若是，则转步骤s4；若否，则转步骤s10。
[0109]
s4、判断it＜ix是否成立，若是，则转步骤s5；若否，则转步骤s6。
[0110]
s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至步骤s7。
[0111]
s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1。
[0112]
s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的最大完工时间。
[0113]
s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量。
[0114]
s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转步骤s3；若否，则直接转步骤s3；times表示每次迭代过程中的最大搜索次数。
[0115]
s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。
[0116]
基于上述处理，本发明通过编码确定加工工件的分配以及加工顺序，再根据动态规划算法来确定每个机器上工件的组批方式，然后通过变邻域搜索算法迭代来寻找到最优值，其中当变邻域搜索算法迭代到一定次数后，两种启发式算法与变邻域搜索算法结合运行对当前最优解进行寻优，从而使得在搜索效率和求解质量之间达到很好的平衡，前期提高了算法的收敛速度，后期也保证迭代过程中能深度寻找最优解，使得在保证近似最优解的求解质量的基础上，缩短了求解过程所需时间。
[0117]
本发明通过设计一种结合了动态规划思想和启发式算法的变邻域搜索算法，来解决存在恶化效应、加工工件动态到达、多平行机器生产的供应链调度问题，目标是最小化最大完工时间。
[0118]
针对步骤s1，工件信息和机器信息包括：在一个装备制造过程中，有n个工件需要加工，有m个平行机器，每个工件在一个机器上就可以完成生产，机器的加工方式是连续批生产。每个批次开始加工之前需要一个设置时间，每个批次的最大容量是c，仓库的工件数量是n0(小于n)，需要从第三方供应商采购零部件(即，本发明中的工件)，工件是动态到达的，加工过程中存在恶化效应，目标是最小化加工时间。
[0119]
所加工的工件集j＝{j
[1]
，j
[2]
，...，j
[n]
}，工件的到达时间集为(其中，有n0个工件的到达时间为0)，工件的基础加工时间的集合为加工机器集为m＝{m1，m2，...，mm}。j
[i][k][r]
表示第i个工件在机器mk上第r个位置进行加工，b
[z][k]
表示机器mk上第z个批次，且该批次的释放时间为上第z个批次，且该批次的释放时间为表示批次b
[z][k]
上加工工件的数量，表示批次b
[z][k]
的完工时间。由于批次开始时间必须不小于上一个批次结束时间以及这个批次的释放时间，则批次b
[z][k]
的开始时间为
[0120]
由于制造过程中存在恶化效应，批次b
[z][k]
的实际设置时间为
θ是设置时间的恶化系数。由于机器加工过程中刀具会磨损，设工件j
[i]
的实际加工时间为为机器mk上加工l个工件到第r个工件累计的实际加工时间，b为加工的恶化系数，则工件机器处理工件j
[i][k][r]
的实际加工时间为(其中，
[0121]
在发明提供的技术方案中，假设机器mk的完工时间为ck，目标函数是最小化最大完工时间c
max
＝max{c1，c2，...，cm}。
[0122]
针对步骤s1，编码v＝{v1，v2}中，v1＝(v1，v2，v3，...，vn)，且v2＝(v
n+1
，v
n+2
，v
n+3
，...，v
2n
)；其中，v1，v2，v3，...，vn表示为1至m中的随机整数；vj的数值表示第j个工件分配至序号为vj的机器；v
n+1
，v
n+2
，v
n+3
，...，v
2n
表示处于1至n的整数，且均不相同，v
n+j
表示第j个工件的加工优先级，所述加工优先级越低则表示对应的工件越先进行加工；1≤j≤n。
[0123]
参见图2，图2为本发明中的编码解码过程的流程示意图。如图2所示，左边编码为v1，其编码为机器的序号1、2、3；右边编码为v2，其编码为每一工件对应的加工顺序。其中，解码编码过程包括：步骤1、工件分配，表示根据编码v1将不同的工件分配至相应的机器；步骤2、调整工件顺序表示根据编码v2对应的加工顺序将每一机器中的多个工件进行顺序调整。
[0124]
在一些实施例中，基于动态规划算法，获取机器mk中的工件分批方案，包括：
[0125]
s401、设定当r＝0时，f(r)
[k]
＝0，且max{r-c，0}≤l≤r-1；其中，f(r)
[k]
表示在工件加工顺序确定后，仅考虑机器m
[k]
中前r个工件加工的最短完工时间，0≤r≤nk，nk表示分配至机器m
[k]
的工件数量；其中，r表示工件的顺序。
[0126]
s402、遍历r，并基于预设公式s402、遍历r，并基于预设公式以得到最小的f(r)
[k]
对应的r，l的数值，分别作为r
′
和l
′
；其中，表示机器mk上第l+1个批次的释放时间；θ表示设置时间的恶化系数。
[0127]
s403、判断r
′
＝nk是否成立，若是，则转至步骤s404，若否，则转至步骤s402。
[0128]
s404、若l
′
＜r
′‑
1，则将第l
′
+1个工件至第r
′
个工件设置于的同一个批次，令r
′
＝l
′
，并更新对应l
′
的值，转至步骤s405；若l
′
＝r
′‑
1，则将第r
′
个工件设置于一个新的批次，令r
′
＝l
′
，并更新对应l
′
的值，转至s405。
[0129]
s405、若l
′
＝0，则转至步骤s406；若否，则转至步骤s404。
[0130]
s406：输出机器mk中的工件分批方案和完工时间f(nk)
[k]
；其中，f(nk)
[k]
与的数值相同，表示机器m
[k]
的完工时间。
[0131]
在一些实施例中，基于第一启发式算法对调度方案中的v2进行更新的过程包括：
[0132]
s101、基于动态规划算法，获取机器mk中的工件分批方案并令n
seq
＝nk；其中，b
[z][k]
表示机器mk上第z个批次，表示机器mk上的批次总数量；nk表示分配至机器m
[k]
的工件数量。
[0133]
s102、判断z＞1是否成立，若是，则转至步骤s103；若否，则转到步骤s107。
[0134]
s103、判断是否成立，若是，则令r0＝1，是否成立，若是，则令r0＝1，转至步骤s104；若否，则令z＝z-1，转至步骤s102；其中，c表示每个批次中工件的最大容量；表示机器mk上第z个批次的工件数量；p0表示第r0个工件开始加工前该机器累计加工时间；表示第l个工件在机器mk上的基础加工时间。
[0135]
s104、判断s104、判断是否成立；若是，则将j
[k][r0]
设置在批次中工件j
[k][r2]
的加工顺序之后，并转至步骤s101；若否，则转到步骤s105；其中，表示第a0个工件在机器mk上第r0个位置进行加工的基础加工时间；b表示工件加工的恶化系数。
[0136]
s105、判断r2＜n
seq
是否成立；若是，则令r2＝r2+1，转至步骤s104；若否，则令并转至步骤s106；其中，表示批次b
[z][k]
上加工工件的数量。
[0137]
s106、判断r0＜r1是否成立；若是，则令r0＝r0+1，转至步骤s104；若否，则令z＝z-1，转至步骤s102。
[0138]
s107：更新机器mk上工件的加工优先级，输出机器mk的分批方案，并向机器mk的下一个机器m
k+1
执行步骤s101-s107，直到全部机器均输出分批方案，作为更新后的v2。
[0139]
在一些实施例中，基于第二启发式算法对调度方案中的v2部分进行更新的过程包括：
[0140]
s201、基于动态规划算法，获取机器mk中的工件分批方案并令z＝1，并令z＝1，其中，表示机器mk上第z0个批次的释放时间。
[0141]
s202、判断z≤z0是否成立；若是，则转至步骤s203；若否，则转至步骤s205。
[0142]
s203、判断是否成立；若是，则转至步骤s204；若否，则令z＝z+1，转至步骤s202；其中，表示机器mk上第z个批次的完工时间。
[0143]
s204、将所述机器mk中属于批次的所有工件，基于工件的基础加工时间进行非递减排列，并令z0＝z-1，z＝1，转至步骤s202。
[0144]
s205：将同一批次内的工件根据基础加工时间进行非递减排列，以更新机器mk中工件的加工优先级，并基于运行动态规划算法得到机器mk新的分批方案，并向机器mk的下一个机器m
k+1
执行步骤s201-s205，直到全部机器均输出分批方案，作为更新后的v2。
[0145]
在一些实施例中，本发明包含4个邻域结构，分别为：
[0146]
邻域结构1；其中，所述邻域结构1应用于调度方案的v1部分，用于从完工时间最大的机器中随机挑选一个工件转移到其他机器进行加工，
[0147]
所述邻域结构1的计算过程包括：
[0148]
s501、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；
[0149]
s502、随机生成1个随机整数rand1；其中，1≤rand1≤n。
[0150]
s503、若则随机生成1个随机整数rand2；若否，则转至步骤s502；其中，1≤rand2≤m，表示在v1′
中工件所属机器的序号。
[0151]
s504、判断rand2≠i是否成立；若是，则令以对v1′
进行更新，并结束；若否，则转至s503。
[0152]
邻域结构2：其中，所述邻域结构2应用于调度方案的v1部分，用于将完工时间最大的机器的一个工件与其他机器的一个基础加工时间更小的工件交换；
[0153]
所述邻域结构2的计算过程包括：
[0154]
s601、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；
[0155]
s602、随机生成1个随机整数rand3；其中，1≤rand3≤n。
[0156]
s603、判断是否成立；若是，则随机生成1个随机整数rand4；若否，则转至步骤s602；其中，1≤rand4≤m，表示在v1′
中工件所属机器的序号。
[0157]
s604、判断是否成立；若是，且则以对v1′
进行更新并结束；若否，则转至s603，其中，表示序号为rand4的工件的基础加工时间。
[0158]
邻域结构3：其中，所述邻域结构3应用于调度方案的v1部分，用于将随机挑选的一部分编码进行逆转；
[0159]
所述邻域结构3的计算过程包括：
[0160]
s701、令v1′
＝v1。
[0161]
s702、随机生成两个整数rand5和rand6；其中，1≤rand5，rand6≤n。
[0162]
s703、判断rand5＝rand6是否成立，若是，则转至步骤s702；若否，则转至步骤s703。
[0163]
s704、判断rand5＞rand6是否成立，若是，则sw＝rand5，rand5＝rand6，rand6＝sw；若否，则转至步骤s702。
[0164]
s705、令ac＝0；其中，表示对(rand
6-rand5+1)/2进行向下取整后的数值。
[0165]
s706、：令s706、：令
[0166]
s707、判断ac＜y是否成立，若是，则转至步骤s706；若否，则对v1′
进行更新并结束。
[0167]
邻域结构4：其中，所述邻域结构4应用于调度方案的v1部分和v2部分；
[0168]
当所述邻域结构4应用于调度方案的v1部分时，以随机挑选两个工件进行交换，并将任意一个工件分配到随机机器上；该处理过程包括：
[0169]
s801、令v1′
＝v1。
[0170]
s802、随机生成两个整数rand7和rand8；其中，1≤rand7，rand8≤n。
[0171]
s803、令
[0172]
s804、随机生成一个整数rand9和一个整数rand
10
；其中，1≤rand9≤n，1≤rand
10
≤m。
[0173]
s805、令以对v1′
进行更新并结束。
[0174]
当邻域结构4应用于调度方案的v2部分时，随机挑选两个工件，以0.5的概率对加工优先级进行交换；该处理过程包括：
[0175]
s901、令v2′
＝v2。
[0176]
s902、随机生成两个整数rand
11
和rand
12
，并随机生成一个小数rand
13
；其中，1≤rand
11
，rand
12
≤n，0＜rand
13
＜1。
[0177]
s903、判断rand
13
＞0.5是否成立，若是，则若否，则转至步骤s809；其中，表示在编码v2′
中优先级为的工件所对应机器的序号。
[0178]
s904、输出v2′
。
[0179]
值得注意的是，其余的邻域结构1、2、3中任一领域结构也可以应用于调度方案的v2部分，且过程也为随机挑选两个工件，以0.5的概率对加工优先级进行交换，具体处理过程与上述内容相同。
[0180]
本发明还提供了一种基于动态规划和vns的装备供应链调度系统，参见图3，图3为本发明提供的一种基于动态规划和vns的装备供应链调度系统的架构图。如图3所示，该系统包括：
[0181]
第一获取模块301，用于执行步骤s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；t
max
表示最大迭代次数，a表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数、it表示迭代次数。
[0182]
第一更新模块302用于执行步骤s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码。
[0183]
第一判断模块303，用于执行步骤s3、判断it＜t
max
是否成立，若是，则转第二判断模304块执行步骤s4；若否，则转第二获取模块执行步骤s10。
[0184]
第二判断模块304，用于执行步骤s4、判断it＜ix是否成立，若是，则转第一搜索模块305执行步骤s5；若否，则转第二搜索模块306执行步骤s6。
[0185]
第一搜索模块305，用于执行步骤s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至第三判断模块执行步骤s7。
[0186]
第二搜索模块306，用于执行步骤s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1。
[0187]
第三判断模块307，用于执行步骤s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的
最大完工时间。
[0188]
第四判断模块308，用于执行步骤s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量。
[0189]
第五判断模块309，用于执行步骤s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转第一判断模块303执行步骤s3；若否，则直接转第一判断模块303执行步骤s3；times表示每次迭代过程中的最大搜索次数。
[0190]
第二获取模块310，用于执行步骤s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。
[0191]
可理解的是，本发明实施例提供的基于动态规划和vns的装备供应链调度系统与上述基于动态规划和vns的装备供应链调度方法相对应，其有关内容的解释、举例、有益效果等部分可以参照基于动态规划和vns的装备供应链调度方法中的相应内容，此处不再赘述。
[0192]
在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现上述任一基于动态规划和vns的装备供应链调度方法的步骤。
[0193]
在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一基于动态规划和vns的装备供应链调度方法。
[0194]
在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。
[0195]
所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(dsl))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，dvd)、或者半导体介质(例如固态硬盘solid state disk(ssd))等。
[0196]
综上所述，与现有技术相比，本发明提供的技术方案具备以下有益效果：
[0197]
1、本发明针对高端设备制造中考虑到设置时间中基于时间的恶化效应，实际加工时间基于累计加工时间的恶化效应，零部件动态到达的调度问题，设计了一种结合了变邻域搜索，动态规划算法，启发式算法的智能优化算法，首先通过编码确定加工工件的分配以及加工顺序，再根据动态规划算法来确定每个机器上工件的组批方式，然后通过变邻域搜索算法迭代来寻找到最优值，其中当变邻域搜索算法迭代到一定次数后，两种启发式算法与变邻域搜索算法结合运行对当前最优解进行寻优。在变邻域算法中，本发明设计4种简单易行的邻域结构以及启发式算法执行的迭代条件，从而使得算法在运行时于搜索效率和解质量之间达到很好的平衡，既提高了前期算法的收敛速度，也保证了后期迭代过程中能深
度寻找最优解。
[0198]
2、本发明基于装备实际供应链制造情况考虑了工件生产加工的恶化效应，零部件动态到达等因素，本发明设计了一个简单且通用的编码，不仅可以用来解决当前问题，也可以适用于其他传统生产调度。
[0199]
3、本发明适用于所提出的复杂调度问题，面对不同水平的库存数量，恶化率，都能够快速有效的求解，可以应对许多复杂情况，相比于其他传统调度算法更加具有现实意义，应用范围更广泛。尤其是在大批量工件的制造场景中，本发明提供的技术方案也可以得出最优解，能够在短时间内为用户提供一个可靠的生产方案。
[0200]
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。
[0201]
以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.一种基于动态规划和vns的装备供应链调度方法，其特征在于，所述方法包括：s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；其中，t
max
表示最大迭代次数，a表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数；it表示迭代次数；s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案v，并基于第一启发式算法和第二启发式算法对所述调度方案v中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码；s3、判断it＜t
max
是否成立，若是，则转步骤s4；若否，则转步骤s10；s4、判断it＜ix是否成立，若是，则转步骤s5；若否，则转步骤s6；s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算v和v
′
的最大完工时间c
max
，time＝time+1，转至步骤s7；s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1；s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的最大完工时间；s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量；s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转步骤s3；若否，则直接转步骤s3；其中，times表示每次迭代过程中的最大搜索次数；s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。2.根据权利要求1所述的方法，其特征在于，所述基于第一启发式算法对调度方案中的vt进行更新的过程，包括：s101、基于动态规划算法，获取机器m
k
中的工件分批方案并令n
seq
＝n
k
；其中，b
[z][k]
表示机器m
k
上第z个批次，表示机器m
k
上的批次总数量；n
k
表示分配至机器m
[k]
的工件数量；s102、判断z＞1是否成立，若是，则转至步骤s103；若否，则转到步骤s107；s103、判断是否成立，若是，则令r0＝1，是否成立，若是，则令r0＝1，转至步骤s104；若否，则令z＝z-1，转至步骤s102；其中，c表示每个批次中工件的最大容量；表示机器m
k
上第z个批次的工件数量；p0表示第r0个工件开始加工前该机器累计加工时间；表示第l个工件在机器m
k
上的基础加工时间；s104、判断s104、判断是否成立；若是，则将j
[k][r0]
设置在批次
中工件j
[k][r2]
的加工顺序之后，并转至步骤s101；若否，则转到步骤s105；其中，表示第a0个工件在机器m
k
上第r0个位置进行加工的基础加工时间；b表示工件加工的恶化系数；s105、判断r2＜n
seq
是否成立；若是，则令r2＝r2+1，转至步骤s104；若否，则令并转至步骤s106；s106、判断r0＜r1是否成立；若是，则令r0＝r0+1，转至步骤s104；若否，则令z＝z-1，转至步骤s102；s107：更新机器m
k
上工件的加工优先级，输出机器m
k
的分批方案，并向机器m
k
的下一个机器m
k+1
执行步骤s101-s107，直到全部机器均输出分批方案，作为更新后的v2。3.根据权利要求1所述的方法，其特征在于，基于第二启发式算法对调度方案v中的v2部分进行更新的过程包括：s201、基于动态规划算法，获取机器m
k
中的工件分批方案并令z＝1，并令z＝1，其中，表示机器m
k
上第z0个批次的释放时间；s202、判断z≤z0是否成立；若是，则转至步骤s203；若否，则转至步骤s205；s203、判断是否成立；若是，则转至步骤s204；若否，则令z＝z+1，转至步骤s202；其中，表示机器m
k
上第z个批次的完工时间；s204、将所述机器m
k
中属于批次的所有工件，基于工件的基础加工时间进行非递减排列，并令z0＝z-1，z＝1，转至步骤s202；s205：将同一批次内的工件根据基础加工时间进行非递减排列，以更新机器m
k
中工件的加工优先级，并基于运行动态规划算法得到机器m
k
新的分批方案，并向机器m
k
的下一个机器m
k+1
执行步骤s201-s205，直到全部机器均输出分批方案，作为更新后的v2。4.根据权利要求2或3任一所述的方法，其特征在于，所述基于动态规划算法，获取机器m
k
中的工件分批方案，包括：s401、设定当r＝0时，f(r)[
k
]＝0，且max{r-c，0}≤l≤r-1；其中，f(r)
[k]
表示在工件加工顺序确定后，仅考虑机器m
[k]
中前r个工件加工的最短完工时间，0≤r≤n
k
，n
k
表示分配至机器m
[k]
的工件数量；其中，r表示工件的顺序；s402、遍历r，并基于预设公式s402、遍历r，并基于预设公式以得到最小的f(r)
[k]
对应的r，l的数值，分别作为r
′
和l
′
；其中，表示机器m
k
上第l+1个批次的释放时间；θ表示设置时间的恶化系数；s403、判断r
′
＝n
k
是否成立，若是，则转至步骤s404，若否，则转至步骤s402；s404、若l
′
＜r
′‑
1，则将第l
′
+1个工件至第r
′
个工件设置于的同一个批次，令r
′
＝l
′
，并更新对应l
′
的值，转至步骤s405；若l
′
＝r
′‑
1，则将第r
′
个工件设置于一个新的批次，令r
′
＝l
′
，并更新对应l
′
的值，转至s405；
s405、若l
′
＝0，则转至步骤s406；若否，则转至步骤s404；s406：输出机器m
k
中的工件分批方案和完工时间其中，与的数值相同，表示机器m
[k]
的完工时间。5.根据权利要求1所述的方法，其特征在于，所述邻域结构包括邻域结构1；其中，所述邻域结构1应用于调度方案的v1部分，用于从完工时间最大的机器中随机挑选一个工件转移到其他机器进行加工，所述邻域结构1的计算过程包括：s501、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；s502、随机生成1个随机整数rand1；其中，1≤rand1≤n；s503、若则随机生成1个随机整数rand2；若否，则转至步骤s502；其中，表示在v1′
中工件所属机器的序号；s504、判断rand2≠i是否成立；若是，则令以对v1′
进行更新，并结束；若否，则转至s503。6.根据权利要求5所述的方法，其特征在于，所述邻域结构还包括邻域结构2：其中，所述邻域结构2应用于调度方案的v1部分，用于将完工时间最大的机器中的一个工件与其他机器中的一个基础加工时间更小的工件进行交换；所述邻域结构2的计算过程包括：s601、计算出所有机器的完工时间，得出最大加工时间机器的序号i，令v1′
＝v1；s602、随机生成1个随机整数rand3；其中，1≤rand3≤n；s603、判断是否成立；若是，则随机生成1个随机整数rand4；若否，则转至步骤s602；其中，表示在v1′
中工件所属机器的序号；s604、判断是否成立；若是，且则以对v1′
进行更新并结束；若否，则转至s603，其中，表示序号为rand4的工件的基础加工时间。7.根据权利要求5所述的方法，其特征在于，所述邻域结构还包括邻域结构3：其中，所述邻域结构3应用于调度方案的v1部分，用于将随机挑选的一部分编码进行逆转；所述邻域结构3的计算过程包括：s701、令v1′
＝v1；s702、随机生成两个整数rand5和rand6；其中，1≤rand5，rand6≤n；s703、判断rand5＝rand6是否成立，若是，则转至步骤s702；若否，则转至步骤s703；s704、判断rand5＞rand6是否成立，若是，则sw＝rand5，rand5＝rand6，rand6＝sw；若否，则转至步骤s702；s705、令ac＝0；其中，表示对(rand
6-rand5+1)/2进行向下取整后的数值；s706、令s706、令ac＝ac+1；
s707、判断ac＜y是否成立，若是，则转至步骤s706；若否，则对v1′
进行更新并结束。8.根据权利要求5所述的方法，其特征在于，所述邻域结构还包括邻域结构4：其中，所述邻域结构4应用于调度方案的v1部分和v2部分；当所述邻域结构4应用于调度方案的v1部分时，以随机挑选两个工件进行交换，并将任意一个工件分配到随机机器上；该处理过程包括：s801、令v1′
＝v1；s802、随机生成两个整数rand7和rand8；其中，1≤rand7，rand8≤n；s803、令s804、随机生成一个整数rand9和一个整数rand
10
；其中，1≤rand9≤n，1≤rand
10
≤m；s805、令以对v1′
进行更新并结束；当邻域结构4应用于调度方案的v2部分时，随机挑选两个工件，以0.5的概率对加工优先级进行交换；该处理过程包括：s901、令v2′
＝v2；s902、随机生成两个整数rand
11
和rand
12
，并随机生成一个小数rand
13
；其中，1≤rand
11
，rand
12
≤n，0＜rand
13
＜1；s903、判断rand
13
＞0.5是否成立，若是，则若否，则转至步骤s809；其中，表示在编码v2′
中优先级为的工件所对应机器的序号；s904、输出v2′
。9.根据权利要求1-8任一所述的方法，其特征在于，所述v＝{v1，v2}中，v1＝(v1，v2，v3，...，v
n
)，且v2＝(v
n+1
，v
n+2
，v
n+3
，...，v
2n
)；其中，v1，v2，v3，...，v
n
表示为1至m中的随机整数；v
j
的数值表示第j个工件分配至序号为v
j
的机器；v
n+1
，v
n+2
，v
n+3
，...，v
2n
表示处于1至n的整数，且均不相同，v
n+j
表示第j个工件的加工优先级，所述加工优先级越低则表示对应的工件越先进行加工；1≤j≤n。10.一种基于动态规划和vns的装备供应链调度系统，其特征在于，所述系统包括：第一获取模块，用于执行步骤s1、获取工件信息、机器信息、算法参数以及邻域结构，并对所述算法参数进行初始化处理；其中，所述初始化处理包括：st＝1，time＝1，it＝1，ix＝a*t
max
；t
max
表示最大迭代次数，a表示第一预设数值，且0＜a＜1；ix表示第二最大迭代次数；st表示邻域结构的顺序；time表示每次迭代过程中的搜索次数、it表示迭代次数；第一更新模块，用于执行步骤s2、随机生成包含各个工件与机器的分配关系、各个工件的加工顺序的调度方案，并基于第一启发式算法和第二启发式算法对所述调度方案中的v2部分进行更新；其中，调度方案v由v1和v2组成，v＝{v1，v2}；v1表示将工件分配至不同机器的编码、v2表示确定工件的加工优先级的编码；第一判断模块，用于执行步骤s3、判断it＜t
max
是否成立，若是，则转第二判断模块执行步骤s4；若否，则转第二获取模块执行步骤s10；第二判断模块，用于执行步骤s4、判断it＜ix是否成立，若是，则转第一搜索模块执行步骤s5；若否，则转第二搜索模块执行步骤s6；第一搜索模块，用于执行步骤s5、在第st个邻域结构内搜索新的调度方案v
′
，分别计算
v和v
′
的最大完工时间c
max
，time＝time+1，转至第三判断模块执行步骤s7；第二搜索模块，用于执行步骤s6、在第st个邻域结构内搜索新的调度方案v
′
，并运行第一启发式算法和第二启发式算法分别对v和v
′
的编码v2进行更新，并计算更新后的v和v
′
的最大完工时间c
max
，time＝time+1；第三判断模块，用于执行步骤s7、判断c
max
(v
′
)＜c
max
(v)是否成立；若是，则更新v为v
′
，st＝0；其中，c
max
(v
′
)表示调度方案v
′
的最大完工时间，c
max
(v)表示调度方案v的最大完工时间；第四判断模块，用于执行步骤s8、判断st＜lst是否成立；若是，则令st＝st+1；若否，则令st＝1；其中，lst表示邻域结构的数量；第五判断模块，用于执行步骤s9、判断time＞times是否成立；若是，则令it＝it+1，time＝1，转第一判断模块执行步骤s3；若否，则直接转第一判断模块执行步骤s3；times表示每次迭代过程中的最大搜索次数；第二获取模块，用于执行步骤s10、获取调度方案v，作为最小最大完工时间的最终调度方案并输出。

技术总结
本发明提供了一种基于动态规划和vns的装备供应链调度方法和系统，涉及供应链调度领域。本发明首先通过编码确定工件的分配以及加工顺序，再根据动态规划算法来确定每个机器上工件的组批方式，然后通过变邻域搜索算法迭代来寻找到最优值，其中当变邻域搜索算法迭代到一定次数后，两种启发式算法与变邻域搜索算法结合运行对当前最优解进行寻优，从而使得在搜索效率和求解质量之间达到很好的平衡，前期提高了算法的收敛速度，后期也保证迭代过程中能深度寻找最优解，在保证近似最优解的求解质量的基础上，缩短了求解过程的时间。缩短了求解过程的时间。缩短了求解过程的时间。


技术研发人员：陆少军 马崇轺 郑锐 崔龙庆 胡朝明 江涛 赵婷
受保护的技术使用者：合肥工业大学
技术研发日：2023.06.19
技术公布日：2023/8/24