CN112884367A - 考虑多技能员工约束的高端装备研发过程多项目协同调度方法及系统 - Google Patents

Abstract

本发明公开了一种考虑多技能员工约束的高端装备研发过程多项目协同调度方法及系统，属于任务调度技术领域。包括：1、获取高端装备的研发任务数据；2、设定算法相关参数；3、执行AC启发式规则；4、得出的结果作为算法初始解；5、对初始解进行Shaking操作；6、执行基于EX、SEC和TEC的变邻域搜索；7、判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤4。本发明能针对考虑多技能员工约束的高端装备研发过程多项目调度问题，求得近似最优解，从而使得高端装备制造企业能在最大限度上利用人力资源，缩短产品研发周期，从而提高企业核心竞争力。

Description

考虑多技能员工约束的高端装备研发过程多项目协同调度方 法及系统

技术领域

本发明涉及任务调度技术领域，具体来说是考虑多技能员工约束的高端装备研发过程多项目协同调度方法及系统。

背景技术

高端装备是指技术含量高、资金投入大、涉及学科多、服役寿命长，其研发与制造一般须要组织跨部门、跨行业、跨地区的力量才能完成的一类技术装备。高端装备研发能力的提升对我国装备制造业转型升级起到重要引擎作用，是国家发展战略的核心层面。高端装备的研发任务规模巨大，研发人员数量众多，任务间关系复杂，使得高端装备的研发调度问题成为企业实际生产中的“卡脖子”技术难点。资源受限的多项目调度问题作为一类经典的组合优化问题，广泛应用于现代化企业实际生产中，如航天装备、高速动车组、智能网联汽车等高端装备领域。与传统项目调度问题不同，在高端装备制造企业的实际研发过程中员工起到了至关重要的作用，包括任务的人员分配，任务的加工顺序，项目的工期缩短等。随着以大数据和人工智能为代表的新一代信息技术的快速发展，国内外学者提出了针对该问题的各类智能算法和启发式算法，推动产品研发的快速高效进行。

关于人员约束下多项目调度问题的现有研究，主要集中在人员多技能或者多模式调度上。通常假设任务可以由多个模式执行或者任务需要多个技能的员工共同完成，各个模式下人员的需求量确定或者多技能员工能力不存在差异。

现有技术中，Smet等人^[1]提出了一种混合两阶段启发式算法来确定员工技能和任务需求的最优匹配；Peteghem等人^[2]提出了针对多模式资源受限项目调度问题构建了元启发式算法并在新的数据集上进行比较算法性能。然而，这些研究都是分别针对多技能和多模式问题进行单独分析，现有技术中关于二者的结合以及员工能力差异化问题的分析相对较少。在实际的研发过程中，一个任务的完成既需要多个技能，同时也存在研发人员的调动和变换。此外，员工的能力也具有差异化表现。最终使得产生的研发任务调度方案无法应用到实际生产环境中，存在较大差异。

[1]Smet P,Wauters T,Mihaylov M,et al.The shift minimisation personneltask scheduling problem:A new hybrid approach and computational insights[J].Omega,2014,46(9):64-73.

[2]VanPeteghem V,Vanhoucke M.An experimental investigation ofmetaheuristics for the multi-mode resource-constrained project schedulingproblem on new dataset instances[J].European Journal of Operational Research,2014,235.

基于以上论述，现有技术存在以下缺陷：

(1)目前对多模式和多技能相结合的多项目协同调度问题的研究相对较少，很多学者提出的调度模型大多集中在资源数量固定下的模式选择、多技能人员和任务的匹配优化上面，而忽略了二者结合对企业实际研发的影响，同时在任务分配阶段要考虑研发人员能力的差异化对缩短项目完工时间尤为重要，这会大大降低研发产品的成本，提高高端装备企业核心竞争力。

(2)针对高端装备研发过程任务数量巨大，研发人员众多，工艺流程复杂等特点，目前相关研究对此较少展开深入分析，而是采用智能算法进行直接寻优，这导致一方面算法收敛速度较慢，另一方面得出的结果和最优解相比差距较大。

(3)除此之外，在算法方面，变邻域搜索算法也存在着依赖初始解和容易早熟等缺点，特别是针对特定的优化问题无法给出稳定可靠的解决方案，不利于多项目协同研发效率的提升。因此，本发明需要根据具体的研究问题，设计有针对性的邻域结构，改进变邻域搜索算法，从而实现高端装备研发过程高效快速的进行。

发明内容

本发明所要解决的技术问题在于现有技术中未考虑多技能员工约束的高端装备研发过程多项目协同调度问题。

本发明通过以下技术手段实现解决上述技术问题：

考虑多技能员工约束的高端装备研发过程多项目协同调度方法，包括以下步骤：

S1、获取高端装备的研发任务数据；生成任务列表，采用X＝(S,M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

S2、设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M}以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

S3、执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工p_m，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

S4、对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

S5、将输出的结果作为变邻域搜索算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1；

S6、对初始解进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(S’，N_k)得到解S’在邻域k中的最优解S”；

S7、判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤5。

进一步的，所述步骤S3中最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

本发明针对考虑多技能员工约束的高端装备研发过程多项目协同调度问题，针对高端装备研发过程的特性，本发明考虑员工具有多技能并且员工能力具有差异性，这属于多技能匹配问题；同时一项任务只分配给一个研发人员，这又涉及到多模式选择问题。本发明创新性地将二者同时考虑，这更符合高端装备企业的实际生产环境，具有广泛的实用性。

进一步的，所述步骤S4中总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务A_ij的最早结束时间。

进一步的，所述步骤S3中实际工期计算方法为：

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

进一步的，所述步骤S6中，所述初始解S在三种邻域结构中寻找最优解，三种邻域结构具体为：

邻域结构1：交换

交换邻域结构是对编码S中相邻的两个任务进行交换位置，编码M中任务相对应的员工位置也随之交换，其中虚拟任务不参与交换；因此得到

个新的邻域解；由于产生的新解可能并不满足紧前紧后关系约束，所以改进策略是在交换两个相邻位置任务之间，先判断任务i是否为任务i+1的紧前任务，因此，最终得到的新解数量会小于等于n-1；

邻域结构2：单员工变换

单员工变换邻域结构改变编码M中一个任务分配的员工并且由此产生的所有新解都是可行解，|M_k|表示可以完成任务k的员工数量，单员工变换邻域结构产生的新解数量取决于任务数量n以及

邻域结构3：双员工变换

双员工变换邻域结构同时改变编码M中两个任务分配的员工，所产生的所有新解都是可行解，

本发明还提供考虑多技能员工约束的高端装备研发过程多项目协同调度系统，包括

任务数据获取模块，获取高端装备的研发任务数据；生成任务列表，采用X＝(S，M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

参数设定模块，设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M)以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

算法执行模块，执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工p_m，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

解码模块，对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

迭代模块，将输出的结果作为变邻域搜索算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1；

Shaking操作模块，对初始解进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(S’，N_k)得到解S’在邻域k中的最优解S”；

判断模块，判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤5。

进一步的，所述算法执行模块中最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

进一步的，所述解码模块中总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务A_ij的最早结束时间。

进一步的，所述算法执行模块中实际工期计算方法为：

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

进一步的，所述Shaking操作中，所述初始解S在三种邻域结构中寻找最优解，三种邻域结构具体为：

邻域结构1：交换

交换邻域结构是对编码S中相邻的两个任务进行交换位置，编码M中任务相对应的员工位置也随之交换，其中虚拟任务不参与交换；因此得到

个新的邻域解；由于产生的新解可能并不满足紧前紧后关系约束，所以改进策略是在交换两个相邻位置任务之间，先判断任务i是否为任务i+1的紧前任务，因此，最终得到的新解数量会小于等于n-1；

邻域结构2：单员工变换

单员工变换邻域结构改变编码M中一个任务分配的员工并且由此产生的所有新解都是可行解，|M_k|表示可以完成任务k的员工数量，单员工变换邻域结构产生的新解数量取决于任务数量n以及

邻域结构3：双员工变换

双员工变换邻域结构同时改变编码M中两个任务分配的员工，所产生的所有新解都是可行解，

本发明的优点在于：

1、本发明针对考虑多技能员工约束的高端装备研发过程多项目协同调度问题，考虑高端装备研发过程的特性，本发明考虑员工具有多技能并且员工能力具有差异性，这属于多技能匹配问题；同时一项任务只分配给一个研发人员，这又涉及到多模式选择问题。本发明创新性地将二者同时考虑，这更符合高端装备企业的实际生产环境，具有广泛的实用性。

2、本发明提出一些关于员工调动时最优的启发式性质。本发明证明了研发人员在面临多个同时需要处理的任务时，如何选择才能符合项目完工时期最短的目标。本发明给出了项目关键路径上任务的员工变换需要满足的条件，才能有效的缩短项目的完工时间。基于上述性质，本发明提出了启发式算法，通过该算法，本发明可以得出问题较优的初始解，这也为后续的智能算法的快速收敛提供了基础。

3、根据本发明研究问题的特性，本发明设计了三种邻域结构并提出了一种变邻域搜索算法求解多技能约束的高端装备研发过程多项目协同调度问题。将启发式算法给出的解作为变邻域搜索算法的初始解，这会加速算法的收敛速度。对初始解进行Shaking操作得到新解，将新解通过三个邻域结构生成大量邻域解，有利于算法最大可能的在解空间内搜索问题的最优解。在解空间内进行搜索，得到邻域最优解。更新全局最优解，通过反复迭代，最终求得近似最优解。通过和其他算法进行比较，在收敛速度和收敛结果上，本发明提出的算法是一种效率很高的算法；通过该算法，解决了考虑多技能员工约束的高端装备研发过程多项目协同调度问题，提高了高端装备的研发效率，降低企业的研发成本，提高高端装备制造企业的核心竞争力。

附图说明

图1为本发明实施例中考虑多技能员工约束的高端装备研发过程多项协同调度方法的执行流程框图；

图2为研发任务数量n＝370时，采用本发明实施例中考虑多技能员工约束的高端装备研发过程多项协同调度方法与其他3种方法的实验收敛对比折线图；

图3为研发任务数量n＝1016时，采用本发明实施例中考虑多技能员工约束的高端装备研发过程多项协同调度方法与其他3种方法的实验收敛对比折线图。

具体实施方式

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

考虑多技能员工约束的高端装备研发过程多项协同调度问题，目标为最小化项目完工日期。该问题描述如下：给定一个项目组包含了N个项目，项目i(i＝1，2，...，N)是由J_i+1个非抢占式任务组成，其中第一个任务(j＝0)和最后一个任务(j＝J_i)为虚拟任务，即任务的工期为0且不占用任何资源。项目i第j项任务A_ij的开始时间为S_ij，其中第一项任务的开始时间要大于项目的释放时间，即S_i0≥r_i。项目组的研发人员共有M个，p＝{p₁，p₂，...，p_M}，每个员工是多技能并且可以独立完成任务。其中，x_ijm＝1表示员工p_m可以完成任务A_ij，否则为0。因此，人员和任务集之间存在一对多的映射关系，即一项任务是由一个研发人员来完成，一个研发人员可以被分配多项任务，但是在同一时间只能做一项任务。本实施例用o_ij来表示所有可以完成任务A_ij的研发人员集合，即

需要优化的目标函数是最小化项目组最大完工时间，即最小化完工时间最大的项目

如图1所示，本实施例考虑多技能员工约束的高端装备研发过程多项目协同调度具体方法如下：

步骤1、获取高端装备的研发任务数据；生成任务列表，采用X＝(S，M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

步骤2、设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M}以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

步骤3、执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工pm，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

步骤4、对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务A_ij的最早结束时间。

步骤5、将输出的结果作为变邻域算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1。

步骤6、对初始解S进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(S’，N_k)得到解S’在邻域k中的最优解S”；初始解S在三种邻域结构中寻找最优解，三种邻域结构具体为：

邻域结构1：交换

交换邻域结构的主要思想是对编码S中相邻的两个任务进行交换位置，编码M中任务相对应的员工位置也随之交换，其中虚拟任务不参与交换。因此本发明可以得到

个新的邻域解。需要注意的一点是产生的新解可能并不满足紧前紧后关系约束，所以本发明提出的改进策略是在交换两个相邻位置任务之间，先判断任务i是否为任务i+1的紧前任务。因此，本发明最终得到的新解数量会小于等于n-1。

邻域结构2：单员工变换

单员工变换邻域结构改变编码M中一个任务分配的员工并且由此产生的所有新解都是可行解。|M_k|表示可以完成任务k的员工数量，单员工变换邻域结构产生的新解数量取决于任务数量n以及

邻域结构3：双员工变换

双员工变换邻域结构同时改变编码M中两个任务分配的员工，和单员工变换邻域结构一样，它所产生的所有新解都是可行解。但是双员工变换产生新解的数量要远大于单员工邻域结构：

Shaking操作的目的是跳出局部最优解，本文提出的Shaking操作是通过随机改变某任务i的执行员工，从而产生新的可行解。这种方法提供了一定程度的多样化，同时无需对当前解进行大幅度修改。

步骤7、判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤5。

本实施例设计任务数量分别为n＝370、n＝1016时四种算法的实验，图2、图3分别为两种任务数量的收敛图，可以看出和其他算法相比，本实施例提出的算法具有更强的优化能力。特别是当案例规模较大时，本文设计的变邻域搜索算法在收敛速度以及收敛能力具有更好的表现。

本实施例还提供了一种考虑多技能员工约束的高端装备研发过程多项目协同调度系统，包括

任务数据获取模块，获取高端装备的研发任务数据；生成任务列表，采用X＝(S，M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

参数设定模块，设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M}以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

算法执行模块，执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工p_m，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

解码模块，对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务A_ij的最早结束时间。

迭代模块，将输出的结果作为变邻域搜索算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1。

Shaking操作模块，对初始解进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(S’，N_k)得到解S’在邻域k中的最优解S”；

判断模块，判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤5。

本实施例还提供一种处理设备，包括至少一个处理器，以及与处理器通信连接的至少一个存储器，存储器存储有可被处理器执行的程序指令，处理器调用程序指令能够执行如权利上述的方法。

本实施例还提供一种计算机可读存储介质，计算机可读存储介质存储计算机指令，计算机指令使计算机执行上述的方法。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (10)

1.考虑多技能员工约束的高端装备研发过程多项目协同调度方法，其特征在于，包括以下步骤：

S1、获取高端装备的研发任务数据；生成任务列表，采用X＝(S，M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

S2、设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M}以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

S3、执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工p_m，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

S4、对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

S5、将输出的结果作为变邻域搜索算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1；

S6、对初始解进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(s’，N_k)得到解S’在邻域k中的最优解S”；

S7、判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤S5。

2.根据权利要求1所述的考虑多技能员工约束的高端装备研发过程多项目协同调度方法，其特征在于，所述步骤S3中最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

3.根据权利要求1所述的考虑多技能员工约束的高端装备研发过程多项目协同调度方法，其特征在于，所述步骤S4中总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务A_ij的最早结束时间。

4.根据权利要求1所述的考虑多技能员工约束的高端装备研发过程多项目协同调度方法，其特征在于，所述步骤S3中实际工期计算方法为：

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

5.根据权利要求1所述的考虑多技能员工约束的高端装备研发过程多项目协同调度方法，其特征在于，所述步骤S6中，所述初始解S在三种邻域结构中寻找最优解，三种邻域结构具体为：

邻域结构1：交换

交换邻域结构是对编码S中相邻的两个任务进行交换位置，编码M中任务相对应的员工位置也随之交换，其中虚拟任务不参与交换；因此得到

个新的邻域解；由于产生的新解可能并不满足紧前紧后关系约束，所以改进策略是在交换两个相邻位置任务之间，先判断任务i是否为任务i+1的紧前任务，因此，最终得到的新解数量会小于等于n-1；

邻域结构2：单员工变换

单员工变换邻域结构改变编码M中一个任务分配的员工并且由此产生的所有新解都是可行解，|M_k|表示可以完成任务k的员工数量，单员工变换邻域结构产生的新解数量取决于任务数量n以及|M_k|：

邻域结构3：双员工变换

双员工变换邻域结构同时改变编码M中两个任务分配的员工，所产生的所有新解都是可行解，

6.考虑多技能员工约束的高端装备研发过程多项目协同调度系统，其特征在于，包括：

任务数据获取模块，获取高端装备的研发任务数据；生成任务列表，采用X＝(S，M)表示任务的人员分配及生产顺序，其中S＝(0，...，k，...n+1)表示任务的调度顺序，M＝(0，...，m，...，0)表示S部分任务对应分配的员工；

参数设定模块，设定启发式算法相关参数；包括各项目释放时间r_i，项目i的任务数量J_i，任务A_ij的标准工期da_ij，员工p＝{p₁，p₂，...，p_M}以及对应的能力系数l₁，l₂，...，l_M，算法的最大迭代次数t_max，当前迭代次数t＝1；

算法执行模块，执行启发式算法，计算各个任务的最早开始时间ES_ij以及最迟完工时间LF_ij，根据最早开始时间ES_ij和最迟完工时间LF_ij随机分配符合条件的员工p_m，然后根据员工p_m的能力系统计算各个任务的实际工期，最后使用AT规则以及最小时差规则产生可行的任务列表；

所述AT规则为：

对于资源受限的多项目协同调度问题，假设当两个并行的研发任务A_ij和A_mn需要使用同一员工时，为了使整个项目组的完工时间最小化，需要首先调度最迟完工时间较小的那个任务；

解码模块，对所述可行的任务列表进行解码，并计算项目的关键路径及非关键路径上每个任务的总时差TF，根据总时差大小进行降序排序，并依次将能力强的员工替换给关键路径上的任务，如果满足规则CE，则转至步骤S3，否则输出结果，

所述CE规则为：

当给出多项目协同调度问题的研发人员安排时，只有满足以下条件，将任务A_ij研发人员p_m改变成能力更强的员工p_n才会缩短项目的完工时期；

(l_n-l_m)≤minTF

其中任务A_ij为关键路径上的任务，minTF表示非关键路径上任务最小总时差。

迭代模块，将输出的结果作为变邻域算法的初始解S；当前迭代次数为t＝1，当前邻域结构为k＝1；

Shaking操作模块，对初始解进行Shaking操作，得到新解S’，对新解S’进行邻域k搜索(s’，N_k)得到解S’在邻域k中的最优解S”；

判断模块，判断是否满足算法执行的终止条件，如果满足则输出算法的全局最优解，否则返回步骤5。

7.根据权利要求6所述的考虑多技能员工约束的高端装备研发过程多项目协同调度系统，其特征在于，所述算法执行模块中最早开始时间ES_ij以及最迟完工时间LF_ij的计算方法为：

ES_i0＝r_i

其中Z为任务A_ij所有紧前任务的集合，Q为任务A_ij所有紧后任务的集合。

8.根据权利要求6所述的考虑多技能员工约束的高端装备研发过程多项目协同调度系统，其特征在于，所述解码模块中总时差TF的计算方法为：

TF_ij＝LS_ij-ES_ij＝LF_ij-EF_ij

其中，LS_ij为任务A_ij的最迟开始时间，ES_ij为任务A_ij的最早开始时间，LF_ij为任务A_ij的最迟结束时间，EF_ij为任务Aij的最早结束时间。

9.根据权利要求6所述的考虑多技能员工约束的高端装备研发过程多项目协同调度系统，其特征在于，所述算法执行模块中实际工期计算方法为：

对于多技能员工约束下的高端装备研发过程多项目协同调度问题，任务A_ij的实际工期必须在分配好研发人员之后才能确定，此外必须满足以下条件：

(1)任务只能分配给一个员工

(2)一个员工在同一时间只能做一件任务

此时可以得到任务A_ij实际的工期为：

其中da_ij为任务A_ij的标准工期，l_m为员工p_m的能力系数。

10.根据权利要求6所述的考虑多技能员工约束的高端装备研发过程多项目协同调度系统，其特征在于，所述步骤S6中，所述初始解S在三种邻域结构中寻找最优解，三种邻域结构具体为：

邻域结构1：交换

交换邻域结构是对编码S中相邻的两个任务进行交换位置，编码M中任务相对应的员工位置也随之交换，其中虚拟任务不参与交换；因此得到

个新的邻域解；由于产生的新解可能并不满足紧前紧后关系约束，所以改进策略是在交换两个相邻位置任务之间，先判断任务i是否为任务i+1的紧前任务，因此，最终得到的新解数量会小于等于n-1；

邻域结构2：单员工变换

单员工变换邻域结构改变编码M中一个任务分配的员工并且由此产生的所有新解都是可行解，|M_k|表示可以完成任务k的员工数量，单员工变换邻域结构产生的新解数量取决于任务数量n以及|M_k|：

邻域结构3：双员工变换

双员工变换邻域结构同时改变编码M中两个任务分配的员工，所产生的所有新解都是可行解，

Images