本发明涉及一种动态调度方法，具体涉及一种基于协同进化遗传规划的线缆生产动态调度方法。
背景技术：
0、技术背景
1、电线电缆被喻为国民经济的“神经”和“血管”，在各行业都有着广泛的应用。线缆生产也是我国重要的传统制造行业，行业总产值已超万亿元，位居世界首位。但是我国线缆企业在生产过程中普遍存在着能耗成本高、管理效率低等问题，随着数字经济的快速发展，线缆生产也亟需数字化智能化转型升级，以实现节能减排、降低成本和提高经济效益的目的。生产调度优化是线缆生产中的关键技术问题，对线缆企业的生产成本和管理效率将带来直接影响，对于线缆企业的提质增效和转型升级具有重要意义。
2、线缆生产过程中存在不确定性强、产品种类多、工艺复杂等问题，对其进行生产调度问题的建模和求解很难做到与实际完全符合。目前线缆生产企业主要仍停留在依靠人工经验进行生产调度的阶段，且有关线缆生产调度的文献较少。申请号为201810526733.7，名称为《一种多类电缆加工的优化调度方法》的发明专利公开了一种多类电缆加工的优化调度方法，用于实现电缆生产加工排程。但是该发明只考虑了所有订单工艺流程均相同的情况，并没有考虑多品种、多工艺以及订单随即到达等情况，与线缆企业的生产实际存在较大差异。实际线缆生产中存在着较强的动态不确定性(如紧急订单到达、机器故障、订单取消等)，对调度的实时性提出了更高要求，但是目前有关线缆生产动态调度方面的研究都没有考虑动态不确定性因素的影响。
3、针对上述问题，本发明针对线缆生产调度中存在的动态不确定性，提出一种基于协同进化遗传规划的线缆生产动态调度方法，该方法通过结合遗传规划和协同进化方法，同时优化得到面向线缆生产动态调度的路由规则和排序规则，其中路由规则实现将随机到达订单的工序分配到最合适机器，排序规则实现从机器上待加工工序队列中选取最合适工序进行操作，基于上述方法实现面向线缆生产的实时动态调度。本发明所提调度方法符合线缆企业的生产实际，可有效应对生产过程中存在的动态不确定性。
技术实现思路
1、本发明所要解决的技术问题是提供一种高效、符合实际的基于协同进化遗传规划的线缆生产动态调度方法。
2、本发明首先结合线缆生产调度问题建立线缆生产调度数学模型，以最小化订单截止日期的均方误差为目标。在此基础上，本发明采用协同进化遗传规划算法框架，基于规则训练模型，寻优同时得到针对机器分配问题和工序排序问题的两个复杂规则，从而实现对于线缆生产线的动态实时调度。
3、本发明是通过以下技术方案来实现的：
4、一种基于协同进化遗传规划的线缆生产动态调度方法，该方法包括如下步骤：
5、步骤1、建立线缆生产调度问题的数学模型；
6、设定线缆生产线中共有m台机器，有n个待生产订单{j1,j2,…,jn}，每个订单ji(i＝1,2，…,n)根据交货截止期di生成ni个工序集合设定工序oi,j(i＝1,2,…,n；j＝1,2,…,ni)在机器mk(k＝1,2,…,m)上的开始时间、完工时间、加工时间分别为bi,j、ci,j、ti,j,k；gp,q表示环节p(p＝1,2,…,7)的第q个规格；si,i′,k表示在机器mk上两个连续的不同生产规格的工序oi,j和oi,j之间更换模具所需的安装时间；设定每台机器一次只能处理一个工序，每个工序只能被处理一次，且当工序开始处理后不允许被抢占或中断，不同订单的工序之间不存在时序约束；
7、以最小化订单截止日期的均方误差(msd)为目标，得到线缆生产调度问题的目标函数为：
8、
9、约束条件如下：
10、ci,j＝bi,j+ti,j,k (2)
11、bi,1≥0 (3)
12、bi,j≥ci,j-1 (4)
13、bi,k ci,k+xi,i,k si,i,k (5)
14、
15、
16、
17、
18、
19、其中，约束(2)是计算工序的完成时间；约束(3)表示每个订单的第一个工序的开始时间必须大于0；约束(4)声明同一个订单ji中后一个工序的开始时间必须要在前一个工序结束后才能开始加工；约束(5)给定了机器mk上一个工序必须要在前一工序结束后才能开始加工；约束(6)和(7)表示每台机器一次只能处理一个工序，且每个工序只能被处理一次；约束(8)～(10)是决策变量；
20、步骤2、构建终端集和函数集；
21、步骤3、设置算法参数并随机生成初始化种群；
22、3.1、设置算法参数：种群大小ps＝40，当前迭代次数t＝0，最大迭代次数t＝50；
23、3.2、随机生成初始化种群：生成两个规模大小均为ps的子种群p1和p2，并从p1和p2中分别随机选择一个个体组成当前最优规则组合(rrt,best,srt,best)，其中子种群p1用于进化处理机器分配问题的路由规则rrt，另一个子种群p2用于进化处理工序排序问题的排序规则srt；
24、步骤4、构建训练实例生成器：将企业历史订单数据作为训练集，训练集当中订单数量nmax＝600，按照订单存入订单数据库的时间顺序，依次选择待处理的订单，采用泊松分布p(λ)模拟订单随机到达过程，其中λ＝7；
25、步骤5、计算子种群p1和p2的适应度值：针对子种群p1中的每一个体rrt,i(i＝1,2,…,ps)，构建组合规则(rrt,i,srt,best)，计算每个订单ji(i＝1,2,…,n)的完工时间ci，并采用公式(1)计算子种群p1中每一个体rrt,i的适应度值为msd(rrt,i)；基于同样方法，针对子种群p2中的每一个体srt,i(i＝1,2,…,ps)，构建组合规则(rrt,best,srt,i)，计算得到子种群p2中每一个体srt,i的适应度值为msd(srt,i)；
26、步骤6、分别记录子种群p1和p2中适应度值最小的个体，作为当前最优规则组合(rrt,best,srt,best)；
27、步骤7、采用遗传规划算法分别对子种群p1和p2进行选择、交叉、变异操作，生成新的子种群p′1和p′2，具体方法如下：
28、7.1、选择：基于轮盘赌方法选择子种群中的个体进行操作，适应度值越小的个体将有更多的机会被选中进行操作；
29、7.2、交叉：根据交叉率rcr和rcs分别对二叉树执行交叉操作并生成新的子树，使用设定点法对个体2i和2i+1(i＝0,1,...,pop/2-1)的树之间进行交叉操作；
30、7.3、变异：根据变异率rmr和rms分别对树进行变异操作并获得最终的树；
31、步骤8、判断t≤t是否成立，若成立，执行t＝t+1，并转到步骤5继续操作；否则训练完成，并输出最优规则组合(rrt,best,srt,best)；
32、步骤9、根据实际线缆生产中下达的订单信息，采用训练得到的最优规则组合(rrt,best,srt,best)，动态实时地输出订单在实际线缆生产线上的最优调度方案及其对应的甘特图；
33、步骤10、当一个订单生产完成后，将订单信息存入历史订单数据库，如果订单数据库中订单数量超过规定最大值nmax，则替换订单数据库中最早存入的订单。
34、在步骤2中构建面向遗传规划的终端集合和函数集合，其中终端集合主要用于描述当前线缆生产上的实时工况信息，终端集合有10个，分别为：(1)机器对应工序等待队列中工序的总加工时间；(2)机器对应工序等待队列中的工序总数；(3)机器当前加工工序的剩余加工时间；(4)机器对应工序等待队列中工序的等待时间；(5)当前工序的下一个工序的平均处理时间；(6)当前工序所在订单的截止日期；(7)当前订单的权重；(8)当前工序在指定机器上的加工时间；(9)当前工序所在订单的剩余工序数；(10)当前工序所在订单剩余工序的总加工时间；函数集合由算术运算符+、-、×、/、max和min组成；其中对于“/”来说，如果分母非零，则其作用与除号一致，但如果分母为零，则返回值为1。
35、步骤5中所述生成调度方案的具体步骤如下：
36、5.1、根据到达的订单ji中工序间的时序约束关系，将当前能操作的工序加入到准备工序集合ro中；
37、5.2、随机选择一个工序oi,j(oi,j∈ro)，采用组合规则中的路由规则rrt，遍历所有当前可用机器，并依次判断工序oi,j是否可以在其中某一台机器mk上加工，若可以，则在满足公式(2)-(10)给定的约束条件基础上，计算机器mk的优先级值pv(mk)；
38、5.3、选取优先级值最小的机器作为oi,j的加工指派机器mk；
39、5.4、判断机器mk是否处在加工状态，如果机器mk当前正忙，则将待处理工序oi,j加入到机器mk的工序等待队列qk中，即qk＝qk∪oi,j；若mk空闲且qk非空，则采用组合规则中的路由规则srt，计算qk中每一个待处理工序的优先级值；
40、5.5、机器mk选取优先级值最小的工序oi,j进行加工，当机器mk加工完工序oi,j后，如果订单ji中所有工序均已处理完成，则转到步骤5.6执行，否则转到步骤5.1执行；
41、5.6、生成订单ji在机器上的生产调度方案，并按照步骤5.1到5.5的方法生成所有订单的调度方案，在此基础上采用公式(1)计算得到个体的适应度值。
42、本发明的有益效果是：根据线缆企业生产的实际情况，以最小化订单截止日期的均方误差(msd)为目标建立数学模型。构建遗传规划算法框架下的终端集合和函数集合，并根据线缆企业生产中的实际数据，构建模拟实际订单随机到达的训练模型。在此基础上提出了基于协同进化遗传规划的动态调度方法，在协同进化遗传规划算法框架下，基于规则训练模型，寻优同时得到针对机器分配问题和工序排序问题的两个最优规则。线缆生产企业在动态调度过程中可基于寻优得到的最优规则实现针对机器分配和工序排序两个子问题的动态实时调度。所提方法可有效应对企业生产实际中存在的动态不确定性，提升调度灵活性和稳健性，对于企业提升生产效率、降低生产成本具有重要意义。
1.一种基于协同进化遗传规划的线缆生产动态调度方法，该方法包括如下步骤：
2.根据权利要求1所述的线缆生产调度优化方法，其特征在于：在步骤2中构建终端集合和函数集合，终端集合有10个，分别为：(1)机器对应工序等待队列中工序的总加工时间；(2)机器对应工序等待队列中的工序总数；(3)机器当前加工工序的剩余加工时间；(4)机器对应工序等待队列中工序的等待时间；(5)当前工序的下一个工序的平均处理时间；(6)当前工序所在订单的截止日期；(7)当前订单的权重；(8)当前工序在指定机器上的加工时间；(9)当前工序所在订单的剩余工序数；(10)当前工序所在订单剩余工序的总加工时间；函数集合由算术运算符+、-、×、/、max和min组成；其中对于“/”来说，如果分母非零，则其作用与除号一致，但如果分母为零，则返回值为1。
3.根据权利要求1所述的线缆生产动态调度方法，其特征在于：步骤5中所述生成调度方案的具体步骤如下：
4.根据权利要求1所述的线缆生产调度优化方法，步骤1中建立线缆生产调度问题的数学模型还设定每台机器一次只能处理一个工序，每个工序只能被处理一次，且当工序开始处理后不允许被抢占或中断，不同订单的工序之间不存在时序约束。
