一种用于分布式装配混合零空闲置换流水线的集成调度方法

1.本发明涉及制造业分布式生产调度技术领域，特别涉及一种用于分布式装配混合零空闲置换流水线的集成调度方法。


背景技术：

2.在全球化背景下，企业为了提高生产效率和产品多样性，逐渐采用智能化生产系统。分布式制造是一种常见的、具有特殊优势的智能生产模式，企业往往在不同地理位置建立多个工厂进行协同生产制造，利用工厂间的信息共享、及时交流对有限的资源进行优化组合、合理配置，从而快速完成产品的生产加工。如今全球企业集团化趋势日趋明显，多层级、多元化的大型企业如雨后春笋般涌现，分布式制造生产管理模式正在兴起，分布式制造系统更具有灵活性和可控性，信息收集更全面，资源整合更加灵活高效。这种兴新的制造模式不仅可以实现资源高效利用，而且可以构建更稳健的多企业协同运作环境。
3.分布式流水车间是一种经典的分布式制造系统，近年来，以分布式制造为背景的分布式流水车间调度(distributed flow-shop scheduling problem，dfsp)得到了广泛的研究。它考虑工件在不同工厂之间的合理分配及在工厂内机器上的加工顺序，帮助企业完成指定目标的最优化。通过对分布式流水车间高效的调度，合理分工与协作，制定科学的生产计划，有利于企业以低成本、低风险的方式生产出高质量的产品。因此，为了充分利用分布式流水车间的优势，提高企业竞争力，分布式流水车间被众多企业采用以提高生产制造效率，如石油化工行业、电子通讯行业及机械制造行业等。
4.生产调度是制造系统中至关重要的连接组件。总的来说，调度是解决机器状态问题的有效途径，是决定执行哪些任务、何时执行、在何处以何种顺序处理这些任务的重要决策过程。它很少被认为是提高能源效率的合适工具。近年来，许多研究人员使用调度方法来提高制造业的能源效率，节能调度已被证明是一种无需或只需少量资本投资即可降低能源消耗的有效途径。
5.生产调度已被证明是一个np难问题，因此，能效调度也不例外。传统的优化方法不能高效地解决大规模调度问题，特别是对于一些具有实时约束的大规模实例。因此，群体智能和进化算法被用于解决此类问题，因为低计算时间和高效率是最重要的标准。对于具有实时约束的大规模情境，群体智能和进化算法可以在极短的计算时间内获得高质量的可行解。群体智能和进化算法在解决具有时间约束的大规模调度和优化问题(包括复杂生产中的能效调度)方面越来越受欢迎。智能调度策略的设计应考虑能源效率和降低能源消耗，这是当前生产调度领域的一个重要调度目标。生产调度作为制造系统的关键组成部分，通过合理确定加工路径、机器分配、执行时间等主要因素，实现利润、效率、能耗等方面的优化目标。由于大规模、强耦合约束的性质，以及某些场景下的实时求解要求，制造调度问题的求解面临着巨大的挑战。
6.为了提高生产效率和效果，调度算法发挥着重要作用，一直是工业工程、自动化、管理科学等交叉学科领域的重要研究课题。生产调度算法主要包括三大类，精确算法、启发
式算法和元启发式算法。精确算法在理论上可以保证获得最优解，但由于np难的性质，很难高效地解决大规模问题。启发式采用一些规则来有效地构建调度解，但不具备全局优化的能力。此外，规则的设计高度依赖于对问题具体特征的深刻理解。元启发式可以在可接受的计算时间内获得优秀的调度解，但搜索算子的设计严重依赖于问题。同时，对于大规模问题，迭代搜索过程非常耗时，难以应用于实时场景。
7.分布式车间调度问题是以不同工厂之间的合作生产或不同工厂之间协作生产等分布式制造为背景，研究工件在工厂间的分配和各工厂内的加工顺序，以实现调度指标最优化。分布式流水车间调度问题属于np-hard问题之一，求解难度很大。分布式车间调度问题在传统的单车间车间调度问题中，多了一个工厂分配环节。如图1所示，单工厂流水车间调度模型中，只有一个加工工厂，待加工工件全部进入该工厂进行加工，加工完成后组成成品。在分布式流水车间调度模型中，存在多个工厂，首先对待加工工件进行分配，保证每个工厂至少加工一个工件，工厂分配结束后，工件再在工厂内部进行排序，当所有工厂中的工件都加工结束后，整个制造过程完成。分布式装配流水车间调度问题是从dfsp演变而来(不仅有分布式工厂约束，还具有装配约束)，需要同时考虑工厂分配、工件的工序和产品的组装三个高度耦合的子问题，其求解难度更高。分布式装配流水车间调度示意图如图2所示。分布式装配混合零空闲置换流水车间调度甘特图如图3所示，在该问题中，工厂中不仅有常规的置换机器还有零空闲机器，二者以一定的比例混合。
8.分布估计算法(estimation of distribution algorithm，eda)作为一种进化算法，其特点在于其产生后代的方式，即基于概率分布采样生成子代解，而不是如其他种类的进化算法，通过交叉和变异算子产生新解。eda采用基于搜索空间的宏观层面的进化方法，具备更强的全局搜索能力和更快的收敛速度。在过去的几十年中，eda已广泛应用于组合优化和连续优化领域。eda有多种概率模型，例如高斯模型、柯西模型和直方图模型，来描述高质量解的分布。高斯型eda(gaussian eda，geda)通常根据变量依赖性分为三类，1)假设所有变量为相互独立的单变量eda；2)仅存在一些成对变量相互作用的双变量eda；以及3)存在多个变量之间相互作用的多变量eda。eda的性能不仅取决于它的搜索范围，还取决于搜索的方向。eda的主搜索方向倾向于与适应度函数的改进方向正交。eda算法用于多种工程优化问题的求解，求解过程简单，使用eda算法求解分布式装配混合零空闲置换流水车间调度问题具有一定的研究基础和优势。


技术实现要素：

9.本发明的目的在于针对现有技术中存在的问题，提供一种用于分布式装配混合零空闲置换流水线的集成调度方法，以最小化最大完工时间为目标，解决分布式装配混合零空闲置换流水车间调度问题。
10.为了实现上述目的，本发明提供以下技术方案：
11.一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于，包括如下步骤：
12.步骤一、调度序列初始化模块；首先，将待加工工件随机分配到个各子工厂中，并保证每个工厂至少分配到一个工件；接着，依次使用低级启发式方法对每个工厂中的工件进行排序；最后，根据排好的序列生成一定数量的个体，组成一个种群，在后续的工作中，对
种群中的个体进行操作；
13.步骤二、操作的概率模型自学习策略模块；在本模块中，设计了一种基于概率模型的增量学习策略，将低级启发式序列总结为知识，用于指导进行自学习的选择操作算子；
14.步骤三、破坏和重构策略模块；在本模块中，设计了分别针对产品和工件的破坏和重构操作，以实现进一步缩短工件完工时间的目的。
15.优选的，在步骤一中，根据随机初始化的序列生成多个个体，组成一个种群，在生成多个个体的时候，采用种群生成策略，既保存了个体中优秀的子序列模块，又增加种群的多样性；使系统在求解分布式装配混合零空闲置换流水车间调度问题时能够获得更高精度的结果。
16.优选的，在步骤二中，根据步骤一生成的工件加工种群序列，概率模型以增量学习的方式学习低级启发式序列，调整序列排列，寻找更优的工件加工排列顺序。
17.具体的，对工件序列进行随机初始化，并将低级启发式依次作用于工件序列，使用该方法生成种群，通过截断选择选择出种群中具有优势的个体，构建概率矩阵。
18.具体的，提出了十种低级启发式规则，并将低级启发式序列总结为知识，通过概率矩阵以增量学习的方式指导算法进行自学习的操作选择。
19.具体的，所述十种低级启发式规则包括：
20.(1)随机选择两个不同的产品并交换它们的位置，属于同一产品的工件之间的相对位置保持不变；
21.(2)随机选择两个不同的产品，将前者置于后者之后，属于同一产品的工件之间的相对位置保持不变；
22.(3)随机选择两个不同的产品，将后者置于前者之前，属于同一产品的工件之间的相对位置保持不变；
23.(4)在产品排列中随机选择两个位置，将产品倒序放置在两个位置之间，属于同一产品的工件之间的相对位置保持不变；
24.(5)在产品排列中随机选择两个相邻的位置并交换相应的产品，排列中第一个和最后一个位置视为相邻位置，属于同一产品的工件之间的相对位置保持不变；
25.(6)从排列中选择一个产品，并选择该产品的两个不同的工件，交换相应的工件；
26.(7)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将后一工件置于前一工件之前；
27.(8)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将前一工件置于后一工件之后；
28.(9)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将两个位置之间的工件逆序放置；
29.(10)从排列中随机选择一个产品，选择该产品相邻的两个工件，交换相应的工件。
30.优选的，在步骤三中，根据步骤一和步骤二产生的加工序列，使用破坏和重构策略，调整加工工件的加工序列，达到缩短完工时间的目的。
31.具体的，随机选择工厂中的一个工件，插入到同一产品的其他工件间的任意位置；随机选择工厂中的一件产品，插入到其他产品间的任意位置，属于同一产品的工件不被分隔。如图8所示。
32.本发明提供一种计算机可读存储介质，其中包含计算机程序，该程序被cpu处理时可实现上述所提供的方法步骤。
33.本发明具有以下有益效果：
34.(1)本发明定义了分布式装配混合零空闲置换流水车间调度问题的整数规划模型。
35.(2)使用分布估计算法作为高层控制策略，通过操作十种低级启发式规则，使得算法能够快速的搜索较好的区域。
36.(3)使用概率模型进行增量学习，将低级启发式序列总结为知识，指导算法进行自学习的操作选择，提升操作的成功率。
37.(4)本发明逻辑简单、易于实现和易于扩展，可以将优化器扩展到满足当前智能制造生产领域中的大多数调度问题中。
附图说明
38.图1是现有技术中单工厂车间调度和分布式车间调度问题对比图。
39.图2是现有技术中分布式装配流水车间调度示意图。
40.图3是现有技术中分布式装配混合零空闲置换流水车间调度甘特图。
41.图4是本发明实施例中的编码示意图。
42.图5是本发明实施例中的解码示意图。
43.图6是本发明实施例中的eda-hh执行流程图。
44.图7是本发明实施例中的概率矩阵更新示意图。
45.图8是本发明实施例中的破坏和重构策略示意图。
具体实施方式
46.为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
47.实施例一
48.eda-hh的执行过程如图6所示。
49.1)初始种群以随机方式形成，每个低级启发式在每个个体中只出现一次；
50.2)为确定一个解，低级启发式依次作用于解空间。利用低级启发式序列演化出的最佳解对每个个体进行评估，并对解进行解码以获得可行的调度序列来计算优化目标；
51.3)通过对个体进行排序，并采用截断选择获得优势子种群。优势低级启发式序列的信息用于构建概率模型，通过对概率模型进行采样获得子代种群；
52.4)将破坏和重构操作用于前一步骤提供的最佳，以获得更有潜力的邻域解。
[0053][0054]
解的表达方式至关重要。eda-hh的个体由解和低级启发式序列组成。低级启发式方法用于个体以在每次迭代中进行进化。为了求解damnipfsp，解的表达方式采用两级表示法。需要注意的是，在生产调度的两个阶段中，属于同一产品的工件紧密相连。图4中提供了一个示例来说明解的编码方案。为了确定将工厂中的任务分配，采用nr2作为解码规则。将工件j分配给在包含工件j后具有最小c
max
的工厂。解码方案的图5所示。然后可以将作业序列解码为可行的调度序列，并计算加工完成时间。
[0055]
eda与其他进化算法的区别在于，eda使用概率模型生成子代。本发明中的概率模型被构建为概率矩阵p，以获取低级启发式序列中隐含的信息。概率矩阵中的元素表示低级启发式j于第g代中出现在位置i或位置i之前的概率。的值表示某一低级启发式在确定低级启发式序列中的重要性。对于任意的i和j，设置为1/θ，这意味着整个低级启发式空间可以被均匀采样，θ为低级启发式的数量。
[0056]
在eda-hh进化的每一代，新个体均通过概率矩阵对低级启发式空间进行采样生成。对于每个位置i，低级启发式j被选择的概率为p
i,j
。若低级启发式j出现，则表示该低级启发式j之前已被使用。然后将概率矩阵p的第j列设置为零，并对p的所有元素进行归一化处理，以使得每一行概率值总和为1。通过以上方式构建低级启发式序列，直到所有低级启发式都被使用。此外，开发了概率更新机制以实现增量学习。概率矩阵p根据以下公式更新：
[0057][0058][0059]
其中α∈(0,1)为学习率，设置为0.5。ps'表示优势种群中个体的数量。更新概率矩阵的过程如图7所示。与其他通过交叉和变异算子迭代维护“积木块”的进化算法不同，eda的概率模型可以捕捉问题的结构特征，并通过隐式地利用来自优势种群的信息来进化下一代。概率模型被用于策略空间而不是解空间。这种统计学习机制用于学习有前途的策略，而
不是操作工件序列。
[0060]
低级启发式通常被认为是超启发式的重要组成部分。在相当大的程度上，超启发式算法能否获得有希望的结果取决于低级启发式算法的搜索能力。设计了十种低级启发式方法来构建llh集合，详细描述如下：
[0061]
(1)随机选择两个不同的产品并交换它们的位置，属于同一产品的工件之间的相对位置保持不变；
[0062]
(2)随机选择两个不同的产品，将前者置于后者之后，属于同一产品的工件之间的相对位置保持不变；
[0063]
(3)随机选择两个不同的产品，将后者置于前者之前，属于同一产品的工件之间的相对位置保持不变；
[0064]
(4)在产品排列中随机选择两个位置，将产品倒序放置在两个位置之间，属于同一产品的工件之间的相对位置保持不变；
[0065]
(5)在产品排列中随机选择两个相邻的位置并交换相应的产品，排列中第一个和最后一个位置视为相邻位置，属于同一产品的工件之间的相对位置保持不变；
[0066]
(6)从排列中选择一个产品，并选择该产品的两个不同的工件，交换相应的工件；
[0067]
(7)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将后一工件置于前一工件之前；
[0068]
(8)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将前一工件置于后一工件之后；
[0069]
(9)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将两个位置之间的工件逆序放置；
[0070]
(10)从排列中随机选择一个产品，选择该产品相邻的两个工件，交换相应的工件。
[0071][0072]
在进行与工件相关的llh之前，随机挑选一个产品且确保属于同一产品的工件在执行llh之后不会被拆分。此外，将模拟退火(sa)引入llh中以提高算法精搜索的能力。改进的llh如算法2所示。表示待处理的产品或工件序列。ξ为退火率。t0表示开始温度，tf表示
终止温度。
[0073]
damnipfsp的解有两种类型的破坏重构操作，即工件和产品的破坏与重构。产品和工件的破坏长度分别用d和dj表示。被移除的产品和工件必须重新插入以创建完整的产品排列和工件序列。属于同一产品的工件不被分隔，以最大限度地减少装配完成时间。属于同一产品的工件用相同的颜色表示，如图8所示。在破坏和重构阶段采用精英主义策略。破坏和重构操作只作用于当前最优解。该策略一方面可以改进当前最优值，另一方面可以节省部分计算资源。
[0074]
上仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于，包括如下步骤：步骤一、调度序列初始化模块；首先，将待加工工件随机分配到个各子工厂中，并保证每个工厂至少分配到一个工件；接着，依次使用低级启发式方法对每个工厂中的工件进行排序；最后，根据排好的序列生成一定数量的个体，组成一个种群，在后续的工作中，对种群中的个体进行操作；步骤二、操作的概率模型自学习策略模块；在本模块中，设计了一种基于概率模型的增量学习策略，将低级启发式序列总结为知识，用于指导进行自学习的选择操作算子；步骤三、破坏和重构策略模块；在本模块中，设计了分别针对产品和工件的破坏和重构操作，以实现进一步缩短工件完工时间的目的。2.根据权利要求1所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：在步骤一中，根据随机初始化的序列生成多个个体，组成一个种群，在生成多个个体的时候，采用种群生成策略，既保存了个体中优秀的子序列模块，又增加种群的多样性。3.根据权利要求1所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：在步骤二中，根据步骤一生成的工件加工种群序列，概率模型以增量学习的方式学习低级启发式序列，调整序列排列，寻找更优的工件加工排列顺序。4.根据权利要求3所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：对工件序列进行随机初始化，并将低级启发式依次作用于工件序列，使用该方法生成种群，通过截断选择选择出种群中具有优势的个体，构建概率矩阵。5.根据权利要求4所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：提出了十种低级启发式规则，并将低级启发式序列总结为知识，通过概率矩阵以增量学习的方式指导算法进行自学习的操作选择。6.根据权利要求5所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：所述的十种低级启发式规则包括：(1)随机选择两个不同的产品并交换它们的位置，属于同一产品的工件之间的相对位置保持不变；(2)随机选择两个不同的产品，将前者置于后者之后，属于同一产品的工件之间的相对位置保持不变；(3)随机选择两个不同的产品，将后者置于前者之前，属于同一产品的工件之间的相对位置保持不变；(4)在产品排列中随机选择两个位置，将产品倒序放置在两个位置之间，属于同一产品的工件之间的相对位置保持不变；(5)在产品排列中随机选择两个相邻的位置并交换相应的产品，排列中第一个和最后一个位置视为相邻位置，属于同一产品的工件之间的相对位置保持不变；(6)从排列中选择一个产品，并选择该产品的两个不同的工件，交换相应的工件；(7)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将后一工件置于前一工件之前；(8)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将前一工件置于后
一工件之后；(9)从排列中随机选择一个产品，并选择该产品的两个不同的工件，将两个位置之间的工件逆序放置；(10)从排列中随机选择一个产品，选择该产品相邻的两个工件，交换相应的工件。7.根据权利要求3所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：在步骤三中，根据步骤一和步骤二产生的加工序列，使用破坏和重构策略，调整加工工件的加工序列，达到缩短完工时间的目的。8.根据权利要求7所述的一种用于分布式装配混合零空闲置换流水线的集成调度方法，其特征在于：随机选择工厂中的一个工件，插入到同一产品的其他工件间的任意位置；随机选择工厂中的一件产品，插入到其他产品间的任意位置，属于同一产品的工件不被分隔。9.一种计算机可读存储介质，其中包含计算机程序，该程序被cpu处理时可实现权利要求1-8任一项所提供的方法步骤。

技术总结
本发明涉及制造业分布式生产调度技术领域，特别涉及一种用于分布式装配混合零空闲置换流水线的集成调度方法，包括如下步骤：步骤一、调度序列初始化模块；将待加工工件随机分配到个各子工厂中，并保证每个工厂至少分配到一个工件；依次使用低级启发式方法对每个工厂中的工件进行排序；根据排好的序列生成一定数量的个体，组成一个种群，在后续的工作中，对种群中的个体进行操作；步骤二、操作的概率模型自学习策略模块；设计了一种基于概率模型的增量学习策略，将低级启发式序列总结为知识，用于指导进行自学习的选择操作算子；步骤三、破坏和重构策略模块；设计了分别针对产品和工件的破坏和重构操作，以实现进一步缩短工件完工时间的目的。时间的目的。时间的目的。


技术研发人员：赵付青 朱波 唐建新 张建林 朱宁宁 许天鹏
受保护的技术使用者：兰州理工大学
技术研发日：2023.06.26
技术公布日：2023/8/31