基于改进人工免疫算法的平行机成组调度方法及系统

摘要

本发明实施例涉及一种基于人工免疫算法的平行机成组调度方法及系统，该方法包括：1设定算法参数；2随机生成初始解；3计算适应度值并确定全局最优解；4计算抗体浓度；5计算每个个体的选择概率；6交叉变异；7变邻域搜索；8更新种群；9判断终止条件是否满足，如果满足则输出全局最优解，否则返回步骤3；本发明能针对恶化工件情形下的平行机成组调度问题，求得近似最优解，本发明中的求解模型更加贴近实际生产过程，有利于在复杂生产环境中提高企业生产效率，优化企业服务质量。

说明书

技术领域

本发明实施例涉及软件技术领域，具体涉及一种基于改进人工免疫算法的平行机成组调度方法及系统。

背景技术

批调度问题广泛存在于现代加工制造的各行各业，例如半导体制造、货物运输、航空工业等。不同于经典的调度问题中同一时刻一台机器只能加工一个工件，批处理机可以同时加工一批工件，有助于生产效率的提升。另外，在多品种小批量的生产环境下，为了缩短加工时间，企业可以使用成组技术进行混流生产，由此而来的调度问题称为成组调度问题。批调度和成组调度的有机结合称为成组批调度问题，有效地进行成组批调度有助于企业节约资源、提高效率、增强核心竞争力。因此，对成组批调度问题进行研究具有很强的现实意义。

在以往的研究中，智能算法被广泛应用于解决批调度和成组调度问题中，一部分学者提出了一种蚁群算法求解具有差异工件尺寸的平行机批调度问题，实验结果验证了该算法的有效性。一部分学者利用动态规划和遗传算法的混合算法，求解工件动态到达的批处理问题，实验结果显示所提算法优于GA和BEST算法。还有学者提出了一种混合遗传算法求解流水车间的成组调度问题，并通过实验验证了该算法的性能。

然而，在进行发明创造的过程中发明人发现，现有技术存在以下缺陷：在以往的研究中，对批调度的研究主要集中在单机和平行机问题；对成组调度的研究主要集中在单机、流水车间问题。但是，对于工件恶化情形下的平行机成组批调度问题的研究几乎空白。而在实际加工过程中，工件恶化往往贯穿于整个加工过程中，在批调度问题中广泛存在。此外，多品种、小批量的生产需求也使成组调度实际存在于平行机批调度的加工过程中，不可忽视。此类批调度问题更加复杂，它需要同时考虑工件恶化、组在机器上的分配方式、组的加工顺序、工件的组批方式以及工件的加工顺序等诸多要素。除此之外，在方法上，人工免疫算法也存在着局部收敛性差和容易早熟等缺点，而且在基于信息熵计算抗体亲和度和抗体浓度的过程中也存在问题。无法为特定的调度问题提供持续稳定可靠的解决方案。

发明内容

本发明实施例提供了一种基于改进人工免疫算法的平行机成组调度方法及系统，用以解决上述至少一个技术问题。

第一方面，本发明实施例提供一种基于改进人工免疫算法的平行机成组调度方法，包括：

S1、输入每个机器的容量和工件的加工时间，设定改进人工免疫算法参数，包括最大迭代次数t_max，全局最优解gbest，变异概率PR，抗体区间(pmin,pmax)，浓度限制CM，迭代次数t＝1；

S2、初始化种群；考虑共有poplong个抗体，第l个抗体的基因定义为其中表示第l个抗体在第i维上的基因，表明第i组工件被分配至第个机器；

S3、计算种群中每个抗体的适应度值，更新全局最优解gbest；

S4、计算种群中的抗体浓度con；

S5、判断con≤CM*poplong是否成立，若成立，则计算每个抗体的选择概率其中fit_l表示第l个抗体的适应度值，即制造跨度，fit_l越小说明解越优；否则，计算每个抗体的概率为

S6、设定变量h＝1；

S7、从种群以概率pro_l选择第l个抗体X_l，判断rand＜PR是否成立，其中rand为[0,1]之间的随机数，若成立；则执行变异操作产生一个新的抗体作为新种群中的第h个个体；否则，执行交叉操作产生一个新的抗体作为新种群中的第h个个体；

S8、对第h个个体执行变邻域搜索操作，令h＝h+1，判断h≤poplong是否成立，若成立，执行步骤S7；否则，执行步骤S9；

S9、令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法并输出全局最优解gbest，输出最优的组内组批和加工顺序，组分配和每个机器上的组加工顺序。

第二方面，本发明实施例提供一种基于改进人工免疫算法的平行机成组调度系统，包括：

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

S1、输入每个机器的容量和工件的加工时间，设定改进人工免疫算法参数，包括最大迭代次数t_max，全局最优解gbest，变异概率PR，抗体区间(pmin,pmax)，浓度限制CM，迭代次数t＝1；

S2、初始化种群；考虑共有poplong个抗体，第l个抗体的基因定义为其中表示第l个抗体在第i维上的基因，表明第i组工件被分配至第个机器；

S3、计算种群中每个抗体的适应度值，更新全局最优解gbest；

S4、计算种群中的抗体浓度con；

S5、判断con≤CM*poplong是否成立，若成立，则计算每个抗体的选择概率其中fit_l表示第l个抗体的适应度值，即制造跨度，fit_l越小说明解越优；否则，计算每个抗体的概率为

S6、设定变量h＝1；

S7、从种群以概率pro_l选择第l个抗体X_l，判断rand＜PR是否成立，其中rand为[0,1]之间的随机数，若成立。则执行变异操作产生一个新的抗体作为新种群中的第h个个体；否则，执行交叉操作产生一个新的抗体作为新种群中的第h个个体；

S8、对第h个个体执行变邻域搜索操作，令h＝h+1，判断h≤poplong是否成立，若成立，执行步骤S7；否则，执行步骤S9；

S9、令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法；

输出单元，用于输出全局最优解gbest，输出最优的组内组批和加工顺序，组分配和每个机器上的组加工顺序。

本发明能针对恶化工件情形下的平行机成组调度问题，求得近似最优解，本发明中的求解模型更加贴近实际生产过程，有利于在复杂生产环境中提高企业生产效率，优化企业服务质量。

附图说明

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

图1是本发明实施例提供的平行机成组批调度问题示意图；

图2是本发明实施例提供的一种基于改进人工免疫算法的平行机成组调度方法流程图；

图3是本发明实施例提供的一种基于改进人工免疫算法的平行机成组调度系统结构示意图。

具体实施方式

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

本发明实施例能够解决恶化情形下的平行机成组批调度问题，确定每组工件将分配至哪个机器，以及该机器上的工件的组批方式，工件加工顺序和组的加工顺序，以最小化制造跨度。基于问题所特有的性质，提出有效的算法，解决该组合优化问题，推动生产效率的提升。

为便于理解，下面首先对本发明实施例要解决问题进行详细说明，具体来说：

如图1所示，恶化情形下的平行机成组批调度问题，目标为最小化制造跨度。该问题描述如下：给定包含n个组的任务集合G＝{G₁,G₂,G₃,···,G_n}需要在m个平行批处理机上进行加工。每个组内不同的工件具有不同的一般加工时间，相同的单位尺寸和相同的恶化率，第i组内第j个工件的实际加工时间表示为其中一般加工时间由p_ij(i＝1,2,···,n)表示，b表示恶化率，t表示工件的开始加工时间。每个批和每个组加工之前分别存在装置时间θ_b和θ_g。问题假设如下：

(1)所有工件和机器在零时刻准备完毕，工件具有单位尺寸和不同的加工时间，各批处理机具有相同的容量和加工速度；

(2)不同组的工件是不相容的，在满足机器容量约束的条件下只能将多个同组工件放入同一批中进行加工，批的加工时间由批中加工时间最长的工件所决定；

(3)批的加工过程不允许中断，中途不允许工件退出或加入。

基于此，本发明的一个实施例提供了一种基于改进人工免疫算法的平行机成组调度方法，如图2所示，包括：

S1、输入每个机器的容量和工件的加工时间，设定改进人工免疫算法参数，包括最大迭代次数t_max，全局最优解gbest，变异概率PR，抗体区间(pmin,pmax)，浓度限制CM，迭代次数t＝1；

S2、初始化种群；考虑共有poplong个抗体，第l个抗体的基因定义为其中表示第l个抗体在第i维上的基因，表明第i组工件被分配至第个机器；

S3、计算种群中每个抗体的适应度值，更新全局最优解gbest；

S4、计算种群中的抗体浓度con；

S5、判断con≤CM*poplong是否成立，若成立，则计算每个抗体的选择概率其中fit_l表示第l个抗体的适应度值，即制造跨度，fit_l越小说明解越优；否则，计算每个抗体的概率为

S6、设定变量h＝1；

S7、从种群以概率pro_l选择第l个抗体X_l，判断rand＜PR是否成立，其中rand为[0,1]之间的随机数，若成立；则执行变异操作产生一个新的抗体作为新种群中的第h个个体；否则，执行交叉操作产生一个新的抗体作为新种群中的第h个个体；

S8、对第h个个体执行变邻域搜索操作，令h＝h+1，判断h≤poplong是否成立，若成立，执行步骤S7；否则，执行步骤S9；

S9、令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法并输出全局最优解gbest，输出最优的组内组批和加工顺序，组分配和每个机器上的组加工顺序。

本发明能针对恶化工件情形下的平行机成组调度问题，求得近似最优解，本发明中的求解模型更加贴近实际生产过程，有利于在复杂生产环境中提高企业生产效率，优化企业服务质量。

在具体实施时，步骤S3中计算种群中每个抗体的适应度值，包括：

步骤S31：在每组内将所有工件按加工时间非减序进行排列,得到排序后的工件集合；

步骤S32：将前组成第一批，之后将剩余工件依次每c个工件组成一批，其中N_i表示第i组内的工件个数，c表示机器同时能加工的工件个数，表示不小于的最小整数；

步骤S33：按照抗体编码将各组工件分配至相应的机器；

步骤S34：对每个组计算

其中m_i表示第i组中批的个数，θ_b和θ_g分别表示批和组的装置时间，b表示工件的恶化率；

步骤S35：按照ρ[G_i]非增序在每个机器上组的加工对应的组；

步骤S36：返回C_max＝max_k∈m{C_k}，其中，C_k表示第k个机器的完工时间，算法结束。

在具体实施时，所述步骤S4包括：

步骤S41：令l＝1，con＝0；

步骤S42：判断是否成立，若成立，则令con＝con+1；

步骤S43：令l＝l+1，判断l≤poplong是否成立，若成立，则执行步骤S42；否则，结束计算过程。

在具体实施时，所述步骤S7包括：

步骤S71：生成0到1之间的随机数rand，设定l＝1，sum＝0；

步骤S72：令sum＝sum+pro_l，判断sum＜rand是否成立，若成立，则执行步骤S74；否则，执行步骤S73；

步骤S73：令l＝l+1，返回步骤S72；

步骤S74：生成0到1之间的随机数rand1，判断rand1≤PR是否成立，若成立，随机选取抗体中的一个基因，以1到n之间的随机整数替代之，产生一个新的抗体，结束搜索；否则，随机选取抗体中的一个基因从种群中随机选取另一个抗体，用该抗体上第i位置以后的序列替代原抗体中第i位置以后的序列，产生一个新的抗体，结束搜索。

在具体实施时，所述步骤S8包括：

步骤S81、设定参数s＝1，将基本步骤7的得到的新抗体作为初始解；

步骤S82、判断s＝1是否成立，若成立，则随机选取抗体中的两个基因，交换这两个基因的位置，得到新的个体X'；否则，执行步骤S83；

步骤S83、判断s＝2是否成立，若成立，则随机选取抗体中的两个基因，用1到n之间的随机数替代该基因对应的数值，得到新的个体X'；否则，执行步骤S84；

步骤S84、判断s＝3是否成立，若成立，则随机选取抗体中的两个基因，将这两个基因间的序列按照原顺序的倒序排列，得到新的个体X'；

步骤S85、计算个体X'的适应度，判断其是否优于其原个体，若是，则替代原个体成为新的初始解，令s＝1，执行步骤2；否则，令s＝s+1，执行步骤S86；

步骤S86、判断s＜4是否成立，若成立，执行步骤3；否则，结束搜索。

本发明的有益效果如下：

1、本发明针对工件恶化情形下的平行机成组批调度问题，通过改进的人工免疫算法，首先将组以编码的方式，分配到各个机器上，然后依据问题的性质提出组内的分批和加工策略，计算每个组的属性值；再根据组的属性对组的加工顺序进行安排；基于个体的适应度对种群执行交叉变异操作；通过变邻域搜索提高每个新产生个体的质量；通过重复迭代，实现对种群的不断更新，最终求的最优解。改进的人工免疫算法在收敛速度和收敛结果上，是一种效率很高的算法；通过该算法，解决了工件恶化情形下的平行机成组批调度问题，提高了企业的生产效率，加速了企业生产进度，优化了企业的服务质量。

2、本发明在提出了恶化情形下每组工件内部确定最优组批方式和加工顺序的最优算法，并设计了能够最大化每个机器生产效率的最优调度算法，能够保证充分利用每个机器的生产能力，在每个机器上实现加工进度的最优化。

3、本发明针对人工免疫算法局部收敛性不足和容易早熟的问题，结合在该问题中的具体应用，设计了抗体浓度的判断准则，并通过变邻域搜索操作对新个体进行改进，保证新个体的质量，不仅有效地提高了算法的局部收敛能力，也在一定程度上提升了种群的多样性和算法的搜索效率。

基于同样的发明构思，本发明又一实施例提供了一种基于改进人工免疫算法的平行机成组调度系统，如图3所示，包括：

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

S1、输入每个机器的容量和工件的加工时间，设定改进人工免疫算法参数，包括最大迭代次数t_max，全局最优解gbest，变异概率PR，抗体区间(pmin,pmax)，浓度限制CM，迭代次数t＝1；

S2、初始化种群；考虑共有poplong个抗体，第l个抗体的基因定义为其中表示第l个抗体在第i维上的基因，表明第i组工件被分配至第个机器；

S3、计算种群中每个抗体的适应度值，更新全局最优解gbest；

S4、计算种群中的抗体浓度con；

S5、判断con≤CM*poplong是否成立，若成立，则计算每个抗体的选择概率其中fit_l表示第l个抗体的适应度值，即制造跨度，fit_l越小说明解越优；否则，计算每个抗体的概率为

S6、设定变量h＝1；

S7、从种群以概率pro_l选择第l个抗体X_l，判断rand＜PR是否成立，其中rand为[0,1]之间的随机数，若成立。则执行变异操作产生一个新的抗体作为新种群中的第h个个体；否则，执行交叉操作产生一个新的抗体作为新种群中的第h个个体；

S8、对第h个个体执行变邻域搜索操作，令h＝h+1，判断h≤poplong是否成立，若成立，执行步骤S7；否则，执行步骤S9；

S9、令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法；

输出单元202，用于输出全局最优解gbest，输出最优的组内组批和加工顺序，组分配和每个机器上的组加工顺序。

可选地，处理单元201执行步骤S3中计算种群中每个抗体的适应度值，可以包括：

步骤S31：在每组内将所有工件按加工时间非减序进行排列,得到排序后的工件集合；

步骤S32：将前组成第一批，之后将剩余工件依次每c个工件组成一批，其中N_i表示第i组内的工件个数，c表示机器同时能加工的工件个数，表示不小于的最小整数；

步骤S33：按照抗体编码将各组工件分配至相应的机器；

步骤S34：对每个组计算

其中m_i表示第i组中批的个数，θ_b和θ_g分别表示批和组的装置时间，b表示工件的恶化率；

步骤S35：按照ρ[G_i]非增序在每个机器上组的加工对应的组；

步骤S36：返回C_max＝max_k∈m{C_k}，其中，C_k表示第k个机器的完工时间，算法结束。

可选地，处理单元201执行所述步骤S4可以包括：

步骤S41：令l＝1，con＝0；

步骤S42：判断是否成立，若成立，则令con＝con+1；

步骤S43：令l＝l+1，判断l≤poplong是否成立，若成立，则执行步骤S42；否则，结束计算过程。

可选地，处理单元201执行所述步骤S7可以包括：

步骤S71：生成0到1之间的随机数rand，设定l＝1，sum＝0；

步骤S72：令sum＝sum+pro_l，判断sum＜rand是否成立，若成立，则执行步骤S74；否则，执行步骤S73；

步骤S73：令l＝l+1，返回步骤S72；

步骤S74：生成0到1之间的随机数rand1，判断rand1≤PR是否成立，若成立，随机选取抗体中的一个基因，以1到n之间的随机整数替代之，产生一个新的抗体，结束搜索；否则，随机选取抗体中的一个基因x_lⁱ，从种群中随机选取另一个抗体，用该抗体上第i位置以后的序列替代原抗体中第i位置以后的序列，产生一个新的抗体，结束搜索。

可选地，处理单元201执行所述步骤S8可以包括：

步骤S81、设定参数s＝1，将基本步骤7的得到的新抗体作为初始解；

步骤S82、判断s＝1是否成立，若成立，则随机选取抗体中的两个基因，交换这两个基因的位置，得到新的个体X'；否则，执行步骤S83；

步骤S83、判断s＝2是否成立，若成立，则随机选取抗体中的两个基因，用1到n之间的随机数替代该基因对应的数值，得到新的个体X'；否则，执行步骤S84；

步骤S84、判断s＝3是否成立，若成立，则随机选取抗体中的两个基因，将这两个基因间的序列按照原顺序的倒序排列，得到新的个体X'；

步骤S85、计算个体X'的适应度，判断其是否优于其原个体，若是，则替代原个体成为新的初始解，令s＝1，执行步骤2；否则，令s＝s+1，执行步骤S86；

步骤S86、判断s＜4是否成立，若成立，执行步骤3；否则，结束搜索。

由于本实施例所介绍的基于改进人工免疫算法的平行机成组调度系统为可以执行本发明实施例中的基于改进人工免疫算法的平行机成组调度方法的系统，故而基于本发明实施例中所介绍的基于改进人工免疫算法的平行机成组调度的方法，本领域所属技术人员能够了解本实施例的基于改进人工免疫算法的平行机成组调度系统的具体实施方式以及其各种变化形式，所以在此对于该基于改进人工免疫算法的平行机成组调度系统如何实现本发明实施例中的基于改进人工免疫算法的平行机成组调度方法不再详细介绍。只要本领域所属技术人员实施本发明实施例中基于改进人工免疫算法的平行机成组调度方法所采用的系统，都属于本申请所欲保护的范围。

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

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