专利摘要

本发明实施例提供了一种基于改进引力搜索和遗传算法的生产运输协同调度方法及系统，所述方法按如下步骤进行：1设定算法参数；2随机生成初始解；3编码修正；4将工件进行组批；5计算适应度值；6更新最优解和最差解和每个个体的质量；7保存全局最优个体；8计算每个个体的作用力；9更新个体的加速度和速度；10更新个体的位置；11邻域搜索；12判断终止条件是否满足，如果满足则输出全局最优解，否则返回步骤3；本发明能在物联网环境下，对各个制造商的制造方案进行统一调度，实现生产运输的有效协同，从而降低各企业成本，提高企业联盟工作效率。

权利要求

1.一种基于改进引力搜索和遗传算法的生产运输协同调度方法，其特征在于，包括：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，调整常数ε，最大迭代次数t_max，常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的引力质量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i为第i个物体的引力质量，M_ii为第i个物体的惯性质量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是第i个物体的引力质量和第j个物体的引力质量，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

步骤10、判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序；

所述步骤3中所述对种群中所有解进行编码修正，包括：

步骤31、考虑种群中的Q个个体 其中 表示第i个物体在第d维上的位置；

步骤32、设定参数I＝1；

步骤33、判断 是否成立，若成立，则令 执行步骤36；否则，执行步骤34；

步骤34、设定参数K＝1；

步骤35、判断 是否成立，若成立，则令 否则，令K＝K+1，重复步骤35；

步骤36、判断I＞n是否成立，若成立，则结束调整，否则，令I＝I+1，返回步骤33；

所述方法通过如下步骤计算个体的适应度，包括：

步骤1’、把个体X_i中N个位置上元素值相同的元素组成一个集合，从而分别形成在m台机器上加工的工件集合J^M＝{J¹,…,Jⁱ,…,J^m}，Jⁱ表示分配到第i台机器上加工的工件集合；

步骤2’、定义变量i，t_i，并初始化i＝1；

步骤3’、初始化t_i＝0，将上述工件集合Jⁱ进行分批，获得批处理集合Bⁱ；

步骤4’、依次把批处理集合中各批次中最后一个离开机器工件的完工时间赋值给t_i，并将t_i+T_i赋值给t_i；其中T_i表示第i台机器到客户的运输时间；

步骤5’、判断条件i≤m是否成立，若成立则返回步骤3’；否则获得各机器制造跨度时间集合t＝{t₁,…,t_i,…,t_m}，并返回步骤6’；

步骤6’、从上述的时间集合中选出值最大的元素记为C_max，并把C_max赋值给fit(X_i)，记为个体X_i的适应度值。

2.根据权利要求1所述的方法，其特征在于，步骤4中所述在各供应商处对工件进行组批和安排生产，包括：

步骤41、将工件集合中的工件按加工时间非递增进行排序，从而获得经过排序后的工件集合；

步骤42、将经过排序的工件集合中第i个未分配的工件暂时放入能容纳该工件的所有批中，并选出其中放入该工件后批剩余容量最小的批，把该工件分配到选定的批中；若当前所有批的剩余空间都不能容纳第i个未分配工件，则将该工件放入一个批容量为c的新批中，令i＝i+1；

步骤43、重复步骤42，直至把工件集合中所有的工件都分配到相应的批中，批的加工时间由批中所有工件加工时间总和决定。

3.根据权利要求1所述的方法，其特征在于，步骤9中所述对当前种群执行邻域搜索操作，包括：

步骤91、定义变量λ₁，λ₂，p_m，并初始化变量λ₁＝0.1，λ₂＝0.3， 其中t表示当前时间，T表示最大迭代时间；

步骤92、产生一个在(0,1)区间范围内的随机数，记为random，随机产生两个在区间[1,n]范围内的整数，分别记为x，y；

步骤93、判断条件random＜λ₁是否成立，若成立，则执行步骤94；否则判断条件random＜λ₁+λ₂是否成立，若成立，则执行步骤95；否则判断random＜λ₁+λ₂+p_m是否成立，若成立，执行步骤96；否则，执行步骤97；

步骤94、把个体X_i上第x个位置上的元素插到第y个位置上，且x+1到y个位置之间的元素向前移动一个位置，个体中的其他元素位置保持不变，从而形成一个更新后的个体X_i′；

步骤95、把个体X_i上第x个位置上的元素与第y个位置上的元素进行交换，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X_i′；

步骤96、随机产生两个在区间[1,n]范围内的整数记为k，把个体X_i上第x个位置上的元素替换为k，从而形成一个经过搜索后的个体X_i′；

步骤97、从种群中随机选取另一个个体X_z，用个体X_z上第x个位置和第y个位置之间的序列替换个体X_i上第x个位置和第y个位置之间的序列，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X_i′。

4.一种基于改进引力搜索和遗传算法的生产运输协同调度系统，其特征在于，包括：

计算模块，用于执行：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，调整常数ε，最大迭代次数t_max，常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的引力质量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i为第i个物体的引力质量，M_ii为第i个物体的惯性质量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是第i个物体的引力质量和第j个物体的引力质量，，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

输出模块，用于执行：步骤10，判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序；

所述计算模块中步骤3所述对种群中所有解进行编码修正，包括：

步骤31、考虑种群中的Q个个体 其中 表示第i个物体在第d维上的位置；

步骤32、设定参数I＝1；

步骤33、判断 是否成立，若成立，则令 执行步骤36；否则，执行步骤34；

步骤34、设定参数K＝1；

步骤35、判断 是否成立，若成立，则令 否则，令K＝K+1，重复步骤35；

步骤36、判断I＞n是否成立，若成立，则结束调整，否则，令I＝I+1，返回步骤33；

所述计算模块通过如下步骤计算个体的适应度，包括：

步骤1’、把个体X_i中N个位置上元素值相同的元素组成一个集合，从而分别形成在m台机器上加工的工件集合J^M＝{J¹,…,Jⁱ,…,J^m}，Jⁱ表示分配到第i台机器上加工的工件集合；

步骤2’、定义变量i，t_i，并初始化i＝1；

步骤3’、初始化t_i＝0，将上述工件集合Jⁱ进行分批，获得批处理集合Bⁱ；

步骤4’、依次把批处理集合中各批次中最后一个离开机器工件的完工时间赋值给t_i，并将t_i+T_i赋值给t_i；其中T_i表示第i台机器到客户的运输时间；

步骤5’、判断条件i≤m是否成立，若成立则返回步骤3’；否则获得各机器制造跨度时间集合t＝{t₁,…,t_i,…,t_m}，并返回步骤6’；

步骤6’、从上述的时间集合中选出值最大的元素记为C_max，并把C_max赋值给fit(X_i)，记为个体X_i的适应度值。

说明书

技术领域

本发明涉及供应链技术领域，具体涉及一种基于改进引力搜索和遗传算法的生产运输协同调度方法及系统。

背景技术

在物联网环境下，各制造商能够成立以自身为核心的企业联盟，通过协同生产模式，优化资源配置，提高生产效率并满足产品交货期。但是，在全球化协作背景下，联盟中的企业可能分布在不同的地理位置，从而使得各成员企业与核心制造企业间的运输时间存在差异，进而提高了协作的难度。由于该类问题的复杂性，在以往的研究中，元启发式算法被广泛应用于解决该类问题，Garcia与Lozano(2005)考虑了带有时间窗的生产运输协同调度问题，提出一种禁忌搜索(TS)算法。Liu(2011)提出了改进的遗传算法(MGA)用于解决协同生产过程中的成本最小化问题。引力搜索算法(GSA)是由Rashedi(2007)最初提出的，并被广泛应用于各类优化问题，本文中为最大化生产效益问题构建的混合引力搜索和遗传算法是建立在已有的引力搜索算法基础上的。引力搜索算法的步骤一般包括：(1)初始化种群；(2)计算适应度，记录最优和最差解；(3)计算引力；(4)更新种群。通过重复以上步骤在整个空间内搜索最优解。

然而，在实施本发明实施例的过程中，发明人发现，已有的研究中主要针对生产过程进行优化，很少有考虑到从联盟的角度合理调度，难以针对物联网企业的具体问题做出整体优化方案。除此之外，在方法上，虽然引力搜索在优化问题中展现出良好的性能，但是，引力搜索也存在着局部收敛性差和容易早熟等缺点，这些问题通常会干扰优化方案的确定，不利于物联网企业生产效率的提升。

发明内容

本发明实施例的一个目的针对物联网环境下考虑多个制造商和不等工件尺寸的生产运输协同调度问题，依据工件的加工时间和尺寸以及供应商的地理位置对工件任务进行指派，分批和排序，确定工件加工任务的执行者，工件组批和加工顺序，旨在最小化制造跨度时间，基于引力搜索提出新的元启发式方法，提高算法性能，推动企业联盟合作效率的提升，降低企业成本，提高服务水平。

第一方面，本发明实施例提供了一种基于改进引力搜索和遗传算法的生产运输协同调度方法，包括：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，一个很小的调整常数ε，最大迭代次数t_max，一个很大的常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的重量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i是物体i，M_ii为物体i的重量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是物体i和j，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

步骤10、判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序。

可选地，步骤3中所述对种群中所有解进行编码修正，包括：

步骤31、考虑种群中的Q个个体 i＝1,2,...,Q，其中 表示第i个物体在第d维上的位置；

步骤32、设定参数I＝1；

步骤33、判断 是否成立，若成立，则令 否则，执行步骤4；

步骤34、设定参数K＝1；

步骤35、判断 是否成立，若成立，则令 否则，令K＝K+1，重复步骤35；

步骤36、判断I＞n是否成立，若成立，则结束调整，否则，令I＝I+1，返回步骤33。

可选地，步骤4中所述在各供应商处对工件进行组批和安排生产，包括：

步骤41、将工件集合中的工件按加工时间非递增进行排序，从而获得经过排序后的工件集合；

步骤42、将经过排序的工件集合中第i个未分配的工件暂时放入能容纳该工件的所有批中，并选出其中放入该工件后批剩余容量最小的批，把该工件分配到选定的批中；若当前所有批的剩余空间都不能容纳第i个未分配工件，则将该工件放入一个批容量为c的新批中，令i＝i+1；

步骤43、重复步骤42，直至把工件集合中所有的工件都分配到相应的批中，批的加工时间由批中所有工件加工时间总和决定。

可选地，所述方法通过如下步骤计算个体的适应度，包括：

步骤1’、把个体X_i中N个位置上元素值相同的元素组成一个集合，从而分别形成在m台机器上加工的工件集合J^M＝{J¹,…,Jⁱ,…,J^m}，J_i表示分配到第i台机器上加工的工件集合；

步骤2’、定义变量i，t_i，并初始化i＝1；

步骤3’、初始化t_i＝0，将上述工件集合Jⁱ进行分批，获得批处理集合Bⁱ；

步骤4’、依次把批处理集合中各批次中最后一个离开机器工件的完工时间赋值给t_i，并将t_i+T_i赋值给t_i；

步骤5’、判断条件i≤m是否成立，若成立则返回步骤3’；否则获得各机器制造跨度时间集合t＝{t₁,…,t_i,…,t_m}，并返回步骤6’；

步骤6’、从上述的时间集合中选出值最大的元素记为C_max，并把C_max赋值给fit(X_i)，记为个体X_i的适应度值。

可选地，步骤9中所述对当前种群执行邻域搜索操作，包括：

步骤91、定义变量λ₁，λ₂，p_m，并初始化变量λ₁＝0.1，λ₂＝0.3， 其中t表示当前时间；

步骤92、产生一个在(0，1)区间范围内的随机数，记为random，随机产生两个在区间[1，n]范围内的整数，分别记为x，y；

步骤93、判断条件random＜λ₁是否成立，若成立，则执行步骤94；否则判断条件random＜λ₁+λ₂是否成立，若成立，则执行步骤95；否则判断random＜λ₁+λ₂+p_m是否成立，若成立，执行步骤96；否则，执行步骤7；

步骤94、把个体X_i上第x个位置上的元素插到第y个位置上，且x+1到y个位置之间的元素向前移动一个位置，个体中的其他元素位置保持不变，从而形成一个更新后的个体X′_i；

步骤95、把个体X_i上第x个位置上的元素与第y个位置上的元素进行交换，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i；

步骤96、随机产生两个在区间[1,n]范围内的整数记为k，把个体X_i上第x个位置上的元素替换为k，从而形成一个经过搜索后的个体X′_i；

步骤97、从种群中随机选取另一个个体X_z，用个体X_z上第x个位置和第y个位置之间的序列替换个体X_i上第x个位置和第y个位置之间的序列，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i。

第二方面，本发明实施例还提供了一种基于改进引力搜索和遗传算法的生产运输协同调度系统，包括：

计算模块，用于执行：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，一个很小的调整常数ε，最大迭代次数t_max，一个很大的常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 i＝1,2,...,Q,其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的重量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i是物体i，M_ii为物体i的重量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是物体i和j，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

输出模块，用于执行：步骤10，判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序。

本发明实施例提供了一种基于改进引力搜索和遗传算法的生产运输协同调度方法及系统，所述方法按如下步骤进行：1设定算法参数；2随机生成初始解；3编码修正；4将工件进行组批；5计算适应度值；6更新最优解和最差解和每个个体的质量；7保存全局最优个体；8计算每个个体的作用力；9更新个体的加速度和速度；10更新个体的位置；11邻域搜索；12判断终止条件是否满足，如果满足则输出全局最优解，否则返回步骤3；本发明能在物联网环境下，对各个制造商的制造方案进行统一调度，实现生产运输的有效协同，从而降低各企业成本，提高企业联盟工作效率。

附图说明

通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：

图1是本发明一实施例提供的基于不同地理位置的多制造商的生产运输协同调度问题示意图；

图2是本发明一实施例提供的一种基于改进遗传算法的不同容量的同类平行机批调方法的流程示意图；

图3是本发明一实施例提供的一种基于改进遗传算法的不同容量的同类平行机批调系统的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

本发明各个实施例针对物联网环境下考虑多个制造商和不等工件尺寸的生产运输协同调度问题，依据工件的加工时间和尺寸以及供应商的地理位置对工件任务进行指派，分批和排序，确定工件加工任务的执行者，工件组批和加工顺序，旨在最小化制造跨度时间，基于引力搜索提出新的元启发式方法，提高算法性能，推动企业联盟合作效率的提升，降低企业成本，提高服务水平。

为便于理解，下面结合图1对本发明实施例所解决的问题进行详细描述。

基于物联网环境下多制造商的生产运输协同调度问题，目标为最小化制造跨度时间。该问题描述如下：m个分布在不同区域的制造商，每个制造商处有一个挤压机，该挤压机相当于连续批处理机。给定一组包含N个工件的任务集合J＝{J₁,J₂,J₃,···,J_N}。不同的工件具有不同的加工时间和尺寸，分别由p_i和s_i(i＝1,2,···,N)表示。该问题主要包含两个阶段，工件首先在制造商的机器上以连续批的方式进行生产加工，之后工件将从制造商处运往客户进行进一步加工操作。

(1)在第一阶段中，工件将被分为多个批在制造商处的机器上加工，批的加工时间等于该批内所有加工时间总和。所有批处理机能同时处理的工件尺寸之和上限为c，即任何批次中所有工件尺寸之和不大于c。每个批次在加工之前，需要机器准备时间s。批次b_k的加工时间为P_k。

(2)在第二阶段中，车辆将所有批次从对应的制造商处运往客户进行进一步生产加工。不同的制造商j到客户的单程运输时间不同，表示为T_j(j＝1,2,···,m)。在所考虑的问题中，我们假设所有车辆的能力与机器的能力相同，且车辆在每次运输过程中能够装载任一批次。

基于此，本发明实施例提供了一种基于改进引力搜索和遗传算法的生产运输协同调度方法，参见图2，包括：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，一个很小的调整常数ε，最大迭代次数t_max，一个很大的常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 i＝1,2,...,Q,其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的重量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i是物体i，M_ii为物体i的重量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是物体i和j，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

步骤10、判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序。

在具体实施时，步骤3中所述对种群中所有解进行编码修正可以有多种实施方式，其中一种可选的实施方式为：

步骤31、考虑种群中的Q个个体 i＝1,2,...,Q，其中 表示第i个物体在第d维上的位置；

步骤32、设定参数I＝1；

步骤33、判断 是否成立，若成立，则令 否则，执行步骤4；

步骤34、设定参数K＝1；

步骤35、判断 是否成立，若成立，则令 否则，令K＝K+1，重复步骤35；

步骤36、判断I＞n是否成立，若成立，则结束调整，否则，令I＝I+1，返回步骤33。

在具体实施时，步骤4中所述在各供应商处对工件进行组批和安排生产可以有多种实施方式，其中一种可选的实施方式为：

步骤41、将工件集合中的工件按加工时间非递增进行排序，从而获得经过排序后的工件集合；

步骤42、将经过排序的工件集合中第i个未分配的工件暂时放入能容纳该工件的所有批中，并选出其中放入该工件后批剩余容量最小的批，把该工件分配到选定的批中；若当前所有批的剩余空间都不能容纳第i个未分配工件，则将该工件放入一个批容量为c的新批中，令i＝i+1；

步骤43、重复步骤42，直至把工件集合中所有的工件都分配到相应的批中，批的加工时间由批中所有工件加工时间总和决定。

在具体实施时，本发明实施例提供的方法通过如下步骤计算个体的适应度，包括：

步骤1”、把个体X_i中N个位置上元素值相同的元素组成一个集合，从而分别形成在m台机器上加工的工件集合J^M＝{J¹,…,Jⁱ,…,J^m}，Jⁱ表示分配到第i台机器上加工的工件集合；

步骤2’、定义变量i，t_i，并初始化i＝1；

步骤3’、初始化t_i＝0，将上述工件集合Jⁱ进行分批，获得批处理集合Bⁱ；

步骤4’、依次把批处理集合中各批次中最后一个离开机器工件的完工时间赋值给t_i，并将t_i+T_i赋值给t_i；

步骤5’、判断条件i≤m是否成立，若成立则返回步骤3’；否则获得各机器制造跨度时间集合t＝{t₁,…,t_i,…,t_m}，并返回步骤6’；

步骤6’、从上述的时间集合中选出值最大的元素记为C_max，并把C_max赋值给fit(X_i)，记为个体X_i的适应度值。

在具体实施时，步骤9中所述对当前种群执行邻域搜索操作可以由多种实施方式，其中一种可选的实施方式为：

步骤91、定义变量λ₁，λ₂，p_m，并初始化变量λ₁＝0.1，λ₂＝0.3， 其中t表示当前时间；

步骤92、产生一个在(0,1)区间范围内的随机数，记为random，随机产生两个在区间[1,n]范围内的整数，分别记为x，y；

步骤93、判断条件random＜λ₁是否成立，若成立，则执行步骤94；否则判断条件random＜λ₁+λ₂是否成立，若成立，则执行步骤95；否则判断random＜λ₁+λ₂+p_m是否成立，若成立，执行步骤96；否则，执行步骤7；

步骤94、把个体X_i上第x个位置上的元素插到第y个位置上，且x+1到y个位置之间的元素向前移动一个位置，个体中的其他元素位置保持不变，从而形成一个更新后的个体X′_i；

步骤95、把个体X_i上第x个位置上的元素与第y个位置上的元素进行交换，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i；

步骤96、随机产生两个在区间[1,n]范围内的整数记为k，把个体X_i上第x个位置上的元素替换为k，从而形成一个经过搜索后的个体X′_i；

步骤97、从种群中随机选取另一个个体X_z，用个体X_z上第x个位置和第y个位置之间的序列替换个体X_i上第x个位置和第y个位置之间的序列，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i。

本发明的有益效果如下：

1、本发明针对物联网环境下的分布式协同制造模式，研究制造联盟的生产与运输协同调度问题，通过改进的混合引力搜索和遗传算法，首先将工件以编码的方式，分配到各个制造商处，然后针对差异工件和问题的性质提出相应的分批和生产调度策略，得出相应个体的适应度值；在根据个体的适应度值计算个体的质量，记录种群的最优个体和最差个体；根据种群的个体情况计算加速度和速度，并依据种群更新规则，通过重复迭代，实现对种群的不断进化，最终寻得最优解。混合引力搜索和遗传算法在收敛速度和收敛结果上，是一种效率很高的算法；通过该算法，解决了物联网环境下的企业联盟调度方案的制定问题，提高了联盟中企业的合作效率，优化了企业运作成本，实现了服务水平的提升。

2、本发明在编码时针对该问题中可能出现的非可行解，提出了相应的修正策略，将非可行解调整为可行解，从而根据相应的策略计算个体的适应度，既避免了搜索资源的浪费，又保证了搜索结果的多样性。

3、本发明针对引力搜索算法局部收敛性不足和容易早熟的问题，提出了基于遗传算子的交换、插入、变异和交叉策略，并随着迭代次数的增加，自适应的调整邻域策略的执行概率，在保证算法前期运行速度的同时，确保了算法后期的收敛能力

基于相同的构思，本发明另一实施例还提供了一种基于改进引力搜索和遗传算法的生产运输协同调度系统，参见图3，包括：

计算模块，用于执行：

步骤1、输入多个制造商的运输时间，每个工件的尺寸和加工时间，设定混合引力搜索和遗传算法参数，包括t时刻的引力常数G(t)，一个很小的调整常数ε，最大迭代次数t_max，一个很大的常数MC，全局最优解gbest＝MC；

步骤2、初始化种群，考虑共有Q个物体，第i个物体的位置定义为 i＝1,2,...,Q,其中 表示第i个物体在第d维上的位置，对应在问题中表示该位置工件将被分配至第 个机器；

步骤3、对种群中所有解进行编码修正，消除非可行解；

步骤4、在各供应商处对工件进行组批和安排生产，计算个体适应度；

步骤5、通过适应度计算物体的重量，保存最优和最差个体，记录全局最优解，相关定义如下：

M_i＝M_ii,i＝1,2,...,Q,

其中，M_i是物体i，M_ii为物体i的重量，fit_j(t)表示物体j在t时刻的适应度函数值；

步骤6、判断gbest＞best(t)是否成立，若成立，则令gbest＝best(t)；

步骤7、计算每个个体所受到的引力，在t时刻物体j作用于物体i的作用力定义为：

其中，M_i和M_j分别是物体i和j，R_ij(t)为t时刻物体i和物体j之间的距离；

物体i在第d维上的引力总和为所有其他物体在第d维上所作用的随机加权引力总和，其定义为，

其中，rand_j为[0,1]之间的随机数；

步骤8、计算加速度和速度，更新种群，在t时刻物体i在第d维上的加速度表示为：

下一个时间点物体i的速度和位置分别表示为，

其中rand_i为[0,1]之间的随机数， 和 分别为物体当前的速度和位置；

步骤9、根据当前迭代次数确定各邻域结构选择概率，对当前种群执行邻域搜索操作，更新个体位置，令t＝t+1；

输出模块，用于执行：步骤10，判断t≤t_max是否成立，若成立，返回步骤3，否则，结束算法，并输出工件任务分布安排，组批方式和批的加工顺序。

可选地，计算模块21执行步骤3中所述对种群中所有解进行编码修正，可以包括：

步骤31、考虑种群中的Q个个体 i＝1,2,...,Q，其中 表示第i个物体在第d维上的位置；

步骤32、设定参数I＝1；

步骤33、判断 是否成立，若成立，则令 否则，执行步骤4；

步骤34、设定参数K＝1；

步骤35、判断 是否成立，若成立，则令 否则，令K＝K+1，重复步骤35；

步骤36、判断I＞n是否成立，若成立，则结束调整，否则，令I＝I+1，返回步骤33。

可选地，计算模块21执行步骤4中所述在各供应商处对工件进行组批和安排生产，可以包括：

步骤41、将工件集合中的工件按加工时间非递增进行排序，从而获得经过排序后的工件集合；

步骤42、将经过排序的工件集合中第i个未分配的工件暂时放入能容纳该工件的所有批中，并选出其中放入该工件后批剩余容量最小的批，把该工件分配到选定的批中；若当前所有批的剩余空间都不能容纳第i个未分配工件，则将该工件放入一个批容量为c的新批中，令i＝i+1；

步骤43、重复步骤42，直至把工件集合中所有的工件都分配到相应的批中，批的加工时间由批中所有工件加工时间总和决定。

可选地，计算模块21可以通过如下步骤计算个体的适应度，包括：

步骤1”、把个体X_i中N个位置上元素值相同的元素组成一个集合，从而分别形成在m台机器上加工的工件集合J^M＝{J¹,…,Jⁱ,…,J^m}，Jⁱ表示分配到第i台机器上加工的工件集合；

步骤2’、定义变量i，t_i，并初始化i＝1；

步骤3’、初始化t_i＝0，将上述工件集合Jⁱ进行分批，获得批处理集合Bⁱ；

步骤4’、依次把批处理集合中各批次中最后一个离开机器工件的完工时间赋值给t_i，并将t_i+T_i赋值给t_i；

步骤5’、判断条件i≤m是否成立，若成立则返回步骤3’；否则获得各机器制造跨度时间集合t＝{t₁,…,t_i,…,t_m}，并返回步骤6’；

步骤6’、从上述的时间集合中选出值最大的元素记为C_max，并把C_max赋值给fit(X_i)，记为个体X_i的适应度值。

可选地，计算模块21执行步骤9中所述对当前种群执行邻域搜索操作，可以包括：

步骤91、定义变量λ₁，λ₂，p_m，并初始化变量λ₁＝0.1，λ₂＝0.3， 其中t表示当前时间；

步骤92、产生一个在(0,1)区间范围内的随机数，记为random，随机产生两个在区间[1,n]范围内的整数，分别记为x，y；

步骤93、判断条件random＜λ₁是否成立，若成立，则执行步骤94；否则判断条件random＜λ₁+λ₂是否成立，若成立，则执行步骤95；否则判断random＜λ₁+λ₂+p_m是否成立，若成立，执行步骤96；否则，执行步骤7；

步骤94、把个体X_i上第x个位置上的元素插到第y个位置上，且x+1到y个位置之间的元素向前移动一个位置，个体中的其他元素位置保持不变，从而形成一个更新后的个体X′_i；

步骤95、把个体X_i上第x个位置上的元素与第y个位置上的元素进行交换，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i；

步骤96、随机产生两个在区间[1,n]范围内的整数记为k，把个体X_i上第x个位置上的元素替换为k，从而形成一个经过搜索后的个体X′_i；

步骤97、从种群中随机选取另一个个体X_z，用个体X_z上第x个位置和第y个位置之间的序列替换个体X_i上第x个位置和第y个位置之间的序列，而个体的其他元素都保持不变，从而形成一个经过搜索后的个体X′_i。

本发明实施例提供的系统能在物联网环境下，对各个制造商的制造方案进行统一调度，实现生产运输的有效协同，从而降低各企业成本，提高企业联盟工作效率。

本发明实施例还公开一种计算机程序产品，所述计算机程序产品包括计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，计算机能够执行上述各方法实施例所提供的方法，例如包括：第一方面所述的方法。

在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。

类似地，应当理解，为了精简本公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。

基于改进引力搜索算法的生产运输协同调度方法及系统专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。