基于人员综合能力的设计任务调度优化算法的制作方法

1.本发明涉及工业生产调度任务分配领域，具体涉及基于人员综合能力的设计任务调度优化算法。


背景技术：

2.任务调度问题是制造流程规划和管理中最关键的问题之一，这个领域最困难的问题之一是作业车间调度问题(job-shop scheduling problem,jsp)，该问题中，一组机器需处理一组工件，每个工件由一系列具有先后顺序约束的工序形成，每个工序只需要一台机器，机器一直可用，可以一次处理一个操作而不会中断。决策内容包括如何对机器上的工序进行排序，已优化给定的性能指标。再次基础上产生了柔性作业车间调度问题(flexible job-shop scheduling problem,fjsp)，该问题是经典jsp的拓展，该问题中每个工序允许在一组可用机器中的任何一个上进行处理。fjsp比传统的jsp更难，因为它引入了除了排序之外的另一个决策内容，即作业路径。确定作业路径意味着为每个工序决定使用哪台机器处理它。
3.而针对人员的任务调度问题则更加复杂。人员工种和能力的差异等因素，会直接影响设计任务的完成时间和完成效率，同时由于人员差异性大、调度空间大等特点，人员的合理调度以及任务的合理配置更是成为智能制造行业的重点和难点。
4.因此，本发明基于以往的fjsp问题，并结合人员调度问题，提出了一种基于人员综合能力的设计任务调度优化算法，以解决上述问题。


技术实现要素：

5.针对上述现有方法存在的不足，本发明提供了一种基于人员综合能力的设计任务调度优化算法，以解决现有技术中人员调度以及任务配置不合理的问题。
6.本发明要解决的问题为改进的柔性作业车间调度问题(flexible job-shop scheduling problem，fjsp)，该fjsp问题可具体描述为针对新的设计任务需面向设计员进行设计任务的调度与分配，该fjsp问题的具体模型为该新型号产品设计任务的调度与分配的目标为将n个设计任务分配给m个设计员。本发明的目的在于达到使设计人员工作负荷尽可能均衡、任务设计完成时间最早的目标。
7.本发明基于评分算法和改进的遗传算法，引入评分机制来评估设计员在设计任务中技能值、经验值和业绩值，全体设计员评分全排列表；基于改进的遗传算法对车间设计任务的工时调度求解，获得较优解的设计员分配方案；将全体设计员评分全排列表和较优解的设计员分配方案进行线性组合后获得最优解的设计员分配方案，设计了合理的柔性作业车间人员调度及任务分配方案，达到了设计人员工作负荷尽可能均衡、任务设计完成时间最早的目标，提高了人员调度及任务分配的精确性和可靠性。
8.本发明提供了一种基于人员综合能力的设计任务调度优化算法，包括：
9.s1:发布产品定制需求并形成产品设计任务以及设计任务的具体参数,所述任务
参数中为空的位置使用0占位；
10.s2:基于所述步骤s1中形成的所述任务参数,使用评分算法计算全体设计员的技能分、经验分和业绩分，通过ahp层次分析法赋予每项评分权重，计算出每位设计员总评分，根据所述总评分形成全体设计员评分全排列表，计算总评分的公式为：
11.s＝ω1s1+ω2s2+ω3s312.其中，s为设计员总评分，s1为设计员技能分分值，s2为设计员经验分分值，s3为设计员业绩分分值，ω1为设计员技能分权重值，ω2为设计员经验分权重值，ω3为设计员业绩分权重值；
13.s3：建立带有约束条件的作业车间调度数学模型，所述作业车间调度数学模型包括工时目标函数和约束条件，所述作业车间调度数学模型描述为：
14.将n个设计任务分配给m个设计能力不同的设计员进行设计，所述n个设计任务不仅包含有未分配的设计任务，还包含有优先级最高的未完成任务，其中需求ri(i∈{1，2，...，n})包含个设计任务，设计员pk(k∈{1，2，...，m})对设计任务的工时用表示，工时为空的项则说明该设计员没有设计此项任务的能力，设计员pk对需求ri的设计任务的开始设计时间和完成设计时间分别为则设计员pk对设计任务的设计完成时间为：
[0015][0016]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务，k表示此项设计任务交给第k个设计员；表示设计员pk对第i个需求中第ni个设计任务的前一个设计任务n
i-1的完成时间；tek表示设计员pk结束第i个需求中第n
i-1个设计任务所需要的时间，即还需要多久的空闲时间；表示设计员pk结束第i个需求中第n
i-1个设计任务所需要的最大时间；
[0017]
需求中全部设计任务所有最晚完工时间为：
[0018][0019]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务；表示第i个需求中第ni个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第ni个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；
[0020]
故，工时目标函数为：
[0021][0022]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务；表示第i个需求中第ni个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第ni个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；pt表示最早完工时间，即完成任意一项需求中全部设计任务所有最晚完工时间中的最早完工时间；
[0023]
所述约束条件具体为：
[0024]
a.在零时刻，所有设计任务都可以被执行；
[0025]
b.同需求的设计任务严格按照设计顺序设计，每个设计任务必须在其前一个设计任务完成后才能进行；
[0026]
c.每个设计任务只能从可进行设计的设计员选择一名进行分配；
[0027]
s4：对所述步骤s3中的模型利用改进后的遗传算法进行处理，通过编码、生成初始种群、解码、计算适应度函数、选择操作、交叉操作及变异操作，直到满足迭代终止条件后输出，并选取输出结果的前5％作为较优解群；
[0028]
s5:结合所述步骤s4中获得的所述较优解群的设计员分配方案和所述步骤s2中获得的全体设计员评分表中所述较优解群中设计员在每个任务中的总评分，获得最早完工时间pt和初始总评分ps，将二者进行线性组合后得到最终评分，选取最终评分最大的方案为最优解，所述步骤s5具体为：
[0029]
s51：在所述步骤s4中获得的较优解群中确定每一个调度解的最早完工时间pt；
[0030]
s52：在所述步骤s2中获得的全体设计员评分表中查询所述较优解群中设计员在每个任务中的总评分，将每个任务的总评分相加后得到初始总评分ps；
[0031]
s53：分别对所述初始总评分ps和所述最早完工时间pt进行归一化处理，获得目标总评分ps
′
和目标最早完工时间pt
′
，具体为：
[0032][0033][0034]
其中，ps
max
表示最大值初始总评分ps，ps
min
表示最小值初始总评分ps；pt
max
表示最大值最早完工时间pt，pt
min
表示最小值最早完工时间pt；
[0035]
s54：计算最终评分sc，并将所述最终评分sc到大排序，其计算公式为：
[0036]
sc＝ω
01
ps
′
+ω
02
pt
′
[0037]
其中，sc为最终评分，ps
′
为目标总评分，ω
01
为目标总评分ps
′
的权重值，pt
′
为目标最早完工时间，ω
02
为目标最早完工时间pt
′
的权重值；
[0038]
s55：根据最终结果，选取sc的最大值的方案为最优解；
[0039]
s6：根据最优解进行设计任务的调度与设计人员的分配。
[0040]
优选的，所述步骤s2中使用评分算法计算全体设计员的技能分、经验分和业绩分具体规则为：
[0041]
技能分，是根据以往设计任务与所述步骤s1中形成的设计任务的相似度来进行赋分，所述相似度是通过采用欧氏距离方法计算获得，先计算出与以往每个设计任务的相似度并按相似度从大到小排序，选前三个相似度值相加后取平均值，即为该设计员的技能分分值；
[0042]
经验分，是根据设计员已经完成的此类设计任务的数量占满分设计员任务数量的比重进行赋分，完成此类任务最多的设计员即为满分设计员，所述此类设计任务是指与所述步骤s1中形成的设计任务的相似度≥30％的设计任务；
[0043]
业绩分，是根据所述技能分中相似任务列表中客户反馈形成的分值相加后取平均
值来进行赋分，每位客户评分的分值范围为0～100分，同时对于此次分配前已经开始但在零时刻仍未完成的相似任务，将进行该任务的设计员该项评分直接赋值为100分。
[0044]
优选的，所述步骤s2中通过ahp层次分析法赋予每项评分权重，具体为：
[0045]
a.建立评价指标，所述评价指标包括：技能、经验和业绩；
[0046]
b.根据所述评价指标构造判断矩阵；
[0047]
c.对所述判断矩阵进行一致性检验，当所述判断矩阵通过一致性检验时利用算数平均法计算各指标数据的权重。
[0048]
优选的，所述步骤s4中对所述步骤s3中的模型利用改进后的遗传算法进行处理的具体步骤为：
[0049]
s41:设置参数：设置种群规模popsize，初始交叉概率p
c1
和p
c2
，初始变异概率p
m1
和p
m2
，最大迭代次数gmax以及其他终止条件；
[0050]
s42:生成初始种群：对所述步骤s3中的模型编码成染色体，生成初始种群；
[0051]
s43:解码：根据染色体将设计任务分配到对应设计员得到的调度解采用改进的贪婪算法思想进行插入式解码操作，首先将染色体按照设计任务顺序解码得到调度解，然后再对这些解进行插入，即在调度每个任务的开始时刻时，考虑在满足同一设计任务而不改变设计任务顺序的情况下，将该设计任务分配到最早拥有空余时间大于等于设计工时的设计员手中，解码得到新的解，并将新编码顺序替换旧编码顺序，从而产生调度方案；
[0052]
s44:适应度计算：计算当代种群中出所有个体的适应度f(i)值，并找到值最优适应度值，将其作为当前当代最优解和当前全局最优解，所述适应度函数f(i)值是根据步骤s3计算所述工时目标函数值，再将所述工时目标函数值转化为适应度值，转化公式如下：
[0053][0054]
其中，pt为最早完工时间，f(i)为从零时刻到最后工件完成时间点所需时间的倒数；
[0055]
s45:判断算法是否满足终止条件，若满足则输出较优解的设计员分配方案，算法结束；若不满足，则进入下一步；
[0056]
s46:选择操作：根据适应度的高低，选择个体适应度值在5％的精英个体遗传到下一代，剩下的95％个体则根据当前种群中个体适应度值的详情执行轮盘赌选择操作，直至新一代种群规模与所述步骤s41中的设置的种群规模相同时，进行下一步；
[0057]
s47:交叉操作：对选择后的种群进行交叉操作，所述交叉操作包括pox交叉和mpx交叉，所述pox交叉仅对所述设计任务顺序部分父代染色体进行交叉，所述mpx交叉仅对所述设计员部分父代染色体进行交叉，根据改进的交叉操作确定是否交叉，所述改进的交叉操作公式为：
[0058][0059]
其中，p
c1
表示最大交叉概率，p
c2
表示最小交叉概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f
′
为要交叉的两个个体中较大的适应度值，f为要变异
个体的适应度值；
[0060]
s48:变异操作：根据改进的变异操作进行变异，所述变异操作包括插入变异和点对点变异，所述插入变异仅对所述设计任务顺序部分父代染色体进行变异，所述点对点变异仅对所述设计员部分父代染色体进行变异，所述改进的变异操作公式为：
[0061][0062]
其中，p
m1
表示最大变异概率，p
m2
表示最小变异概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f为要变异个体的适应度值；
[0063]
s49：生成下一代种群：经过步骤s46、s47、s48，生成新一代的种群；
[0064]
s410：计算当前种群适应度：先计算出当代种群所有个体适应度值，并且找出其中最大的那一个标记为当代最优个体，再把它与全局最优个体相互比较，若它的值更优，则将其作为全局最优个体，否则不作变化；
[0065]
s411：算法终止：判断是否满足迭代终止条件，若否，算法回转至s46；若是，则输出，算法结束；
[0066]
s412：选择较优解群：合并所述步骤s411中输出的相同方案，并从合并后的方案中选取前5％作为较优解群。
[0067]
优选的，所述编码采用双段编码方式，每一个染色体代表一种调度方案，染色体长度等于任务数量n，包括设计任务顺序编码和设计员编码，所述设计任务顺序编码用来确定设计任务出现的先后次序；所述设计员编码是按照设计任务的进行次序来排列的，用来获取每个设计任务对应的设计员。
[0068]
优选的，所述设计任务顺序编码的初始化方法为随机生成；所述设计员编码的初始化方法包括全局选择和局部选择，这两种初始化方法的比例为1:1，由此生成初始种群，所述设计员编码的初始化方法具体步骤为：
[0069]
所述全局选择方法具体为：设置一个数组，长度和人员数相等，数组的顺序依次对应设计人员的顺序，每一位上的值对应设计人员完成此任务的工时，随机在需求集中选择一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推，直到当前需求中的所有任务的设计人员选择完毕后，然后再随机选择一个需求开始，直到所有需求中的的所有任务选择完毕为止；
[0070]
所述局部选择方法具体为：对一个需求选择完毕时，数组需要重新设置为零，不存在随机选择需求，设置一个数组，长度和人员相等，选择需求集中第一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推。
[0071]
优选的，所述步骤s45在判断终止条件时，采用两种终止条件，分别如下：
[0072]
a.如果全局最优染色体在连续x代无更优解，则终止程序，并将此解作为最优解输
出；
[0073]
b.如果未出现情况a，则一直执行到最大迭代次数gmax，并输出全局最优解。
[0074]
优选的，所述步骤s52中在所述步骤s2中获得的全体设计员评分表中查询到所述较优解群中设计员在每个任务中的总评分后，每个任务的总评分相加过程是由系统自动获取相加后得到初始总评分ps。
[0075]
优选的，所述步骤s54中赋予的权重是根据柔性作业车间实际需求设置。
[0076]
与现有技术方案相比，本发明具有如下有益效果：
[0077]
1、本发明相较传统的fjsp问题，引入了零时刻时尚未完成任务的约束，将零时刻没有完成的任务也加入了考虑范围，提高了柔性作业车间调度方案的灵活性与可行性；
[0078]
2、本发明在解决fjsp问题的传统方法中加入了评分算法，综合评估了设计人员在设计任务中技能值、经验值和业绩值，有效避免了人员能力差异所带来的影响，同时在设计任务分配过程中有效提高了人员调度的精确性；
[0079]
3、本发明基于负载均衡策略对设计员编码进行初始化，将设计任务合理分配给设计员，达到了在平衡设计员工作负荷的同时获得最早完工时间的目标，有效提高了设计任务分配的精确度，有效缩短了设计任务执行时间；
[0080]
4、本发明针对遗传算法易丢失优良解、造成陷入局部最优解的不足，改进了子代种群产生方式，采用精英保留策略避免最优解的流失，并通过轮盘赌的方法来加速淘汰垃圾基因，加快种群求解速度；同时，通过改进后的交叉、变异操作，充分促进了基因重组,提高了变异操作的指导性与精确性，增加了种群的多样性；
[0081]
5、本发明通过结合评分算法和改进的遗传算法来设计了合理的柔性作业车间人员调度及任务分配方案，达到设计人员工作负荷尽可能均衡、任务设计完成时间最早的目标，提高了人员调度及任务分配的精确性和可靠性。
附图说明
[0082]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
[0083]
图1为本发明实施例中的基于人员综合能力的设计任务调度优化算法的求解流程图。
[0084]
图2为本发明实施例中的基于人员综合能力的设计任务调度优化算法的遗传算法流程图。
[0085]
图3为本发明实施例中设计任务顺序和设计员编码图。
[0086]
图4为本发明实施例中设计任务顺序和设计员解码图。
[0087]
图5为本发明实施例求解所得对应调度分配结果甘特图。
具体实施方式
[0088]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于
本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0089]
在本发明的描述中，需要说明的是，术语“中心”、“上”、“下”、“左”、“右”、“竖直”、“水平”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此不能理解为对本发明的限制；术语“第一”、“第二”、“第三”仅用于描述目的，而不能理解为指示或暗示相对重要性，此外，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。
[0090]
基于人员综合能力的设计任务调度优化算法，包括：
[0091]
s1:发布产品定制需求并形成产品设计任务以及设计任务的具体参数,所述任务参数中为空的位置使用0占位。
[0092]
以电机产品为例，发布电机产品定制需求后，系统根据电机定制需求形成相应的产品设计任务，所述电机产品设计任务具体参数包括额定功率、转速、扭矩、电压、接线方式、冷却方式和完成该任务所需时间，其中任务参数中为空的位置使用0占位。
[0093]
s2:基于所述步骤s1中形成的所述任务参数,使用评分算法计算全体设计员的技能分、经验分和业绩分，通过ahp层次分析法赋予每项评分权重，计算出每位设计员总评分，根据所述总评分形成全体设计员评分全排列表，计算总评分的公式为：
[0094]
s＝ω1s1+ω2s2+ω3s3[0095]
其中，s为设计员总评分，s1为设计员技能分分值，s2为设计员经验分分值，s3为设计员业绩分分值，ω1为设计员技能分权重值，ω2为设计员经验分权重值，ω3为设计员业绩分权重值。
[0096]
表1为全体设计员评分全排列表(参见下表)，由表1可知任意一位设计员执行任意一个需求中的任意一项设计任务时获得的总评分，例如设计员p1执行需求r1中的设计任务w
1，1
时获得的总评分s为85。
[0097][0098][0099]
表1.全体设计员评分全排列列表
[0100]
优选的，所述步骤s2中使用评分算法计算全体设计员的技能分、经验分和业绩分具体规则为：
[0101]
技能分，是根据以往设计任务与所述步骤s1中形成的设计任务的相似度来进行赋分，所述相似度是通过采用欧氏距离方法计算获得，先计算出与以往每个设计任务的相似度并按相似度从大到小排序，选前三个相似度值相加后取平均值，即为该设计员的技能分分值；
[0102]
经验分，是根据设计员已经完成的此类设计任务的数量占满分设计员任务数量的比重进行赋分，完成此类任务最多的设计员即为满分设计员，所述此类设计任务是指与所述步骤s1中形成的设计任务的相似度≥30％的设计任务；
[0103]
业绩分，是根据所述技能分中相似任务列表中客户反馈形成的分值相加后取平均值来进行赋分，每位客户评分的分值范围为0～100分，同时对于此次分配前已经开始但在零时刻仍未完成的相似任务，将进行该任务的设计员该项评分直接赋值为100分。
[0104]
本发明引入评分机制来对设计人员的各项能力进行评分，在评分中没有此项任务设计则评分为空。
[0105]
具体的，本发明中计算技能分时，当前三个相似度值分别为91％、90％、88％时，则相加后取三者的平均值89.67％作为当项评分中的技能分分值，即89.67分；计算经验分时，若设计员p1完成设计任务最多，则设计员p1的经验分记为100分，设计员p2完成设计任务数量是设计员p1的百分之八十，则设计员p2的经验分记为80分。
[0106]
优选的，所述步骤s2中通过ahp层次分析法赋予每项评分权重，具体为：
[0107]
a.建立评价指标，所述评价指标包括：技能、经验和业绩；
[0108]
b.根据所述评价指标构造判断矩阵；
[0109]
c.对所述判断矩阵进行一致性检验，当所述判断矩阵通过一致性检验时利用算数平均法计算各指标数据的权重。
[0110]
需要强调的是，当所述判断矩阵不能通过一致性检验时，需要不断调整所述判断矩阵调整，直到满足为止，本发明不对调整所述判断矩阵的方法做限定。
[0111]
本发明在计算中将各权重值相加后取平均值为各指标最终权重值，计算后获得的各指标数据权重依次为：ω1＝0.3，ω2＝0.3，ω3＝0.4，本发明获得的各指标数据权重值适用于计算本发明中全体设计员的总评分。
[0112]
s3:建立带有约束条件的作业车间调度数学模型，所述作业车间调度数学模型包括工时目标函数和约束条件，所述作业车间调度数学模型描述为：
[0113]
将n个设计任务(任务中包含有优先级最高的未完成任务)分配给m个设计能力不同的设计员进行设计，其中需求ri(i∈{1,2,
…
,n})包含个设计任务，设计员pk(k∈{1,2,
…
,m})对设计任务的工时用表示，设计员对每项设计任务的工时如表2所示(参见下表)，工时为空的项则说明该设计员没有设计此项任务的能力。
[0114]
[0115][0116]
表2.设计员完成设计任务需要的工时
[0117]
设计员pk对需求ri的设计任务的开始设计时间和完成设计时间分别为则设计员pk对设计任务的设计完成时间为：
[0118][0119]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务，k表示此项设计任务交给第k个设计员；表示设计员pk对第i个需求中第ni个设计任务的前一个设计任务n
i-1的完成时间；tek表示设计员pk结束第i个需求中第n
i-1个设计任务所需要的时间，即还需要多久的空闲时间；表示设计员pk结束第i个需求中第n
i-1个设计任务所需要的最大时间；
[0120]
需求中全部设计任务所有最晚完工时间为：
[0121][0122]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务；表示第i个需求中第ni个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第ni个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；
[0123]
故，工时目标函数为：
[0124]
[0125]
其中，i表示第i个需求，ni表示第i个需求中第ni个设计任务；表示第i个需求中第ni个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第ni个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；pt表示最早完工时间，即完成任意一项需求中全部设计任务所有最晚完工时间中的最早完工时间；
[0126]
所述约束条件具体为：
[0127]
a.在零时刻，所有设计任务都可以被执行；
[0128]
b.同需求的设计任务严格按照设计顺序设计，每个设计任务必须在其前一个设计任务完成后才能进行；
[0129]
c.每个设计任务只能从可进行设计的设计员选择一名进行分配。
[0130]
s4：对所述步骤s3中的模型利用改进后的遗传算法进行处理，通过编码、生成初始种群、解码、计算适应度函数、选择操作、交叉操作及变异操作，直到满足迭代终止条件后输出，并选取输出结果的前5％作为较优解群。
[0131]
优选的，所述步骤s4中对所述步骤s3中的模型利用改进后的遗传算法进行处理的具体步骤为：
[0132]
s41:设置参数：设置种群规模popsize，初始交叉概率p
c1
和p
c2
，初始变异概率p
m1
和p
m2
，最大迭代次数gmax以及其他终止条件。
[0133]
改进的遗传算法的初始种群规模大小、交叉变异概率、迭代次数都会影响算法的收敛性，本发明在实际操作过程中，当种群规模算例小于10x10时，迭代次数为300代；当种群规模算例大于10x10时，迭代次数为500代。本发明初始交叉概率p
c1
和p
c2
、初始变异概率p
m1
和p
m2
如表3所示：
[0134]
参数含义初值p
c1
交叉概率0.9p
c2
交叉概率0.6p
m1
变异概率0.1p
m2
变异概率0.001
[0135]
表3.改进遗传算法参数表
[0136]
s42:生成初始种群：对所述步骤s3中的模型编码成染色体，生成初始种群。
[0137]
优选的，所述编码采用双段编码方式，每一个染色体代表一种调度方案，染色体长度等于任务数量n，包括设计任务顺序编码和设计员编码，所述设计任务顺序编码用来确定设计任务出现的先后次序；所述设计员编码是按照设计任务的进行次序来排列的，用来获取每个设计任务对应的设计员。
[0138]
优选的，所述设计任务顺序编码的初始化方法为随机生成；所述设计员编码的初始化方法包括全局选择和局部选择，这两种初始化方法的比例为1:1，由此生成初始种群，所述设计员编码的初始化方法具体步骤为：
[0139]
所述全局选择方法具体为：设置一个数组，长度和人员数相等，数组的顺序依次对应设计人员的顺序，每一位上的值对应设计人员完成此任务的工时，随机在需求集中选择一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组
中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推，直到当前需求中的所有任务的设计人员选择完毕后，然后再随机选择一个需求开始，直到所有需求中的所有任务选择完毕为止；
[0140]
所述局部选择方法具体为：对一个需求选择完毕时，数组需要重新设置为零，不存在随机选择需求，设置一个数组，长度和人员相等，选择需求集中第一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推。
[0141]
本发明中，对所述基于设计员的编码采取全局选择和局部选择进行初始化是基于负载均衡策略，以最早完工时间为目标，将设计任务合理分配给设计员，平衡设计员工作负荷，提高任务分配精确度，缩短设计任务执行时间。
[0142]
s43:解码：根据染色体将设计任务分配到对应设计员得到的调度解采用改进的贪婪算法思想进行插入式解码操作，首先将染色体按照设计任务顺序解码得到调度解，然后再对这些解进行插入，即在调度每个任务的开始时刻时，考虑在满足同一设计任务而不改变设计任务顺序的情况下，将该设计任务分配到最早拥有空余时间大于等于设计工时的设计员手中，解码得到新的解，并将新编码顺序替换旧编码顺序，从而产生调度方案。
[0143]
本发明通过此种方式优化了调度解，有效减少出现多条染色体对应一种调度解的情况，加快了求解速度。
[0144]
s44:适应度计算：计算当代种群中出所有个体的适应度f(i)值，并找到值最优适应度值，将其作为当前当代最优解和当前全局最优解，所述适应度函数f(i)值是根据步骤s3计算所述工时目标函数值，再将所述工时目标函数值转化为适应度值，转化公式如下：
[0145][0146]
其中，pt为最早完工时间，f(i)为从零时刻到最后工件完成时间点所需时间的倒数。
[0147]
fii)的值越大表示解的质量越高，通过适应度函数可以筛选出优秀的染色体种群，既能达到执行测试任务的最早完工时间，又能避免仅仅依据测试时间为判定结构的局部优化的情况。
[0148]
s45:判断算法是否满足终止条件，若满足则输出较优解的设计员分配方案，算法结束；若不满足，则进入下一步。
[0149]
优选的，所述步骤s45在判断终止条件时，采用两种终止条件，分别如下：
[0150]
a.如果全局最优染色体在连续x代无更优解，则终止程序，并将此解作为最优解输出；
[0151]
b.如果未出现情况a，则一直执行到最大迭代次数gmax，并输出全局最优解。
[0152]
本发明中，当遗传算法最近的30次迭代中不出现新的最优解时,遗传算法停止并输出当前最优解的设计员分配方案；在判断终止条件时，首先判断a，而后判断b，添加这样的终止条件，可减少不必要的迭代次数，提高程序执行效率。
[0153]
s46:选择操作：根据适应度的高低，选择个体适应度值在5％的精英个体遗传到下
一代，剩下的95％个体则根据当前种群中个体适应度值的详情执行轮盘赌选择操作，直至新一代种群规模与所述步骤s41中的设置的种群规模相同时，进行下一步。
[0154]
轮盘赌选择算法每次计算出的选择概率都在[0,1]之间，且染色体被选择的概率完全由其自身的适应度决定。采用轮盘赌的方法从种群中选择子代种群时，个体选中的概率与其适应度函数值成正比。适应度越高的染色体越有可能被选中，自身优秀的基因更有可能传给下一代，适应程度较低的染色体也有概率被选中，这样增加了种群中染色体的多样性。
[0155]
s47：交叉操作：对选择后的种群进行交叉操作，所述交叉操作包括pox交叉和mpx交叉，所述pox交叉仅对所述设计任务顺序部分父代染色体进行交叉，所述mpx交叉仅对所述设计员部分父代染色体进行交叉，根据改进的交叉操作确定是否交叉，所述改进的交叉操作公式为：
[0156][0157]
其中，p
c1
表示最大交叉概率，p
c2
表示最小交叉概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f
′
为要交叉的两个个体中较大的适应度值，f为要变异个体的适应度值。
[0158]
s48：变异操作：根据改进的变异操作进行变异，所述变异操作包括插入变异和点对点变异，所述插入变异仅对所述设计任务顺序部分父代染色体进行变异，所述点对点变异仅对所述设计员部分父代染色体进行变异，所述改进的变异操作公式为：
[0159][0160]
其中，p
m1
表示最大变异概率，p
m2
表示最小变异概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f为要变异个体的适应度值。
[0161]
遗传算法的成功需要较大的交叉概率pc(0.5《pc《1.0)和较小的变异概率pm(0.001《pm《0.05)，交叉概率pc利于基因充分重组，而变异概率pm有益于增加种群的多样性能并防止种群陷入局部最优。为了保证染色体基因的充分重组,本发明采用了改进的交叉概率方法和改进的变异操作方法。
[0162]
为了提高变异操作的指导性与精确性，本发明对于不同的染色体采用不同的变异概率，对于优质个体应该采用较低的变异概率与变异方式来进行优良基因的保留，而对于劣质个体应该采用较高的变异概率与方式使其更适于生存。
[0163]
s49：生成下一代种群：经过步骤s46、s47、s48，生成新一代的种群。
[0164]
s410：计算当前种群适应度：先计算出当代种群所有个体适应度值，并且找出其中最大的那一个标记为当代最优个体，再把它与全局最优个体相互比较，若它的值更优，则将其作为全局最优个体，否则不作变化。
[0165]
s411：算法终止：判断是否满足迭代终止条件，若否，算法回转至s46；若是，则输
出，算法结束。
[0166]
s412：选择较优解群：合并所述步骤s411中输出的相同方案，并从合并后的方案中选取前5％作为较优解群。
[0167]
本发明针对遗传算法易丢失优良解、造成陷入局部最优解的不足，改进了子代种群产生方式，采用精英保留策略避免最优解的流失，并通过轮盘赌的方法来加速淘汰垃圾基因，加快种群求解速度。本发明选择出父代基因最优的5％的个体，将其基因排序进行主动调度解码，得到精英群体，将当前精英群体直接复制到下一代，剩下的95％子代种群由父代个体通过轮盘赌的方法选择，通过改进的交叉、变异操作进行交叉、变异后，选择适应度和基因质量高的遗传到下一代种群，经过迭代后达到终止条件并输出调度方案。由于输出的全部调度方案中会存在相同的调度方案，因此在所述步骤s412中选取时需先合并相同的调度方案，再从合并后的调度方案中选取前5％的调度方案作为较优解群。
[0168]
s5:结合所述步骤s4中获得的所述较优解群的设计员分配方案和所述步骤s2中获得的全体设计员评分表中所述较优解群中设计员在每个任务中的总评分，获得最早完工时间pt和初始总评分ps，将二者进行线性组合后得到最终评分，选取最终评分最大的方案为最优解，所述步骤s5具体为：
[0169]
s51：在所述步骤s4中获得的较优解群中确定每一个调度解的最早完工时间pt；
[0170]
s52：在所述步骤s2中获得的全体设计员评分表中查询所述较优解群中设计员在每个任务中的总评分，将每个任务的总评分相加后得到初始总评分ps；
[0171]
优选的，所述步骤s52中在所述步骤s2中获得的全体设计员评分表中查询到所述较优解群中设计员在每个任务中的总评分后，每个任务的总评分相加过程是由系统自动获取相加后得到初始总评分ps。
[0172]
s53：分别对所述初始总评分ps和所述最早完工时间pt进行归一化处理，获得目标总评分ps
′
和目标最早完工时间pt
′
，具体为：
[0173][0174][0175]
其中，ps
max
表示最大值初始总评分ps，ps
min
表示最小值初始总评分ps；pt
max
表示最大值最早完工时间pt，pt
min
表示最小值最早完工时间pt；
[0176]
归一化处理的目的就是使得预处理的数据被限定在一定的范围内(比如[0，1]或者[-1，1])，从而减小奇异样本数据导致的不良影响。这样做的意义可以加快模型的训练，加快收敛，甚至可能提高精度。
[0177]
本发明对所述初始总评分ps和所述最早完工时间pt进行归一化处理就是为了将其限定在一定的范围内，减小奇异样本数据导致的不良影响，收敛到最优解，提高精度。
[0178]
s54：计算最终评分sc，并将所述最终评分sc到大排序，其计算公式为：
[0179]
sc＝ω
01
ps
′
+ω
02
pt
′
[0180]
其中，sc为最终评分，ps
′
为目标总评分，ω
01
为目标总评分ps
′
的权重值，pt
′
为目标最早完工时间，ω
02
为目标最早完工时间pt
′
的权重值；
[0181]
优选的，所述步骤s54中赋予的权重是根据柔性作业车间实际需求设置。
[0182]
本发明出于车间实际产品设计任务作业需求，对目标总评分ps
′
和目标最早完工时间pt
′
的权重取值分别为：ω
01
取值为0.4，ω
02
取值为0.6。
[0183]
s55：根据最终结果，选取sc的最大值的方案为最优解。
[0184]
本发明中，sc越大说明求解质量越高，sc最大值即为算法求解的最优调度解。
[0185]
s6：根据最优解进行设计任务的调度与设计人员的分配。
[0186]
最后应说明的是：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.基于人员综合能力的设计任务调度优化算法，其特征在于，包括：s1:发布产品定制需求并形成产品设计任务以及设计任务的具体参数,所述任务参数中为空的位置使用0占位；s2:基于所述步骤s1中形成的所述任务参数,使用评分算法计算全体设计员的技能分、经验分和业绩分，通过ahp层次分析法赋予每项评分权重，计算出每位设计员总评分，根据所述总评分形成全体设计员评分全排列表，计算总评分的公式为：s1s1+ω2s2+ω3s3其中，s为设计员总评分，s1为设计员技能分分值，s2为设计员经验分分值，s3为设计员业绩分分值，ω1为设计员技能分权重值，ω2为设计员经验分权重值，ω3为设计员业绩分权重值；s3:建立带有约束条件的作业车间调度数学模型，所述作业车间调度数学模型包括工时目标函数和约束条件，所述作业车间调度数学模型描述为：将n个设计任务分配给m个设计能力不同的设计员进行设计，所述n个设计任务不仅包含有未分配的设计任务，还包含有优先级最高的未完成任务，其中需求r
i
(i∈{1,2,
…
,n})包含个设计任务，设计员p
k
(k∈{1,2,
…
,m对设计任务的工时用表示，工时为空的项则说明该设计员没有设计此项任务的能力，设计员p
k
对需求r
i
的设计任务的开始设计时间和完成设计时间分别为则设计员p
k
对设计任务的设计完成时间为：其中，i表示第i个需求，n
i
表示第i个需求中第n
i
个设计任务，k表示此项设计任务交给第k个设计员；表示设计员p
k
对第i个需求中第n
i
个设计任务的前一个设计任务n
i-1的完成时间；te
k
表示设计员p
k
结束第i个需求中第n
i-1个设计任务所需要的时间，即还需要多久的空闲时间；表示设计员p
k
结束第i个需求中第n
i-1个设计任务所需要的最大时间；需求中全部设计任务所有最晚完工时间为：其中，i表示第i个需求，n
i
表示第i个需求中第n
i
个设计任务；表示第i个需求中第n
i
个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第n
i
个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；故，工时目标函数为：其中，i表示第i个需求，n
i
表示第i个需求中第n
i
个设计任务；表示第i个需求中第
n
i
个设计任务的的完成时间，即完成第i个需求中全部设计任务的完成时间；表示完成第i个需求中第n
i
个设计任务所有最晚时间，即完成任意一项需求中全部设计任务所有最晚完工时间；pt表示最早完工时间，即完成任意一项需求中全部设计任务所有最晚完工时间中的最早完工时间；所述约束条件具体为：a.在零时刻，所有设计任务都可以被执行；b.同需求的设计任务严格按照设计顺序设计，每个设计任务必须在其前一个设计任务完成后才能进行；c.每个设计任务只能从可进行设计的设计员选择一名进行分配；s4：对所述步骤s3中的模型利用改进后的遗传算法进行处理，通过编码、生成初始种群、解码、计算适应度函数、选择操作、交叉操作及变异操作，直到满足迭代终止条件后输出，并选取输出结果的前5％作为较优解群；s5:结合所述步骤s4中获得的所述较优解群的设计员分配方案和所述步骤s2中获得的全体设计员评分表中所述较优解群中设计员在每个任务中的总评分，获得最早完工时间pt和初始总评分ps，将二者进行线性组合后得到最终评分，选取最终评分最大的方案为最优解，所述步骤s5具体为：s51：在所述步骤s4中获得的较优解群中确定每一个调度解的最早完工时间pt；s52：在所述步骤s2中获得的全体设计员评分表中查询所述较优解群中设计员在每个任务中的总评分，将每个任务的总评分相加后得到初始总评分ps；s53：分别对所述初始总评分ps和所述最早完工时间pt进行归一化处理，获得目标总评分ps
′
和目标最早完工时间pt
′
，具体为：，具体为：其中，
max
表示最大值初始总评分ps，ps
min
表示最小值初始总评分ps；pt
max
表示最大值最早完工时间pt，pt
min
表示最小值最早完工时间pt；s54：计算最终评分s
c
，并将所述最终评分s
c
到大排序，其计算公式为：s
c
＝ω
01
ps
′
+ω
02
pt
′
其中，s
c
为最终评分，
′
为目标总评分，ω
01
为目标总评分ps
′
的权重值，
′
为目标最早完工时间，ω
02
为目标最早完工时间pt
′
的权重值；s55：根据最终结果，选取s
c
的最大值的方案为最优解；s6:根据最优解进行设计任务的调度与设计人员的分配。2.根据权利要求1所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s2中使用评分算法计算全体设计员的技能分、经验分和业绩分具体规则为：技能分，是根据以往设计任务与所述步骤s1中形成的设计任务的相似度来进行赋分，所述相似度是通过采用欧氏距离方法计算获得，先计算出与以往每个设计任务的相似度并按相似度从大到小排序，选前三个相似度值相加后取平均值，即为该设计员的技能分分值；
经验分，是根据设计员已经完成的此类设计任务的数量占满分设计员任务数量的比重进行赋分，完成此类任务最多的设计员即为满分设计员，所述此类设计任务是指与所述步骤s1中形成的设计任务的相似度≥30％的设计任务；业绩分，是根据所述技能分中相似任务列表中客户反馈形成的分值相加后取平均值来进行赋分，每位客户评分的分值范围为0～100分，同时对于此次分配前已经开始但在零时刻仍未完成的相似任务，将进行该任务的设计员该项评分直接赋值为100分。3.根据权利要求2所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s2中通过ahp层次分析法赋予每项评分权重，具体为：a.建立评价指标，所述评价指标包括：技能、经验和业绩；b.根据所述评价指标构造判断矩阵；c.对所述判断矩阵进行一致性检验，当所述判断矩阵通过一致性检验时利用算数平均法计算各指标数据的权重。4.根据权利要求3所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s4中对所述步骤s3中的模型利用改进后的遗传算法进行处理的具体步骤为：s41:设置参数：设置种群规模popsize，初始交叉概率p
c1
和p
c2
，初始变异概率p
m1
和p
m2
，最大迭代次数gmax以及其他终止条件；s42:生成初始种群：对所述步骤s3中的模型编码成染色体，生成初始种群；s43:解码：根据染色体将设计任务分配到对应设计员得到的调度解采用改进的贪婪算法思想进行插入式解码操作，首先将染色体按照设计任务顺序解码得到调度解，然后再对这些解进行插入，即在调度每个任务的开始时刻时，考虑在满足同一设计任务而不改变设计任务顺序的情况下，将该设计任务分配到最早拥有空余时间大于等于设计工时的设计员手中，解码得到新的解，并将新编码顺序替换旧编码顺序，从而产生调度方案；s44:适应度计算：计算当代种群中出所有个体的适应度f(i)值，并找到值最优适应度值，将其作为当前当代最优解和当前全局最优解，所述适应度函数f(i)值是根据步骤s3计算所述工时目标函数值，再将所述工时目标函数值转化为适应度值，转化公式如下：其中，pt为最早完工时间，f(i)为从零时刻到最后工件完成时间点所需时间的倒数；s45:判断算法是否满足终止条件，若满足则输出较优解的设计员分配方案，算法结束；若不满足，则进入下一步；s46:选择操作：根据适应度的高低，选择个体适应度值在5％的精英个体遗传到下一代，剩下的95％个体则根据当前种群中个体适应度值的详情执行轮盘赌选择操作，直至新一代种群规模与所述步骤s41中的设置的种群规模相同时，进行下一步；s47:交叉操作：对选择后的种群进行交叉操作，所述交叉操作包括pox交叉和mpx交叉，所述pox交叉仅对所述设计任务顺序部分父代染色体进行交叉，所述mpx交叉仅对所述设计员部分父代染色体进行交叉，根据改进的交叉操作确定是否交叉，所述改进的交叉操作公式为：
其中，p
c1
表示最大交叉概率，p
c2
表示最小交叉概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f
′
为要交叉的两个个体中较大的适应度值，f为要变异个体的适应度值；s48:变异操作：根据改进的变异操作进行变异，所述变异操作包括插入变异和点对点变异，所述插入变异仅对所述设计任务顺序部分父代染色体进行变异，所述点对点变异仅对所述设计员部分父代染色体进行变异，所述改进的变异操作公式为：其中，p
m1
表示最大变异概率，p
m2
表示最小变异概率，f
max
为群体中个体最大适应度值，f
avg
为每代群体的平均适应度值，f为要变异个体的适应度值；s49：生成下一代种群：经过步骤s46、s47、s48，生成新一代的种群；s410：计算当前种群适应度：先计算出当代种群所有个体适应度值，并且找出其中最大的那一个标记为当代最优个体，再把它与全局最优个体相互比较，若它的值更优，则将其作为全局最优个体，否则不作变化；s411：算法终止：判断是否满足迭代终止条件，若否，算法回转至s46；若是，则输出，算法结束；s412：选择较优解群：合并所述步骤s411中输出的相同方案，并从合并后的方案中选取前5％作为较优解群。5.根据权利要求4所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述编码采用双段编码方式，每一个染色体代表一种调度方案，染色体长度等于任务数量n，包括设计任务顺序编码和设计员编码，所述设计任务顺序编码用来确定设计任务出现的先后次序；所述设计员编码是按照设计任务的进行次序来排列的，用来获取每个设计任务对应的设计员。6.根据权利要求5所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述设计任务顺序编码的初始化方法为随机生成；所述设计员编码的初始化方法包括全局选择和局部选择，这两种初始化方法的比例为1:1，由此生成初始种群，所述设计员编码的初始化方法具体步骤为：所述全局选择方法具体为：设置一个数组，长度和人员数相等，数组的顺序依次对应设计人员的顺序，每一位上的值对应设计人员完成此任务的工时，随机在需求集中选择一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推，直到当前需求中的所有任务的设计人员选择完毕后，然后再随机选择一个需求开始，直到所有需求中的的所有任务选择完毕
为止；所述局部选择方法具体为：对一个需求选择完毕时，数组需要重新设置为零，不存在随机选择需求，设置一个数组，长度和人员相等，选择需求集中第一个需求，从当前需求中的第一个任务开始，将当前任务的可选设计人员的工时加上数组中对应的时间，从中选择最短的时间作为当前任务的设计人员，并且将数组更新，即把被选择的设计人员的工时加到数组中相应的位置上，以此类推。7.根据权利要求6所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s45在判断终止条件时，采用两种终止条件，分别如下：a.如果全局最优染色体在连续x代无更优解，则终止程序，并将此解作为最优解输出；b.如果未出现情况a，则一直执行到最大迭代次数gmax，并输出全局最优解。8.根据权利要求7所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s52中在所述步骤s2中获得的全体设计员评分表中查询到所述较优解群中设计员在每个任务中的总评分后，每个任务的总评分相加过程是由系统自动获取相加后得到初始总评分ps。9.根据权利要求8所述的基于人员综合能力的设计任务调度优化算法，其特征在于，所述步骤s54中赋予的权重是根据柔性作业车间实际需求设置。

技术总结
本发明公开了一种基于人员综合能力的设计任务调度优化算法，包括：发布定制需求并形成设计任务以及具体的任务参数；基于任务参数使用评分算法计算全体设计员的总评分，得到全体设计员评分全排列表；建立柔性作业车间调度数学模型，利用改进后的遗传算法对模型进行求解，获得较优解群的设计员分配方案；结合较优解群的设计员分配方案和全体设计员评分表进行线性组合后得到最终评分，选取最终评分最大的方案为最优解；根据最优解进行设计任务的调度与设计人员的分配。本发明结合评分算法和改进的遗传算法来设计柔性作业车间人员调度及任务分配方案，达到了在平衡设计员工作负荷的同时获得最早完工时间的目标。同时获得最早完工时间的目标。同时获得最早完工时间的目标。


技术研发人员：范浩 代勇 赵琳 闫宪峰 葛海婷 乔康定
受保护的技术使用者：山西省机电设计研究院有限公司
技术研发日：2023.05.08
技术公布日：2023/8/4