专利摘要
本发明实施例涉及一种基于改进变邻域搜索和差分进化算法的调度方法及系统，该方法包括：1设定算法的参数；2构建邻域结构；3初始化种群；4确定初始解；5计算适应度值；6局部搜索；7父体选择；8个体倒位变异；9更新种群；10更新初始解；11更新算法搜索的邻域结构；12判断算法执行的终止条件是否满足，若满足则输出算法搜索的全局最优解，否则返回步骤6。本发明实施例能针对基于差异工件的制造商单机情形下的生产与运输协同批调度问题，求得近似最优解，从而使得企业能在最大限度上充分利用其生产资源，降低生产成本，并提高企业服务水平和顾客满意度水平。
权利要求
1.一种基于改进变邻域搜索和差分进化算法的生产批调度方法，其特征在于，包括：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束并输出全局最优解Xbest的适应度值和工件对应的组批方案；
步骤S6中在该邻域结构中对种群中的个体进行局部搜索策略，包括：
步骤S61’：定义变量 表示存储种群质量前top的个体，Nother表示种群SI剩余其他个体的数量， 表示存储种群SI剩余其他个体集合，Nc表示变异个体的数量，Nr表示随机个体的数量， 表示存储随机个体集合；
步骤S62’：针对种群SI-1，把该种群中适应度前top的个体赋值给 剩余个体赋值给
步骤S63’：取迭代次数I除以Nother的余数，并把该余数赋值给Nc，若Nc＝0，则令Nc＝1；
步骤S64’：在 中随机选择一个个体，针对该个体，随机产生两个位置rand1和rand2，并且rand1≠rand2，对该个体在这两个位置之间的元素进行对称交换处理；
步骤S65’：重复步骤S64’，直至选出Nc个各不相同的个体进行相应的变异操作；
步骤S66’：判断当代的邻域结构是否与上一代相同，若相同，则随机生成Nr个个体，并存储于Sr中；否则执行步骤S67’；
步骤S67’：随机选择邻域结构初始解 中的两个元素，并对这两个元素进行交换产生一个新个体，重复此操作直至产生Nr个个体，并把这些个体存储于Sr中；
步骤S68’：分别将 Sc和Sr中所有的个体都赋值给SI，作为本代更新后的种群；
步骤S5中分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解，包括：
步骤S51：定义变量j＝1；
步骤S52：判断变量j的值，若等于1则执行步骤S53；若值等于2则执行步骤S54；若等于3则执行步骤S55；若为其他值则执行步骤S56；
步骤S53：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其到达时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S54：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S55：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递增进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S56：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件进行随机排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S57：将j+1赋值给j，判断j≤Q是否成立，若成立，则返回步骤S52；否则种群初始化完毕；
步骤S58：根据初始种群，选出其中质量最好的个体，并把该个体赋值给初始解Xs；
步骤S7中计算个体适应度值，包括：
步骤S71：把个体X的工件序列中第一个未分配的工件放置现存的第一个能容纳该工件的批中,若现存的每个批无法容纳该工件,则创建一个容量为C的新批，并把该工件放置新批中；
步骤S72：重复步骤S71，直至个体X中所有的工件都分配到相应的批中，得到一个工件批集合B＝{B1,...,Bi,...,Bl}，l表示批的数量；
步骤S73：将步骤S72中所获得的批集合中的工件批按其批的到达时间非递减进行排序，得到一个经过排序后的批集合B'＝{B′1,...,B′i,...,B′l}，其中B′i表示在加工机器中第l个位置上进行加工的工件批；
步骤S74：定义变量Cmax＝0，表示制造跨度所需时间，循环变量j＝1，批集合B'中工件批B′i的加工时间记为PiB'，到达时间记为riB'；
步骤S75：判断当前 是否成立，若成立则把 赋值给Cmax，否则将 赋值给Cmax；
步骤S76：将j+1赋值给j，判断j≤l是否成立，若成立则返回步骤S75，否则将将Cmax+T赋值给Cmax；
步骤S77：将步骤S76中最终获得的Cmax值作为该个体X适应度值。
2.根据权利要求1所述的方法，其特征在于，步骤S6中选定邻域结构，包括：
步骤S61：定义变量Xtemp， 这两个变量的各元素含义均与初始解Xs相同，把Xs赋值给Xtemp；
步骤S62：判断变量K的值，若为1则执行步骤S63；若为2则执行步骤S64；若为3则执行步骤S65；
步骤S63：定义变量x'，随机选择Xtemp中的一个元素xrandom，把xrandom的值赋给x'，随机产生一个在区间[1，n]范围内的整数m，并把xrandom的值替换为m，同时把Xtemp中值与m相同的另一个元素值替换为x'；
步骤S64：随机选择Xtemp中的两个元素，并把这两个元素进行交换；
步骤S65：随机选择Xtemp中的两个元素，并把其中的一个元素插入到另一个元素的后一个位置上；
步骤S66：把经过变换的Xtemp赋值给 作为该邻域结构的初始解。
3.一种基于改进变邻域搜索和差分进化算法的生产批调度系统，其特征在于，包括：
处理单元，用于执行以下步骤：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束；
输出单元，用于输出全局最优解Xbest的适应度值和工件对应的组批方案；
所述处理单元执行步骤S6中在该邻域结构中对种群中的个体进行局部搜索策略，包括：
步骤S61’：定义变量 表示存储种群质量前top的个体，Nother表示种群SI剩余其他个体的数量， 表示存储种群SI剩余其他个体集合，Nc表示变异个体的数量，Nr表示随机个体的数量， 表示存储随机个体集合；
步骤S62’：针对种群SI-1，把该种群中适应度前top的个体赋值给 剩余个体赋值给
步骤S63’：取迭代次数I除以Nother的余数，并把该余数赋值给Nc，若Nc＝0，则令Nc＝1；
步骤S64’：在 中随机选择一个个体，针对该个体，随机产生两个位置rand1和rand2，并且rand1≠rand2，对该个体在这两个位置之间的元素进行对称交换处理；
步骤S65’：重复步骤S64’，直至选出Nc个各不相同的个体进行相应的变异操作；
步骤S66’：判断当代的邻域结构是否与上一代相同，若相同，则随机生成Nr个个体，并存储于Sr中；否则执行步骤S67’；
步骤S67’：随机选择邻域结构初始解 中的两个元素，并对这两个元素进行交换产生一个新个体，重复此操作直至产生Nr个个体，并把这些个体存储于Sr中；
步骤S68’：分别将 Sc和Sr中所有的个体都赋值给SI，作为本代更新后的种群；
所述处理单元执行步骤S5中分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解，包括：
步骤S51：定义变量j＝1；
步骤S52：判断变量j的值，若等于1则执行步骤S53；若值等于2则执行步骤S54；若等于3则执行步骤S55；若为其他值则执行步骤S56；
步骤S53：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其到达时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S54：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S55：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递增进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S56：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件进行随机排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S57：将j+1赋值给j，判断j≤Q是否成立，若成立，则返回步骤S52；否则种群初始化完毕；
步骤S58：根据初始种群，选出其中质量最好的个体，并把该个体赋值给初始解Xs；
所述处理单元执行步骤S7中计算个体适应度值，包括：
步骤S71：把个体X的工件序列中第一个未分配的工件放置现存的第一个能容纳该工件的批中,若现存的每个批无法容纳该工件,则创建一个容量为C的新批，并把该工件放置新批中；
步骤S72：重复步骤S71，直至个体X中所有的工件都分配到相应的批中，得到一个工件批集合B＝{B1,...,Bi,...,Bl}，l表示批的数量；
步骤S73：将步骤S72中所获得的批集合中的工件批按其批的到达时间非递减进行排序，得到一个经过排序后的批集合B'＝{B′1,...,B′i,...,B′l}，其中B′i表示在加工机器中第l个位置上进行加工的工件批；
步骤S74：定义变量Cmax＝0，表示制造跨度所需时间，循环变量j＝1，批集合B'中工件批Bi'的加工时间记为PiB'，到达时间记为riB'；
步骤S75：判断当前 是否成立，若成立则把 赋值给Cmax，否则将 赋值给Cmax；
步骤S76：将j+1赋值给j，判断j≤l是否成立，若成立则返回步骤S75，否则将将Cmax+T赋值给Cmax；
步骤S77：将步骤S76中最终获得的Cmax值作为该个体X适应度值。
4.根据权利要求3所述的系统，其特征在于，所述处理单元执行步骤S6中选定邻域结构，包括：
步骤S61：定义变量Xtemp， 这两个变量的各元素含义均与初始解Xs相同，把Xs赋值给Xtemp；
步骤S62：判断变量K的值，若为1则执行步骤S63；若为2则执行步骤S64；若为3则执行步骤S65；
步骤S63：定义变量x'，随机选择Xtemp中的一个元素xrandom，把xrandom的值赋给x'，随机产生一个在区间[1，n]范围内的整数m，并把xrandom的值替换为m，同时把Xtemp中值与m相同的另一个元素值替换为x'；
步骤S64：随机选择Xtemp中的两个元素，并把这两个元素进行交换；
步骤S65：随机选择Xtemp中的两个元素，并把其中的一个元素插入到另一个元素的后一个位置上；
步骤S66：把经过变换的Xtemp赋值给 作为该邻域结构的初始解。
说明书
技术领域
本发明实施例涉及软件技术领域，具体涉及一种基于改进变邻域搜索和差分进化算法的调度方法及系统。
背景技术
资源配置问题一直以来都是社会关注的焦点，而生产批调度问题是一类典型的组合优化问题，最先起源于芯片测试阶段，受其实际问题的启发，批调度问题成为了研究的热点课题。批调度理论在实际行业的应用十分广泛，例如：物流运输，重金属制造业等领域。在批调度问题中，多个生产任务在同一时刻能利用同一个加工资源，在实际的生产过程中生产任务受多种条件约束。在满足现行的生产约束条件下，设计科学合理的生产调度方案可以规范企业的生产管理水平并提高企业的生产效率，从而可以使企业在如今买方成为主流的市场中提升核心竞争力。由此可见，对批调度问题进行研究无论是在企业还是整个社会的运转管理中都具有极为显著的现实意义。
综合现有的研究成果，大多数批调度问题都属于NP难问题，因此在解决该类组合优化问题时普遍运用智能算法来寻求近似最优的调度方案。一种研究方法研究了单机批调度问题，考虑了工件不同的尺寸和加工时间，并设计了离散粒子群算法进行解决该问题；一种方法是针对同样的问题分别设计了自由搜索算法和混合邻域搜索算法；还一种方法是基于蚁群算法解决该类问题。
然而，在进行发明创造的过程中发明人发现，现有技术存在一下缺陷：(1)在研究问题上，以往的文献中研究单机批调度问题主要从工件约束进行考虑，比如工件的尺寸，加工时间，到达时间，这些文献研究的模型主要还是集中在生产阶段，而研究生产与运输协同批调度问题较少。在实际环境中，由于生产与运输都是决定客户满意水平的关键因素，因此企业不仅需要考虑在生产阶段提高生产效率，还需要考虑运输阶段的效益。(2)在研究方法上，初始解的质量、邻域结构以及邻域结构内的搜索策略，这些因素都影响着变邻域搜索算法的性能。
发明内容
本发明实施例提供了一种基于改进变邻域搜索和差分进化算法的调度方法及系统，用以解决上述至少一个技术问题。
第一方面，本发明实施例提供一种基于改进变邻域搜索和差分进化算法的调度方法，包括：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束并输出全局最优解Xbest的适应度值和工件对应的组批方案。
第二方面，本发明实施例提供一种基于改进变邻域搜索和差分进化算法的调度系统，包括：
处理单元，用于执行以下步骤：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束；
输出单元，用于输出全局最优解Xbest的适应度值和工件对应的组批方案。
本发明实施例能针对基于差异工件的制造商单机情形下的生产与运输协同批调度问题，求得近似最优解，从而使得企业能在最大限度上充分利用其生产资源，降低生产成本，并提高企业服务水平和顾客满意度水平。
附图说明
通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：
图1是本发明实施例提供的一种基于改进变邻域搜索和差分进化算法的调度方法流程图；
图2是本发明实施例提供的一种基于改进变邻域搜索和差分进化算法的调度系统结构示意图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
本发明实施例考虑动态到达差异工件，制造商单机情形下的生产与运输协同批调度问题，优化目标为最小化制造时间跨度。根据问题特点，设计了有效的智能算法，解决该组合优化问题，促进企业生产效率与运输效率的提升。
为便于理解，下面首先对本发明实施例要解决的问题进行详细说明，具体来说：
(1)生产加工工件的集合为J＝{J1,...,Ji,...,Jn}，工件Ji的加工时间记为pi，尺寸记为si，到达时间记为ri。
(2)加工机器为一台平行批处理机，该处理机的容量为C，工件在加工时可自由进行组批在处理机上以批的形式加工，规定每个批中工件尺寸之和不能超过C。
(3)批的到达时间由批内到达时间最大的工件决定，批的完工时间等于批中所有工件的最大完工时间，特定的批一旦形成，不能将该批中的工件移出，且不可在该批中添加新工件。
(4)当所有批都加工完毕后，由运输车辆把工件送达给客户，假设运输车辆具有无限运输能力。
(5)需要优化的目标为工件开始加工至最后一个工件送达给客户时所需的时间跨度。
基于此，本发明的一个实施例提供了一种基于改进变邻域搜索和差分进化算法的调度方法，如图1所示，包括：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束并输出全局最优解Xbest的适应度值和工件对应的组批方案。
本发明实施例能针对基于差异工件的制造商单机情形下的生产与运输协同批调度问题，求得近似最优解，从而使得企业能在最大限度上充分利用其生产资源，降低生产成本，并提高企业服务水平和顾客满意度水平。
在具体实施时，步骤S5中分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解，可以包括：
步骤S51：定义变量j＝1；
步骤S52：判断变量j的值，若等于1则执行步骤S53；若值等于2则执行步骤S54；若等于3则执行步骤S55；若为其他值则执行步骤S56；
步骤S53：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其到达时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S54：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S55：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递增进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S56：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件进行随机排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S57：将j+1赋值给j，判断j≤Q是否成立，若成立，则返回步骤S52；否则种群初始化完毕；
步骤S58：根据初始种群，选出其中质量最好的个体，并把该个体赋值给初始解Xs。
在具体实施时，步骤S6中选定邻域结构，可以包括：
步骤S61：定义变量Xtemp， 这两个变量的各元素含义均与初始解Xs相同，把Xs赋值给Xtemp；
步骤S62：判断变量K的值，若为1则执行步骤S63；若为2则执行步骤S64；若为3则执行步骤S65；
步骤S63：定义变量x'，随机选择Xtemp中的一个元素xrandom，把xrandom的值赋给x'，随机产生一个在区间[1，n]范围内的整数m，并把xrandom的值替换为m，同时把Xtemp中值与m相同的另一个元素值替换为x'；
步骤S64：随机选择Xtemp中的两个元素，并把这两个元素进行交换；
步骤S65：随机选择Xtemp中的两个元素，并把其中的一个元素插入到另一个元素的后一个位置上；
步骤S66：把经过变换的Xtemp赋值给 作为该邻域结构的初始解。
在具体实施时，步骤S6中在该邻域结构中对种群中的个体进行局部搜索策略，可以包括：
步骤S61’：定义变量 表示存储种群质量前top的个体，Nother表示种群SI剩余其他个体的数量， 表示存储种群SI剩余其他个体集合，Nc表示变异个体的数量，Nr表示随机个体的数量， 表示存储随机个体集合；
步骤S62’：针对种群SI-1，把该种群中适应度前top的个体赋值给 剩余个体赋值给
步骤S63’：取迭代次数I除以Nother的余数，并把该余数赋值给Nc，若Nc＝0，则令Nc＝1；
步骤S64’：在 中随机选择一个个体，针对该个体，随机产生两个位置rand1和rand2，并且rand1≠rand2，对该个体在这两个位置之间的元素进行对称交换处理；
步骤S65’：重复步骤S64’，直至选出Nc个各不相同的个体进行相应的变异操作；
步骤S66’：判断当代的邻域结构是否与上一代相同，若相同，则随机生成Nr个个体，并存储于Sr中；否则执行步骤S67’；
步骤S67’：随机选择邻域结构初始解 中的两个元素，并对这两个元素进行交换产生一个新个体，重复此操作直至产生Nr个个体，并把这些个体存储于Sr中；
步骤S68’：分别将 Sc和Sr中所有的个体都赋值给SI，作为本代更新后的种群。
在具体实施时，步骤S7中计算个体适应度值，可以包括：
步骤S71：把个体X的工件序列中第一个未分配的工件放置现存的第一个能容纳该工件的批中,若现存的每个批无法容纳该工件,则创建一个容量为C的新批，并把该工件放置新批中；
步骤S72：重复步骤S71，直至个体X中所有的工件都分配到相应的批中，得到一个工件批集合B＝{B1,...,Bi,...,Bl}，l表示批的数量；
步骤S73：将步骤S72中所获得的批集合中的工件批按其批的到达时间非递减进行排序，得到一个经过排序后的批集合B'＝{B'1,...,B'i,...,B'l}，其中B'i表示在加工机器中第l个位置上进行加工的工件批；
步骤S74：定义变量Cmax＝0，表示制造跨度所需时间，循环变量j＝1，批集合B'中工件批B'i的加工时间记为 到达时间记为
步骤S75：判断当前 是否成立，若成立则把 赋值给Cmax，否则将 赋值给Cmax；
步骤S76：将j+1赋值给j，判断j≤l是否成立，若成立则返回步骤S75，否则将将Cmax+T赋值给Cmax；
步骤S77：将步骤S76中最终获得的Cmax值作为该个体X适应度值。
本发明的有益效果如下：
1、本发明针对单机情形下的生产与运输协同批调度问题，通过改进的变邻域搜索算法，首先将需要处理的工件进行编码，根据分批策略把工件分配到相应的批中，即调度方案，并得出相应个体的适应度值。选择搜索的邻域结构，在该邻域结构中进行局部搜索，搜索种群通过交叉和保留等操作，不断提高种群的质量。通过迭代以上步骤，在解空间内不断搜索，最终求得最优解。改进的变邻域搜索算法在收敛速度和搜索的解质量方面表现出了良好的性能。通过本发明设计的算法，解决了单机情形下的差异工件生产与运输协同批调度问题，提升企业在生产与运输的管理水平，从而提高企业在这两个阶段的整体效益。
2、本发明在产生初始种群时，首先通过利用ERT、LPT、SPT等启发式生成相对应的个体作为初始种群的个体，初始种群剩余个体则随机产生，然后通过在初始种群中选出最好的一个个体作为初始解，这样保证了初始种群的质量。
3、本发明在邻域结构设置中共设计了三种邻域结构，分别是变异邻域结构、交叉邻域结构和插入邻域结构，这样有利于算法在搜索过程中跳出局部最优，避免算法过早收敛。
4、本发明在邻域内进行搜索时，种群利用了保留、交叉和随机等策略进行更新，既保证了种群了多样性同时也遗传了优秀个体，始终保证种群的个体的质量，有效地提高了改进算法的搜索效率。
基于同样的发明构思，本发明又一实施例提供了一种基于改进变邻域搜索和差分进化算法的调度系统，如图2所示，包括：
处理单元201，用于执行以下步骤：
S1、初始化算法的输入参数，包括工件数量n，工件尺寸s，工件基本加工时间p，工件到达时间r，加工机器的容量C，工件从制造商运输到客户所需的时间T，加工工件集合记为J＝{J1,...,Ji,...,Jn}，其中Ji表示第i个工件；
S2、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，种群规模Q，算法初始解Xs，种群优秀个体数量top，全局最优解Xbest＝Xs；
S3、设定邻域结构NK(X)，其中X表示初始解，K表示邻域结构的种类；考虑三种邻域结构，分别为当K＝1时，表示变异邻域结构；当K＝2时，表示交叉邻域结构；当K＝3时，表示插入邻域结构；
S4、初始化局部搜索中种群个体集合S；考虑共有Q个个体，其中第I代种群中的第j个个体定义为 1≤I≤Imax，j＝1,2,...,Q，d＝1,2,...,n，其中 表示在个体 第d个位置上的是工件集中第 个工件；
S5、分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解；
S6、选定邻域结构，定义邻域结构的初始解 在该邻域结构中对种群中的个体进行局部搜索策略，以提高种群个体的质量；
S7、分别计算种群中每个个体的适应度值，从而获得种群中最小适应度值个体Xlocal；
S8、更新算法的全局最优解，判断F(Xlocal)＜F(Xbest)是否成立，若成立则把Xlocal赋值给Xbest，其中F(X)表示个体X的适应度值；
S9、更新初始解，判断F(Xlocal)＜F(Xs)是否成立，若成立则把Xlocal赋值给Xs；
S10、更新邻域结构初始解，判断 是否成立，若成立则把Xlocal赋值给
S11、将I+1赋值给I，判断I≤Imax是否成立，若成立则执行步骤S12，否则执行步骤S13；
S12、判断 是否更新，若更新则返回步骤S6，否则将K+1赋值给K，若K＞3则令K＝1，并返回步骤S6；
S13、算法执行结束；
输出单元202，用于输出全局最优解Xbest的适应度值和工件对应的组批方案。
可选地，所述处理单元201执行步骤S5中分别用三种启发式算法产生三个初始个体，并把该初始解作为初始种群中的三个个体，初始种群中的剩余个体则随机产生，从初始种群中选出最优个体作为初始解，包括：
步骤S51：定义变量j＝1；
步骤S52：判断变量j的值，若等于1则执行步骤S53；若值等于2则执行步骤S54；若等于3则执行步骤S55；若为其他值则执行步骤S56；
步骤S53：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其到达时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S54：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递减进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S55：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件按其加工处理时间非递增进行排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S56：将工件集J＝{J1,...,Ji,...,Jn}中的所有工件进行随机排序，将经过排序后的工件集合J'作为初始种群中的个体
步骤S57：将j+1赋值给j，判断j≤Q是否成立，若成立，则返回步骤S52；否则种群初始化完毕；
步骤S58：根据初始种群，选出其中质量最好的个体，并把该个体赋值给初始解Xs。
可选地，所述处理单元201执行步骤S6中选定邻域结构，包括：
步骤S61：定义变量Xtemp， 这两个变量的各元素含义均与初始解Xs相同，把Xs赋值给Xtemp；
步骤S62：判断变量K的值，若为1则执行步骤S63；若为2则执行步骤S64；若为3则执行步骤S65；
步骤S63：定义变量x'，随机选择Xtemp中的一个元素xrandom，把xrandom的值赋给x'，随机产生一个在区间[1，n]范围内的整数m，并把xrandom的值替换为m，同时把Xtemp中值与m相同的另一个元素值替换为x′；
步骤S64：随机选择Xtemp中的两个元素，并把这两个元素进行交换；
步骤S65：随机选择Xtemp中的两个元素，并把其中的一个元素插入到另一个元素的后一个位置上；
步骤S66：把经过变换的Xtemp赋值给 作为该邻域结构的初始解。
可选地，所述处理单元201执行步骤S6中在该邻域结构中对种群中的个体进行局部搜索策略，包括：
步骤S61’：定义变量 表示存储种群质量前top的个体，Nother表示种群SI剩余其他个体的数量， 表示存储种群SI剩余其他个体集合，Nc表示变异个体的数量，Nr表示随机个体的数量， 表示存储随机个体集合；
步骤S62’：针对种群SI-1，把该种群中适应度前top的个体赋值给 剩余个体赋值给
步骤S63’：取迭代次数I除以Nother的余数，并把该余数赋值给Nc，若Nc＝0，则令Nc＝1；
步骤S64’：在 中随机选择一个个体，针对该个体，随机产生两个位置rand1和rand2，并且rand1≠rand2，对该个体在这两个位置之间的元素进行对称交换处理；
步骤S65’：重复步骤S64’，直至选出Nc个各不相同的个体进行相应的变异操作；
步骤S66’：判断当代的邻域结构是否与上一代相同，若相同，则随机生成Nr个个体，并存储于Sr中；否则执行步骤S67’；
步骤S67’：随机选择邻域结构初始解 中的两个元素，并对这两个元素进行交换产生一个新个体，重复此操作直至产生Nr个个体，并把这些个体存储于Sr中；
步骤S68’：分别将 Sc和Sr中所有的个体都赋值给SI，作为本代更新后的种群。
可选地，所述处理单元201执行步骤S7中计算个体适应度值，包括：
步骤S71：把个体X的工件序列中第一个未分配的工件放置现存的第一个能容纳该工件的批中,若现存的每个批无法容纳该工件,则创建一个容量为C的新批，并把该工件放置新批中；
步骤S72：重复步骤S71，直至个体X中所有的工件都分配到相应的批中，得到一个工件批集合B＝{B1,...,Bi,...,Bl}，l表示批的数量；
步骤S73：将步骤S72中所获得的批集合中的工件批按其批的到达时间非递减进行排序，得到一个经过排序后的批集合B'＝{B'1,...,B'i,...,B'l}，其中B'i表示在加工机器中第l个位置上进行加工的工件批；
步骤S74：定义变量Cmax＝0，表示制造跨度所需时间，循环变量j＝1，批集合B'中工件批B′i的加工时间记为 到达时间记为
步骤S75：判断当前 是否成立，若成立则把 赋值给Cmax，否则将 赋值给Cmax；
步骤S76：将j+1赋值给j，判断j≤l是否成立，若成立则返回步骤S75，否则将将Cmax+T赋值给Cmax；
步骤S77：将步骤S76中最终获得的Cmax值作为该个体X适应度值。
由于本实施例所介绍的基于改进变邻域搜索和差分进化算法的调度系统为可以执行本发明实施例中的基于改进变邻域搜索和差分进化算法的调度方法的系统，故而基于本发明实施例中所介绍的基于改进变邻域搜索和差分进化算法的调度的方法，本领域所属技术人员能够了解本实施例的基于改进变邻域搜索和差分进化算法的调度系统的具体实施方式以及其各种变化形式，所以在此对于该基于改进变邻域搜索和差分进化算法的调度系统如何实现本发明实施例中的基于改进变邻域搜索和差分进化算法的调度方法不再详细介绍。只要本领域所属技术人员实施本发明实施例中基于改进变邻域搜索和差分进化算法的调度方法所采用的系统，都属于本申请所欲保护的范围。
在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。
类似地，应当理解，为了精简本公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。
基于改进变邻域搜索和差分进化算法的调度方法及系统专利购买费用说明
Q：办理专利转让的流程及所需资料
A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。
1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。
2：按规定缴纳著录项目变更手续费。
3：同时提交相关证明文件原件。
4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。
Q:专利著录项目变更费用如何缴交
A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式
Q：专利转让变更，多久能出结果
A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。
动态评分
0.0