基于改进交叉熵算法的多目标柔性作业车间调度方法

摘要

本发明针对现阶段求解多目标柔性作业车间调度问题存在的问题，提出了一种基于改进交叉熵算法的多目标柔性作业车间调度方法，包括步骤：初始化迭代次数M和策略切换阈值n_switch，初始化种群P、工序概率分布矩阵、机器概率分布矩阵与外部记忆库E，根据工序搜索算子与机器搜索算子得到新种群，对于具有相同目标向量的个体使用突变算子进行去重，采用基于SPEA2的环境选择算子筛选优良个体，采用种群P更新外部记忆库E；采用层次化多目标邻域搜索对种群P与外部记忆库E进行搜索优化，迭代M次；对外部记忆库E使用非支配排序得到最终的非支配解集。本发明可有效求解相关非支配解集，同时具有较好的多样性与收敛性。

说明书

技术领域

本发明属于多目标柔性作业车间调度技术领域，尤其涉及一种基于改进交叉熵算法的多目标柔性作业车间调度方法。

背景技术

船舶制造业作为国家综合国力的体现之一，关乎到国计民生、国家安全和民族复兴，与此同时，船舶制造业也是技术密集型和劳动密集型企业的代表，属于大型装备制造行业。随着国家对船舶制造的逐渐重视，到目前为止已经建立起强大而全面的船舶与海工装备制造体系，推动了国家的海洋发展和海洋运输等方面的发展。

作业车间制造作为船舶企业生产的基础之一，其相关发展及智能数字化水平密切影响项目的整体成本以及推进进度。但是目前国内车间智能制造管理层面对作业车间的整体排产规划较为欠缺，相对国际水平还是较为落后。此外船厂车间层级的相关顶层设计还不够完善，车间与项目之间的底层逻辑尚未打通。所以，在当前全球疫情反复而导致船舶市场低迷的情况下，船舶制造企业亟待加快车间的智能制造化，更深入地推进企业产信融合、提高全球竞争力。

通过对国内主要船舶制造厂进行调研并分析发现，国内船舶制造企业与发达国家的造船行业存在较大差距，车间级的信息化程度不高，按照每天、每周等定期生产进度来临时决定后续生产计划，并且车间通过文件的形式来接收上级进度安排，存在生产计划接收不及时的问题；对车间的场地、设备及班组等资源不能有效利用，难以合理安排生产加工计划。

柔性车间调度问题是船舶制造过程的一种抽象描述，对于单目标柔性车间调度问题主要集中在算法的创新与改进上来得到更优的结果，而对于多目标柔性车间调度问题，大部分研究集中在最晚完工时间、机器总负载和机器最大负载三个目标上，也有研究考虑了生产成本与能量损耗，最后对于动态柔性车间调度问题，预测反应时调度是当前的研究热点，主要考虑了生产效率与稳定性两个方面，对生产成本与能量消耗的考虑较少，存在多样性与收敛性不好、求解不准确的问题。

发明内容

本发明的目的在于提供一种基于改进交叉熵算法的多目标柔性作业车间调度方法，可以准确求解多目标柔性作业车间调度问题，且具有较好的收敛性、种群多样性与健壮性。

实现本发明目的的技术方案为：一种基于改进交叉熵算法的多目标柔性作业车间调度方法，包括步骤：

步骤1，初始化迭代次数M和策略切换阈值n_switch，初始化种群P、工序概率分布矩阵S、机器概率分布矩阵Q与外部记忆库E，采用交叉熵算法搜索，根据工序搜索算子与机器搜索算子得到新种群H，对于具有相同目标向量的个体使用突变算子进行去重，采用基于SPEA2的环境选择算子筛选优良个体，采用种群P更新外部记忆库E；

步骤2，采用层次化多目标邻域搜索对种群P与外部记忆库E进行搜索优化，迭代M次；

步骤3，对外部记忆库E使用非支配排序得到最终的非支配解集。

本发明与现有技术相比，其显著效果为：本发明使用协同进化策略对交叉熵算法进行改进，解决了朴素交叉熵算法局部搜索能力不足的问题，采用层次化多目标邻域搜索策略，使用随机权重的方式作为邻域搜索时解的替换条件，在保证算法一定收敛性的前提下，增强种群的多样性；本发明具有较好的优越性与健壮性，并且可以有效求得相应问题的优质解。

附图说明

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

图1为本实施方式中改进交叉熵算法的流程图。

图2为本实施方式中用例Mk07优质解甘特图。

图3为本实施方式中用例Mk10优质解甘特图。

图4为本实施方式中析取图模型与对应的甘特图。

具体实施方式

对于多目标柔性作业车间调度问题的求解，通常使用基于交叉、变异等算子的遗传算法进行求解，由于该算子的搜索的盲目性，本发明采用了交叉熵算法进行求解，交叉熵算法属于一种分布估计算法，通过维护一个概率模型，然后对其采样来得到新解。然而朴素的交叉熵算法使用概率模型进行全局搜索，相应的局部搜索能力较弱，最终得到的结果存在进一步优化空间，因此本发明提出了一种基于改进交叉熵算法的多目标柔性作业车间调度方法，这种方法不仅可以有效求解相关非支配解集，同时多样性与收敛性在某些情况下明显优于一些最新算法。本发明所提出的层次化多目标邻域搜索主要解决了两个关键问题：其一，朴素交叉熵算法的局部搜索能力不足；其二，在邻域搜索时对多个目标的考虑。发明主要包括：根据交叉熵算法局部搜索能力不足的问题，使用协同进化策略对其进行改进。对于多目标柔性作业车间调度问题需要考虑多个目标的优化的问题：同时提出一种层次化多目标邻域搜索策略，使用随机权重的方式作为邻域搜索时解的替换条件，在保证算法一定收敛性的前提下，增强种群的多样性。

本发明采用协同进化策略对朴素的交叉熵算法进行改进，当持续若干代算法无法得到更优的解时，采用工序搜索算子与机器搜索算子对其进行局部搜索，接着使用层次化多目标邻域搜索进一步优化，当持续若干代仍然无法得到更优的解时，则重新使用概率模型进行全局搜索。

层次化多目标邻域搜索是为了解决多目标柔性作业车间调度下，局部搜索时需要考虑多个目标优化的问题，与单目标柔性作业车间调度不同，优化时只需要考虑最晚完工时间，多目标问题需要额外考虑最大机器负载与机器总负载。层次化多目标邻域搜索主要分别面向多目标的搜索策略与层次化搜索策略，其中多目标搜索策略主要解决上述的局部搜索将多个目标纳入考虑的问题，而层次化搜索策略分别针对柔性车间调度问题的两个子问题--机器分配子问题与工序顺序子问题--进行优化，同时使用了基于资源切换的邻域搜索与基于空闲时间的邻域搜索，二者存在互补的关系，前者主要考虑其它机器上的空闲时间，而后者主要考虑当前机器上的空闲时间。

结合图1，基于上述问题描述，为了实现本发明的目的，本发明的基于层次化多目标邻域搜索的改进交叉熵算法(Co-CEM)采用如下步骤：

步骤001.初始化迭代次数M，策略切换阈值n_switch，初始化种群P、工序概率分布矩阵S、机器概率分布矩阵Q与外部记忆库E。

步骤002.对种群P与外部记忆库E进行搜索优化，一共迭代M次。

步骤003.对外部记忆库E使用非支配排序得到最终的非支配解集。

所述步骤001具体包括如下步骤：

步骤00101.初始化种群P：包括初始化种群P中解向量的机器分配部分与工序顺序部分。使用4种机器分配规则来初始化解向量的机器分配部分，包括2种全局初始化规则、1种局部分配规则与1种随机分配规则。详细描述如下：

(1)全局最小负载：每次从所有的机器中选择负载最小的机器进行分配；

(2)随机排列：首先对工序向量进行随机排序，接着从左往右依次遍历工序向量，对每道工序选择负载最小的机器；

(3)最小加工时间：工序分配给加工时间最短的机器；

(4)随机分配：每一道工序，随机分配对应的加工机器；

针对种群P初始化解向量中的工序部分，本发明使用了3种排序规则，详细描述如下：

(1)最多剩余工时：根据每个任务剩余的工时进行工序分配。从所有任务中选择一个具有最小剩余工时的任务分配其工序，如果没有下一道工序，则将该任务从待分配任务集合中删除；如果有多个具有最小剩余工时的任务则随机选择一个；

(2)最多剩余工序：根据每个任务剩余的工序数进行工序分配。从所有任务中选择一个具有最少工序数的任务分配其工序，如果没有下一道工序，则将该任务从待分配任务集合中删除；如果有多个具有最少工序数的任务则随机选择一个；

(3)随机排序：随机分配所有工序的加工顺序；

步骤00102.初始化概率分布矩阵(概率分布矩阵包括工序概率分布矩阵和机器概率分布矩阵)。定S∈R

由于同一任务的工序之间存在先后关系约束，工序向量的第x个位置可选择的工序不能任意取自1,2,...,N，而与工序向量下标0到x-1所选择的工序有关。同样，由于机器选取与工序选取的内在关系，机器向量受到相同约束制约，即第x个位置可选择机器不能任意取自所有机器，而是与该位置对应工序可选择的机器集有关。针对该约束条件，分别引入工序向量order_mask与机器向量machine_mask。以order_mask向量为例，定义order_mask∈R

当对工序向量的位置x选择工序时，使用order_mask进行筛选，得到概率分布向量sample_vec，然后对其处理保证概率和为1，使得生成的工序是可行解，计算步骤下式所示：

sample_vec＝P[x,:]*order_mask

sample_vec＝sample_vec/sum(sample_vec)

sum()表示求和，一旦工序向量第x个位置的工序确定，则更新order_mask，保证后续生成的工序有效。

对于机器向量的生成步骤也采用类似的方法处理。通过machine_mask去除掉采样过程中的无用解，保证了所生成的解是有效的。

在采样得到新种群后，交叉熵算法会根据适应度选择n_elite个精英个体用来更新工序概率分布矩阵S和机器概率分布矩阵Q，如下式所示：

其中，α和β分别为S和Q的学习率，

步骤00103.初始化外部记忆库

步骤00104.根据工序搜索算子与机器搜索算子得到新种群H。对于工序搜索算子，设存在父代个体m、n，则详细步骤如下：

步骤1：首先判断m与n是否相同，如果相同则随机交换两道不属于同一任务的工序得到新个体并直接返回；否则执行步骤2；

步骤2：设当前任务数为N，对N个任务进行编号，从其中随机选择若干个任务到集合u，定义v为集合u的补集，如果选择的任务数为0或者等于N，则重新进行选择；

步骤3：子代p个体中属于集合u中的工序从父代个体m中依次拷贝到对应位置，剩余属于集合v中的工序则依次从父代个体n中依次拷贝到对应位置；

步骤4：相反的，子代q个体中属于集合u中的工序从父代个体n中依次拷贝到对应位置，剩余属于集合v中的工序则依次从父代个体m中依次拷贝到对应位置。

进行工序搜索时，为了避免相同父代个体而得到等价后代个体，首先对父代个体进行相似度检查，如果二者完全相同则直接随机交换两道工序得到新个体。相应的机器搜索算子的详细步骤如下：

步骤1：设当前工序数为N，从N道工序中，随机选择k道组成集合u，如果集合u中元素的个数为0或者等于N，则重新进行选择。

步骤2：将父代个体m和n中属于集合u中的工序，对其分配的机器进行交换得到后代个体p、q。

步骤00105.令种群P←P∪H，对于具有相同目标向量的个体使用突变算子进行去重，其中使用到的变异算子或局部搜索算子如下：

(1)基于最大负载的机器重分配算子：从具有最大负载的机器上加工的工序中，随机选择一道，将其重分配到另外具有相对更小负载的机器上进行加工。

(2)基于最晚完工时间的机器重分配算子：随机选择一道完工时间最晚的机器上的工序，将其重分配到另外一台具有更小最晚完工时间的机器上进行加工。

(3)关键工序移动：对当前个体随机获取一条关键路径，并随机找到一个当前关键路径上的关键块，然后随机选择一道工序前移或者后移到关键块的头部或者尾部。

(4)关键工序重插入：随机选择一道关键工序，将其移动到另一台可加工设备上。

步骤00106.使用基于SPEA2的环境选择算子筛选优良个体，并赋给种群P。由于SPEA2使用了种群中密度信息可以较好地保持种群多样性，本发明使用其作为环境选择算子。SPEA2加入了一些保证种群多样性的手段，例如特定的适应度分配策略、密度估计算法和改进的截断法，其首先计算种群中每一对个体之间的支配关系，然后定义相关的强度值Str(x)，定义下式所示：

Str(x

其中，P表示种群，x

表示支配当前个体的强度值之和。此外，定义一个额外的密度信息值Den(x)，用来辨别具有相同Raw值的个体，定义如下式所示：

其中，k为种群大小的平方根，

Fitness(x

使用基于SPEA2的环境选择算子时，首先会从候选解中优选选择适应度值小于1的个体，也就是非支配解，如果非支配解个数不足够，会根据适应度值依次选取合适数目的个体；否则会执行相应的阶段步骤将多余的个体剔除，也就是具有较小欧式距离的个体。

步骤00107.使用种群P更新外部记忆库E。记忆库的更新过程如下：

步骤1：将每一个优良个体与外部记忆库中的每一个个体的目标函数向量进行比较；

步骤2：如果支配外部记忆库中的个体则替换；

步骤3：如果二者的目标函数向量相同，则计算机器向量的海明距离，如果为0则使用变异策略直到含有不同的目标函数值并查看是否有可替换的个体；否则继续向后比较。

所述步骤002，具体包括以下步骤：

步骤00201.根据策略标识flag选择进化策略：通过采样工序矩阵S与机器矩阵Q或者使用动态交叉算子。基于动态交叉概率的方式产生后代个体可以增强种群的多样性，相应的交叉概率随着迭代次数的增加而逐渐变化。设当前迭代次数为Iteration，总共迭代次数为Total_Iteration，则对应的交叉概率为P

步骤00202.使用层次化多目标邻域搜索策略对Q进行局部搜索得到新个体K。首先定义析取图模型及相关符号。析取图模型最初被提出并应用于作业车间调度，其为有向无环图。首先定义图G＝(V,U,E)描述FJSP，其中，V表示所以工序组成的节点的集合，同时分别确定一个虚拟的起始节点s和一个结束节点e。U表示所有合取弧(conjunctive edge)组成的集合，其确定工序间的加工优先级。E表示所有析取弧(disjunctive edge)的集合，且满足

如图4表示一个可行解在确定分配机器后得到的析取图及其对应的甘特图。在此基于析取图定义一些符号方便后续描述层次化多目标邻域搜索策略。定义析取图G上的节点对应任务i下的工序j，用符号O

定义

令

有向图G中，关键路径为相邻关键工序组成的路径。如图4所示，其中存在一条关键路径(s→O

然后定义基于资源切换的邻域搜索。定义工序ω，则其可移动时间段为前驱工序PJ

设工序ω的当前加工机器为k，相应的加工时间为t

当上式不成立时，工序ω在资源切换后不能减小最晚完工时间，所以为避免无用的局部搜索，提高效率，不应该移动工序ω。

然后定义同样定义关键工序ω。存在最优插入位置当且仅当满足下式：

其中，

最后定义基于空闲时间的邻域搜索。设工序p、q为图G中的相邻工序，其加工机器均为m。设关键工序ω，其加工机器为m，则ω的可交换时间段为

也就是说，如果二者时间段的交集不为0，那么将关键工序ω变换到新的位置，就有可能减少最晚完工时间。

层次化多目标邻域搜索策略包含两个部分：面向多目标的搜索策略与层次化搜索策略。

(1)面向多目标的搜索策略

由于在多目标FJSP往往需要同时考虑多个指标，同时最晚完工时间最难优化，所以专利提出面向多目标的搜索策略。首先对调度解G，定义ψ(G)＝{co

其中，m

面向多目标的搜索策略主要包含两个阶段，分别使用到了基于资源切换的邻域搜索与基于关键工序的邻域搜索。首先，由于资源切换的邻域搜索保证得到解在最晚完工时间条件下可能是改进的，所以优先使用其作为第一阶段邻域搜索。然后，对当前调度解G所对应的所有动作，按照一种分级策略，分别对Δt与Δc进行非降序排序，使得在最晚完工时间可能改进的条件下，优先考虑具有更小Δt，其次才考虑Δc。随后，对排序完毕后得到的动作集π(G)依次使用第一阶段基于资源切换的邻域搜索，如果找到一个可行的动作，则结束搜索；否则，使用第二阶段基于关键工序的邻域搜索，在找到一个可行动作后结束搜索。

(2)基于层次化的搜索策略

层次化的搜索策略主要为了分别解决FJSP的机器分配及工序顺序两个子问题，其中第一层使用面向多目标的搜索策略解决机器分配子问题，第二层使用基于空闲时间的邻域搜索策略用来解决工序顺序子问题。此外，使用一种随机生成权重向量的聚合函数方式来完成新解替换旧解：根据特定的方法随机产生权重向量λ，如果新解的目标向量与λ的点积小于旧解与λ的点积，则替换；否则不替换。

第一层针对跨机器的空闲时间进行优化，第二层使用基于空闲时间的邻域搜索，在第一层结果的基础上，对当前工序的加工顺序进行进一步的优化。由于只改变工序间的加工顺序，不会改变工序所分配的机器，所以只会影响最晚完工时间。前一层是针对当前调度中机器较大空闲时间的利用，而当前这层则是针对机器中较小空闲时间的利用，二者存在一种互补的关系，可以有效增强了算法的局部优化能力。

步骤00203.令P←P∪H∪K，并使用突变算子去除重复个体。

步骤00204.P←对P使用基于SPEA2的环境选择算子筛选优良个体。

步骤00205.E’←使用层次化多目标邻域搜索策略对E进行局部搜索。

步骤00206.E←E’∪E，并使用突变算子去除重复个体。

步骤00207.E←对E使用基于SPEA2的环境选择算子筛选优良个体。

步骤00208.E←使用P更新外部记忆库E。

步骤00209.S、Q←根据flag使用外部记忆库更新概率矩阵。

步骤00210.策略标识flag←如果持续n_switch代没有更新外部记忆库则切换进化策略。

对于步骤003中对外部记忆库E使用非支配排序得到最终的非支配解集为本领域公知方法，在此不再详细累述。

为了验证本发明方法Co-CEM的有效性，使用公开数据集：Kacem用例与BRdata用例数据集，其中Kacem数据集包括5项用例，BRdata包含10项用例。每项用例均确定了机器数、任务数还有每项任务下工序的具体信息。分别使用对比指标超体积HV、反向世代距离IGD，将Co-CEM分别与hDPSO、DABC、BEG-NSGA-II和INSBBO算法进行对比，加粗表示在所对比算法中最优，结果如下表所示。

表1 Co-CEM与其它算法结果对比

首先对比HV指标，可以看出Co-CEM一共在5项用例中取得了相对最优的结果，其中在8项用例中超过hDPSOA、在9项用例中超过BEG-NSGA-II、在4项用例中超过INSBBO、在1项用例中超过DABC。值得注意的是在数据规模最大的Mk10用例中，Co-CEM明显优于所对比的全部算法

然后对比IGD指标，可以看出hDPSO在2项用例中最优，DABC与INSBBO均在3项用例中优于其它算法，而Co-CEM在6项用例中取得了优于其它算法的结果。同时，Co-CEM在8项用例中超过hDPSO、所有用例中超过BEG-NSGA-II、2项用例超过DABC、5项用例超过INSBBO。

综上所述，该实验证明了Co-CEM相对于其它算法具有一定的优越性，并且可以有效求得相应问题的优质解。

本发明的优化算法，对传统的排产问题进行求解，从而保证国内船舶制造企业生产计划的稳定性和有效性，减少计划的盲目性。除船舶制造业外，其他领域如电力系统、医疗资源分配系统等均存在以上需求，因此基于柔性车间调度模型对传统调度问题进行求解，对实际的生产制造如国家工业4.0、中国制造2025等规划以及人民生活方面如医疗系统、电力系统等均具有重要的现实意义。