一种分布式装配零等待流水车间调度问题的优化系统

摘要

本发明涉及制造生产调度领域和路径规划技术领域，具体涉及一种分布式装配零等待流水车间调度问题的优化系统，其包括初始调度工件序列生成模块、工厂内优化模块、工厂间优化模块和产品装配模块；其有益效果：本发明系统地分析了零等待流水车间调度问题中隐含的最优工件块知识，并将其拓展为一种新的块移动策略；本发明使用新的启发式方法来构造高质量的初始化调度序列，使得系统能够快速的搜索可行域；本发明逻辑简单、易于实现和扩展，本优化系统可以求解其他领域中的调度问题，如旅行商问题、车辆路规划问题等。

说明书

技术领域

本发明涉及制造生产调度领域和路径规划技术领域，具体涉及一种分布式装配零等待流水车间调度问题的优化系统。

背景技术

复杂制造系统是“智能制造”的核心和关键，具有不确定性、多约束、多目标、多资源相互协调等特点。复杂制造系统的理论研究涉及系统工程、人工智能、运筹学、计算机技术、控制理论等多门学科。鉴于其重要的应用价值和理论价值，复杂制造系统已然成为学术界和工业界的研究热点。生产调度是制造系统能够合理运行的关键环节，也是理论研究中最为重要的问题之一。德国汉诺威大学生产系统研究所对6个不同行业的企业所做的调查结果显示，在实际的生产过程中，零件的实际加工时间只占15％。而等待、搬运、排队的时间占85％。因此合理的调度策略和高效的优化方法是制造企业在生产过程中提高生产效率、经济效益和市场竞争力的重要手段。

调度本质是一个集成决策的过程。调度问题研究的是在满足一定技术和资源的情况下，针对某项可以分解的任务，按照一定的约束条件合理地为每部分任务分配资源，最终使得所求性能指标最优。已有研究表明，绝大多数调度问题属于NP-hard问题。因此，对调度问题的研究具有重要的学术意义和工程价值。调度问题存在着诸多的复杂性，例如建模难(数学模型和仿真模型难以建立或建立不准确)、维数灾难问题(随着问题规模的扩大解空间可能会呈现指数级增长的趋势)、约束复杂(存在着人力、物力、工艺、效益等多种约束)、随机性(加工过程中存在着诸多不确定因素)等。由于以上的局限性，传统的方法已不再适用于求解大规模调度问题。

因此，寻求一种不依赖于具体问题的高效调度优化算法已是大势所趋。元启发式算法是近年来出现的一类新兴优化算法，它以简单的算法结构、独特的求解思路、较低的问题耦合度被广泛应用于调度领域，逐渐成为学术界的研究热点。

发明内容

本发明为了克服现有算法在解决分布式装配零等待流水车间调度问题(DANWFSP)时存在的无法满足质量的问题，提供了一种分布式装配零等待流水车间调度问题的优化系统。

为实现上述目的，本发明提供如下技术方案：

一种分布式装配零等待流水车间调度问题的优化系统，其特征在于，包括初始调度工件序列生成模块、工厂内优化模块、工厂间优化模块和产品装配模块；

所述初始调度工件序列生成模块包括是工件序列构造模块、产品序列构造模块和工件分配模块；

所述工厂内优化模块利用块移动策略来在各个生产工厂内对工件序列进行优化调整，基于最优工件块的块移动策略保证了父代候选解中的最优信息成功继承到子代候选解中；

所述工厂间优化模块利用变邻域下降算法来对关键工厂和其它工厂的工件序列进行优化调整，该变邻域下降算法包含两种邻域结构，一种是关键工厂和非关键工厂间工件的交换结构，另一种是关键工厂和非关键工厂间工件的插入结构；

所述产品装配模块利用优化后的调度工件序列计算出每个产品的放行时间R

进一步的，在初始调度工件序列生成模块中，

首先，得到每个工件在各个机器上的加工时间，然后得到组成每个产品的工件，利用NEH启发式为每个产品构造一个工件序列P

进一步的，在初始调度工件序列生成模块中，基于产品装配时间最小化原则的构造启发式方法被用来产生一个初始调度工件序列，该工件序列用于表示各个生产工厂中的工件分配情况，以及工件在生产机器上的加工路径。

进一步的，在工厂内优化模块中，基于最优工件块的块移动作为一种保优策略在算法的迭代过程中动态的调整初始调度工件序列，获得第二调度序列，该块移动操作将当前候选解中的最优子序列传承到下一代候选解中，使得候选解始终保持着较好的进化能力。

进一步的，在工厂间优化模块中的交换结构中，关键工厂中的所有工件与其他工厂中的工件进行交换，直至找到一个最优的工件序列。

进一步的，在工厂间优化模块中的插入结构中，关键工厂中的所有工件被依次取出并重新插入到其他工厂中，直至找到一个最优的工件序列。

一种计算机可读存储介质，其中包含计算机程序，该程序被CPU处理时可实现一种分布式装配零等待流水车间调度问题的优化系统所提供的方法步骤。

本发明具有以下有益效果：

(1)本发明系统地分析了零等待流水车间调度问题中隐含的最优工件块知识，并将其拓展为一种新的块移动策略。

(2)本发明使用新的启发式方法来构造高质量的初始化调度序列，使得系统能够快速的搜索可行域。

(3)本发明逻辑简单、易于实现和扩展，本优化系统可以求解其他领域中的调度问题，如旅行商问题、车辆路规划问题等。

附图说明

附图用来提供对本发明的进一步理解，并构成说明书的一部分，与本发明的实施例一起用于解释本发明，并不构成对本发明的限制。在附图中：

图1是本发明中分布式装配零等待流水车间调度问题的优化系统的结构示意图；

图2是分布式装配流水车间示意图；

图3是本发明中初始调度工件序列生成模块提供的构造启发式的示意图；

图4是本发明中基于最优工件块的块移动示意图；

图5是本发明系统与其他系统的对比图。

具体实施方式

为了更清楚地说明本发明的目的、技术方案及优点，以下结合附图具体的解释每个模块的功能及优点。

实施例1：

一种分布式装配零等待流水车间调度问题的优化系统，如图1所示，包括初始调度工件序列生成模块、工厂内优化模块、工厂间优化模块和产品装配模块；

所述初始调度工件序列生成模块包括是工件序列构造模块、产品序列构造模块和工件分配模块；

所述工厂内优化模块利用块移动策略来在各个生产工厂内对工件序列进行优化调整，基于最优工件块的块移动策略保证了父代候选解中的最优信息成功继承到子代候选解中；

所述工厂间优化模块利用变邻域下降算法来对关键工厂和其它工厂的工件序列进行优化调整，该变邻域下降算法包含两种邻域结构，一种是关键工厂和非关键工厂间工件的交换结构，另一种是关键工厂和非关键工厂间工件的插入结构；

所述产品装配模块利用优化后的调度工件序列计算出每个产品的放行时间R

进一步的，在初始调度工件序列生成模块中，

首先，得到每个工件在各个机器上的加工时间，然后得到组成每个产品的工件，利用NEH启发式为每个产品构造一个工件序列P

进一步的，在初始调度工件序列生成模块中，基于产品装配时间最小化原则的构造启发式方法被用来产生一个初始调度工件序列，该工件序列用于表示各个生产工厂中的工件分配情况，以及工件在生产机器上的加工路径。

进一步的，在工厂内优化模块中，基于最优工件块的块移动作为一种保优策略在算法的迭代过程中动态的调整初始调度工件序列，获得第二调度序列，该块移动操作将当前候选解中的最优子序列传承到下一代候选解中，使得候选解始终保持着较好的进化能力。

进一步的，在工厂间优化模块中的交换结构中，关键工厂中的所有工件与其他工厂中的工件进行交换，直至找到一个最优的工件序列。

进一步的，在工厂间优化模块中的插入结构中，关键工厂中的所有工件被依次取出并重新插入到其他工厂中，直至找到一个最优的工件序列。

一种计算机可读存储介质，其中包含计算机程序，该程序被CPU处理时可实现一种分布式装配零等待流水车间调度问题的优化系统所提供的方法步骤。

实施例2：

图2是分布式装配流水车间示意图。如图所示，分布式装配流车间调度问题(DAFSP)是将分布式流水车间生产的工件在装配工厂内组装成产品的过程。DAFSP分为两个阶段。生产阶段是在生产工厂生产构成产品的所有工件。生产阶段描述如下。n个工件{J

装配阶段是对加工阶段产生的n个工件在装配工厂中组装成产品的过程。在装配工厂中只有一台机器M

实施例3：

图3是初始调度工件序列生成模块提供的构造启发式的示意图((a)代表工件4被分配到工厂1的第1个位置的图，(b)代表工件4被分配到工厂1的第2个位置的图，(c)代表工件4被分配到工厂1的第3个位置的图，(d)代表工件4被分配到工厂2的第1个位置的图,(e)代表工件4被分配到工厂2的第2个位置的图)。

构造启发式利用NEH为每个产品构造一个工件序列P

步骤1:根据ENH启发式，将构成每个产品的工件构造成一个工件序列。

步骤2:利用每个产品的R′

步骤3:利用每个产品的C′

步骤4:将π

为了说明构造启发式的具体实施步骤，接下来采用一个5工件、2个生产工厂、2个产品和2台机器的例子进一步解释其原理。

步骤1:利用NEH启发式算法对组成P

步骤2:利用P

步骤3:利用P

步骤4:将π

根据NR

图3是根据NR

步骤5:重复步骤4中的操作，直至π

实施例4：

图4是工厂内优化模块提供的基于最优工件块的块移动示意图。零等待流水车间调度问题中，同一工件的相邻的两道工序之间没有等待时间。因此，可以将同一工件的所有工序拼接成一个整体，计算相邻两个工件之间的完工时间差D

以图4为例，工件序列为{J

实施例5:

为了分析该系统的有效性，将本文发明的系统与其他几种系统做了对比。所选对比系统为：BR-ILS(D.Ferone,S.Hatami,E.M.Gonzalez-Neira,A.A.Juan,P.Festa,Abiased-randomized iterated local search for the distributed assemblypermutation flow-shop problem,International Transactions in OperationalResearch,27(2020)1368-1391.)，IG(Q.-K.Pan,L.Gao,X.-Y.Li,F.M.Jose,Effectiveconstructive heuristics and meta-heuristics for the distributed assemblypermutation flowshop scheduling problem,Applied Soft Computing,81(2019).)，ILS(W.Shao,D.Pi,Z.Shao,Local Search Methods for a Distributed Assembly No-IdleFlow Shop Scheduling Problem,Ieee Systems Journal,13(2019)1945-1956.)。

图5是本发明系统与其他系统的对比图((a)代表时间系数＝10的情况，(b)代表时间系数＝20的情况，(c)代表时间系数＝30的情况)，由对比结果可知BKBSA系统在不同的CPU时间下所得的结果均优于其他几种系统。因为BKBSA由问题的特性出发，针对不同的阶段设计了不同的优化子系统，各个子系统间分工协作共同保证了所得解的质量。

以上内容介绍了本发明实例的基本原理、主要特征与优点。相关从业人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的只是说明本发明的原理。本发明可以应用到其他任何具有调度性质的的领域中。本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。