基于改进人工蜂群算法的生产调度方法及系统

摘要

基于改进人工蜂群算法的生产调度方法及系统，本发明实施例公开了恶化情形下一种基于改进的人工蜂群算法的平行机批调度方法及系统，该方法能针对恶化工件情形下考虑维修的平行机批调度问题，求得近似最优解，本发明中的模型来源于实际生产过程，考虑了实际生产中的机器维修和组批加工方式，以及工件和机器随着时间的延长会出现额外的加工和维修处理时间，本发明对该问题的解决有利于在复杂的现实生产环境中为企业生产和维修提供可靠的决策支持，降低企业运营成本，提高企业生产效率，推动企业现代化智能工厂的构建。

说明书

技术领域

本发明实施例涉及软件技术领域，具体涉及一种基于改进人工蜂群算法的生产调度方法及系统。

背景技术

恶化工件调度问题最初由Gupta和Gupta(1988)提出，是一个典型的组合优化问题，在近年来得到广泛的重视和研究。它广泛存在于现代化生产的各行各业，如：钢铁加工业、医疗行业、环境治理等领域。与传统调度问题中每个工件具有固定的加工时间不同，恶化情形下，越早开始加工，工件的加工持续时间会越短。而且在实际生产中，一台机器通常可以同时处理一定数量的工件，但是为了保证机器的持续有效性和产品的质量水平，机器在加工过程中需要进行检修，合理有效的利用工件加工规律，设计相应的工件和维修安排规则，将显著提升当前复杂环境下企业的生产效率，提高企业的市场竞争力。因此，对恶化情形下考虑维修的平行机批调度问题进行研究具有很强的现实意义。

在以往的研究中，智能算法被广泛应用于解决各类平行机调度问题，一种方法运用遗传算法解决了一般情形下的平行机调度问题。另一种方法运用粒子群算法解决了模糊环境下的平行机调度问题。还有一种方法在前者的研究基础上提出了混合遗传粒子群算法，并通过实验证明了所提混合算法在搜索能力和鲁棒性要求上均优于前者。

然而，在进行发明创造的过程中发明人发现，现有技术存在以下缺陷：在传统调度模型中，一般假设工件加工时间是固定并已知的，但是在复杂生产环境中，由于机器的恶化和人的疲劳，工件的加工时间会随着工件开始加工时间的延长而延长，而且在加工过程中机器还会存在维修等情况，虽然近年来也有很多文献开始研究机器恶化调度问题，但是同时考虑恶化和平行批处理机的研究较少，而且通过文献调查，没有发现研究者将恶化，维修，平行批加工和不相关平行机同时考虑而构建复杂的调度模型，而实际生产环境中，这些因素可能会同时存在，这一复杂问题的解决是破解企业生产难题的关键，而传统的调度模型并不能解决这一问题。除此之外，在方法上，人工蜂群算法存在着容易陷入局部最优缺点，但是在与其它智能算法相结合时展现出良好的性能，包括在某些特定问题中与启发式算法的结合，传统的人工蜂群算法很难适用于解决当前复杂生产问题。

发明内容

本发明实施例提供了一种基于改进人工蜂群算法的生产调度方法及系统，用以解决上述至少一个技术问题。

第一方面，本发明实施例提供一种基于改进人工蜂群算法的生产调度方法，包括：

S1、输入每个机器的容量和工件的一般加工时间，设定改进人工蜂群算法参数，包括最大迭代次数t_max，全局最优解gbest，蜜源搜索限制UP，雇佣蜂数量SN，迭代次数t＝1；

S2、初始化种群；考虑共有SN个蜜源，第q个蜜源的位置定义为其中表示第q个蜜源在第j维上的位置，表明第j个工件被分配至第个机器；

S3、计算解集中每个蜜源的适应度值，更新全局最优解gbest；

S4、计算当前代的邻域选择概率设定变量q＝1；

S5、判断rand(0,1)≤R_a是否成立，若成立，则对X_q执行交换变异操作，并依据贪婪规则保留蜜源，其中rand(0,1)表示0到1之间的随机数；否则，对X_q执行倒位变异操作，并依据贪婪规则保留蜜源；若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；其中，up_q表示对第q个蜜源的搜索次数；

S6、q＝q+1，判断q≤SN是否成立，若成立，则返回步骤S5；否则，执行步骤S7；

S7、计算概率其中，fit_q表示第q个蜜源的适应度值，由于所求问题为最小化问题，fit_q越小表示解决方案越优；

S8、从种群以概率pro_q选择第q个蜜源X_q，执行禁忌搜索操作，若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；重复该操作共SN次对解集进行更新；

S9、设定变量q＝1；

S10、若up_q≤UP，则q＝q+1；否则，以随机产生的新解代替X_q，并令up_q＝0，q＝q+1；

S11、判断q≤SN是否成立，若成立，则返回步骤S10；否则，执行步骤S12；

S12、用随机产生的蜜源替代解集中后20％的蜜源；令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法并输出全局最优解gbest，输出最优的工件指派，工件组批，批加工顺序和每个机器上维修开始的时间。

第二方面，本发明实施例提供一种基于改进人工蜂群算法的生产调度系统，包括：

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

S1、输入每个机器的容量和工件的一般加工时间，设定改进人工蜂群算法参数，包括最大迭代次数t_max，全局最优解gbest，蜜源搜索限制UP，雇佣蜂数量SN，迭代次数t＝1；

S2、初始化种群；考虑共有SN个蜜源，第q个蜜源的位置定义为其中表示第q个蜜源在第j维上的位置，表明第j个工件被分配至第个机器；

S3、计算解集中每个蜜源的适应度值，更新全局最优解gbest；

S4、计算当前代的邻域选择概率设定变量q＝1；

S5、判断rand(0,1)≤R_a是否成立，若成立，则对X_q执行交换变异操作，并依据贪婪规则保留蜜源，其中rand(0,1)表示0到1之间的随机数；否则，对X_q执行倒位变异操作，并依据贪婪规则保留蜜源；若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；其中，up_q表示对第q个蜜源的搜索次数；

S6、q＝q+1，判断q≤SN是否成立，若成立，则返回步骤S5；否则，执行步骤S7；

S7、计算概率其中，fit_q表示第q个蜜源的适应度值，由于所求问题为最小化问题，fit_q越小表示解决方案越优；

S8、从种群以概率pro_q选择第q个蜜源X_q，执行禁忌搜索操作，若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；重复该操作共SN次对解集进行更新；

S9、设定变量q＝1；

S10、若up_q≤UP，则q＝q+1；否则，以随机产生的新解代替X_q，并令up_q＝0，q＝q+1；

S11、判断q≤SN是否成立，若成立，则返回步骤S10；否则，执行步骤S12；

S12、用随机产生的蜜源替代解集中后20％的蜜源；令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法；

输出单元，用于输出全局最优解gbest，输出最优的工件指派，工件组批，批加工顺序和每个机器上维修开始的时间。

本发明实施例能针对恶化工件情形下考虑维修的平行机批调度问题，求得近似最优解，本发明中的模型来源于实际生产过程，考虑了实际生产中的机器维修和组批加工方式，以及工件和机器随着时间的延长会出现额外的加工和维修处理时间，本发明对该问题的解决有利于在复杂的现实生产环境中为企业生产和维修提供可靠的决策支持，降低企业运营成本，提高企业生产效率，推动企业现代化智能工厂的构建。

附图说明

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

图1是本发明实施例提供的考虑维修的平行机批调度问题示意图；

图2是本发明实施例提供的一种基于改进人工蜂群算法的生产调度方法流程图；

图3是本发明实施例提供的一种基于改进人工蜂群算法的生产调度系统结构示意图。

具体实施方式

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

本发明实施例用于解决恶化情形下考虑维修的平行机批调度问题，目的是确定每个工件将分配至具体的机器，该机器上的工件的组批方式，批的加工顺序和维修开始的时间点，以最小化制造跨度。基于问题特点，运用理论分析和数学推导提出有效的混合算法，解决该组合优化问题，为复杂环境下的企业生产进度管理提供新方法。

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

如图1所示，恶化情形下考虑机器维修的平行机批调度问题，目标为最小化制造跨度。该问题描述如下：给定包含个工件的工件集合需要在个平行批处理机上进行加工。不同的工件在不同的机器上具有不同的一般加工时间，相同的单位尺寸和相同的恶化率，第个工件在第个机器上的实际加工时间表示为。其中一般加工时间由表示，表示恶化率，表示工件的开始加工时间。每个机器在加工结束前必须执行一次维修，第个机器的维修时间表示为，其中表示第个机器的维修开始时间。问题假设如下：

(1)所有工件和机器在时刻准备完毕，工件具有单位尺寸和不同的一般加工时间，各批处理机具有相同的容量和加工速度，在维修结束后，机器可以随时投入使用；

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

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

基于此，本发明的一个实施例提供了一种基于改进人工蜂群算法的生产调度方法，如图2所示，包括：

S1、输入每个机器的容量和工件的一般加工时间，设定改进人工蜂群算法参数，包括最大迭代次数t_max，全局最优解gbest，蜜源搜索限制UP，雇佣蜂数量SN，迭代次数t＝1；

S2、初始化种群；考虑共有SN个蜜源，第q个蜜源的位置定义为其中表示第q个蜜源在第j维上的位置，表明第j个工件被分配至第个机器；

S3、计算解集中每个蜜源的适应度值，更新全局最优解gbest；

S4、计算当前代的邻域选择概率设定变量q＝1；

S5、判断rand(0,1)≤R_a是否成立，若成立，则对X_q执行交换变异操作，并依据贪婪规则保留蜜源，其中rand(0,1)表示0到1之间的随机数；否则，对X_q执行倒位变异操作，并依据贪婪规则保留蜜源；若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；其中，up_q表示对第q个蜜源的搜索次数；

S6、q＝q+1，判断q≤SN是否成立，若成立，则返回步骤S5；否则，执行步骤S7；

S7、计算概率其中，fit_q表示第q个蜜源的适应度值，由于所求问题为最小化问题，fit_q越小表示解决方案越优；

S8、从种群以概率pro_q选择第q个蜜源X_q，执行禁忌搜索操作，若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；重复该操作共SN次对解集进行更新；

S9、设定变量q＝1；

S10、若up_q≤UP，则q＝q+1；否则，以随机产生的新解代替X_q，并令up_q＝0，q＝q+1；

S11、判断q≤SN是否成立，若成立，则返回步骤S10；否则，执行步骤S12；

S12、用随机产生的蜜源替代解集中后20％的蜜源；令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法并输出全局最优解gbest，输出最优的工件指派，工件组批，批加工顺序和每个机器上维修开始的时间。

本发明实施例能针对恶化工件情形下考虑维修的平行机批调度问题，求得近似最优解，本发明中的模型来源于实际生产过程，考虑了实际生产中的机器维修和组批加工方式，以及工件和机器随着时间的延长会出现额外的加工和维修处理时间，本发明对该问题的解决有利于在复杂的现实生产环境中为企业生产和维修提供可靠的决策支持，降低企业运营成本，提高企业生产效率，推动企业现代化智能工厂的构建。

在具体实施时，步骤S3中计算解集中每个蜜源的适应度值，可以包括：

步骤S31：依据编码规则先依次将第j个工件被分配至第个机器，在每个机器上，将工件按照一般加工时间非减序排序；

步骤S32：在每个机器上，将前个工件组成第一批，并从工件列表中删除，再将剩余列表中前c个工件组成一批，并从工件列表中删除，以此类推，直至工件列表中所有工件安排完毕，其中n_i表示第i个机器上的工件个数，c表示机器同时能加工的工件个数，表示不小于的最小整数；

步骤S33：设定参数e＝1，表明维修从第一个工件加工完成后开始；

步骤S34：对与每个机器计算

其中B_i表示第i个机器上批的总个数；

步骤S35：将每个机器上所有批按加工时间非减排序，将第一批排至w_hi值最大的位置，即将第一个工件安排在第h个加工，将该批和w_hi从列表中删除，重复此操作，直至每个批和加工次序一一对应；

步骤S36：在每个机器上计算完工时间令e＝e+1，判断e≤B_i是否成立，若成立，则返回步骤S34；否则，在机器上确认维修在第L^*个工件加工完成后开始，其中，即将维修位置安排在所有位置中加工时间最短的位置，算法结束。

在具体实施时，步骤S5可以包括：

步骤S51：获取一个蜜源编码，生成0到1之间的随机数rand；

步骤S52：判断rand＜R_a是否成立，若成立，则执行步骤S53；否则，执行步骤S54；

步骤S53：随机产生1到n之间的两个正整数x和y，交换蜜源中第x和y处位置对应的数值，得到一个新的蜜源位置编码；

步骤S54：随机产生1到n之间的两个正整数x和y，将第x和y处位置之间的序列进行逆序排列，得到一个新的蜜源位置编码。

在具体实施时，步骤S7可以包括：

步骤S71：获取一个蜜源编码，将其作为当前最优解，定义迭代次数itmax，禁忌表长度tabulong，邻域搜索次数Slong；

步骤S72：随机产生1到n之间的两个正整数x和y，将第x处的数值移到第y处，再将第x+1至y之间的数值排列至新编码的第x至y-1处，得到一个新的蜜源编码；

步骤S73：重复步骤S72产生Slong个新的蜜源编码，计算所有解的适应度；

步骤S74：将适应度最好的解与当前最优解进行比较，若优于当前最优解，执行步骤S76；否则，执行步骤S75；

步骤S75：将各解按适应度从好到坏排序，依次检查其对应的x和y值是否在禁忌表中出现，直至有一个的结果为未出现，将其作为适应度最好解执行步骤S76；

步骤S76：用适应度最好的解替换当前最优解，判断禁忌表记录条数是否大于tabulong，若大于，则删除禁忌表最后一个元素，各元素向下移动一个位置，并将适应度最好解对应的x和y值加入禁忌表第一个位置；否则，直接将各元素向下移动一个位置，并将适应度最好解对应的x和y值加入禁忌表第一个位置；

步骤S77：it＝it+1，判断it≤itmax是否成立，若成立，则返回步骤S72；否则，结束搜索。

本发明的有益效果如下：

1、本发明针对工件恶化情形下考虑维修的平行机批调度问题，通过改进的人工蜂群算法，首先将工件以编码的方式，分配到各个机器上，然后依据问题的性质提出针对每个机器的工件分批，排序和维修的安排策略，在多项式时间内得到每个机器上最优的生产维修方案；对每个蜜源执行自适应的邻域搜索操作；基于蜜源的适应度，有选择地进行基于禁忌搜索的系统化更新；通过重复迭代，实现对种群的不断更新，最终求的最优解。改进的人工蜂群算法在收敛速度和收敛结果上，是一种效率很高的算法；通过该算法，解决了工件恶化情形下考虑维修的平行机批调度问题，提高了实际复杂环境中企业的生产效率，为企业提供了有效的决策支持，有利于加速企业的智能化进程。

2、本发明在提出了恶化情形下在每个特定的机器上对工件进行组批，排序和对维修进行安排的最优算法，确保了在工件集合指派到机器的过程完成后，每个机器的生产能力能够得到充分的发挥，即在每个机器上实现加工进度的最优化。

3、一般人工蜂群算法存在着容易陷入局部最优的问题，但人工蜂群算法在应用中与多种算法结合时展现出良好的性能，本发明针对人工蜂群算法的缺点和优势，结合在该问题中的具体应用，设计了自适应的邻域搜索机制，并通过禁忌搜索算法对加强跟随蜂的搜索能力，保证蜜源更新的效率，不仅有效地提高了算法收敛速和解的多样性，也在一定程度上加强了算法末期的局部收敛能力。

基于同样的发明构思，本发明又一实施例提供了一种基于改进人工蜂群算法的生产调度系统，如图3所示，包括：

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

S1、输入每个机器的容量和工件的一般加工时间，设定改进人工蜂群算法参数，包括最大迭代次数t_max，全局最优解gbest，蜜源搜索限制UP，雇佣蜂数量SN，迭代次数t＝1；

S2、初始化种群；考虑共有SN个蜜源，第q个蜜源的位置定义为其中表示第q个蜜源在第j维上的位置，表明第j个工件被分配至第个机器；

S3、计算解集中每个蜜源的适应度值，更新全局最优解gbest；

S4、计算当前代的邻域选择概率设定变量q＝1；

S5、判断rand(0,1)≤R_a是否成立，若成立，则对X_q执行交换变异操作，并依据贪婪规则保留蜜源，其中rand(0,1)表示0到1之间的随机数；否则，对X_q执行倒位变异操作，并依据贪婪规则保留蜜源；若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；其中，up_q表示对第q个蜜源的搜索次数；

S6、q＝q+1，判断q≤SN是否成立，若成立，则返回步骤S5；否则，执行步骤S7；

S7、计算概率其中，fit_q表示第q个蜜源的适应度值，由于所求问题为最小化问题，fit_q越小表示解决方案越优；

S8、从种群以概率pro_q选择第q个蜜源X_q，执行禁忌搜索操作，若蜜源被更新，up_q＝0；否则，up_q＝up_q+1；重复该操作共SN次对解集进行更新；

S9、设定变量q＝1；

S10、若up_q≤UP，则q＝q+1；否则，以随机产生的新解代替X_q，并令up_q＝0，q＝q+1；

S11、判断q≤SN是否成立，若成立，则返回步骤S10；否则，执行步骤S12；

S12、用随机产生的蜜源替代解集中后20％的蜜源；令t＝t+1；判断t≤t_max是否成立，若成立，返回步骤S3，否则，结束算法；

输出单元，用于输出全局最优解gbest，输出最优的工件指派，工件组批，批加工顺序和每个机器上维修开始的时间。

可选地，处理单元201执行步骤S3中计算解集中每个蜜源的适应度值，可以包括：

步骤S31：依据编码规则先依次将第j个工件被分配至第x_q^j个机器，在每个机器上，将工件按照一般加工时间非减序排序；

步骤S32：在每个机器上，将前个工件组成第一批，并从工件列表中删除，再将剩余列表中前c个工件组成一批，并从工件列表中删除，以此类推，直至工件列表中所有工件安排完毕，其中n_i表示第i个机器上的工件个数，c表示机器同时能加工的工件个数，表示不小于的最小整数；

步骤S33：设定参数e＝1，表明维修从第一个工件加工完成后开始；

步骤S34：对与每个机器计算

其中B_i表示第i个机器上批的总个数；

步骤S35：将每个机器上所有批按加工时间非减排序，将第一批排至w_hi值最大的位置，即将第一个工件安排在第h个加工，将该批和w_hi从列表中删除，重复此操作，直至每个批和加工次序一一对应；

步骤S36：在每个机器上计算完工时间令e＝e+1，判断e≤B_i是否成立，若成立，则返回步骤S34；否则，在机器上确认维修在第L^*个工件加工完成后开始，其中，即将维修位置安排在所有位置中加工时间最短的位置，算法结束。

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

步骤S51：获取一个蜜源编码，生成0到1之间的随机数rand；

步骤S52：判断rand＜R_a是否成立，若成立，则执行步骤S53；否则，执行步骤S54；

步骤S53：随机产生1到n之间的两个正整数x和y，交换蜜源中第x和y处位置对应的数值，得到一个新的蜜源位置编码；

步骤S54：随机产生1到n之间的两个正整数x和y，将第x和y处位置之间的序列进行逆序排列，得到一个新的蜜源位置编码。

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

步骤S71：获取一个蜜源编码，将其作为当前最优解，定义迭代次数it max，禁忌表长度tabulong，邻域搜索次数Slong；

步骤S72：随机产生1到n之间的两个正整数x和y，将第x处的数值移到第y处，再将第x+1至y之间的数值排列至新编码的第x至y-1处，得到一个新的蜜源编码；

步骤S73：重复步骤S72产生Slong个新的蜜源编码，计算所有解的适应度；

步骤S74：将适应度最好的解与当前最优解进行比较，若优于当前最优解，执行步骤S76；否则，执行步骤S75；

步骤S75：将各解按适应度从好到坏排序，依次检查其对应的x和y值是否在禁忌表中出现，直至有一个的结果为未出现，将其作为适应度最好解执行步骤S76；

步骤S76：用适应度最好的解替换当前最优解，判断禁忌表记录条数是否大于tabulong，若大于，则删除禁忌表最后一个元素，各元素向下移动一个位置，并将适应度最好解对应的x和y值加入禁忌表第一个位置；否则，直接将各元素向下移动一个位置，并将适应度最好解对应的x和y值加入禁忌表第一个位置；

步骤S77：it＝it+1，判断it≤itmax是否成立，若成立，则返回步骤S72；否则，结束搜索。

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

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

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