专利摘要

本发明实施例涉及一种基于改进禁忌搜索算法的生产与运输协同调度方法及系统，该方法包括：1工件组批；2初始化算法参数；3产生初始解4产生邻域解集；5个体进行变异、交叉和选择；6确定候选解集；7计算个体适应度值；8更新候选解集；9更新禁忌表；10判断算法终止条件是否满足，若满足则输出全局最优解，否则返回步骤4；本发明主要是针对多制造商情形下的生产与运输协同批调度问题，求得该问题的近似最优解，即获得一个科学有效的生产与运输协同调度方案，从而可以提高企业在生产与运输两个阶段中实现整体效益最大化，并为企业的客户提供优质服务，提升企业的核心竞争力。

权利要求

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

S1、将工件集合J＝{J1,...,Ji,...,Jn}中所有工件按基本加工时间非递增进行排序，得到经过排序后的工件集合J'＝{J′1,...,J′i,...,J'n}；其中Ji表示工件集合中第i个工件，J′i表示排序后工件集合中第i个工件；

S2、根据工件集合J'，在现存的批中选出能容纳第一个未分配的工件的所有批，从已选出的批中获取剩余空间最小的批，将J'中第一个未分配的工件放置于最终选出的批中，并将该工件从工件列表中删除；

S3、重复步骤S2，直至工件集J'中所有工件都分配到相应的批中，从而形成批集合记为B＝{b1,...,bd,...,bl}；其中bd表示第d个批次，l表示批次的数量；

S4、初始化算法的输入参数，所述输入参数包括工件数量n，工件尺寸s，工件基本加工时间p，加工机器数量m，工件到达加工机器所需时间r，每个批次所能容纳的最大工件数量C和处理速度v，工件从各加工机器运输到客户所需的时间T；

S5、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，交叉概率CR，算法初始解Xs＝{x1,...,xd,...,xl}，其中xd表示第d个批次被分配到第xd个机器，全局最优解Xbest＝Xs；

S6、根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)；

S7、判断List(Xs)是否为空集，若为空集则执行步骤S12；否则选出List(Xs)中的最优个体Y；

S8、判断个体Y是否优于全局最优解Xbest，若优于Xbest，则将Y赋值给Xbest，并执行步骤S11；否则执行步骤S9；

S9、判断步骤S7获得的个体Y是否符合禁忌表TSList中的禁忌规则，若符合则执行步骤S10；否则执行步骤S11；

S10、更新候选解集List(Xs)，把List(Xs)中的个体Y移出该集合，并返回步骤S7；

S11、判断是否获得新个体Y，若个体Y更新，则把Y赋值给Xs；

S12、根据初始解Xs更新禁忌表TSList；

S13、将I+1赋值给I，判断I≤Imax是否成立，若成立则返回步骤S6；否则算法执行结束，输出最优解Xbest适应度值，工件集中工件的组批方案以及工件批在各加工机器上的分配方案；

所述步骤S5中设定算法初始解Xs＝{x1,...,xd,...,xl}，包括：

步骤S51：将批集合B＝{b1,...,bd,...,bl}中所有的批按其加工长度非递增进行排序，形成经过排序后的批集合记为B'＝{b′1,...,b'd,...,b′l}；

步骤S52：将机器按其加工速度非递增进行排序，得到经过排序后的机器集合M＝{M1,...,Mk,...,Mm}，Mk表示加工处理速度处于第k位且编号为Mk的加工机器；

步骤S53：定义变量d＝1，k＝1；

步骤S54：则把Mk赋值给xd；

步骤S55：将k+1赋值给k，判断k≤m是否成立，若成立，则执行步骤S56；否则，令k＝1并执行步骤S56；

步骤S56：把d+1赋值给d，判断d≤l是否成立，若成立，则返回步骤S54；否则，以X＝{x1,...,xd,...,xl}作为初始解Xs。

2.根据权利要求1所述的方法，其特征在于，步骤S6中根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)，包括：

步骤S61：产生邻域解集，邻域解中共考虑W个个体，其解集记为N(Xs)＝{X1,...,Xj,...,XW}，其中Xj表示邻域解中的第j个个体，该个体由初始解Xs随机交换I次获得；

步骤S62：定义变量N'(Xs)＝{X′1,...,X'j,...,X'W}，该变量与N(Xs)具有相同的含义，并把N(Xs)中的个体赋值给N'(Xs)，令变量j＝1；

步骤S63：随机产生两个在区间[1，W]范围内的随机数分别记为index1和index2，并且index1、index2和j各不相同；

步骤S64：定义变量Vj和Uj，Vj和Uj与个体Xj具有相同维度，令变量d＝1，产生一个在区间(0，1]范围内的随机数random，并把随机数赋值给变量F；

步骤S65：利用公式Vjd＝Xbd+F×(Xindex1d-Xindex2d)更新Vjd，其中Xbd表示全局最优解中第d个元素；

步骤S66：随机产生一个在区间(0，1]范围内的随机数rand，判断rand≤CR是否成立，若成立则把Vjd赋值给Ujd；否则把Xjd赋值给Ujd；

步骤S67：把d+1赋值给d，判断d≤l是否成立，若成立则返回步骤S65，否则执行步骤S68；

步骤S68：分别计算个体X′j和中间体Uj适应度值F(X′j)和F(Uj)，并比较F(X′j)和F(Uj)，若F(X′j)≤F(Uj)则把Uj赋值给个体Xj；

步骤S69：把j+1赋值给j，判断j≤W是否成立，若成立则返回步骤S63；否则执行步骤S610；

步骤S610：在候选解集中考虑Q个个体，候选解集记为List(Xs)，把N(Xs)中W个个体按其适应度值非递减进行排序，从序列中选出位于前Q个位置的个体，并将选出的Q个个体赋值给List(Xs)。

3.根据权利要求1所述的方法，其特征在于，步骤S12中根据初始解Xs更新禁忌表TSList，包括：

步骤S121：根据初始解Xs确定第k个机器上的工件集合Bk；

步骤S122：从Bk中选出个工件批形成批集合B'k，变量|Bk|表示集合Bk中工件批的数量；

步骤S123：重复步骤S122，直至各机器都已选出集合，从而形成一个禁忌表元素记为S＝{B′1,...,B'k,...,B'm}；

步骤S124：判断S与禁忌表现存的所有元素是否相同，若存在有元素与S相同，则返回步骤S122；

步骤S125：把S插入到禁忌表中，然后把禁忌表中最先插入的元素移除。

4.根据权利要求1所述的方法，其特征在于，步骤S13中输出个体的适应度值，包括：

步骤S131：遍历个体X＝{x1,...,xd,...,xl}中各元素，定义变量d＝1，变量Bk表示第k个机器上被分配到的工件批的集合，变量|Bk|表示集合Bk中工件批的数量；

步骤S132：判断1≤xd≤m是否满足，如果溢出该范围则执行步骤S133；否则执行步骤S134；

步骤S133：产生一个在区间[1，m]范围内的随机整数记为random，并把random赋值给xd；

步骤S134：判断xd＝k是否成立，其中k∈{1,...,m}，若成立则把bd放置于Bk中；

步骤S135：把d+1赋值给d，判断d≤l是否成立，若成立则返回步骤S132；否则执行步骤S136；

步骤S136：定义变量k＝1；

步骤S137：定义变量j＝1，Ck＝0，Ck表示第k个机器的完工时间；

步骤S138：把赋值给Ck；其中表示第k个机器上第j个批次的处理时间；

步骤S139：把j+1赋值给j，判断j≤|Bk|是否成立，若成立则返回步骤S138；否则把Ck+rk+Tk赋值给Ck；

步骤S1310：把k+1赋值给k，判断k≤|Bk|是否成立，若成立则返回步骤S137；否则可获得各机器制造跨度的集合记为C*＝{C1,...,Ck,...,Cm}；

步骤S1311：根据步骤S1310中获得的制造跨度集合C*，选出其中最大的元素，并把该元素赋值给Cmax，即Cmax＝max{C1,...,Ck,...,Cm}，变量Cmax表示个体X适应度值。

5.一种基于改进禁忌搜索算法的生产运输协同调度系统，其特征在于，包括：

处理单元，用于执行以下步骤：

S1、将工件集合J＝{J1,...,Ji,...,Jn}中所有工件按基本加工时间非递增进行排序，得到经过排序后的工件集合J'＝{J′1,...,J′i,...,J'n}；其中Ji表示工件集合中第i个工件，J′i表示排序后工件集合中第i个工件；

S2、根据工件集合J'，在现存的批中选出能容纳第一个未分配的工件的所有批，从已选出的批中获取剩余空间最小的批，将J'中第一个未分配的工件放置于最终选出的批中，并将该工件从工件列表中删除；；

S3、重复步骤S2，直至工件集J'中所有工件都分配到相应的批中，从而形成批集合记为B＝{b1,...,bd,...,bl}，其中bd表示第d个批次，l表示批次的数量；

S4、初始化算法的输入参数，所述输入参数包括工件数量n，工件尺寸s，工件基本加工时间p，加工机器数量m，工件到达加工机器所需时间r，每个批次所能容纳的最大工件数量C和处理速度v，工件从各加工机器运输到客户所需的时间T；

S5、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，交叉概率CR，算法初始解Xs＝{x1,...,xd,...,xl}，其中xd表示第d个批次被分配到第xd个机器，全局最优解Xbest＝Xs；

S6、根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)；

S7、判断List(Xs)是否为空集，若为空集则执行步骤S12；否则选出List(Xs)中的最优个体Y；

S8、判断个体Y是否优于全局最优解Xbest，若优于Xbest，则将Y赋值给Xbest，并执行步骤S11；否则执行步骤S9；

S9、判断步骤S7获得的个体Y是否符合禁忌表TSList中的禁忌规则，若符合则执行步骤S10；否则执行步骤S11；

S10、更新候选解集List(Xs)，把List(Xs)中的个体Y移出该集合，并返回步骤S7；

S11、判断是否获得新个体Y，若个体Y更新，则把Y赋值给Xs；

S12、根据初始解Xs更新禁忌表TSList；

S13、将I+1赋值给I，判断I≤Imax是否成立，若成立则返回步骤S6；否则算法执行结束；

输出单元，用于输出最优解Xbest适应度值，工件集中工件的组批方案以及工件批在各加工机器上的分配方案；

所述所述处理模块执行步骤S5中设定算法初始解Xs＝{x1,...,xd,...,xl}，包括：

步骤S51：将批集合B＝{b1,...,bd,...,bl}中所有的批按其加工长度非递增进行排序，形成经过排序后的批集合记为B'＝{b′1,...,b'd,...,b′l}；

步骤S52：将机器按其加工速度非递增进行排序，得到经过排序后的机器集合M＝{M1,...,Mk,...,Mm}，Mk表示加工处理速度处于第k位且编号为Mk的加工机器；

步骤S53：定义变量d＝1，k＝1；

步骤S54：则把Mk赋值给xd；

步骤S55：将k+1赋值给k，判断k≤m是否成立，若成立，则执行步骤S56；否则，令k＝1并执行步骤S56；

步骤S56：把d+1赋值给d，判断d≤l是否成立，若成立，则返回步骤S54；否则，以X＝{x1,...,xd,...,xl}作为初始解Xs。

6.根据权利要求5所述的系统，其特征在于，所述处理模块执行步骤S6中根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)，包括：

步骤S61：产生邻域解集，邻域解中共考虑W个个体，其解集记为N(Xs)＝{X1,...,Xj,...,XW}，其中Xj表示邻域解中的第j个个体，该个体由初始解Xs随机交换I次获得；

步骤S62：定义变量N'(Xs)＝{X′1,...,X'j,...,X'W}，该变量与N(Xs)具有相同的含义，并把N(Xs)中的个体赋值给N'(Xs)，令变量j＝1；

步骤S63：随机产生两个在区间[1，W]范围内的随机数分别记为index1和index2，并且index1、index2和j各不相同；

步骤S64：定义变量Vj和Uj，Vj和Uj与个体Xj具有相同维度，令变量d＝1，产生一个在区间(0，1]范围内的随机数random，并把随机数赋值给变量F；

步骤S65：利用公式Vjd＝Xbd+F×(Xindex1d-Xindex2d)更新Vjd，其中Xbd表示全局最优解中第d个元素；

步骤S66：随机产生一个在区间(0，1]范围内的随机数rand，判断rand≤CR是否成立，若成立则把Vjd赋值给Ujd；否则把Xjd赋值给Ujd；

步骤S67：把d+1赋值给d，判断d≤l是否成立，若成立则返回步骤S65，否则执行步骤S68；

步骤S68：分别计算个体X′j和中间体Uj适应度值F(X′j)和F(Uj)，并比较F(X′j)和F(Uj)，若F(X′j)≤F(Uj)则把Uj赋值给个体Xj；

步骤S69：把j+1赋值给j，判断j≤W是否成立，若成立则返回步骤S63；否则执行步骤S610；

步骤S610：在候选解集中考虑Q个个体，候选解集记为List(Xs)，把N(Xs)中W个个体按其适应度值非递减进行排序，从序列中选出位于前Q个位置的个体，并将选出的Q个个体赋值给List(Xs)。

7.根据权利要求5所述的系统，其特征在于，所述处理模块执行步骤S12中根据初始解Xs更新禁忌表TSList，包括：

步骤S121：根据初始解Xs确定第k个机器上的工件集合Bk；

步骤S122：从Bk中选出个工件批形成批集合B'k，变量|Bk|表示集合Bk中工件批的数量；

步骤S123：重复步骤S122，直至各机器都已选出集合，从而形成一个禁忌表元素记为S＝{B1',...,B'k,...,B'm}；

步骤S124：判断S与禁忌表现存的所有元素是否相同，若存在有元素与S相同，则返回步骤S122；

步骤S125：把S插入到禁忌表中，然后把禁忌表中最先插入的元素移除。

8.根据权利要求5所述的系统，其特征在于，所述处理模块执行步骤S13中输出个体的适应度值，包括：

步骤S131：遍历个体X＝{x1,...,xd,...,xl}中各元素，定义变量d＝1，变量Bk表示第k个机器上被分配到的工件批的集合，变量|Bk|表示集合Bk中工件批的数量；

步骤S132：判断1≤xd≤m是否满足，如果溢出该范围则执行步骤S133；否则执行步骤S134；

步骤S133：产生一个在区间[1，m]范围内的随机整数记为random，并把random赋值给xd；

步骤S134：判断xd＝k是否成立，其中k∈{1,...,m}，若成立则把bd放置于Bk中；

步骤S135：把d+1赋值给d，判断d≤l是否成立，若成立则返回步骤S132；否则执行步骤S136；

步骤S136：定义变量k＝1；

步骤S137：定义变量j＝1，Ck＝0，Ck表示第k个机器的完工时间；

步骤S138：把赋值给Ck；表示第k个机器上第j个批次的处理时间；

步骤S139：把j+1赋值给j，判断j≤|Bk|是否成立，若成立则返回步骤S138；否则把Ck+rk+Tk赋值给Ck；

步骤S1310：把k+1赋值给k，判断k≤|Bk|是否成立，若成立则返回步骤S137；否则可获得各机器制造跨度的集合记为C*＝{C1,...,Ck,...,Cm}；

步骤S1311：根据步骤S1310中获得的制造跨度集合C*，选出其中最大的元素，并把该元素赋值给Cmax，即Cmax＝max{C1,...,Ck,...,Cm}，变量Cmax表示个体X适应度值。

说明书

技术领域

本发明实施例涉及软件技术领域，具体涉及一种基于改进禁忌搜索算法的生产运输协同调度方法及系统。

背景技术

批调度问题作为一类典型的组合优化问题，广泛存在于现代的生产活动中，如交通运输，生产运输以及船闸调度等领域。而在同类平行机批调度问题中，各机器的处理能力相同但处理速度不同，批处理机在能力范围内可以同时加工处理多个工件。在当今的云制造主流模式背景下，为充分利用现有的生产资源从而为客户提供优质的服务，针对客户同一个订单，企业间以合作形式共同完成该订单生产任务。设计科学合理的分布式同类机生产调度方案不仅可以使得社会的生产资源得以充分利用，还可以促进企业生产能力的提高。因此，针对分布式同类平行机批调度问题，如何确定一个合理有效的生产调度方案成为企业亟待解决的问题，对该类问题的研究具有重要的实际意义。

在以往的研究中，智能算法和启发式算法被广泛应用于解决复杂情形下的生产运输协同调度问题。一种研究是针对差异工件相同平行机批调度问题进行研究，工件具有不同的尺寸和加工时间，并设计了混合模拟退火和遗传算法解决该问题；另一种研究是考虑工件含不同加工时间，到达时间，截止时间和尺寸，并设计了群算法解决该问题；还有一种研究是考虑了分布式环境下工件动态到达各批处理机，且加工前后都有运输时间，针对该问题提出了若干个启发式算法。本文针对分布式制造商的同类平行机生产与运输协同批调度问题，设计了改进的禁忌搜索算法，通过该算法确定各工件批在机器上的分配方案，从而获得一个使得生产与运输两阶段整体效益最大化的生产与运输协同调度方案。禁忌搜索算法的一般步骤包括：(1)生成初始解；(2)产生邻域解；(3)确定候选解；(4)选出候选解集中满足禁忌规则的最优个体；(5)更新候选集；(6)更新禁忌表；(7)更新全局最优解。通过重复以上步骤在整个解空间搜索并获取最优解，即最优的生产与运输协同调度方案。

然而，在进行发明创造的过程中发明人发现，现有技术存在以下缺陷：(1)在研究问题上，以往研究的关注点主要集中在相同平行机上，而对同类机上批调度问题的研究相对较少，并且在同类机情形下同时考虑生产与运输的研究成果较少。在实际生产活动中，存在着同一个订单生产任务由多个企业共同完成，由于各企业的生产条件不同，所以企业的加工机器处理速度并不完全相同。在解决此类调度问题时，不仅需要考虑工件的差异性，同时还需要考虑机器的差异对问题所优化制造时间跨度的影响。(2)在研究方法上，候选解的确定，禁忌规则，禁忌表长度等，这些因素都影响着禁忌搜索算法的性能。

发明内容

本发明实施例提供了一种基于改进禁忌搜索算法的生产运输协同调度方法及系统，用以解决上述至少一个技术问题。

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

S1、将工件集合J＝{J1,...,Ji,...,Jn}中所有工件按基本加工时间非递增进行排序，得到经过排序后的工件集合J'＝{J'1,...,J'i,...,J'n}；

S2、根据工件集合J'，在现存的批中选出能容纳第一个未分配的工件的所有批，从已选出的批中获取剩余空间最小的批，将J'中第一个未分配的工件放置于最终选出的批中，并将该工件从工件列表中删除；

S3、重复步骤S2，直至工件集J'中所有工件都分配到相应的批中，从而形成批集合记为B＝{b1,...,bd,...,bl}；

S4、初始化算法的输入参数，所述输入参数包括工件数量n，工件尺寸s，工件基本加工时间p，加工机器数量m，工件到达加工机器所需时间r，加工机器的容量C和处理速度v，工件从各加工机器运输到客户所需的时间T；

S5、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，交叉概率CR，算法初始解Xs＝{x1,...,xd,...,xl}，其中xd表示第d个批所分配到的机器，全局最优解Xbest＝Xs；

S6、根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)；

S7、判断List(Xs)是否为空集，若为空集则执行步骤S12；否则选出List(Xs)中的最优个体Y；

S8、判断个体Y是否优于全局最优解Xbest，若优于Xbest，则将Y赋值给Xbest，并执行步骤S11；否则执行步骤S9；

S9、判断步骤S7获得的个体Y是否符合禁忌表TSList中的禁忌规则，若符合则执行步骤S10；否则执行步骤S11；

S10、更新候选解集List(Xs)，把List(Xs)中的个体Y移出该集合，并返回步骤S7；

S11、判断是否获得新个体Y，若个体Y更新，则把Y赋值给Xs；

S12、根据初始解Xs更新禁忌表TSList；

S13、将I+1赋值给I，判断I≤Imax是否成立，若成立则返回步骤S6；否则算法执行结束，输出最优解Xbest适应度值，工件集中工件的组批方案以及工件批在各加工机器上的分配方案。

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

处理单元，用于执行以下步骤：

S1、将工件集合J＝{J1,...,Ji,...,Jn}中所有工件按基本加工时间非递增进行排序，得到经过排序后的工件集合J'＝{J'1,...,J'i,...,J'n}；

S2、根据工件集合J'，在现存的批中选出能容纳第一个未分配的工件的所有批，从已选出的批中获取剩余空间最小的批，将J'中第一个未分配的工件放置于最终选出的批中，并将该工件从工件列表中删除；

S3、重复步骤S2，直至工件集J'中所有工件都分配到相应的批中，从而形成批集合记为B＝{b1,...,bd,...,bl}；

S4、初始化算法的输入参数，所述输入参数包括工件数量n，工件尺寸s，工件基本加工时间p，加工机器数量m，工件到达加工机器所需时间r，加工机器的容量C和处理速度v，工件从各加工机器运输到客户所需的时间T；

S5、设定算法的执行参数，所述执行参数包括最大迭代次数Imax，当前迭代次数I＝1，交叉概率CR，算法初始解Xs＝{x1,...,xd,...,xl}，其中xd表示第d个批所分配到的机器，全局最优解Xbest＝Xs；

S6、根据初始解Xs产生邻域解集N(Xs)，对N(Xs)中的个体进行更新，确定候选解集List(Xs)；

S7、判断List(Xs)是否为空集，若为空集则执行步骤S12；否则选出List(Xs)中的最优个体Y；

S8、判断个体Y是否优于全局最优解Xbest，若优于Xbest，则将Y赋值给Xbest，并执行步骤S11；否则执行步骤S9；

S9、判断步骤S7获得的个体Y是否符合禁忌表TSList中的禁忌规则，若符合则执行步骤S10；否则执行步骤S11；

S10、更新候选解集List(Xs)，把List(Xs)中的个

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

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

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

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

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

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

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

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

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

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

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