一种分布式异构阻塞混合流水车间调度方法

1.本发明属于车间调度领域，具体涉及到一种分布式异构阻塞混合流水车间调度问题的数学模型和元启发式求解算法。


背景技术：

2.分布式异构混合流水车间调度问题(dhhfsp)是指工件需要分配到一个分布式的由不同异构混合流水生产线组成的工厂集中进行加工的调度问题，其中每个工厂的生产线拥有不同的作业配置环境和生产能力，需要进行合理的调度和作业安排，以最大程度地提高多个工厂的生产效率和资源利用率。对于大部分分布式混合流水车间调度问题的研究都还只是停留在同构工厂中，假设了所有工厂内部配置环境均相同，且机器都为相同并行机，而现实中对于不同地域工厂中的机器数量与机器的加工能力都难以做到相同，因而研究相同阶段采用数量不同的不相关并行机更加符合现实中的工厂制造情况。dhhfsp由于考虑到异构工厂的因素，是一个更为复杂的np-hard问题，需要解决三个强耦合问题：工件需要分配给合适的工厂、为每个工厂内的工件分配合适的机器、给每台机器上需要加工的零件进行排序。此外，本文的dhhfsp还考虑了工厂带阻塞约束情况，当一个工件在某个工序上发生阻塞时，将会影响到该工件在后续工序上的加工进度，同时也会对其它作业的加工进度产生影响，是一种具有挑战性的现实优化问题。在求解此类调度问题中，元启发式算法是最为常见的求解方法。
3.在生产过程中，企业为保证利润的最大化，需要同时考虑制造过程的众多因素，例如，最大完工时间、最大拖期、总完成时间等。在实际生产中，及时地交付客户订单产品能够提高客户的满意度，能在未来为企业带来更多的利益。相反，订单的拖期时间越久，客户的不满意度就会越高，不利于企业未来发展。因而在解决实际调度问题中基于交货日期为目标已经变得比基于最大生产周期为目标更为重要。
4.差分进化(de)算法由于独特多样的差分策略在求解车间调度问题中具有高效的求解性能。因此本文设计了一种多目标差分进化(mode)算法，将多种差分策略进行混合设计，并且算法中根据问题特征设计了一种工厂分配规则、种群初始化方法和6种领域结构的变领域下降算法，对多目标分布式异构混合流水车间调度问题进行求解。


技术实现要素：

5.为解决上述分布式异构阻塞混合流水车间调度问题存在的难题，本发明的目的在于提供一种分布式异构阻塞混合流水车间调度方法，本发明的方法给出了相应的数学模型。为求解该模型，提出一种基于pareto方法的多目标差分进化算法，该算法针对异构车间的复杂性，引入了一类新的工厂分配规则，并设计了4种启发式算法，以提高初始种群的质量。为了更好地保证算法的多样性和收敛性，算法将两种差分策略混合设计。此外，依据问题特性设计了6种领域结构的变领域下降算法以增强算法的局部搜索能力。从而减小最大完工时间和总拖期时间，提高分布式混合流水车间的生产效率。
6.本发明是通过以下技术方案实现的：
7.一种分布式异构阻塞混合流水车间调度方法与系统，包括：
8.s1：研究了多目标分布式异构阻塞混合流水车间调度问题(dhbhfsp)，在这个问题中同时考虑了对最大完工时间和总拖期时间的目标优化；
9.s2：建立了对应的dhbhfsp数学模型，确定优化目标和约束条件；
10.s3：采用提出的基于pareto方法的多目标差分进化算法(mode)对数学模型进行求解；
11.s4：基于问题的异构特性设计了一种工厂分配规则；
12.s5：设计了基于优化目标的4种启发式算法提高初始解质量；
13.s6：差分策略部分采用双差分混合策略；
14.s7：提出基于问题特征的6种领域结构的变邻域下降算法进行局部搜索；
15.所述步骤s1研究的多目标分布式异构阻塞混合流水车间调度问题中，有一批工件i＝{1,2,
…
,n}需要被分配到一异构工厂集f＝{1,2,
…
,f}中进行加工。每个工厂都是一个阻塞混合流水车间，且都有相同数量的加工阶段s，每个加工阶段至少有一台并行机，每个工厂同一加工阶段内的并行机数量不一定相同，且相同阶段的并行机均为不相关并行机，每个工件都可以在任意一个工厂内完成s个加工阶段。每个工件分配到某一个工厂后不得转移到其他工厂中且从开始到结束都需要经历s个加工阶段，工件在每个加工阶段中可以被该阶段的任意一台机器加工。所有阶段中任意两个相邻加工的工件之间无中间缓冲区，工件的加工准备时间和运输时间包括在该阶段加工时间当中。需要优化的目标为最小化最大完工时间和总拖期时间。
16.所述步骤s2中的数学模型、优化目标和约束条件如下:
17.数学模型的参数符号定义如下：
18.f——工厂总数；
19.n——工件总数；
20.s——阶段总数；
21.f——工厂索引，f∈{1,2,...,f}；
22.ii'——工件索引，i,i'∈{1,2,...,n},i≠i'；
23.jj'——阶段索引,j,j'∈{1,2,...,s}，j≠j'；
24.k
fj
——工厂f的阶段j的机器数量；
25.m
fj
——工厂f的阶段j的机器索引,m
fj
∈{1,2,...,k
fj
}；
26.——工件i在工厂f的阶段j上的机器m
f,j
上的加工时间；
27.o
i,j
——工件i在阶段j的工序；
28.t
i,j
——工序o
i,j
开始时间；
29.n——一个非常大的正值(例如取值106)；
30.di——工件i的交货时间；
31.——工件i在本阶段j机器m
fj
上开始加工的时间；
32.c
i,j
——工件i在阶段j的完工时间；
33.cf——工厂f的最大完工时间；
34.c
max
——所有工厂的最大完工时间；
35.ti——工件i的总拖期时间；
36.t_total——所有工件的总拖期时间；
37.数学模型的决策变量如下：
38.x
i,f
——工件i在工厂f则为1，否则为0；
39.——工件i的工序o
i,j
在工厂f的阶段j的机器m
fj
上加工为1，否则为0；
40.——同在机器m
fj
上加工的工件i工序o
i,j
比工件i'的工序o
i',j
早则为1，否则为0；
41.z
f,j,i,i'
——工件i在工厂f的阶段j的任意位置都比工件i'之前则为1，否则为0；
42.数学模型的优化目标和约束条件如下：
[0043][0044][0045][0046]
ti＝max[c
i,s-di,0]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)
[0047][0048]
minimize(c
max
,t_total)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0049]
s.t.
[0050][0051][0052][0053][0054][0055]
[0056][0057][0058][0059][0060][0061][0062]
上述中，式(1)表示第i个工件的最大完工时间；式(2)表示为第f个工厂的最大完工时间；式(3)表示所有工厂的最大完工时间；式(4)表示第i个工件的拖期时间；式(5)表示所有工件的总拖期时间；式(6)表示为需要优化的两个目标函数；式(7)保证每个工件只能分配到一个工厂；式(8)保证每个工件经过所有阶段且在每个阶段只在一台机器上加工；式(9)表示每台机器不能同时加工多个工件；式(10)和式(11)保证在一个时间上机器只能加工一个工件且一个工件只能被一台机器加工；式(12)表示每个工件在j+1阶段的开始加工时间不得早于j阶段的加工结束时间；式(13)表示同一工厂f的同一阶段j的同一机器上m
f,j
中工件i'的开始加工时间不早于前一个工件i的加工结束时间；式(14)保证了每一个工件的拖期时间为最后一个阶段的；式(15)-(18)表示决策变量的条件。
[0063]
所述步骤s3提出的基于pareto方法的多目标差分进化算法引入占优概念区分支配解和非支配解，使得算法进化过程中保证一个目标函数不变坏的情况下，优化另外一个目标函数。算法步骤如下：
[0064]
step1：初始化种群数量psize参数、变异缩放因子fr、交叉概率cr；
[0065]
step2：利用提出的dneh1、dneh2、dneh
r1
、dneh
r2
4种启发式算法对种群进行初始化。
[0066]
step3：将种群中的个体进行pareto等级排序，按照pareto等级将种群分为较好部分和较差部分；
[0067]
step4：双差分策略
[0068]
step4.1：pareto等级排序中前psize*70％个个体采用de/rand/1差分策略；
[0069]
step4.2：pareto等级排序中后psize*30％个个体采用de/best/1差分策略；
[0070]
step5：采用具有6个邻域结构的变领域下降算法对差分策略生成的实验个体进行局部搜索；
[0071]
step6：确定局部搜索后的实验个体与目标个体之间的支配关系。若实验个体支配目标个体，则实验个体替代掉目标个体进入下一个进化种群中；反之，目标个体进入下一次进化种群中；
[0072]
step7：判断是否达到终止条件，是则输出pareto最优解集，否则返回步骤3继续循环迭代；
[0073]
进一步地，所述s3中的基于pareto方法的多目标差分进化算法的编码形式采用置换编码方法，这种编码形式高效且易实现，具体为：π＝{π1；π2；
…
；πf；
…
；πf},'；'为工厂分隔符，每个πf都表示为第f个工厂内部工件的置换编码，其中的工件编码排序也是每个工厂
第一个加工件阶段的工件加工顺序，其余加工阶段的顺序按照fifo规则由工件在上一阶段加工完成时间的先后确定。
[0074]
所述步骤s4中基于问题异构特性设计的一种工厂分配规则如下：
[0075]
该工厂分配规则能够将工件放入到更加合适的工厂中进行加工，步骤：
[0076]
(1)首先计算出每个工件在每个工厂中总共需要的综合加工时间，每个工件的综合加工时间计算公式如下：
[0077][0078]
(2)随后根据工件i在每个工厂的的倒数形成轮盘，采用轮盘赌方法选择其中一个工厂作为加工工厂，越小则选择该工厂的概率就会越大。
[0079]
所述步骤s5的基于优化目标的4种启发式算法，具体如下：
[0080]
dneh1：分别计算所有工件的综合加工时间，随后工件按加工时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中。
[0081]
dneh2：按照每个工件的拖期时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中。
[0082]
dneh
r1
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中。
[0083]
dneh
r2
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中。
[0084]
所述步骤s6的双差分混合策略，具体如下：
[0085]
对于pareto等级排序中前psize*70％个个体采用de/rand/1差分策略，其第l个目标个体的第g次迭代变异策略可以描述为如下：
[0086][0087]
可将变异策略拆分为两个部分：
[0088]
第一部分：
[0089][0090]
第二部分：
[0091][0092]
与de/rand/1对应的交叉算子会结合变异个体v'
l,g
和目标个体生成实验个体交叉算子会从变异个体中提取一些工件后通过本文提出的工厂分配规则选择其中一个工厂插入到该工厂的最好位置，该交叉算子能够有更大的概率将提取出来的工件插入到最好的工厂中，这个过程循环执行h次选择最好的解。具体见如下：
[0093]
步骤一：提取变异个体中每个维度中第一个出现的工件放入v'中。
[0094]
步骤二：v'每个维度中的数值取舍由一随机数与交叉概率cr进行比较判断，若随机数大于等于交叉概率cr，则保留该数值，否则置为0，得到v”。
[0095]
步骤三：令实验个体＝目标个体移除中与v”相同的非0工件，依次将移除的工件插入到所选择的工厂中的所有可能位置，选择能使该工厂最大完工时间最小的位置，并保存该解。
[0096]
步骤四：判断是否达到h次循环，否则返回步骤二，是则从h个解中选择最好一个解并退出循环。
[0097]
对于pareto等级排序中剩下的psize*30％个个体采用de/best/1差分策略，可表述为
[0098][0099]
该差分策略过程与de/rand/1差分策略基本相同，唯一不同的是将随机个体替换成了种群中的最优解其de/best/1对应的交叉算子也与上述所说的交叉算子相似，不同点在于目标个体变为种群中最优解
[0100]
所述步骤s7的基于问题特征的变邻域下降算法，具体的6种邻域结构如下：
[0101]
n1：pareto拖期工件交换
[0102]
提取所有工件中具有最大拖期时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0103]
n2：pareto拖期工件插入
[0104]
提取所有工件中具有最大拖期时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
[0105]
n3：pareto最大完工时间插入
[0106]
提取具有最大完工时间工厂中的任一工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0107]
n4：pareto最大完工时间交换
[0108]
提取具有最大完工时间工厂中的任一工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
[0109]
n5：最大阻塞工件插入
[0110]
提取所有工件中具有最大阻塞时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0111]
n6：最大阻塞工件交换
[0112]
提取所有工件中具有最大阻塞时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
附图说明
[0113]
图1mode算法流程图；
[0114]
图2变异过程图；
[0115]
图3交叉过程图；
[0116]
图4四个算例的解集映射图。
[0117]
具体实施方法
[0118]
为了便于本领域技术人员的理解，下面结合实例与附图对本发明作进一步的说明，实施方式提及的内容并非对本发明的限定。
[0119]
1.分布式异构阻塞混合流水车间调度问题描述与数学模型
[0120]
有一批工件i＝{1,2,
…
,n}需要被分配到一异构工厂集f＝{1,2,
…
,f}中进行加工。每个工厂都是一个阻塞混合流水车间，且都有相同数量的加工阶段s，每个加工阶段至少有一台并行机，每个工厂同一加工阶段内的并行机数量不一定相同，且相同阶段的并行机均为不相关并行机，每个工件都可以在任意一个工厂内完成s个加工阶段。每个工件分配到某一个工厂后不得转移到其他工厂中且从开始到结束都需要经历s个加工阶段，工件在每个加工阶段中可以被该阶段的任意一台机器加工。所有阶段中任意两个相邻加工的工件之间无中间缓冲区，工件的加工准备时间和运输时间包括在该阶段加工时间当中。需要优化的目标为最小化最大完工时间和总拖期时间。
[0121]
数学模型的参数符号定义如下：
[0122]
f——工厂总数
[0123]
n——工件总数
[0124]
s——阶段总数
[0125]
f——工厂索引，f∈{1,2,...,f}
[0126]
ii'——工件索引,i,i'∈{1,2,...,n},i≠i'
[0127]
jj'——阶段索引,j,j'∈{1,2,...,s},j≠j'
[0128]kfj
——工厂f的阶段j的机器数量
[0129]mfj
——工厂f的阶段j的机器索引,m
fj
∈{1,2,...,k
fj
}
[0130]
——工件i在工厂f的阶段j上的机器m
f,j
上的加工时间
[0131]oi,j
——工件i在阶段j的工序
[0132]
t
i,j
——工序o
i,j
开始时间
[0133]
n——一个非常大的正值
[0134]di
——工件i的交货时间
[0135]
——工件i在本阶段j机器m
fj
上开始加工的时间
[0136]ci,j
——工件i在阶段j的完工时间
[0137]cf
——工厂f的最大完工时间
[0138]cmax
——所有工厂的最大完工时间
[0139]
ti——工件i的总拖期时间
[0140]
t_tatal——所有工件的总拖期时间
[0141]
数学模型的决策变量如下：
[0142]
x
i,f
——工件i在工厂f则为1，否则为0
[0143]
——工件i的工序o
i,j
在工厂f的阶段j的机器m
fj
上加工为1，否则为0
[0144]
——同在机器m
fj
上加工的工件i工序o
i,j
比工件i'的工序o
i',j
早则为1，否则为0
[0145]zf,j,i,i'
——工件i在工厂f的阶段j的任意位置都比工件i'之前则为1，否则为0
[0146]
数学模型的优化目标和约束条件如下：
[0147][0148][0149][0150]
ti＝max[c
i,s-di,0]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)
[0151][0152]
minimize(c
max
,t_total)
ꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0153]
s.t.
[0154][0155][0156][0157][0158]
[0159][0160][0161][0162][0163][0164][0165][0166]
上述中，式(1)表示第i个工件的最大完工时间；式(2)表示为第f个工厂的最大完工时间；式(3)表示所有工厂的最大完工时间；式(4)表示第i个工件的拖期时间；式(5)表示所有工件的总拖期时间；式(6)表示为需要优化的两个目标函数；式(7)保证每个工件只能分配到一个工厂；式(8)保证每个工件经过所有阶段且在每个阶段只在一台机器上加工；式(9)表示每台机器不能同时加工多个工件；式(10)和式(11)保证在一个时间上机器只能加工一个工件且一个工件只能被一台机器加工；式(12)表示每个工件在j+1阶段的开始加工时间不得早于j阶段的加工结束时间；式(13)表示同一工厂f的同一阶段j的同一机器上m
f,j
中工件i'的开始加工时间不早于前一个工件i的加工结束时间；式(14)保证了每一个工件的拖期时间为最后一个阶段的；式(15)-(18)表示决策变量的条件。
[0167]
2.求解分布式异构阻塞混合流水车间调度问题的多目标差分进化算法
[0168]
2.1算法框架
[0169]
采用本文提出的基于pareto方法的多目标差分进化算法对上述数学模型进行求解。基于pareto的多目标差分进化算法引入占优概念区分支配解和非支配解，使得算法进化过程中保证一个目标函数不变坏的情况下，优化另外一个目标函数。算法流程如图1，步骤如下：
[0170]
step1：初始化种群数量psize参数、变异缩放因子fr、交叉概率cr；
[0171]
step2：利用提出的dneh1、dneh2、dneh
r1
、dneh
r2
4种启发式算法对种群进行初始化。
[0172]
step3：将种群中的个体进行pareto等级排序，按照pareto等级将种群分为较好部分和较差部分；
[0173]
step4：双差分策略
[0174]
step4.1：pareto等级排序中前psize*70％个个体采用de/rand/1差分策略；
[0175]
step4.2：pareto等级排序中后psize*30％个个体采用de/best/1差分策略；
[0176]
step5：采用具有6个邻域结构的变领域下降算法对差分策略生成的实验个体进行局部搜索；
[0177]
step6：确定局部搜索后的实验个体与目标个体之间的支配关系。若实验个体支配
目标个体，则实验个体替代掉目标个体进入下一个进化种群中；反之，目标个体进入下一次进化种群中；
[0178]
step7：判断是否达到终止条件，是则输出pareto最优解集，否则返回步骤3继续循环迭代；
[0179]
2.2编码与解码
[0180]
本发明将使用在分布式调度问题中广泛应用的置换编码方法，这种编码形式高效且易实现，具体为：π＝{π1；π2；
…
；πf；
…
；πf},'；'为工厂分隔符，每个πf都表示为第f个工厂内部工件的置换编码，其中的工件编码排序也是每个工厂第一个加工件阶段的工件加工顺序，其余加工阶段的顺序按照fifo规则由工件在上一阶段加工完成时间的先后确定。
[0181]
2.3工厂分配规则
[0182]
考虑到dhbhfsp中的每个工厂同阶段具有不相同数量的不相关并行机因素，提出一种适用于本发明异构工厂的工厂分配规则：
[0183]
(1)首先计算出每个工件在每个工厂中总共需要的综合加工时间，每个工件的综合加工时间计算公式如下：
[0184][0185]
式中表示为工件i在第f个工厂的综合加工时间。
[0186]
(2)随后根据工件i在每个工厂的的倒数形成轮盘，采用轮盘赌方法选择其中一个工厂插入其中，越小则选择该工厂的概率就会越大。
[0187]
2.4种群初始化
[0188]
结合需要优化的两个目标最小化最大完工时间和总拖期时间，提出四种启发式算法生成初始种群保证种群多样性和种群质量，分别记为dneh1、dneh2、dneh
r1
、dneh
r2
。初始种群中两个个体分别由dneh1和dneh2生成，其余个体有dneh
r1
和dneh
r2
生成。
[0189]
dneh1：分别计算所有工件的综合加工时间，随后工件按加工时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中。
[0190]
dneh2：按照每个工件的拖期时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中。
[0191]
dneh
r1
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中。
[0192]
dneh
r2
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中。
[0193]
2.5双差分策略
[0194]
对于pareto等级排序中前psize*70％个个体采用de/rand/1差分策略，其第l个目标个体的第g次迭代变异策略可以描述为如下：
[0195]
[0196]
可将变异策略拆分为两个部分：
[0197]
第一部分：
[0198][0199]
第二部分：
[0200][0201][0202]
与de/rand/1对应的交叉算子会结合变异个体v'
l,g
和目标个体生成实验个体交叉算子会从变异个体中提取一些工件后通过本文提出的工厂分配规则选择其中一个工厂插入到该工厂的最好位置，该交叉算子能够有更大的概率将提取出来的工件插入到最好的工厂中，这个过程循环执行h次选择最好的解。具体见如下：
[0203]
步骤一：提取变异个体中每个维度中第一个出现的工件放入v'中。
[0204]
步骤二：v'每个维度中的数值取舍由一随机数与交叉概率cr进行比较判断，若随机数大于等于交叉概率cr，则保留该数值，否则置为0，得到v”。
[0205]
步骤三：令实验个体＝目标个体移除中与v”相同的非0工件，依次将移除的工件插入到所选择的工厂中的所有可能位置，选择能使该工厂最大完工时间最小的位置，并保存该解。
[0206]
步骤四：判断是否达到h次循环，否则返回步骤二，是则从h个解中选择最好一个解并退出循环。
[0207]
为了进一步说明变异与交叉过程，给出了一个10工件，2工厂的例子，缩放因子fr和交叉概率cr均为0.5，图2、图3分别为变异过程图与交叉过图。
[0208]
对于pareto等级排序中剩下的psize*30％个个体采用de/best/1差分策略，可表述为
[0209][0210]
该差分策略过程与de/rand/1差分策略基本相同，唯一不同的是将随机个体替换成了种群中的最优解其de/best/1对应的交叉算子也与上述所说的交叉算子相似，不同点在于目标个体变为种群中最优解
[0211]
2.6局部搜索
[0212]
为增强mode算法的局部搜索能力，设计了结合问题的优化目标和dhbhfsp问题特性的具有6种领域结构的变领域下降算法。n1和n2邻域结构用于减小工件拖期时间从而减
小总拖期时间；n3和n4邻域结构用于降低目标函数最大完工时间；工件的阻塞会严重影响最大完工时间和总拖期时间两个优化目标，因而通过n5、n6邻域结构减少阻塞时间。每个邻域结构中保留下来的多个解都将进行非支配关系排序，从中选择pareto最优解，若出现多个pareto最优解则随机选择一个输出。
[0213]
n1：pareto拖期工件交换
[0214]
提取所有工件中具有最大拖期时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0215]
n2：pareto拖期工件插入
[0216]
提取所有工件中具有最大拖期时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
[0217]
n3：pareto最大完工时间插入
[0218]
提取具有最大完工时间工厂中的任一工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0219]
n4：pareto最大完工时间交换
[0220]
提取具有最大完工时间工厂中的任一工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
[0221]
n5：最大阻塞工件插入
[0222]
提取所有工件中具有最大阻塞时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解。
[0223]
n6：最大阻塞工件交换
[0224]
提取所有工件中具有最大阻塞时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。
[0225]
实施例1:
[0226]
本实施例1给出64个算例，进行验证上述分布式异构阻塞混合流水车间调度方法与系统的科学性和有效性：
[0227]
加工零件数量n∈{20,40,60,80}，工厂数量f∈{2,3,4,5}，加工阶段数s∈{2,3,5,8}，n、f、s进行组合可生成64个算例。每个算例中每个工厂内的每个加工阶段的不相关并行机数量在[1-4]内随机生成，零件加工时间在[1-99]内随机生成。每个工件的交货期限设置为如下公式：
[0228]di
＝pi×
(1+random
×
3)
[0229]
式中，di表示为工件的交货期限；pi表示为工件的综合总加工时间，random是0到1之间的随机数。
[0230]
算法的终止条件时间设置为即(工件数*工厂数*阶段数*0.2(s))。每个算法在求解某一算例时都将进行10次独立运行，最后通过世代距离(generational distance，gd)、反世代距离(inverted generational distance，igd)和超体积指标(hypervolume，hv)作为评价指标，衡量算法的性能。
[0231]
对多目标差分进化算法的基本参数设置如表1：
[0232]
表1基本参数表
[0233]
种群数量psize异缩放因子fr交叉概率cr
200.70.9
[0234]
将参数校正过的mode算法与广泛用于处理多目标问题的nsgaii算法进行实验对比。nsgaii算法中的编码形采用与本文中相同的编码形式，交叉变异中采用单点交叉方法，随后子代个体中相同的工件将被移除，未出现的工件将随机插入到子代个体中，局部搜索策略采用本文提出的vnd算法进行搜素。nsgaii算法的种群设置为50，其余参数与算法原文中相同。表2给出了两个算法的平均gd、igd、hv的实验对比结果，表中的最优指标数据已由加粗表示。
[0235]
表2算法对比结果
[0236]
[0237][0238]
由表中可知，就gd指标而言，mode算法获得了58个算例中的所有最优值，nsgaii算法获得了6个最优值，显然mode算法在收敛性方面要远优于nsgaii算法；就igd指标而言，nsgaii获得了7次最优值，mode算法获得了57次最优值，表明mode在收敛性和分布性上同样都更好；就hv指标而言，mode算法获得了55次最好的值，nsgaii算法获得了9次最优值，这表明mode算法的综合性能要比nsgaii强很多。nsgaii算法在3个指标中所获得的最佳值均是
在工件为20的小算例中，而随着工件数量的增加，求解难度的加大，mode算法体现出了更强的寻优能力。综上结果可以得到，mode算法在求解dhbhfsp中具有高效的性能。
[0239]
表3指标平均值(工件、工厂、阶段)
[0240][0241]
为了更好地了解mode算法对不同数量的工件、工厂和阶段的影响，对每个数量的工件、工厂和阶段进行gd、igd、hv平均值统计分析，如表3所示。从表中可以看到工件数量为20时，nsgaii算法的综合性能与mode算法相差不大。随着工件规模的增加，mode算法相对nsgaii算法在3个平均指标上都表现出越来越强的求解性能，图4给出了两个算法在工厂数为4、阶段数为3的不同工件下的4个算例解的空间映射图。对于不用数量的工厂和阶段，mode算法在3个指标上的表现虽然都较为均衡，但比nsgaii算法明显更加优越。两个算法在局部搜索采用相同策略的情况下，随求解规模的增大，mode算法具有更好的寻优能力，这表明所提的工厂分配规则、双差分策略和vnd搜索策略能够更好地平衡全局搜索和局部勘探能力。

技术特征：
1.一种分布式异构阻塞混合流水车间调度方法，其特征在于包括，s1：研究多目标分布式异构阻塞混合流水车间调度问题dhbhfsp，在这个问题中同时考虑对最大完工时间和总拖期时间的目标优化；s2：基于步骤s1研究的问题以及同时引入考虑的对最大完工时间和总拖期时间的目标优化，建立对应的dhbhfsp数学模型，确定优化目标和约束条件；s3：采用提出的基于pareto方法的多目标差分进化算法mode对数学模型进行求解；s4：基于问题的异构特性设计一种新的工厂分配规则；s5：设计基于优化目标的4种启发式算法提高初始解质量；s6：差分策略部分采用双差分混合策略；s7：提出基于问题特征的6种领域结构的变邻域下降算法进行局部搜索。2.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s1中分布式异构阻塞混合流水车间调度问题的特性为：有一批工件i＝{1,2,
…
,n}需要被分配到一异构工厂集f＝{1,2,
…
,f}中进行加工；每个工厂都是一个阻塞混合流水车间，且都有相同数量的加工阶段s，每个加工阶段至少有一台并行机，每个工厂同一加工阶段内的并行机数量不一定相同，且相同阶段的并行机均为不相关并行机，每个工件都可以在任意一个工厂内完成s个加工阶段；每个工件分配到某一个工厂后不得转移到其他工厂中且从开始到结束都需要经历s个加工阶段，工件在每个加工阶段中可以被该阶段的任意一台机器加工；所有阶段中任意两个相邻加工的工件之间无中间缓冲区，工件的加工准备时间和运输时间包括在该阶段加工时间当中；需要优化的目标为最小化最大完工时间和总拖期时间。3.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s2建立的dhbhfsp数学模型如下：数学模型的参数符号定义如下：f——工厂总数；n——工件总数；s——阶段总数；f——工厂索引，f∈{1,2,...,f}；i i'——工件索引,i,i'∈{1,2,...,n},i≠i'；j j'——阶段索引,j,j'∈{1,2,...,s}，j≠j'；k
fj
——工厂f的阶段j的机器数量；m
fj
——工厂f的阶段j的机器索引,m
fj
∈{1,2,...,k
fj
}；——工件i在工厂f的阶段j上的机器m
f,j
上的加工时间；o
i,j
——工件i在阶段j的工序；t
i,j
——工序o
i,j
开始时间；n——一个非常大的正值；d
i
——工件i的交货时间；——工件i在本阶段j机器m
fj
上开始加工的时间；c
i,j
——工件i在阶段j的完工时间；
c
f
——工厂f的最大完工时间；c
max
——所有工厂的最大完工时间；t
i
——工件i的总拖期时间；t_total——所有工件的总拖期时间；数学模型的决策变量如下：x
i,f
——工件i在工厂f则为1，否则为0；——工件i的工序o
i,j
在工厂f的阶段j的机器m
fj
上加工为1，否则为0；——同在机器m
fj
上加工的工件i工序o
i,j
比工件i'的工序o
i',j
早则为1，否则为0；z
f,j,i,i'
——工件i在工厂f的阶段j的任意位置都比工件i'之前则为1，否则为0；数学模型的优化目标和约束条件如下：数学模型的优化目标和约束条件如下：数学模型的优化目标和约束条件如下：t
i
＝max[c
i,s-d
i
,0]
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(4)minimize(c
max
,t_total)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)s.t.s.t.s.t.s.t.s.t.s.t.
上述中，式(1)表示第i个工件的最大完工时间；式(2)表示为第f个工厂的最大完工时间；式(3)表示所有工厂的最大完工时间；式(4)表示第i个工件的拖期时间；式(5)表示所有工件的总拖期时间；式(6)表示为需要优化的两个目标函数；式(7)保证每个工件只能分配到一个工厂；式(8)保证每个工件经过所有阶段且在每个阶段只在一台机器上加工；式(9)表示每台机器不能同时加工多个工件；式(10)和式(11)保证在一个时间上机器只能加工一个工件且一个工件只能被一台机器加工；式(12)表示每个工件在j+1阶段的开始加工时间不得早于j阶段的加工结束时间；式(13)表示同一工厂f的同一阶段j的同一机器上m
f,j
中工件i'的开始加工时间不早于前一个工件i的加工结束时间；式(14)保证了每一个工件的拖期时间为最后一个阶段的；式(15)-(18)表示决策变量的条件。4.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s3采用提出的基于pareto方法的多目标差分进化算法，基于pareto的多目标差分进化算法引入占优概念区分支配解和非支配解，使得算法进化过程中保证一个目标函数不变坏的情况下，优化另外一个目标函数；算法步骤如下：step1：初始化种群数量psize参数、变异缩放因子fr、交叉概率cr；step2：利用提出的dneh1、dneh2、dneh
r1
、dneh
r2
4种启发式算法对种群进行初始化；step3：将种群中的个体进行pareto等级排序，按照pareto等级将种群分为较好部分和较差部分；step4：双差分策略step4.1：pareto等级排序中前psize*70％个个体采用de/rand/1差分策略；step4.2：pareto等级排序中后psize*30％个个体采用de/best/1差分策略；step5：采用具有6个邻域结构的变领域下降算法对差分策略生成的实验个体进行局部搜索；step6：确定局部搜索后的实验个体与目标个体之间的支配关系；若实验个体支配目标个体，则实验个体替代掉目标个体进入下一个进化种群中；反之，目标个体进入下一次进化种群中；step7：判断是否达到终止条件，是则输出pareto最优解集，否则返回步骤3继续循环迭代。5.根据权利要求4所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：基于pareto方法的多目标差分进化算法的编码形式采用置换编码方法，这种编码形式
高效且易实现，具体为：π＝{π1；π2；
…
；π
f
；
…
；π
f
},'；'为工厂分隔符，每个π
f
都表示为第f个工厂内部工件的置换编码，其中的工件编码排序也是每个工厂第一个加工件阶段的工件加工顺序，其余加工阶段的顺序按照fifo规则由工件在上一阶段加工完成时间的先后确定。6.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述s4的基于问题异构特性设计了一种新的工厂分配规则，具体如下(1)首先计算出每个工件在每个工厂中总共需要的综合加工时间，每个工件的综合加工时间计算公式如下：(2)随后根据工件i在每个工厂的的倒数形成轮盘，采用轮盘赌方法选择其中一个工厂作为加工工厂，越小则选择该工厂的概率就会越大。7.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s5的基于优化目标的4种启发式算法，具体如下：dneh1：分别计算所有工件的综合加工时间，随后工件按加工时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中；dneh2：按照每个工件的拖期时间从大到小进行排序得到子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中；dneh
r1
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使最大完工时间最小的位置，直至子排序中的所有工件都插入到解中；dneh
r2
：随机产生一个子排序，依次提取子排序中的每个工件插入到所有可以插入的位置，选择能使该工件拖期时间最小的位置，直至子排序中的所有工件都插入到解中。8.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s6双差分混合策略，具体如下：对于pareto等级排序中前psize*70％个个体采用de/rand/1差分策略，其第l个目标个体的第g次迭代变异策略描述为如下：将变异策略拆分为两个部分：第一部分：第二部分：
与de/rand/1对应的交叉算子会结合变异个体v'
l,g
和目标个体生成实验个体交叉算子会从变异个体中提取一些工件后通过提出的工厂分配规则选择其中一个工厂插入到该工厂的最好位置，该交叉算子能够有更大的概率将提取出来的工件插入到最好的工厂中，这个过程循环执行h次选择最好的解；具体见如下：步骤一：提取变异个体中每个维度中第一个出现的工件放入v'中；步骤二：v'每个维度中的数值取舍由一随机数与交叉概率cr进行比较判断，若随机数大于等于交叉概率cr，则保留该数值，否则置为0，得到v”；步骤三：令实验个体＝目标个体移除中与v”相同的非0工件，依次将移除的工件插入到所选择的工厂中的所有可能位置，选择能使该工厂最大完工时间最小的位置，并保存该解；步骤四：判断是否达到h次循环，否则返回步骤二，是则从h个解中选择最好一个解并退出循环。9.根据权利要求1所述的一种分布式异构阻塞混合流水车间调度方法，其特征在于：所述步骤s7的基于问题特征的变邻域下降算法，具体的6种邻域结构如下n1：pareto拖期工件交换提取所有工件中具有最大拖期时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解；n2：pareto拖期工件插入提取所有工件中具有最大拖期时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解；n3：pareto最大完工时间插入提取具有最大完工时间工厂中的任一工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解；n4：pareto最大完工时间交换提取具有最大完工时间工厂中的任一工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解；n5：最大阻塞工件插入提取所有工件中具有最大阻塞时间的工件，依次将其插入到解序列中的所有可以插入的位置，保存所有解，从中选择pareto最优解；n6：最大阻塞工件交换提取所有工件中具有最大阻塞时间的工件，依次将其与解序列中的所有其余工件进行交换，保存所有解，从中选择pareto最优解。

技术总结
本发明公开了一种分布式异构阻塞混合流水车间调度方法，本发明的方法基于分布式异构阻塞混合流水车间的特点，构建以最小化最大完工花间和总拖期时间为多目标的分布式异构阻塞混合流水车间调度模型。提出pareto方法的多目标差分进化算法，对分布式异构阻塞混合流水车间调度模型进行求解。算法编码采用置换编码形式，引入了一类新的工厂分配规则，并根据求解目标设计了4种启发式算法，以提高初始种群的质量。为了更好地保证算法的多样性和收敛性，算法将两种差分策略混合设计。此外，依据问题特性设计了6种领域结构的变领域下降算法以增强算法的局部搜索能力。从而减小最大完工时间和总拖期时间，提高分布式混合流水车间的生产效率。产效率。产效率。


技术研发人员：郦仕云 杨孟平 裴植
受保护的技术使用者：浙江工业大学
技术研发日：2023.05.15
技术公布日：2023/8/23