基于分布式异构流水车间组调度问题的求解方法

专利主权项内容

1.一种基于分布式异构流水车间组调度问题的求解方法，其特征在于，包括以下步骤，S1、分析在PCB生产制造中分布式异构流水车间组调度问题的问题特性，确定以最小化总延迟时间为问题求解目标，并初始化参数，包括种群大小PS，当前邻域结构连续更新最大失败数Nmax，种群重启连续更新最大失败数R；S2、初始化种群，使用构造式启发式算法生成种群中的第一个个体；在第一个个体的基础上经过扰动策略的扰动，生成PS/2个个体；随机生成剩余的种群中的个体，选择其中目标值最小的个体作为最优解决方案；S3、雇佣蜂阶段，对种群中的个体使用具有6个邻域结构的可变邻域下降搜索策略，接受目标值比原个体更小的个体作为新个体；S4、旁观蜂阶段，对种群中的个体使用改进的具有6个邻域结构的可变邻域下降深度搜索策略，结合涉及族和工件两个层面的协作策略，接受目标值比原个体更小的个体作为新个体；S5、侦察蜂阶段，判断是否需要进行种群重启，是则随机移除一半种群的个体，并使用随机策略结合扰动策略生成的个体代替移除的种群中的个体；S6、更新最优解决方案，判断是否满足终止条件，是则输出当前在PCB生产制造中分布式异构流水车间组调度问题的最优解决方案，包括族中工件的加工序列，族在生产单元的分配和生产单元中族的加工序列，否则返回S3；其中，一个完整的个体定义为 ，其中，/>，代表每个族内的工件加工序列，/>代表一个族，/>代表族的数量，/>表示相应族/>的工件序列，/>，代表族/>中的一个工件， />表示族 />中的工件数，/>表示族 />中的第/>个工件；，代表每个生产单元中族的加工序列，/>代表一个生产单元，/>是生产单元的数量，/>表示对应生产单元/>中的族加工序列，/> ，/>代表生产单元 />中的一个族，/>表示生产单元/>中分配的族的数量，/>表示生产单元 />中的第/>个族；构造式启发式算法的实现过程包括以下步骤，(1)定义以下参数，代表一个族，/>代表族的集合，/> ， />代表族的数量， />表示族 />中工件的集合，/>，/>表示族/>中的工件数，/>代表族 />中的一个工件，/>代表生产单元的集合，/> ，/>是生产单元的数量，/>代表一个生产单元，/>代表机器的集合，/> ，/>是机器的数量， />代表某一个机器，/>代表族/>中工件 />在生产单元 />上的机器/>上的加工时间，/>代表族 />中工件 />在生产单元 />上的机器 />上的加工时间；(2)计算每台机器上一个工件与所有其他工件的处理时间的绝对差异之和，即计算族中每个工件的指标值，计算公式为，
，其中，代表计算族/>中工件/>的指标值；(3)族中每个工件的指标值的降序排序，并对应族内的工件进行降序排序，从而得到每个族中的工件序列；(4)采用最早可用时间规则选择要分配族的生产单元；(5)将最小总体空闲时间规则应用于族序列，选择已经确定的生产单元上需要进行处理的族，空闲时间是指族的最小完成时间和预期完成时间的时间差，最小总体空闲时间规则计算公式如下，
，其中， 代表族 />的最小总体空闲时间，/>代表族 />的预期完成时间；(6)采用局部搜索规则改进分配到生产单元的族内的工件序列，具体步骤如下，步骤1，选择每个族中的前两个工件，然后从两个部分序列中选择目标值较小的作为当前部分序列；步骤2，从第三个工件作业开始，重复以下步骤直到最后一个工件作业；在当前部分序列中的所有可能位置插入所选作业；选择插入作业后目标值最小的部分序列作为新的当前部分序列；对当前部分序列通过局部搜索方法进行搜索，得到改进的部分序列，局部搜索方法通过允许分配给部分序列的所有工件，在每次迭代结束时检查所有其他位置来改变其各自的位置来提高个体的质量；(7)返回到步骤(4)，直到所有族调度完成为止；扰动策略实现过程包括，首先从选定的个体中的 中随机移除一半的族，然后为每个生产单元初始化一个种子序列，每个生产单元的种子序列包含所有移除的族，根据族在不同生产单元中的加工信息，通过总加工时间降序排列处理得到，分别对每个生产单元的种子序列中的第一个族进行评估，评估方式为，将第一个族插入到原个体中的 />的某个生产单元的某位置，计算目标值并记录族、生产单元、插入的位置和目标值，然后移出，重复上述评估方式将第一个族在所有生产单元中的所有位置进行评估，每个生产单元的种子序列中的第一个族全部评估完成后，选择导致最低目标值的族插入对应的生产单元以及生产单元中的位置，然后从所有生产单元的种子序列中将所插入的族移除，确定每个生产单元的种子序列中的新的第一个族，重复上述过程，直到种子序列为空为止；雇佣蜂阶段采用了具有6种邻域结构的可变邻域下降搜索策略对种群中的个体进行优化，为每个个体生成多个通过邻域结构改进的个体，接受目标值比原个体更小的改进个体作为新个体，其中，族层面采用了四种邻域结构，包括，涉及生产单元之间的族交换，选定两个不同的生产单元，之后分别从两个生产单元中选定一个族，进行交换；生产单元间的族插入，选定两个不同的生产单元，之后从一个生产单元中选定一个族，再从另外一个生产单元中选定一个位置，将选定的族插入选定的位置，并将选定的族从原生产单元移除；生产单元内族交换，选定一个生产单元，从这个生产单元中选定两个不同的族，进行交换；生产单元内族插入，选定一个生产单元，从这个生产单元中选定一个位置的族，再从这个生产单元中选定一个不同的位置，将选定的族插入到选定的位置，并将选定的族从原位置移除；工件层面采用了两种邻域结构，包括，族内工件交换，选定一个族，从这个族中选定两个不同的工件，进行交换；族内工件插入，选定一个族，从这个族中选定一个位置的工件，再从这个族中选定一个不同的位置，将选定的工件插入到选定的位置，并将选定的工件从原位置移除；可变邻域下降搜索策略实现过程包括，在对种群中的个体进行邻域搜索时，将第一种邻域结构作为当前邻域结构，并将当前邻域结构连续更新失败数设为零，若使用当前邻域结构进行搜索获得比原个体目标值更小的新个体，则对原个体进行更新，用新个体代替原个体，并且将当前邻域结构连续更新失败数重置为零，并继续使用当前邻域结构进行搜索；若没有获得比原个体目标值更小的新个体，则将当前邻域结构连续更新失败数加一，并继续使用当前邻域结构进行搜索，在当前邻域结构连续更新失败数达到当前邻域结构连续更新最大失败数时，将下一种邻域结构作为当前邻域结构，并将当前邻域结构连续更新失败数设为零，重复上述过程，当所有邻域结构都无法对当前个体进行更新时，则切换到下一个个体；旁观蜂阶段采用改进的具有6种邻域结构的可变邻域下降深度搜索策略对种群中的个体进行深度搜索，得到一个改进的个体，再通过与当前的最优解决方案进行协作，得到一个新的改进个体，接受目标值比原个体更小的改进个体作为新个体，其中，族层面采用了四种邻域结构，包括，涉及生产单元之间的族交换，选定两个不同的生产单元，之后分别从两个生产单元中选定一个族，进行交换；生产单元间的族插入，选定两个不同的生产单元，之后从一个生产单元中选定一个族，再从另外一个生产单元中选定一个位置，将选定的族插入选定的位置，并将选定的族从原生产单元移除；生产单元内族交换，选定一个生产单元，从这个生产单元中选定两个不同的族，进行交换；生产单元内族插入，选定一个生产单元，从这个生产单元中选定一个位置的族，再从这个生产单元中选定一个不同的位置，将选定的族插入到选定的位置，并将选定的族从原位置移除；工件层面采用了两种邻域结构，包括，族内工件交换，选定一个族，从这个族中选定两个不同的工件，进行交换；族内工件插入，选定一个族，从这个族中选定一个位置的工件，再从这个族中选定一个不同的位置，将选定的工件插入到选定的位置，并将选定的工件从原位置移除；改进的可变邻域下降深度搜索策略实现过程包括，在对种群中的个体进行邻域搜索时，将第一种邻域结构作为当前邻域结构，并将当前邻域结构连续更新失败数设为零，若使用当前邻域结构进行搜索获得比原个体目标值更小的新个体，则对原个体进行更新，用新个体代替原个体，并且将当前邻域结构连续更新失败数重置为零，并继续使用当前邻域结构进行搜索；若没有获得比原个体目标值更小的新个体，则将当前邻域结构连续更新失败数加一，并继续使用当前邻域结构进行搜索，在当前邻域结构连续更新失败数达到当前邻域结构连续更新最大失败数时，需要判断当前个体与原个体相比是否通过当前邻域结构进行了更新，若是则将当前邻域结构重置为第一邻域结构，否则将下一种邻域结构作为当前邻域结构，判断完成后将当前邻域结构连续更新失败数设为零，重复上述过程，当所有邻域结构都无法对当前个体进行更新时，对当前个体与当前的最优解决方案执行协作策略；协作策略包括工件层面和族层面，在工件层面，对两个个体的相应族中工件序列执行两点交叉策略，生成新的工件序列；在族层面，将两个个体中分配到相同生产单元的族保留，并应用简单的迭代贪婪运算来优化这些族的序列，对未分配到相同生产单元的族移除，然后分别计算各个族在所有生产单元的总处理时间，进行降序排序，按照顺序，选择具有最小总延迟时间的生产单元，从该生产单元中选择导致最小总延迟时间的位置进行插入，重复此过程，直到插入所有移除的族为止；在当前最优解决方案的连续更新失败次数达到重启连续更新最大失败数时，触发重新启动策略，具体方法为从当前种群中随机移除一半的种群个体，然后通过对随机生成的个体结合扰动策略来替换种群中被移除的一半个体。