1.本发明涉及一种多品种小批量车间优化调度方法，具体涉及一种基于改进差分进化算法的调度优化求解方法，属于制造生产车间的调度排产技术领域。
背景技术：2.车间调度(job-shop scheduling problem,jsp)是生产制造业规划和管理层面的一个重要领域，其调度方案数量庞大、求解复杂，属于np-hard优化问题。多品种、小批量的生产模式依照客户订单安排生产流程，能够满足客户的定制化需求、提供快速服务，有广阔的销售市场。然而，多品种小批量生产方式在规定的生产期限内需加工的产品种类较多，且每种产品的生产数量较少，具有更高的计算复杂度。因此，考虑如何制定排产方案，使最大完工时间更短、抗干扰性更强，从而在多品种小批量的生产模式下实现高效率、高质量、低成本的车间作业，成为制造类企业一个非常现实和亟需解决的问题，同时也是多年来学术研究的热点。
3.目前，常用于解决多品种小批量生产调度的方法有遗传算法、粒子群优化技术、帝国竞争算法、布谷鸟算法和迁徙鸟群优化等。作为演化算法的一种，差分进化算法(differential evolution,de)根据不同个体间的差异进行变异，实现种群的高效并行进化，具有结构简单、容易实现、收敛快速、鲁棒性强等特点，迄今为止已被应用于大数据处理、人工智能等领域。然而，在解决车间调度等具有离散特性的问题方面，差分进化算法由于其连续特性而应用较少，即现有的解决多品种小批量车间调度的技术普遍存在适用度低、性能较差的问题。
技术实现要素：4.针对现有的解决多品种小批量车间调度的技术普遍存在适用度低、性能较差的问题，本发明提供了一种基于差分进化算法的多品种小批量车间调度方法。
5.本发明所述基于差分进化算法的多品种小批量车间调度方法，该方法包括以下步骤：
6.步骤s1：对生产订单进行加工批次划分操作，并初始化参数；
7.步骤s2：建立以最大完工时间最短为目标的数学模型，并使用元启发式算法生成初始种群；
8.步骤s3：对参与进化的个体的染色体模型进行连续化转换，模型转换的步骤依次为：
9.染色体模型中工序编码部分连续化转换的步骤；
10.染色体模型中基因按照自然工序排序的步骤；
11.染色体模型中机器编码部分连续化转换的步骤；
12.步骤s4：使用基于多种进化策略和参数自适应更新策略的差分进化算法对步骤s3转换后的模型进行求解，使用该算法求解模型的步骤依次为：
13.差分变异、交叉、选择的步骤；
14.外部存档更新的步骤；
15.参数自适应更新的步骤；
16.部分个体进行邻域搜索的步骤；
17.种群更新的步骤；
18.步骤s5：判断算法的运行时间是否满足步骤s1中初始化参数给出的终止条件，是，则执行步骤s6；否，则返回执行步骤s4；
19.步骤s6：对算法求得的最优调度方案进行解码，转换为直观的甘特图。
20.优选地，步骤s1中所述的加工批次划分的过程为：
21.步骤s1-1、计算全部工件的需求量的平均值；
22.步骤s1-2、根据平均值将生产订单划分为两组，其中工件需求量小于或等于平均值的生产订单划分为第一组，工件需求量大于平均值的生产订单划分为第二组；
23.步骤s1-3、第一组中每个生产订单作为一个加工批次；
24.对第二组中每个生产订单进行加工批次的重新拆分，以第一组生产订单中全部工件需求量的平均值为拆分标准，第二组中的每个生产订单被拆分为两个批次，其中一个加工批次的工件需求量大于拆分标准，另一个加工批次的工件需求量小于或等于拆分标准。
25.优选地，步骤s1中初始化参数包括：种群规模pop_size、外部存档规模arc_size、最大运行时间max_time、邻域搜索个体在种群中的占比p_select、精英个体在种群中的占比p_best、变异因子的数学期望mu_f和交叉因子的数学期望mu_cr。
26.优选地，步骤s2中建立以最大完工时间最短为目标的数学模型，计算公式：
27.c＝min{max(endi)},1≤i≤total_op_num，其中endi表示第i个工序的完工时间，total_op_num为全部加工批次所包含工序数量的总和；
28.使用元启发式算法生成初始种群的过程为：
29.步骤s2-1、对于染色体中工序编码部分的每一个基因，从当前剩余工序数目最多的工件中随机选择一个；
30.步骤s2-2、对于染色体中的机器编码部分，按照工序编码中的工序顺序，依次为每道工序选择加工用时最短的机器；
31.步骤s2-3、根据染色体中的工序编码部分和机器编码部分，确定每道工序的实际加工时间，并写入时间编码部分。
32.优选地，步骤s3中所述染色体模型连续化转换的过程为：
33.步骤s3-1、对于染色体中的工序编码部分，记每一道工序在该段染色体中的次序为indexi；
34.步骤s3-2、对工序编码中的每个基因计算total_op_num-indexi+1，并用该值代替原基因中的内容；
35.步骤s3-3、将染色体中的工序编码、机器编码和时间编码均按照自然工序顺序进行排列；
36.步骤s3-4、对于每一道工序，建立机器选择概率矩阵，并将各机器的选择概率初始化为1。
37.优选地，步骤s4中所述使用优化算法求解模型的步骤：从精英群体、当前种群、外
部存档与当前种群的并集中分别随机选择一个个体，对于当前种群中的每一个个体，依次进行差分变异、交叉和选择等步骤，随后更新外部存档和优化算法中的参数，并选择部分个体进行邻域搜索，最后更新当前种群，其中选择个体进行差分变异、交叉、选择的具体实现过程为：
38.步骤s4a-1、从精英群体中随机选择一个个体记作pbest，从当前种群中随机选择一个个体记作r1，从当前种群与外部存档的并集中随机选择一个个体记作r2；
39.步骤s4a-2、分别以mu_f和0.1为正态分布的数学期望和标准差，生成变异因子f，分别以mu_cr和0.1为柯西分布的数学期望和标准差，生产交叉因子cr；
40.步骤s4a-3、工序编码部分的差分变异公式为：
41.v_x＝r0_x+f
·
(pbest_x-r0_x)+f
·
(r1_x-r2_x)，其中，v_x为变异个体的连续化工序编码，pbest_x为pbest个体经过连续化转换的工序编码，r1_x为r1个体经过连续化转换的工序编码，r2_x为r2个体经过连续化转换的工序编码，r0_x为当前个体r0经过连续化转换的工序编码；
42.步骤s4a-4、对于每一道工序，记pbest个体选择的机器为pbest_m，记r1个体选择的机器为r1_m，记r2个体选择的机器为r2_m，并将其对应的机器选择概率矩阵中pbest_m、r1_m、r2_m机器的概率在原基础上分别增加2f、增加f、减小f；
43.步骤s4a-5、对每一道工序的机器选择概率矩阵进行归一化，随后使用轮盘赌的方法，为每一道工序选择加工机器，得到变异个体的机器编码v_m；
44.步骤s4a-6、工序编码部分的交叉公式为：
45.u_x＝cr
·
v_x+(1-cr)
·
r0_x，其中，u_x为子代个体u的连续化工序编码；
46.步骤s4a-7、对于机器编码中的每一个基因，随机生成0～1之间的随机数，随机数小于或等于cr的机器编码基因由v_m提供，其余机器编码的基因由r0_m提供，得到子代个体u的机器编码u_m；
47.步骤s4a-8、计算子代个体u的目标函数值，并将其与当前个体r0的目标函数值比较，若子代个体u优于r0，则将当前个体r0用子代个体u替换，反之，则不作处理；
48.按上述方式完成当前种群中全部个体的差分变异、交叉、选择等操作。
49.优选地，步骤s4中所述外部存档根据种群内个体与子代个体间的选择情况进行更新，具体实现过程如下：
50.步骤s4b-1、将种群中被子代个体替换的个体存入外部存档；
51.步骤s4b-2、若当前外部存档中的个体数目大于arc_size，则执行步骤s4b-3，否则结束外部存档更新；
52.步骤s4b-3、随机选择外部存档中的部分个体删除，使得外部存档中的个体数目等于arc_size。
53.优选地，步骤s4中所述优化算法使用的参数根据种群内个体与子代个体间的选择情况进行自适应更新，具体实现过程如下：
54.步骤s4c-1、称子代个体优于原个体为成功进化，将本次迭代中成功进化所使用的变异因子与交叉因子进行存储；
55.步骤s4c-2、根据如下公式计算变异因子的数学期望mu_f：
56.其中sf为成功进化个体所使用的变异因子的集合，c为更新mu_f时的权重；
57.步骤s4c-3、根据如下公式计算变异因子的数学期望mu_cr：
58.其中s
cr
为成功进化个体所使用的变异因子的集合。
59.优选地，步骤s4中所述选择部分个体，并在其周围进行邻域搜索，具体实现过程如下：
60.步骤s4d-1、根据个体的目标函数值，使用轮盘赌方法，从当前种群中选择p_select
×
100％个个体，对上述个体执行步骤s4d-2；
61.步骤s4d-2、对于每一个参与邻域搜索的个体，随机选择三道来自不同工件的工序，对其进行全排列后插入染色体的原位置，得到6个邻域个体；
62.步骤s4d-3、分别计算6个邻域个体的目标函数值，选择最优秀的个体存入邻域个体集合；
63.步骤s4d-4、对邻域个体集合中的每个个体，随机选择一道工序，将其加工机器随机替换为另一台可加工的机器；
64.步骤s4d-5、计算邻域个体集合中全部个体的目标函数值。
65.优选地，步骤s4中所述在完成种群进化、外部存档更新、参数自适应更新，以及邻域搜索等操作后，对当前种群进行更新，具体实现过程如下：
66.步骤s4e-1、将当前种群与邻域个体集合相结合，并将上述个体按照目标函数值升序排列；
67.步骤s4e-2、选择排名前pop_size个个体，作为本次迭代的最终种群。
68.本发明的有益效果：本发明能够从差分进化算法和柔性作业车间调度的原理出发，同时考虑工序加工的顺序限制、订单工件需求数量限制和加工机器的可行性限制，该方法首先建立以最大完工时间最短为目标的数学模型，设计元启发式算法生成初始种群，随后对参与进化的个体的染色体模型进行连续化转换，再经过差分变异、交叉等操作生成子代个体，通过比较目标函数值选择优秀个体，并对进化算法中的参数、外部存档进行更新，最后基于部分优秀个体进行邻域搜索，循环上述步骤直至算法结束，得到最优加工方案。该方法是一种针对离散问题的改进差分进化算法，通过数学模型的连续化转换，同时改进差分变异策略，能够改善差分进化算法在求解离散问题上的性能，从而获得最小化最大完工时间的作业车间调度方案，提高了多品种小批量生产模式下车间生产加工的效率和可靠性。
附图说明
69.图1为本发明的算法流程图；
70.图2为本发明一个个体的染色体数学模型；
71.图3为本发明进化个体的工序编码连续化转换示意图；
72.图4为本发明进化个体的机器编码连续化转换示意图；
73.图5为本发明进化个体间工序编码差分变异示意图；
74.图6为本发明进化个体间工序编码交叉示意图；
75.图7为本发明进化个体间机器编码差分变异及交叉示意图；
76.图8为本发明邻域搜索的流程图；
77.图9为本发明求解5
×
6算例的甘特图；
78.图10为本发明求解10
×
6算例的甘特图；
79.图11为本发明求解11
×
8算例的甘特图。
具体实施方式
80.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动的前提下所获得的所有其它实施例，都属于本发明保护的范围。
81.本发明提供一种基于差分进化算法的多品种小批量车间调度方法，属于制造生产车间的调度排产技术领域。对于以最大完工时间最小为优化目标的多品种小批量车间调度问题，该方法首先建立以最大完工时间最短为目标的数学模型，设计元启发式算法生成初始种群，随后对参与进化的个体的染色体模型进行连续化转换，再经过差分变异、交叉等操作生成子代个体，通过比较目标函数值选择优秀个体，并对进化算法中的参数、外部存档进行更新，最后基于部分优秀个体进行邻域搜索，循环上述步骤直至算法结束，得到最优加工方案。该方法能够改善差分进化算法在求解离散问题上的性能，获得高效稳定的调度方案，从而提高多品种小批量生产模式下车间生产加工的效率和可靠性。
82.需要说明的是，在不冲突的情况下，本发明中的实施例及实施例中的特征可以相互组合。
83.下面结合附图和具体实施例对本发明作进一步说明，但不作为本发明的限定。
84.具体实施方式一：下面结合图1～图11说明本实施方式，本实施方式所述基于差分进化算法的多品种小批量车间调度方法，该方法包括以下步骤：
85.步骤s1：对生产订单进行加工批次划分操作，并初始化参数；
86.多品种小批量车间调度问题可以描述为：k个订单k1,k2,...,kk要在m台机器m1,m2,...,mm上加工，每个订单包含随机数目个生产流程相同的工件，每种工件包含随机数目道工序，求解多品种小批量车间调度问题首先需对包含工件数目不同的订单进行拆分，再以小组为加工单位，为每一组的每道工序选择加工机器，同时确定每台机器上工序的最佳加工顺序及起始加工时间，使得订单中全部工件的完工总时间最短。
87.步骤s1中所述的加工批次划分的过程为：
88.步骤s1-1、计算全部工件的需求量的平均值；
89.步骤s1-2、根据平均值将生产订单划分为两组，其中工件需求量小于或等于平均值的生产订单划分为第一组，工件需求量大于平均值的生产订单划分为第二组；
90.步骤s1-3、第一组中每个生产订单作为一个加工批次；
91.对第二组中每个生产订单进行加工批次的重新拆分，以第一组生产订单中全部工件需求量的平均值为拆分标准，第二组中的每个生产订单被拆分为两个批次，其中一个加
工批次的工件需求量大于拆分标准，另一个加工批次的工件需求量小于或等于拆分标准。
92.以一个包含3种工件订单和5台机器的数据集为例，其加工信息如表1所示，该数据集包含k1，k2，k3三个订单，其中，订单k1包括3个工件，该种类工件包含3道工序o
1，1
，o
1，2
，o
1，3
，订单k2包括2个工件，该种类工件包含3道工序o
2，1
，o
2，2
，o
2，3
，订单k3包括5个工件，该种类工件包含3道工序o
3，1
，o
3，2
，o
3，3
。
93.表1
[0094][0095]
全部订单的工件需求数量的平均值为10/3，第一组的生产订单包括k1，k2，第二组的生产订单包括k3，因此，需对订单k3以订单k1，k2需求数量的平均值5/2为拆分标准进行加工批次的拆分，即订单k3被拆分为两个分别包含3个和2个工件加工批次，因此，订单共被拆分为4个加工批次，分组后的加工信息如表2所示，订单k1转换为加工批次g1，订单k2转换为加工批次g2，订单k3被拆分为g3，g4两个加工批次，每个加工批次的工件均包含3道工序。其中，加工批次g3包括工序o
3，1，1
，o
3，1，2
，o
3，1，3
，代表订单k3的第一个批次的第一道工序、第二道工序和第三道工序，同理，工件组g4包括工序o
3，2，1
，o
3，2，2
，o
3，2，3
，分别代表订单k3的第二个批次的三道工序。将拆分后的订单批次数目记作n，则这一包含3种订单和5台机器的多品种小批量车间调度问题可以转化为包含4个加工批次和5台机器，即加工批次数量n＝4，机器数量m＝5的柔性作业车间调度问题。
[0096]
表2
[0097][0098]
初始化参数包括：种群规模pop_size、外部存档规模arc_size、最大运行时间max_time、邻域搜索个体在种群中的占比p_select、精英个体在种群中的占比p_best、变异因子的数学期望mu_f和交叉因子的数学期望mu_cr。
[0099]
其中，种群规模pop_size的数值通过ceil(2
×
log(n
×
m))
×
10计算确定，设置外部存档规模arc_size与种群规模pop_size为相同数值，最大运行时间max_time通过0.05
×k×
m计算确定，变异因子的数学期望mu_f和交叉因子的数学期望mu_cr的初始值均设定为0.5。
[0100]
步骤s2：建立以最大完工时间最短为目标的数学模型，并使用元启发式算法生成初始种群；计算公式为c＝min{max(endi)},1≤i≤total_op_num，其中endi表示第i个工序的完工时间，total_op_num为全部加工批次所包含工序数量的总和，在表2所示的数据集中，total_op_num的数值为12。
[0101]
以后涉及的目标函数值都按这种方式处理。
[0102]
使用元启发式算法生成初始种群的过程为：
[0103]
步骤s2-1、对于染色体中工序编码部分的每一个基因，从当前剩余工序数目最多的工件中随机选择一个；
[0104]
步骤s2-2、对于染色体中的机器编码部分，按照工序编码中的工序顺序，依次为每道工序选择加工用时最短的机器；
[0105]
步骤s2-3、根据染色体中的工序编码部分和机器编码部分，确定每道工序的实际加工时间，并写入时间编码部分。
[0106]
如图2所示，为表2数据集对应的一个个体的染色体数学模型，可以看出批次g1的第一道工序o
1,1
在机器m1上加工，用时为351分钟，批次g3的第二道工序o
3,1,2
在机器m4上加工，用时为210分钟。
[0107]
步骤s3：对参与进化的个体的染色体模型进行连续化转换，模型转换的步骤依次为：
[0108]
染色体模型中工序编码部分连续化转换的步骤；
[0109]
染色体模型中基因按照自然工序排序的步骤；
[0110]
染色体模型中机器编码部分连续化转换的步骤；
[0111]
步骤s3中所述染色体模型连续化转换的过程为：
[0112]
步骤s3-1、对于染色体中的工序编码部分，记每一道工序在该段染色体中的次序为indexi；
[0113]
步骤s3-2、对工序编码中的每个基因计算total_op_num-indexi+1，并用该值代替原基因中的内容；
[0114]
步骤s3-3、将染色体中的工序编码、机器编码和时间编码均按照自然工序顺序进行排列；
[0115]
步骤s3-4、对于每一道工序，建立机器选择概率矩阵，并将各机器的选择概率初始化为1。
[0116]
以图2中个体的染色体数学模型为例，该模型连续化转换的过程如图3所示，原染色体模型中的工序编码为1 2 4 3 2 4 1 3 4 1 2 3，即加工批次一的第一道工序o
1,1
第一个被加工，随后加工批次二的第一道工序o
2,1
，以此类推。根据每道工序在原染色体模型中的排列顺序，可得到indexi为1 7 10 2 5 11 4 8 12 3 6 9，又total_op_num的数值为12，则可得到该个体的染色体模型中工序编码部分连续化转换结果为12 6 3 11 8 2 9 5 1 10 7 4。
[0117]
根据加工机器的可行性限制，以及图2个体的染色体数学模型，可建立各工序的机器选择概率矩阵，如图4所示，对于每道工序，其可加工机器的概率均初始化为1，不可行机器的加工概率用符号
“‑”
表示。
[0118]
步骤s4：使用基于多种进化策略和参数自适应更新策略的差分进化算法对步骤s3转换后的模型进行求解，使用该算法求解模型的步骤依次为：
[0119]
差分变异、交叉、选择的步骤；
[0120]
外部存档更新的步骤；
[0121]
参数自适应更新的步骤；
[0122]
部分个体进行邻域搜索的步骤；
[0123]
种群更新的步骤；
[0124]
步骤s4中所述使用优化算法求解模型的步骤：从精英群体、当前种群、外部存档与当前种群的并集中分别随机选择一个个体，对于当前种群中的每一个个体，依次进行差分变异、交叉和选择等步骤，随后更新外部存档和优化算法中的参数，并选择部分个体进行邻域搜索，最后更新当前种群，选择个体进行差分变异、交叉、选择的具体实现过程为：
[0125]
步骤s4a-1、从精英群体中随机选择一个个体记作pbest，从当前种群中随机选择一个个体记作r1，从当前种群与外部存档的并集中随机选择一个个体记作r2；
[0126]
步骤s4a-2、分别以mu_f和0.1为正态分布的数学期望和标准差，生成变异因子f，分别以mu_cr和0.1为柯西分布的数学期望和标准差，生产交叉因子cr；
[0127]
步骤s4a-3、工序编码部分的差分变异公式为：
[0128]
v_x＝r0_x+f
×
(pbest_x-r0_x)+f
×
(r1_x-r2_x)，其中，v_x为变异个体的连续化工序编码，pbest_x为pbest个体经过连续化转换的工序编码，r1_x为r1个体经过连续化转换的工序编码，r2_x为r2个体经过连续化转换的工序编码，r0_x为当前个体r0经过连续化转换的工序编码；
[0129]
步骤s4a-4、对于每一道工序，记pbest个体选择的机器为pbest_m，记r1个体选择的机器为r1_m，记r2个体选择的机器为r2_m，并将其对应的机器选择概率矩阵中pbest_m、r1_m、r2_m机器的概率在原基础上分别增加2f、增加f、减小f；
[0130]
步骤s4a-5、对每一道工序的机器选择概率矩阵进行归一化，随后使用轮盘赌的方法，为每一道工序选择加工机器，得到变异个体的机器编码v_m；
[0131]
步骤s4a-6、工序编码部分的交叉公式为：
[0132]
u_x＝cr
×
v_x+(1-cr)
×
r0_x，其中，u_x为子代个体u的连续化工序编码；
[0133]
步骤s4a-7、对于机器编码中的每一个基因，随机生成0～1之间的随机数，随机数小于或等于cr的机器编码基因由v_m提供，其余机器编码的基因由r0_m提供，得到子代个体u的机器编码u_m；
[0134]
步骤s4a-8、计算子代个体u的目标函数值，并将其与个体r0的目标函数值比较，若子代个体u优于r0，则将个体r0用子代个体u替换，反之，则不作处理；
[0135]
按上述方式完成当前种群中全部个体的差分变异、交叉、选择等操作。
[0136]
例如，如图5所示，pbest个体染色体模型的工序编码部分为1 2 4 3 2 4 1 3 4 1 2 3，对其进行连续化转换后，得到index
pbest
为12 6 3 11 8 2 9 5 1 10 7 4；r0个体染色体模型的工序编码部分为2 1 4 4 1 3 2 1 3 2 4 3，对其进行连续化转换后，得到index
r0
为11 8 5 12 6 3 7 4 1 10 9 2；r1个体染色体模型的工序编码部分为4 3 1 2 3 1 4 4 3 2 1 2，对其进行连续化转换后，得到index
r1
为10 7 2 9 3 1 11 8 4 12 6 5；r2个体染色体模型的工序编码部分为3 1 2 3 4 2 3 1 4 2 4 1，对其进行连续化转换后，得到index
r2
为11 5 1 10 7 3 12 9 6 8 4 2；若取fi的值为0.5，则可根据步骤s4a-3中差分变异公式，计算得出变异个体的连续化工序编码v_x为11 8 4.5 11 5 1.5 9 5.5 4 1 11.5 6，从而完成进化个体间工序编码的差分变异。
[0137]
如图6所示，若取cri的值为0.5，则很具步骤s4a-6的交叉公式可得子代个体的连续化工序编码u_x为11 8 4.5 11 5 1.5 7.5 4 0.5 12 9 4.5，经过转换最终得到子代个体的工序编码为4 1 2 4 1 3 2 1 4 3 2 3。
[0138]
对于每一道工序，将pbest个体为该道工序选择的机器对应的机器选择概率，在初始概率值基础上增加2f，将r1个体为该道工序选择的机器对应的机器选择概率，在初始概率值基础上增加f，将r2个体为该道工序选择的机器对应的机器选择概率，在初始概率值基础上减小f，得到如图7所示的机器选择概率矩阵，再对该矩阵进行归一化，最后通过轮盘赌方法，得到与子代个体的工序编码一一对应的机器编码u_m，在本实例中u_m为2 2 3 4 2 1 3 4 4 5 3 5。
[0139]
步骤s4中所述外部存档根据种群内个体与子代个体间的选择情况进行更新，具体实现过程如下：
[0140]
步骤s4b-1、将种群中被子代个体替换的个体存入外部存档；
[0141]
步骤s4b-2、若当前外部存档中的个体数目大于arc_size，则执行步骤s4b-3，否则
结束外部存档更新；
[0142]
步骤s4b-3、随机选择外部存档中的部分个体删除，使得外部存档中的个体数目等于arc_size。
[0143]
步骤s4中所述优化算法使用的参数根据种群内个体与子代个体间的选择情况进行自适应更新，具体实现过程如下：
[0144]
步骤s4c-1、称子代个体优于原个体为成功进化，将本次迭代中成功进化所使用的变异因子与交叉因子进行存储；
[0145]
步骤s4c-2、根据如下公式计算变异因子的数学期望mu_f：
[0146]
其中sf为成功进化个体所使用的变异因子的集合，c为更新mu_f时的权重；
[0147]
步骤s4c-3、根据如下公式计算变异因子的数学期望mu_cr：
[0148]
其中s
cr
为成功进化个体所使用的变异因子的集合。
[0149]
步骤s4中所述选择部分个体，并在其周围进行邻域搜索，具体实现过程如下：
[0150]
步骤s4d-1、根据个体的目标函数值，使用轮盘赌方法，从当前种群中选择p_select
×
100％个个体，对上述个体执行步骤s4d-2；
[0151]
步骤s4d-2、对于每一个参与邻域搜索的个体，随机选择三道来自不同工件的工序，对其进行全排列后插入染色体的原位置，得到6个邻域个体；
[0152]
步骤s4d-3、分别计算6个邻域个体的目标函数值，选择最优秀的个体存入邻域个体集合；
[0153]
步骤s4d-4、对邻域个体集合中的每个个体，随机选择一道工序，将其加工机器随机替换为另一台可加工的机器；
[0154]
步骤s4d-5、计算邻域个体集合中全部个体的目标函数值。
[0155]
步骤s4中所述在完成种群进化、外部存档更新、参数自适应更新，以及邻域搜索等操作后，对当前种群进行更新，具体实现过程如下：
[0156]
步骤s4e-1、将当前种群与邻域个体集合相结合，并将上述个体按照目标函数值升序排列；
[0157]
步骤s4e-2、选择排名前pop_size个个体，作为本次迭代的最终种群。
[0158]
步骤s5：判断算法的运行时间是否满足步骤s1中初始化参数给出的终止条件，是，则执行步骤s6；否，则返回执行步骤s4；
[0159]
步骤s6：对算法求得的最优调度方案进行解码，转换为直观的甘特图。
[0160]
为了验证基于差分进化算法的多品种小批量车间调度方法的可行性，本发明对生产规模k
×
m为5
×
6、10
×
6，以及11
×
8的算例进行了实验，将实验结果与遗传算法(ga)和粒子群优化(pso)进行对比分析。
[0161]
设置c-jade的相关参数如下：精英个体在种群中的占比p_best＝0.1，种群规模pop_size＝ceil(2
×
log(n
×
m))
×
10，邻域搜索个体在种群中的占比p_select＝0.85，最大运行时间max_time＝0.05
×k×
m，外部存档规模arc_size＝pop_size。三种算法求解各
实例的最大完工时间如表3所示，对应c-jade所得到的车间调度方案用图9-11的甘特图表示。
[0162]
表3
[0163][0164]
由表3可知，与ga、pso相比，从目标数值上看，本发明提出的c-jade算法的调度结果较为突出，且随着订单规模的扩大，其综合性能更加优异，寻优效果更好，稳定性更高。综上所述，本发明公开的基于差分进化算法的多品种小批量车间调度方法可以在多品种小批量生产模式下有效缩短工期，保证生产效率。
[0165]
虽然在本文中参照了特定的实施方式来描述本发明，但是应该理解的是，这些实施例仅仅是本发明的原理和应用的示例。因此应该理解的是，可以对示例性的实施例进行许多修改，并且可以设计出其他的布置，只要不偏离所附权利要求所限定的本发明的精神和范围。应该理解的是，可以通过不同于原始权利要求所描述的方式来结合不同的从属权利要求和本文中所述的特征。还可以理解的是，结合单独实施例所描述的特征可以使用在其它所述实施例中。
技术特征：1.一种基于差分进化算法的多品种小批量车间调度方法，其特征在于，该方法包括以下步骤：步骤s1：对生产订单进行加工批次划分操作，并初始化参数；步骤s2：建立以最大完工时间最短为目标的数学模型，并使用元启发式算法生成初始种群；步骤s3：对参与进化的个体的染色体模型进行连续化转换，模型转换的步骤依次为：染色体模型中工序编码部分连续化转换的步骤；染色体模型中基因按照自然工序排序的步骤；染色体模型中机器编码部分连续化转换的步骤；步骤s4：使用基于多种进化策略和参数自适应更新策略的差分进化算法对步骤s3转换后的模型进行求解，使用该算法求解模型的步骤依次为：差分变异、交叉、选择的步骤；外部存档更新的步骤；参数自适应更新的步骤；部分个体进行邻域搜索的步骤；种群更新的步骤；步骤s5：判断算法的运行时间是否满足步骤s1中初始化参数给出的终止条件，是，则执行步骤s6；否，则返回执行步骤s4；步骤s6：对算法求得的最优调度方案进行解码，转换为直观的甘特图。2.根据权利要求1所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s1中所述的加工批次划分的过程为：步骤s1-1、计算全部工件的需求量的平均值；步骤s1-2、根据平均值将生产订单划分为两组，其中工件需求量小于或等于平均值的生产订单划分为第一组，工件需求量大于平均值的生产订单划分为第二组；步骤s1-3、第一组中每个生产订单作为一个加工批次；对第二组中每个生产订单进行加工批次的重新拆分，以第一组生产订单中全部工件需求量的平均值为拆分标准，第二组中的每个生产订单被拆分为两个批次，其中一个加工批次的工件需求量大于拆分标准，另一个加工批次的工件需求量小于或等于拆分标准。3.根据权利要求2所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s1中初始化参数包括：种群规模pop_size、外部存档规模arc_size、最大运行时间max_time、邻域搜索个体在种群中的占比p_select、精英个体在种群中的占比p_best、变异因子的数学期望mu_f和交叉因子的数学期望mu_cr。4.根据权利要求3所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s2中建立以最大完工时间最短为目标的数学模型，计算公式：c＝min{max(end
i
)},1≤i≤total_op_num，其中end
i
表示第i个工序的完工时间，total_op_num为全部加工批次所包含工序数量的总和；使用元启发式算法生成初始种群的过程为：步骤s2-1、对于染色体中工序编码部分的每一个基因，从当前剩余工序数目最多的工件中随机选择一个；
步骤s2-2、对于染色体中的机器编码部分，按照工序编码中的工序顺序，依次为每道工序选择加工用时最短的机器；步骤s2-3、根据染色体中的工序编码部分和机器编码部分，确定每道工序的实际加工时间，并写入时间编码部分。5.根据权利要求4所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s3中所述染色体模型连续化转换的过程为：步骤s3-1、对于染色体中的工序编码部分，记每一道工序在该段染色体中的次序为index
i
；步骤s3-2、对工序编码中的每个基因计算total_op_num-index
i
+1，并用该值代替原基因中的内容；步骤s3-3、将染色体中的工序编码、机器编码和时间编码均按照自然工序顺序进行排列；步骤s3-4、对于每一道工序，建立机器选择概率矩阵，并将各机器的选择概率初始化为1。6.根据权利要求5所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s4中所述使用优化算法求解模型的步骤：从精英群体、当前种群、外部存档与当前种群的并集中分别随机选择一个个体，对于当前种群中的每一个个体，依次进行差分变异、交叉和选择等步骤，随后更新外部存档和优化算法中的参数，并选择部分个体进行邻域搜索，最后更新当前种群，其中选择个体进行差分变异、交叉、选择的具体实现过程为：步骤s4a-1、从精英群体中随机选择一个个体记作pbest，从当前种群中随机选择一个个体记作r1，从当前种群与外部存档的并集中随机选择一个个体记作r2；步骤s4a-2、分别以mu_f和0.1为正态分布的数学期望和标准差，生成变异因子f，分别以mu_cr和0.1为柯西分布的数学期望和标准差，生产交叉因子cr；步骤s4a-3、工序编码部分的差分变异公式为：v_x＝r0_x+f
·
(pbest_x-r0_x)+f
·
(r1_x-r2_x)，其中，v_x为变异个体的连续化工序编码，pbest_x为pbest个体经过连续化转换的工序编码，r1_x为r1个体经过连续化转换的工序编码，r2_x为r2个体经过连续化转换的工序编码，r0_x为当前个体r0经过连续化转换的工序编码；步骤s4a-4、对于每一道工序，记pbest个体选择的机器为pbest_m，记r1个体选择的机器为r1_m，记r2个体选择的机器为r2_m，并将其对应的机器选择概率矩阵中pbest_m、r1_m、r2_m机器的概率在原基础上分别增加2f、增加f、减小f；步骤s4a-5、对每一道工序的机器选择概率矩阵进行归一化，随后使用轮盘赌的方法，为每一道工序选择加工机器，得到变异个体的机器编码v_m；步骤s4a-6、工序编码部分的交叉公式为：u_x＝cr
·
v_x+(1-cr)
·
r0_x，其中，u_x为子代个体u的连续化工序编码；步骤s4a-7、对于机器编码中的每一个基因，随机生成0～1之间的随机数，随机数小于或等于cr的机器编码基因由v_m提供，其余机器编码的基因由r0_m提供，得到子代个体u的机器编码u_m；步骤s4a-8、计算子代个体u的目标函数值，并将其与当前个体r0的目标函数值比较，若
子代个体u优于r0，则将当前个体r0用子代个体u替换，反之，则不作处理；按上述方式完成当前种群中全部个体的差分变异、交叉、选择等操作。7.根据权利要求6所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s4中所述外部存档根据种群内个体与子代个体间的选择情况进行更新，具体实现过程如下：步骤s4b-1、将种群中被子代个体替换的个体存入外部存档；步骤s4b-2、若当前外部存档中的个体数目大于arc_size，则执行步骤s4b-3，否则结束外部存档更新；步骤s4b-3、随机选择外部存档中的部分个体删除，使得外部存档中的个体数目等于arc_size。8.根据权利要求7所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s4中所述优化算法使用的参数根据种群内个体与子代个体间的选择情况进行自适应更新，具体实现过程如下：步骤s4c-1、称子代个体优于原个体为成功进化，将本次迭代中成功进化所使用的变异因子与交叉因子进行存储；步骤s4c-2、根据如下公式计算变异因子的数学期望mu_f：其中s
f
为成功进化个体所使用的变异因子的集合，c为更新mu_f时的权重；步骤s4c-3、根据如下公式计算变异因子的数学期望mu_cr：其中s
cr
为成功进化个体所使用的变异因子的集合。9.根据权利要求8所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s4中所述选择部分个体，并在其周围进行邻域搜索，具体实现过程如下：步骤s4d-1、根据个体的目标函数值，使用轮盘赌方法，从当前种群中选择p_select
×
100％个个体，对上述个体执行步骤s4d-2；步骤s4d-2、对于每一个参与邻域搜索的个体，随机选择三道来自不同工件的工序，对其进行全排列后插入染色体的原位置，得到6个邻域个体；步骤s4d-3、分别计算6个邻域个体的目标函数值，选择最优秀的个体存入邻域个体集合；步骤s4d-4、对邻域个体集合中的每个个体，随机选择一道工序，将其加工机器随机替换为另一台可加工的机器；步骤s4d-5、计算邻域个体集合中全部个体的目标函数值。10.根据权利要求9所述基于差分进化算法的多品种小批量车间调度方法，其特征在于，步骤s4中所述在完成种群进化、外部存档更新、参数自适应更新，以及邻域搜索等操作后，对当前种群进行更新，具体实现过程如下：步骤s4e-1、将当前种群与邻域个体集合相结合，并将上述个体按照目标函数值升序排列；
步骤s4e-2、选择排名前pop_size个个体，作为本次迭代的最终种群。
技术总结基于差分进化算法的多品种小批量车间调度方法，属于制造生产车间的调度排产技术领域，本发明为解决多品种小批量车间调度的技术普遍存在适用度低、性能较差的问题。本发明方案：首先建立以最大完工时间最短为目标的数学模型，设计元启发式算法生成初始种群，随后对参与进化的个体的染色体模型进行连续化转换，再经过差分变异、交叉等操作生成子代个体，通过比较目标函数值选择优秀个体，并对进化算法中的参数、外部存档进行更新，最后基于部分优秀个体进行邻域搜索，循环上述步骤直至算法结束，得到最优加工方案。该方法能够改善差分进化算法在求解离散问题上的性能，获得高效稳定的调度方案。的调度方案。的调度方案。
技术研发人员：邓立宝 狄原竹 李春磊
受保护的技术使用者：哈尔滨工业大学（威海）
技术研发日：2022.04.21
技术公布日：2022/7/5
