CN113779492A - 一种面向敏捷开发的需求任务规划算法 - Google Patents

Abstract

本发明涉及一种面向敏捷开发的需求任务规划算法，包括团队合并、生成两个初始解、轮流使用不同的解进行搜索，在解的搜索过程中使用不同的变换操作的算子进行搜索，设计评价矩阵，通过自适应决策机制指导解的搜索。与现有技术相比，本发明通过团队合并缩小了解空间的规模，提高了求解速度；生成了两个初始解，设计了两种执行顺序，根据算法的搜索结果切换解和执行顺序，相当于在解空间中从两个不同的起点按照不同的搜索方向进行搜索，大大避免了陷入局部最优解的可能，搜索效率更高；设计了自适应搜索机制，使用评价矩阵记录项目算子组合的评价值，通过评价矩阵来衡量算子的性能，指导解的搜索，避免了随机盲目搜索导致的资源浪费。

Description

一种面向敏捷开发的需求任务规划算法

技术领域

本发明涉及一种任务规划算法，尤其是涉及一种面向敏捷开发的需求任务规划算法。

背景技术

如今，敏捷开发的开发模式越来越多的被互联网企业、一般企业的IT部门所使用，它是一种迭代、循序渐进、以人为本的软件开发方法，具有改变传统线性开发模式中交付周期长、过程可视化程度弱、团队间协作程度差的问题。敏捷开发依靠非正式的沟通来快速传递整个团队和其它利益相关者的信息，以高效的沟通来替代繁重的正式文档，为需求和开发人员减负，更加关注需求本身而不是各类说明文档等过程“工件”。此外由于互联网环境瞬息万变，敏捷开发模式能够灵活的在开发过程中适应变化的需求情况。

敏捷开发模式具有较多的好处，但协作和沟通是实现敏捷的关键。虽然越来越多的软件开发团体意识到：没有高度协作的环境任何敏捷方法都注定要失败，但实际项目实施过程中，多数的沟通都是通过项目管理人员进行人为干涉。这样的管理方式缺乏科学方法的指引，十分容易造成敏捷模式失效；并且在大规模项目研发、多团队协作的敏捷开发模式实施场景中能够匹配的任务规划方法非常少。面对多个团队、多个项目的场景，如何将项目任务进行合理分配是管理者的一个难题。

现有技术中，解决该问题的任务规划算法大致分为三类。

第一类：(基于DSM的多产品开发项目协同规划方法研究)研究产品与产品、产品与开发团队间依赖关系，通过建立评价体系，用以评价研发团队的各类能力，以及任务的需求强度，规划方式是目标通过合理组合着力于解决研发任务与人员间冲突关系，即为任务寻找更加专业的团队。中国专利CN201910501470.9中公开的基于能力匹配的异地敏捷开发任务分配方法就利用了这一思想。但是，该类任务规划方式往往只能人为的主观判断二者之间的依赖关系(或者有人参与的量化评价这种依赖关系)，同时不能量化不同依赖关系间的强弱，虽然部分研究通过专家评价的方式来对依赖强弱进行量化，但这种方式准确性难以保证，仅能近似描述这种强弱关系。并且该种任务规划方式难以适应大规模任务规划问题，因为需要通过指数级增长的依赖评价后才能进行规划，这在实际场景中几乎是不能实现的。

第二类：通过启发式的算法解决项目管理任务调度方案。该方式一般能够适应大规模任务规划场景，但这类研究很少有以敏捷开发场景作为为背景的，例如(效率异质型员工项目调度算法研究)使用模拟退火算法，算法中基于优先规则生成一个初始调度，交换和插入两种变邻域方式不断更新解，通过经典的模拟退火规则来控制解的接受方式，最终让算法逼近与一个近似最优的规划调度方案。但是，由于没有考虑敏捷开发模式下对沟通的要求，虽然该算法能够通过计算搜索到一个工期最短的可行方案，这并不能适应敏捷开发模式下对沟通的要求。

第三类：多项目多任务的动态规划方案：(多项目多任务选择动态规划及其智能决策)考虑了一种资源受限情况下改进型免疫遗传算法，该算法通过尽量将资源均衡、充分利用，从而更好适应如机器故障、配料临时缺乏等突发因素对项目实施的影响。该算法中设计了：一种拥有项目层、任务层及执行阶段层三个层次的编码方式，基于所使用的编码方式设计了：环境检测、基因重组、基因变异三个算子对细胞群体进行更新，并在每次群体更新前动态调节项目权值，最终输出群体中保存的最优解。但是，同样的，由于没有考虑敏捷开发模式下对沟通的要求，这类研究设计的启发式算子、权重更新机制等模块同样不能完全适应敏捷开发模式，即求解结果并不能关注到敏捷模式对沟通的要求。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种面向敏捷开发的需求任务规划算法。

首先进行一些名词说明、术语解释和前提条件说明：

规划周期是一个时间段，如7月1日至10月31日，R表示规划周期的长度，如90天、100天等，是已知值；

项目集合SC，表示待分配的n个项目S_i(i＝1,2…n)的集合，是已知值；

项目S_i的交付日期记为SD_i，是已知值，项目S_i的所有原子任务应当在交付日期之前完成，否则，项目S_i没有被按时完成；

团队集合GC，表示m个团队G_j(j＝1,2…m)的集合，是已知值；

可用时间窗，是一个时间段，如8月1日至8月10日，7月15日至9月19 日等，团队G_j在自己的可用时间窗内工作，团队G_j的可用时间窗为GS_j至GE_j，团队 G_j的可用时间窗的开始时间点为GS_j，如9月1日，是已知值，团队G_j的可用时间窗的结束时间点为GE_j，如10月20日，是已知值；

单日工作量GD_j(GD_j＞0)，表示团队G_j单日可完成的工作量，是已知值；

原子任务，任意项目S_i可被拆分成t个原子任务，t≥2，原子任务是可直接交由一个团队执行的任务，且原子任务不可再拆分，这t个原子任务的集合为项目S_i的原子任务集合TCⁱ，是已知值，原子任务之间相互独立，不存在时序上的依赖关系，任意团队执行同一原子任务的效果一样，即不考虑时间约束时，任何团队可以完成任意原子任务，且执行任务的效果一样，不同团队执行原子任务的速度与团队的单日工作量有关；

项目S_i的原子任务集合TCⁱ中，T_i,k(k＝1,2…t,t≥2)表示项目S_i的第k个原子任务，项目S_i的工作量为SL_i，原子任务T_i,k的工作量为TL_i,k，均是已知值， x_i,j,k∈{0,1}，当x_i,j,k＝1时表示由团队G_j执行项目S_i下的原子任务T_i,k；

原子任务T_i,k的开始执行时间节点为TS_i,k，如7月1日，原子任务T_i,k的结束执行时间节点为TE_i,k，如7月10日，若原子任务T_i,k被规划给团队G_j执行，则x_i,j,k＝1。

在敏捷开发模式下，沟通时间必不可少，且对沟通时长有要求，将多个项目的多个原子任务分配给多个团队时，如果一个原子任务执行时不满足团队内沟通约束，则该原子任务为内沟通无效的原子任务，如果一个原子任务执行时不满足团队间沟通约束，则该原子任务为外沟通无效的原子任务，如果一个解中各个原子任务既满足团队内沟通约束又满足团队间沟通约束，且每个项目均早于交付日期完成，则该解为可行解。在一个理想的最优的分配方案中，各个原子任务都尽可能的满足团队内沟通约束、团队间沟通约束，而且每个项目都能尽可能的早于交付日期完成。

本发明的目的可以通过以下技术方案来实现：

一种面向敏捷开发的需求任务规划算法，包括以下步骤：

S1、获取项目集合和团队集合，将多个团队进行团队合并，将合并后的团队集合作为新的团队集合；

S2、基于项目集合和团队集合生成两个初始解，将其中一个初始解作为当前解，将另一个初始解作为备选解，将两个初始解中的最优解作为全局最优解，预设置两种执行顺序，将其中一个执行顺序作为当前执行顺序，将另一个执行顺序作为备选执行顺序，如果两个初始解中存在可行解，则将两个初始解中可行且最优的解作为可行最优解，如果不存在可行解，则将可行最优解置零，任意解优于置零解；

S3、变换操作分为三类：优化分配操作、团队内沟通调整操作和团队间沟通操作，按照当前执行顺序，选择一类变换操作，对当前解进行变换操作得到多个候选解，将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

S4、如果满足预设置的终止条件，则输出可行最优解，否则，判断是否满足预设置的解切换条件，如果满足解切换条件，则交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5，如果不满足解交换条件，则直接执行步骤S5；

S5、如果满足预设置的扰动条件，则对当前解进行扰动操作，执行步骤S3，否则，直接执行步骤S3。

进一步的，团队的规模是影响解规模的重要因素，随着项目数量n和团队规模 m的增加，解空间的大小成指数型爆炸增长，因此如果能缩减研发团队规模，解空间也能够被有效缩小，本申请因此提出一种团队合并方法，在步骤S1中进行团队合并，步骤S1包括以下步骤：

A0、将待合并的多个团队放入待合并团队集合；

A1、如果待合并团队集合为空，则团队合并结束，执行步骤A4，否则，计算待合并团队集合中各个团队的可用时间窗的长度，自待合并团队集合中选择可用时间窗长度最大的待合并团队，记为团队G_j，团队G_j的可用时间窗的长度为(GE_j-GS_j)，将待合并团队集合中所有可用时间窗长度小于(R-(GE_j-GS_j))的团队放入团队G_j的候选集合，执行步骤A2；

其中，可用时间窗是一个时间段，各个团队在自己的可用时间窗内工作，团队G_j的可用时间窗的开始时间点预设置为GS_j，团队G_j的可用时间窗的结束时间点预设置为GE_j，R表示规划周期的长度，规划周期是一个预设置的时间段；

A2、如果团队G_j的候选集合为空，则从待合并团队集合中删除团队G_j并将团队 G_j放入已合并团队集合，执行步骤A1，否则，自团队G_j的候选集合中选择(GE_j-GS_j)的值最大的团队，记为团队G_i，执行步骤A3；

A3、如果团队G_i与团队G_j的可用时间窗不重合，则执行步骤A31，如果团队G_i的可用时间窗完全落在团队G_j的可用时间窗内，则执行步骤A32，如果团队G_i的可用时间窗与团队G_j的可用时间窗部分重合，则执行步骤A33；

A31、若GS_j≥GE_i，则将团队G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队 G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若GE_j≤GS_i，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤A1；

A32、GS_j≤GS_i且GE_j≥GE_i，自团队G_j的候选集合中删除团队G_i，执行步骤 A2；

A33、自项目集合中筛选出交付日期晚于GE_i的项目，自这些项目的所有原子项目集合中找出工作量最小的原子任务，将该原子任务的工作量记为TL，如果团队G_i与团队G_j在重合的可用时间窗内均能完成工作量为TL的原子任务，则自团队G_j的候选集合中删除团队G_i，执行步骤A2，否则，执行步骤A331；

其中，一个项目可以被拆分为多个原子任务，任意团队均可以执行任意原子任务，且原子任务不可再拆分，同一个项目的原子任务之间不存在执行时序上的依赖关系；

A331、若TL＞(GE_i-GS_j)·GD_j＞0或TL＞(GE_i-GS_j)·GD_i＞0，则将团队 G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若TL＞(GE_j-GS_i)·GD_j＞0或 TL＞(GE_j-GS_i)·GD_i＞0，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤 A1；其中，GD_i和GD_j分别表示团队G_i和团队G_j的单日工作量；

A4、输出已合并团队集合作为新的团队集合，在新的团队集合中添加虚拟团队G_*，虚拟团队G_*的可用时间窗与规划周期一致，且虚拟团队G_*的单日工作量GD_*趋于无限大，虚拟团队G_*可以保证所有的项目都会被执行。

进一步的，关于合并后的新的团队的可用时间窗和单日工作量，在步骤A31 中，新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

新的团队G_ji的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ji在其可用时间窗内的单日工作量GD_ji如下：

在步骤A331中，新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

新的团队G_ji的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ji在其可用时间窗内的单日工作量GD_ji如下：

其中，SC表示项目集合，由所有待分配的项目组成，项目S_o被拆分成t个原子任务，项目S_o的t个原子任务组成原子任务集合TC^o，TS_o,k表示项目S_o的第k个原子任务T_o,k的开始执行时间节点，k＝1,2…t,t≥2，x_o,i,k∈{0,1}，当x_o,i,k＝1时表示由团队G_i执行项目S_o下的原子任务T_o,k，x_o,j,k同理；

原子任务T_o,k被分配给新的团队G_ij时，如果GS_i≤TS_o,k≤GS_j≤TS_o,k+((1+ α)·TL_o,k/GD_i)≤GE_i，则原子任务T_o,k由团队G_i最终实际执行，如果GS_j≤TS_o,k且 TS_o,k+((1+α)·TL_o,k/GD_j)≤GE_j，则原子任务T_o,k由团队G_j最终实际执行，其它条件下团队G_ij不执行TS_o,k，团队G_ji同理。

进一步的，步骤S2中，初始解的生成包括以下步骤：

B0、获取项目集合，设布尔型变量Switch＝Y，获取团队集合，将团队集合中各个团队的日程已规划时间点设置为团队的可用时间窗的开始时间点；

其中，可用时间窗是一个时间段，各个团队在自己的可用时间窗内工作，团队G_j的可用时间窗的开始时间点记为GS_j，团队G_j的可用时间窗的结束时间点记为GE_j，团队G_j的日程已规划时间点plan^j＝GS_j；

B1、如果项目集合中所有项目均已经被选择，则项目分配完成，输出包含各个团队的任务执行序列的初始解，否则，自项目集合中选出项目工作量最大的项目，记为项目S_i，执行步骤B2；

B2、将团队集合中所有GS_j＜SD_i的团队放入项目S_i的候选团队集，SD_i表示项目S_i的交付日期，项目S_i的候选团队集中至少包括两个团队，获取项目S_i的原子任务集合TCⁱ，执行步骤B3；

B3、计算项目S_i的候选团队集中各个团队与项目S_i的优先度值，选择优先度值最大的两个团队，记为团队G_a和团队G_b，执行步骤B4，其中，任意团队与任意项目的优先度值的最小值大于虚拟团队G_*与任意项目的优先度值的最大值；

其中，团队G_j的优先度值的计算公式为：(plan^j-GS_j)-│(SD_i-GE_j)│；

B4、若原子任务集合TCⁱ为空，则执行步骤B1，否则，自原子任务集合TCⁱ中选择工作量最大的原子任务，记为原子任务T_i,k，检查Switch的值，若Switch＝Y，则执行步骤B41，否则，执行步骤B42；

B41、如果原子任务T_i,k可分配给团队G_a，即plan^a+[(1+α)TL_i,k/GD_a]≤SD_i且plan^a+[(1+α)TL_i,k/GD_a]≤GE_a，则令x_i,a,k＝1，Switch＝N，plan^a更新为 plan^a+[(1+α)TL_i,k/GD_a]，从原子任务集合TCⁱ中删除原子任务T_i,k，执行步骤B4，否则，检查Switch的值，若Switch＝Y，则执行步骤B42，否则，Switch＝N，执行步骤B3；

B42、如果原子任务T_i,k可分配给团队G_b，即plan^b+[(1+α)TL_i,k]/GD_b≤SD_i且plan^b+[(1+α)TL_i,k/GD_b]≤GE_b，则令x_i,b,k＝1，Switch＝Y，plan^b更新为 plan^b+[(1+α)TL_i,k/GD_b]，从原子任务集合TCⁱ中删除原子任务T_i,k，执行步骤 B4，否则，检查Switch的值，若Switch＝Y，则执行步骤B3，否则，Switch＝N，执行步骤B41；

其中，x_i,a,k∈{0,1}，当x_i,a,k＝1时表示由团队G_a执行项目S_i下的原子任务T_i,k，x_i,b,k同理，TL_i,k表示原子任务T_i,k的工作量，0＜α＜1，α表示预设置的内部沟通系数。

进一步的，使用解评价函数计算解的适应度值，基于解的适应度值确定解的优劣，所述解评价函数＝X₁-X₂-X₃，其中，X₁表示项目集合中各个项目的提前完成时间之和，X₂表示团队集合中各个团队中内沟通无效的原子任务的总量，X₃表示团队集合中各个团队中外沟通无效的原子任务的总量；

其中，项目S_i被拆分成t个原子任务，k＝1,2…t,t≥2，项目S_i的t个原子任务组成原子任务集合TCⁱ，T_i,k表示项目S_i的第k个原子任务，x_i,j,k∈{0,1}，当x_i,j,k＝1 时表示由团队G_j执行项目S_i下的原子任务T_i,k，TL_i,k表示原子任务T_i,k的工作量，GD_j表示团队G_j的单日工作量，原子任务T_i,k的开始执行时间节点为TS_i,k，原子任务T_i,k的结束执行时间节点为TE_i,k，SD_i表示项目S_i的交付日期，项目S_i的提前完成时间为项目S_i最晚被完成的原子任务的结束执行时间节点与交付日期SD_i的差值；

如果一个原子任务不满足团队内沟通约束，则该原子任务为内沟通无效的原子任务，如果一个原子任务不满足团队间沟通约束，则该原子任务为外沟通无效的原子任务，在可行解中，各个原子任务既满足团队内沟通约束又满足团队间沟通约束，且各个项目的完成时间早于交付日期；

团队内沟通约束为：

团队G_j在执行项目S_i时，团队G_j完成原子任务T_i,k的开发后，需要继续完成团队内沟通，之后方可继续承担项目S_i的其它原子任务，团队内沟通的工作量为α·TL_i,k，α为内部沟通系数，0＜α＜1，原子任务T_i,k的结束执行时间节点TE_i,k＝TS_i,k+ ((1+α)·TL_i,k/GD_j)，项目S_i的任意两个原子任务T_i,a和T_i,b由团队G_j执行，如果两个原子任务满足下列公式，则这两个原子任务满足团队内沟通约束：

团队间沟通约束为：

TC_i,j,k表示原子任务T_i,k由团队G_j执行时的团队间沟通时长，TC_i,j,k的值等于团队G_j执行原子任务T_i,k的时间窗与其他团队执行项目S_i的原子任务的时间窗的重叠部分的并集，原子任务T_i,k满足团队间沟通约束即：

其中，β表示预设置的工作量比例，0<β<1，SC表示项目集合，由所有的项目组成，GC表示团队集合，由所有的团队组成；

由虚拟团队G_*执行的任意原子任务均不满足团队间沟通约束。

进一步的，步骤S3中每类变换操作包括多个算子，步骤S3包括以下步骤：

C0、选择当前执行顺序中第一个没有被标记的变换操作作为当前变换操作；

C1、获取当前解，随机选择一个项目S_i，自当前变换操作的多个算子中随机选择一个算子；

C2、从项目S_i的原子任务集中随机选择一个原子任务，在当前解中该原子任务是被分配给一个团队执行的，根据算子调整该原子任务的开始执行时间节点和/ 或执行该原子任务的团队，按照预设置的搜索次数重复步骤C2，得到多个候选解；

C3、将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

如果步骤C3中，新的全局最优解相对于之前的全局最优解没有更优，则认为此次步骤S3的执行没有搜索到更优解；

统计步骤S3的每次执行是否搜索到更优解，如果步骤S3使用当前变换操作连续执行Kp次均没有搜索到最优解，Kp>1，则标记当前变换操作；

步骤S4中预设置的解切换条件为：三类变换操作均被标记；

步骤S4中，如果满足预设置的解交换条件，则消除三类变换操作的标记，交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5；

以步骤S4第一次执行至步骤S4中第一次满足解交换条件为第一个循环，以步骤S4中第p次满足解交换条件至步骤S4中第p+1次满足解交换条件为第p+1 个循环，p>0，记录每个循环结束时的全局最优解，步骤S5中预设置的扰动条件为：第p+1个循环和第p+2个循环得到的全局最优解均不优于第p个循环得到的全局最优解；

步骤S4中，预设置的终止条件为步骤S5中的扰动条件被满足Ki次，Ki>1。

进一步的，预设置两种执行顺序分别为：优化分配操作—>团队内沟通调整操作—>团队间沟通调整操作，团队间沟通调整操作—>团队内沟通调整操作—>优化分配操作。

进一步的，步骤S2中，还包括构建评价矩阵，所述评价矩阵的行数和列数是对应所有变换操作的算子数和项目集合中的项目数，评价矩阵中的元素的值表示一个项目算子组合的评价值，步骤S2中评价矩阵的元素初始化为0；

步骤S3的步骤C3中，还包括更新评价矩阵，具体为：

C31、将评价矩阵中的每个元素值加1；

C32、基于步骤C1中选择的项目和算子，在评价矩阵中找到对应的元素；

C33、将当前解和候选解中的最优解作为新的当前解，如果新的当前解优于步骤C1中的当前解，且为可行解，则将评价矩阵中该元素的值加u₁，如果新的当前解优于步骤C1中的当前解，但不是可行解，则将评价矩阵中该元素的值加u₂，如果新的当前解优于可行最优解，则将评价矩阵中该元素的值加u₃，否则，将评价矩阵中该元素的值加u₄，u₁>u₂>u₃>0>u₄；

C34、将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

步骤C1中还包括项目算子重新选择，具体为：

C11、获取当前解，随机选择一个项目，自当前变换操作的多个算子中随机选择一个算子，得到当前的项目算子组合；

C12、将当前变换操作的多个算子与项目集合中的所有项目组合，得到多个项目算子组合，自评价矩阵中获取各个项目算子组合的评价值，将最大的评价值记为 value_max，如果当前的项目算子组合的评价值大于(value_max-u₀)，u₀>u₁则使用当前的项目算子组合，执行步骤C2，否则，选择评价值最大的项目算子组合，执行步骤C2。

进一步的，优化分配操作包括两个优化分配算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个执行项目S_i的团队的空闲时间窗中，该原子任务的原团队和该原子任务插入的团队均执行项目S_i；算子2为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个不执行项目 S_i的团队的空闲时间窗中；

如果当前变换操作为优化分配操作，则步骤C2包括以下步骤：

Ca21、获取优化分配算子，从项目S_i的原子任务集中随机选择一个原子任务T_i,a，在当前解中原子任务T_i,a是由团队1执行的；

Ca22、使用优化分配算子1或优化分配算子2调整原子任务T_i,a的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Ca23、选择一个待调整候选解，将团队1的任务执行序列中所有属于项目S_i且开始执行时间节点晚于原子任务T_i,a的原子任务放入待移动集合，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Ca24；

Ca24、自待移动集合中选出开始执行时间节点最早的原子任务T_i,b，自待移动集合中移除原子任务T_i,b，如果待移动集合为空，则执行步骤Ca23，否则，执行步骤Ca25；

Ca25、获取团队1的任务执行序列中所有早于原子任务T_i,b的开始执行时间节点的空闲时间窗，将原子任务T_i,b移动至各个空闲时间窗内，得到多个移动解，保留有效的移动解作为候选解，执行步骤Ca24；

其中，一个移动解是将原子任务T_i,b移动至一个空闲时间窗得到的，如果移动后团队1中内沟通无效的原子任务数量没有增加，且移动后原子任务T_i,b的团队间沟通时长TC_i,j,b大于移动前，则这个移动解有效；

团队内沟通调整操作包括两个团队内沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

如果当前变换操作为团队内沟通调整操作，则步骤C2包括以下步骤：

Cb21、获取团队内沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cb22、使用团队内沟通算子1或团队内沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Cb23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cb24；

Cb24、所述待调整候选解是对一个或两个原子任务进行调整得到的，选择该待调整候选解所对应的开始执行时间节点最早的原子任务，如果该待调整候选解所对应的所有原子任务均已经被选择，则执行步骤Cb23，否则，执行步骤Cb25；

Cb25、所选择的原子任务的执行团队记为团队G_j，如果该原子任务在团队G_j中满足团队内沟通约束，则执行步骤Cb251，否则，执行步骤Cb252；

Cb251、向前或向后调整该原子任务的开始执行时间节点，在满足团队内沟通的前提下，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最早，得到一个候选解，执行步骤Cb24；

Cb252、将该原子任务或者导致该原子任务不满足团队内沟通约束的原子任务的开始执行时间节点向后移动，直至该原子任务满足团队内沟通约束，如果调整后该原子任务的结束执行时间节点晚于其所属项目的交付日期，或者调整后导致该原子任务不满足团队内沟通约束的原子任务的结束执行时间节点晚于其所属项目的交付日期，则舍弃上述调整，执行步骤Cb24，否则，得到一个候选解，执行步骤 Cb24；

团队间沟通调整操作包括两个团队间沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

如果当前变换操作为团队间沟通调整操作，则步骤C2包括以下步骤：

Cc21、获取团队间沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cc22、使用团队间沟通算子1或团队间沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Cc23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cc24；

Cc24、所述待调整候选解是对一个或两个原子任务进行调整得到的，获取执行调整后的原子任务的全部团队，选择一个团队，如果所有团队均已经被选择，则执行步骤Cc23，否则，执行步骤Cc25；

Cc25、将所选择的团队记为团队G_j，选择团队G_j的任务执行序列中开始执行时间节点最晚的原子任务，如果所有原子任务均已经被选择，则执行步骤Cc24，否则，执行步骤Cc26；

Cc26、调整该原子任务的开始执行时间节点，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最晚，如果该原子任务调整后，不满足团队内沟通约束或该原子任务调整后的结束执行时间节点晚于原子任务所属项目的交付日期，则舍弃上述调整，执行步骤Cc25，否则，得到一个候选解，执行步骤Cc25。

进一步的，步骤S5中，对当前解进行扰动操作具体为：

D1、获取当前解和备选解，选择一个团队G_j，所述团队G_j在当前解中的任务执行序列为L1，所述团队G_j在候选解中的任务执行序列为L2，如果L1和L2中存在重叠原子任务，则执行步骤D2，否则，执行步骤D3，所述重叠原子任务是指同时出现在L1和L2内的原子任务；

D2、L1＝{Q0，Q1}，L2＝{Q0，Q2}，其中，Q0表示所有的重叠原子任务， Q1表示L1中除重叠原子任务外的所有原子任务，Q2表示L2中除重叠原子任务外的所有原子任务，使用优化分配算子2，将Q1中的各个原子任务分别插入到当前解中的其他团队的任务执行序列中，将Q2中的各个原子任务分别插入到备选解中的其他团队的任务执行序列中，将Q2中的各个原子任务插入到L1中，并将Q2 中的原子任务自当前解中的其他团队的任务执行序列中删除，将Q1中的各个原子任务插入到L2中，并将Q1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作；

D3、使用优化分配算子2，将L1中的各个原子任务插入到当前解中的其他团队的任务执行序列中，将L2的各个原子任务插入到备选解中的其他团队的任务执行序列中，将L2中的各个原子任务插入到L1中，并将L2中的原子任务自当前解中的其他团队的任务执行序列中删除，将L1中的各个原子任务插入到L2中，并将L1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作。

与现有技术相比，本发明具有以下有益效果：

(1)提出了团队合并的思想，根据团队的可用时间窗进行团队合并，减少了团队的数量，从而缩小了解空间的规模，节约了计算资源，提高了求解速度；

(2)生成了两个初始解，设计了两种执行顺序，根据算法的搜索结果切换解和执行顺序，相当于在解空间中从两个不同的起点按照不同的搜索方向进行搜索，大大避免了陷入局部最优解的可能，搜索效率更高；

(3)设计了自适应搜索机制，使用评价矩阵记录项目算子组合的评价值，通过评价矩阵来衡量算子的性能，指导解的搜索，避免了随机盲目搜索导致的资源浪费；

(4)当使用两个解进行搜索后均未找到最优解时，进行扰动操作，通过扰动操作交换两个解上的片段，帮助当前搜索跳出局部最优解，能够保留优良性状，不仅能控制扰动程度，还能促进算法收敛；

(5)设计了两个优化分配算子，设计了两个团队内沟通算子，设计了两个团队间沟通算子，能从不同角度进行优化分配操作，进一步提升解的质量。

附图说明

图1为本发明的流程图；

图2为团队合并方法的流程图；

图3为团队合并过程中团队之间可用时间窗的重合关系；

图4为团队内沟通约束示意图；

图5为团队间沟通约束示意图；

图6为步骤S3使用当前变换操作搜索并更新解的流程示意图；

图7为优化分配算子1的操作示例；

图8为优化分配算子2的操作示例；

图9为优化分配调整的操作示例；

图10为团队内/间沟通算子1的操作示例；

图11为团队内/间沟通算子2的操作示例；

图12为团队内沟通调整的操作示例；

图13为团队间沟通调整的操作示例。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

实施例1：

首先进行一些名词说明、术语解释和前提条件说明：

1)规划周期是一个时间段，如7月1日至10月31日，R表示规划周期的长度，如90天、100天等，是已知值；

2)项目集合SC，表示待分配的n个项目S_i(i＝1,2…n)的集合，是已知值；

3)项目S_i的交付日期记为SD_i，是已知值，项目S_i的所有原子任务应当在交付日期之前完成，否则，项目S_i没有被按时完成；

4)团队集合GC，表示m个团队G_j(j＝1,2…m)的集合，是已知值；

5)可用时间窗，是一个时间段，如8月1日至8月10日，7月15日至9月19 日等，团队G_j在自己的可用时间窗内工作，团队G_j的可用时间窗为GS_j至GE_j，团队 G_j的可用时间窗的开始时间点为GS_j，如9月1日，是已知值，团队G_j的可用时间窗的结束时间点为GE_j，如10月20日，是已知值，GE_j＞GS_j，即结束时间节点晚于开始时间节点；

6)单日工作量GD_j(GD_j＞0)，表示团队G_j单日可完成的工作量，是已知值；

7)原子任务，任意项目S_i可被拆分成t个原子任务，t≥2，原子任务是可直接交由一个团队执行的任务，且原子任务不可再拆分，这t个原子任务的集合为项目S_i的原子任务集合TCⁱ，是已知值，原子任务之间相互独立，不存在时序上的依赖关系，任意团队执行同一原子任务的效果一样，即不考虑时间约束时，任何团队可以完成任意原子任务，且执行任务的效果一样，不同团队执行原子任务的速度与团队的单日工作量有关；

8)项目S_i的原子任务集合TCⁱ中，T_i,k(k＝1,2…t,t≥2)表示项目S_i的第k个原子任务，项目S_i的工作量为SL_i，原子任务T_i,k的工作量为TL_i,k，均是已知值， x_i,j,k∈{0,1}，当x_i,j,k＝1时表示由团队G_j执行项目S_i下的原子任务T_i,k；

9)原子任务T_i,k的开始执行时间节点为TS_i,k，如7月1日，原子任务T_i,k的结束执行时间节点为TE_i,k，如7月10日，若原子任务T_i,k被规划给团队G_j执行，则 x_i,j,k＝1。

一种面向敏捷开发的需求任务规划算法，如图1所示，包括以下步骤：

S1、获取项目集合和团队集合，将多个团队进行团队合并，将合并后的团队集合作为新的团队集合；

S2、基于项目集合和团队集合生成两个初始解，将其中一个初始解作为当前解，将另一个初始解作为备选解，将两个初始解中的最优解作为全局最优解，预设置两种执行顺序，将其中一个执行顺序作为当前执行顺序，将另一个执行顺序作为备选执行顺序，如果两个初始解中存在可行解，则将两个初始解中可行且最优的解作为可行最优解，如果不存在可行解，则将可行最优解置零，任意解优于置零解，可行最优解是最终输出的结果，全局最优解用于搜索过程中的评价；

S3、变换操作分为三类：优化分配操作、团队内沟通调整操作和团队间沟通操作，按照当前执行顺序，选择一类变换操作，对当前解进行变换操作得到多个候选解，将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

S4、如果满足预设置的终止条件，则输出可行最优解，否则，判断是否满足预设置的解切换条件，如果满足解切换条件，则交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5，如果不满足解交换条件，则直接执行步骤S5；

S5、如果满足预设置的扰动条件，则对当前解进行扰动操作，执行步骤S3，否则，直接执行步骤S3。

下面对各个步骤进行详细说明。

关于步骤S1中的团队合并方法，众所周知，团队的规模是影响解规模的重要因素，随着项目数量n和团队规模m的增加，解空间的大小成指数型爆炸增长，因此如果能缩减研发团队规模，解空间也能够被有效缩小，本申请因此提出一种团队合并方法，在步骤S1中进行团队合并，如图3所示，步骤S1包括以下步骤：

A0、将待合并的多个团队放入待合并团队集合；

A1、如果待合并团队集合为空，则团队合并结束，执行步骤A4，否则，计算待合并团队集合中各个团队的可用时间窗的长度，自待合并团队集合中选择可用时间窗长度最大的待合并团队，记为团队G_j，团队G_j的可用时间窗的长度为(GE_j-GS_j)，将待合并团队集合中所有可用时间窗长度小于(R-(GE_j-GS_j))的团队放入团队G_j的候选集合，执行步骤A2；

A2、如果团队G_j的候选集合为空，则从待合并团队集合中删除团队G_j并将团队 G_j放入已合并团队集合，执行步骤A1，否则，自团队G_j的候选集合中选择(GE_j-GS_j)的值最大的团队，记为团队G_i，执行步骤A3；

A3、图2中矩形表示团队的可用时间窗，如果团队G_i与团队G_j的可用时间窗不重合，即图2中团队a与团队d，则执行步骤A31，如果团队G_i的可用时间窗完全落在团队G_j的可用时间窗内，即图2中团队a与团队e，则执行步骤A32，如果团队G_i的可用时间窗与团队G_j的可用时间窗部分重合，即图2中团队a与团队b、团队a与团队c，则执行步骤A33；

A31、若GS_j≥GE_i，则将团队G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队 G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若GE_j≤GS_i，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤A1；

新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

新的团队G_ji的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ji在其可用时间窗内的单日工作量GD_ji如下：

A32、GS_j≤GS_i且GE_j≥GE_i，自团队G_j的候选集合中删除团队G_i，执行步骤 A2；

A33、自项目集合中筛选出交付日期晚于GE_i的项目，自这些项目的所有原子项目集合中找出工作量最小的原子任务，将该原子任务的工作量记为TL，如果团队G_i与团队G_j在重合的可用时间窗内均可以完成工作量为TL的原子任务，则自团队 G_j的候选集合中删除团队G_i，执行步骤A2，否则，执行步骤A331；

A331、在重合的可用时间窗内，团队G_i与团队G_j均不能完成工作量为TL的原子任务，或者只有其中一个团队能完成工作量为TL的原子任务，保证了两个团队合并后，为新的团队分配的原子任务实际上只会由团队G_i与团队G_j中的一个执行，不会涉及到两个团队，若TL＞(GE_i-GS_j)·GD_j＞0或TL＞(GE_i-GS_j)·GD_i＞0，则将团队G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若TL＞(GE_j-GS_i)·GD_j> 0或TL＞(GE_j-GS_i)·GD_i＞0，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤A1；其中，GD_i和GD_j分别表示团队G_i和团队G_j的单日工作量；

新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

新的团队G_ji的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ji在其可用时间窗内的单日工作量GD_ji如下：

其中，SC表示项目集合，由所有待分配的项目组成，项目S_o被拆分成t个原子任务，项目S_o的t个原子任务组成原子任务集合TC^o，TS_o,k表示项目S_o的第k个原子任务T_o,k的开始执行时间节点，k＝1,2…t,t≥2，x_o,i,k∈{0,1}，当x_o,i,k＝1时表示由团队G_i执行项目S_o下的原子任务T_o,k，x_o,j,k同理；

原子任务T_o,k被分配给新的团队G_ij时，如果GS_i≤TS_o,k≤GS_j≤TS_o,k+((1+ α)·TL_o,k/GD_i)≤GE_i，则原子任务T_o,k由团队G_i最终实际执行，如果GS_j≤TS_o,k且 TS_o,k+((1+α)·TL_o,k/GD_j)≤GE_j，则原子任务T_o,k由团队G_j最终实际执行，其它条件下团队G_ij不执行TS_o,k，团队G_ji同理。

A4、输出已合并团队集合作为新的团队集合，在新的团队集合中添加虚拟团队G_*，虚拟团队G_*的可用时间窗与规划周期一致，且虚拟团队G_*的单日工作量GD_*趋于无限大，虚拟团队G_*可以保证所有的项目都会被执行。

在其他实施方式中，可以采用其他形式的团队合并方法，如只考虑可用时间窗不重合的团队之间的合并，或者重合长度小于预设置阈值的团队之间的合并等等.

需要注意，上述团队合并方法中使用步骤分步描述只是为了更清楚的描述清楚方法的内容，并不是严格限定步骤之间的执行关系，上述团队合并方法中提到的放入集合、自集合中删除等等也是为了更清楚的描述方法的内容，并未限定必须使用集合的方式，事实上，也可以给每个待合并的团队设置标记，通过标记的值的变化来表示该团队的合并。同理，下文的方法步骤的执行顺序也可以在实际应用中灵活调整，方法中提到的使用集合、自集合中删除等操作并不是对操作方法的限制，在实际实现时，可以灵活使用队列、数组、指针等各种数据结构实现。

本申请通过团队合并方法缩减了团队的规模，有效缩小了解空间，后续解的搜索效率更高，更易找到解空间中的最优解。

SD_i表示项目S_i的交付日期，项目S_i的提前完成时间为项目S_i最晚被完成的原子任务的结束执行时间节点与交付日期SD_i的差值；

在敏捷开发模式下，沟通时间必不可少，且对沟通时长有要求，将多个项目的多个原子任务分配给多个团队时，如果一个原子任务执行时不满足团队内沟通约束，则该原子任务为内沟通无效的原子任务，如果一个原子任务执行时不满足团队间沟通约束，则该原子任务为外沟通无效的原子任务，如果一个解中各个原子任务既满足团队内沟通约束又满足团队间沟通约束，且每个项目均早于交付日期完成，则该解为可行解。在一个理想的最优的分配方案中，应当尽可能的满足团队内沟通约束、团队间沟通约束，而且每个项目都能尽可能的早于交付日期完成。

团队内沟通约束为：

团队G_j在执行项目S_i时，团队G_j完成原子任务T_i,k的开发后，需要继续完成团队内沟通，之后方可继续承担项目S_i的其它原子任务，团队内沟通的工作量为α·TL_i,k，α为预设置的内部沟通系数，0＜α＜1，如0.6，团队G_j执行原子任务T_i,k所耗费的工作时长为(TL_i,k/GD_j)，加上团队内沟通时长后，原子任务T_i,k的结束执行时间节点TE_i,k＝TS_i,k+((1+α)·TL_i,k/GD_j)项目S_i的任意两个原子任务T_i,a和T_i,b由团队 G_j执行，这两个原子任务满足团队内沟通约束可以表述为这两个原子任务满足以下公式：

对于一个原子任务而言，如果该原子任务的开始执行时间节点与任务执行序列中相邻的原子任务的开始执行时间节点满足上述公式，该原子任务即满足团队内沟通约束；

对于一个团队而言，如果该团队的任务执行序列中的任意两个原子任务的开始执行时间节点满足上述公式，该团队即满足团队内沟通约束；

对于一个解而言，一个解实际上包含所有团队的任务执行序列，如果各个团队均满足团队内沟通约束，则这个解满足团队内沟通约束。

如图4所示，图4中矩形表示团队执行原子任务的时间以及团队内沟通的时间，矩形的长度为(1+α)·TL/GD，之后的图5，图7～图13中矩形的含义均为包含团队内沟通时间后原子任务的执行时间窗，团队G_j执行项目S_i的两个原子任务a和b，原子任务a的开始执行时间节点为TS_i,a，原子任务b的开始执行时间节点为TS_i,b，在团队G_j的第一个任务执行序列中，当原子任务a执行完成且完成内沟通后原子任务b才开始执行，满足内沟通约束，在团队G_j的第二个任务执行序列中，原子任务 a执行完成后尚未完成内沟通原子任务b就开始执行，不满足内沟通约束。

团队间沟通约束为：

团队间约束可以简单理解为执行同一项目的不同团队间的沟通，TC_i,j,k表示原子任务T_i,k由团队G_j执行时的团队间沟通时长，TC_i,j,k的值等于团队G_j执行原子任务 T_i,k的时间窗与其他团队执行项目S_i的其他原子任务的时间窗的重叠部分的并集，如图5所示，项目S_i共由三个团队执行，对于项目S_i的原子任务T_i,1而言，原子任务 T_i,1由团队2执行时的团队间沟通时长为线段①+线段②，对于原子任务T_i,5而言，原子任务T_i,5由团队3执行时的团队间沟通时长为线段③。

对于一个原子任务来说，满足团队间沟通约束即：

(TC_i,j,k-β·TL_i,k)≥0

0<β<1，表示预设置的工作量比例，如0.5；

对于项目S_i而言，满足团队间沟通约束即项目S_i的所有原子任务的团队间沟通时长的总和不小于β·SL_i，即：

对于团队G_j而言，满足团队间沟通约束即：

对于引入的虚拟团队G_*，虚拟团队G_*的可用时间窗等于规划周期，单日工作量趋于无限大，可以保证所有的项目都会被执行，其作用是保证分配项目的原子任务时，每一个原子任务理论上都能找到一个团队来执行，为了惩罚由虚拟团队执行原子任务的解，认为由虚拟团队G_*执行的任意原子任务都是不满足团队间沟通约束的。

在其他实施方式中，可以改变团队内沟通约束的内部沟通系数，改变团队间沟通约束中团队间沟通时长的工作量比例等，自定义原子任务的团队内沟通约束、团队间沟通约束，自定义团队的团队内沟通约束、团队间沟通约束等。

步骤S2中，初始解的生成包括以下步骤：

B0、获取项目集合，设布尔型变量Switch＝Y，获取团队集合，将团队集合中各个团队的日程已规划时间点设置为团队的可用时间窗的开始时间点；

其中，可用时间窗是一个时间段，各个团队在自己的可用时间窗内工作，团队 G_j的可用时间窗的开始时间点记为GS_j，团队G_j的可用时间窗的结束时间点记为GE_j，团队G_j的日程已规划时间点plan^j＝GS_j，日程已规划时间点可以简单理解为该团队在日程已规划时间点plan^j至结束时间点GE_j这个时间段内是可分配任务的，日程已规划时间点之前的时段不能被分配任务；

B1、如果项目集合中所有项目均已经被选择，则项目分配完成，输出包含各个团队的任务执行序列的初始解，否则，自项目集合中选出项目工作量最大的项目，记为项目S_i，执行步骤B2；

B2、将团队集合中所有GS_j＜SD_i的团队放入项目S_i的候选团队集，SD_i表示项目S_i的交付日期，项目S_i的候选团队集中至少包括两个团队，获取项目S_i的原子任务集合TCⁱ，执行步骤B3；

B3、计算项目S_i的候选团队集中各个团队与项目S_i的优先度值，选择优先度值最大的两个团队，记为团队G_a和团队G_b，执行步骤B4，其中，任意团队与任意项目的优先度值的最小值大于虚拟团队G_*与任意项目的优先度值的最大值，可以将虚拟团队G_*与任意项目的优先度值强制设置为一个极小值，且小于任意团队与任意项目的优先度值；

其中，团队G_j的优先度值的计算公式为：(plan^j-GS_j)-│(SD_i-GE_j)│；

B4、若原子任务集合TCⁱ为空，则执行步骤B1，否则，自原子任务集合TCⁱ中选择工作量最大的原子任务，记为原子任务T_i,k，检查Switch的值，若Switch＝Y，则执行步骤B41，否则，执行步骤B42；

B41、如果原子任务T_i,k可分配给团队G_a，即plan^a+[(1+α)TL_i,k/GD_a]≤SD_i且plan^a+[(1+α)TL_i,k/GD_a]≤GE_a，则令x_i,a,k＝1，Switch＝N，plan^a更新为 plan^a+[(1+α)TL_i,k/GD_a]，从原子任务集合TCⁱ中删除原子任务T_i,k，执行步骤 B4，否则，检查Switch的值，若Switch＝Y，则执行步骤B42，否则，Switch＝N，执行步骤B3；

B42、如果原子任务T_i,k可分配给团队G_b，即plan^b+[(1+α)TL_i,k]/GD_b≤SD_i且plan^b+[(1+α)TL_i,k/GD_b]≤GE_b，则令x_i,b,k＝1，Switch＝Y，plan^b更新为 plan^b+[(1+α)TL_i,k/GD_b]，从原子任务集合TCⁱ中删除原子任务T_i,k，执行步骤 B4，否则，检查Switch的值，若Switch＝X，则执行步骤B3，否则，Switch＝N，执行步骤B41；

其中，x_i,a,k∈{0,1}，当x_i,a,k＝1时表示由团队G_a执行项目S_i下的原子任务T_i,k，x_i,b,k同理，TL_i,k表示原子任务T_i,k的工作量，0＜α＜1，α表示预设置的内部沟通系数。

本申请中，在生成初始解时，见步骤B41和步骤B42，考虑了团队的任务执行序列中同一项目的相邻两个原子任务的团队内沟通约束，极大的保证了初始解的质量，而且通过Switch标记，使得同一项目的原子任务依次分配给两个团队，保证了两个团队的团队间沟通约束，使得生成的初始解在团队内沟通和团队间沟通方面具有良好的性状，为后续的迭代优化奠定了良好的基础。

解的优劣是通过对解计算适应度值确定的，本实施例中解评价＝X₁-X₂-X₃，其中，X₁表示项目集合中各个项目的提前完成时间之和，X₂表示团队集合中各个团队中内沟通无效的原子任务的总量，X₃表示团队集合中各个团队中外沟通无效的原子任务的总量，适应度值越高，解越优；

在其他实施方式中，可以根据对团队内沟通、团队间沟通和项目提前完成时间的需求度的不同，为X₁、X₂、X₃添加适当的系数，或者引入新的评价解的优劣的变量，如团队的空闲时间窗比例等。

步骤S3中每类变换操作包括多个算子，如图6所示，步骤S3包括以下步骤：

C0、选择当前执行顺序中第一个没有被标记的变换操作作为当前变换操作；

C1、获取当前解，随机选择一个项目S_i，自当前变换操作的多个算子中随机选择一个算子；

C2、从项目S_i的原子任务集中随机选择一个原子任务，在当前解中该原子任务是被分配给一个团队执行的，根据算子调整该原子任务的开始执行时间节点和/ 或执行该原子任务的团队，按照预设置的搜索次数重复步骤C2，得到多个候选解；

C3、将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

本实施例中，预设置的搜索次数为50次，因此，确定当前变换操作后，从当前变换操作的多个算子中随机选择一个算子，记为算子Z，之后随机选择原子任务并使用算子Z进行操作，得到一个候选解，再次随机选择原子任务，同样使用算子Z进行操作，重复50次后，得到50个候选解，使用解评价函数计算适应度，执行步骤C3。

如果步骤C3中，新的全局最优解相对于之前的全局最优解没有更优，则认为此次步骤S3的执行没有搜索到更优解；统计步骤S3的每次执行是否搜索到更优解，如果步骤S3使用当前变换操作连续执行Kp次均没有搜索到最优解，Kp>1，则标记当前变换操作，认为继续使用当前变换操作不能找到更优解，当前变换操作被标记后，下次执行步骤S3时，在步骤C1中会根据当前执行顺序选择下一类未被标记的变换操作；本实施例中，Kp为20次，在其他实施方式中，可以灵活调整。

步骤S4中预设置的解切换条件为：三类变换操作均被标记；

步骤S4中，如果满足预设置的解交换条件(检查三类变换操作，如果均被标记则满足解交换条件)，则消除三类变换操作的标记，交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5(判断是否满足扰动调节，是否需要进行扰动操作)；

以步骤S4第一次执行至步骤S4中第一次满足解交换条件为第一个循环，以步骤S4中第p次满足解交换条件至步骤S4中第p+1次满足解交换条件为第p+1 个循环，p>0，(事实上，在步骤S2中生成了两个初始解，一个当前解，一个备选解，在后续搜索时会根据解交换条件轮流维护两个不同的解，每个解在交换前的搜索过程就是一个循环)，记录每个循环结束时的全局最优解；

步骤S5中预设置的扰动条件为：第p+1个循环和第p+2个循环得到的全局最优解均不优于第p个循环得到的全局最优解；

步骤S4中，预设置的终止条件为步骤S5中的扰动条件被满足Ki次，Ki>1，本实施例中，Ki的值取3，在其他实施方式中，可以灵活调整。

预设置两种执行顺序分别为：优化分配操作—>团队内沟通调整操作—>团队间沟通调整操作，团队间沟通调整操作—>团队内沟通调整操作—>优化分配操作。在其他实施方式中，可以根据需要自行设计两种执行顺序，不用限制两种执行顺序完全逆序。

本实施例中，两种执行顺序恰好是逆序，能最大可能的从不同的方向搜索解，在步骤S2中生成初始解时生成了两个初始解，这两个执行顺序就对应这两个初始解，先以一个初始解作为当前解，进行迭代搜索，如果陷入局部最优解，即满足解交换条件，则交换解，使用另一个初始解作为当前解进行迭代搜索，同时使用另一种执行顺序，当再次陷入局部最优解时，再次切换解。

不同于传统的局部搜索算法，本申请在解的搜索过程中需要维护两个当前解，两个当前解按照不同的执行顺序进行变换操作，能够在不同的特性上保持优良的性状，可以理解为从两个起点按照不同的方向在解空间中进行搜索，如果一个解的搜索陷入局部最优解，则进行解交换操作，进行另一个解的搜索，更有可能在解空间中找到最优解，陷入局部最优解的概率大大降低。

在步骤C2中，确定当前变换操作后，随机选择算子，算子的选择没有指导性，传统随机选择的盲目搜索会导致计算资源被浪费，而过度干涉算子的选择也可能导致搜索陷入局部最优解，因此本申请为了合理引导算法搜索寻优设计了一种考虑决策成本的“决策学习方法”，通过构建评价矩阵来跟踪算子的搜索效果，持续学习各个算子的性能，并最终用于指导算子的搜索。

构建评价矩阵在步骤S2中进行，评价矩阵的行数和列数是对应所有变换操作的算子数和项目集合中的项目数，评价矩阵中的元素的值表示一个项目算子组合的评价值，步骤S2中评价矩阵的元素初始化为0；

本实施例中，优化分配操作、团队内沟通调整操作和团队间沟通调整操作分别有2个算子，项目集合SC中有10个项目，因此构建的评价矩阵ES为6×10或10 ×6，如下所示：

矩阵中的元素ES_x,y表示算子x与项目y的项目算子组合的评价值，x∈X,y∈SC， X表示所有算子组成的集合。

因此，步骤C1中还包括项目算子重新选择，具体为：

C11、获取当前解，随机选择一个项目，自当前变换操作的多个算子中随机选择一个算子，得到当前的项目算子组合；

C12、将当前变换操作的多个算子与项目集合中的所有项目组合，得到多个项目算子组合，自评价矩阵中获取各个项目算子组合的评价值(即找到当前变换操作下，各个算子与各个项目的项目算子组合)，将最大的评价值记为value_max，如果当前的项目算子组合的评价值大于(value_max-u₀)，u₀>u₁则使用当前的项目算子组合，执行步骤C2，否则，选择评价值最大的项目算子组合，执行步骤C2。

步骤S3的步骤C3中，还包括更新评价矩阵，具体为：

C31、将评价矩阵中的每个元素值加1；

C32、基于步骤C1中选择的项目和算子，在评价矩阵中找到对应的元素；

C33、将当前解和候选解中的最优解作为新的当前解，如果新的当前解优于步骤C1中的当前解，且为可行解，则将评价矩阵中该元素的值加u₁，如果新的当前解优于步骤C1中的当前解，但不是可行解，则将评价矩阵中该元素的值加u₂，如果新的当前解优于可行最优解，则将评价矩阵中该元素的值加u₃，否则，将评价矩阵中该元素的值加u₄，u₁>u₂>u₃>0>u₄；

C34、将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

本实施例中，u₀取15，u₁取8，u₂取5，u₃取2，u₄取-1，在其他实施方式中，可以自定义这些参数的值。

本申请通过引入评价矩阵，项目算子组合的评价值越大，表示这个项目算子组合更有可能指导搜索向最优解，在每次执行步骤S3时，尽可能的使用评价值最大的项目算子组合，这种自适应的决策机制既指导了解的搜索，避免资源浪费，也没有过度干涉搜索过程，搜索效果较好。

本实施方式中为每类变换操作设计了2个算子，在其他实施方式中，可以根据需要，自定义设计算子，增减算子的数量，下面将对每类变换操作的各个算子进行介绍。

(一)优化分配操作

优化分配操作包括两个优化分配算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个执行项目S_i的团队的空闲时间窗中，该原子任务的原团队和该原子任务插入的团队均执行项目S_i；算子2为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个不执行项目S_i的团队的空闲时间窗中；

优化分配算子1实际上是将一个原子任务在两个团队(均执行了项目S_i的原子任务)之间调整，优化分配算子2实际上是将一个原子任务在两个团队(一个执行了项目S_i的原子任务，另一个未执行项目S_i的原子任务)之间调整。

如果当前变换操作为优化分配操作，则步骤C2包括以下步骤：

Ca21、获取优化分配算子，从项目S_i的原子任务集中随机选择一个原子任务T_i,a，在当前解中原子任务T_i,a是由团队1执行的；

Ca22、使用优化分配算子1或优化分配算子2调整原子任务T_i,a的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

如图7所示，在步骤Ca21中随机选择的原子任务为项目b中的原子任务b1，由团队1执行，使用优化分配算子1，找到执行项目b的其他原子任务的团队2，将原子任务b1自团队1的任务执行序列中转移至团队2的任务执行序列中，由于团队2的任务执行序列中存在①～⑤五个空闲时间窗，因此步骤Ca22中得到五个待调整候选解。

在插入空闲时间窗时，如果该空闲时间窗与团队1的任务执行序列中项目b 的其他原子任务的时间窗有重合，则将原子任务b1的开始执行时间节点调整为满足团队内沟通约束且使得团队间沟通时长最大的位置，如图7中原子任务b1插入空闲时间窗④所示，得到待调整候选解。

在插入空闲时间窗时，如果该空闲时间窗与团队1的任务执行序列中项目b 的其他原子任务的时间窗没有重合(如图7中空闲时间窗①、③、⑤所示)，或者该空闲时间窗不足以完成原子任务b1时(如图7中空闲时间窗②所示)，将原子任务b1的开始执行时间节点调整为空闲时间窗的开始时间。

同理，优化分配算子2的操作示例如图8所示，在步骤Ca21中随机选择的原子任务为项目b中的原子任务b1，由团队1执行，使用优化分配算子2，找到不执行项目b的任意原子任务的团队2，将原子任务b1自团队1的任务执行序列中转移至团队2的任务执行序列中，由于团队2的任务执行序列中存在①～③三个空闲时间窗，因此步骤Ca22中得到三个待调整候选解。

在插入空闲时间窗时，如果该空闲时间窗与团队1的任务执行序列中项目b 的其他原子任务的时间窗有重合，则将原子任务b1的开始执行时间节点调整为满足团队内沟通约束且使得团队间沟通时长最大的位置，如图8中原子任务b1插入空闲时间窗②所示，得到待调整候选解。

在插入空闲时间窗时，如果该空闲时间窗与团队1的任务执行序列中项目b 的其他原子任务的时间窗没有重合(如图8中空闲时间窗①、③所示)，或者该空闲时间窗不足以完成原子任务b1时，将原子任务b1的开始执行时间节点调整为空闲时间窗的开始时间。

Ca23、选择一个待调整候选解，将团队1的任务执行序列中所有属于项目S_i且开始执行时间节点晚于原子任务T_i,a的原子任务放入待移动集合，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Ca24；

Ca24、自待移动集合中选出开始执行时间节点最早的原子任务T_i,b，自待移动集合中移除原子任务T_i,b，如果待移动集合为空，则执行步骤Ca23，否则，执行步骤Ca25；

Ca25、获取团队1的任务执行序列中所有早于原子任务T_i,b的开始执行时间节点的空闲时间窗，将原子任务T_i,b移动至各个空闲时间窗内，得到多个移动解，保留有效的移动解作为候选解，执行步骤Ca24；

如图9所示，以图7中将原子任务b1插入空闲时间窗①后得到的待调整候选解为例，说明优化分配调整的过程。

团队1的任务执行序列中属于项目b且晚于原子任务b1的原子任务为b2，将原子任务b2放入待移动集合中；团队1的任务执行序列中早于原子任务b1的空闲时间窗有两个(空闲时间窗①和空闲时间窗②)，将原子任务b2移动至两个空闲时间窗，得到两个移动解。

在移动原子任务b2时，与上述优化分配算子1和优化分配算子2移动时同理，如果该空闲时间窗与团队2的任务执行序列中项目b的其他原子任务的时间窗有重合(空闲时间窗①和空闲时间窗②)，则将原子任务b2的开始执行时间节点调整为满足团队内沟通约束且使得团队间沟通时长最大的位置，如果没有重合，或者空闲时间窗不足以完成原子任务b2时，将原子任务b2的开始执行时间节点调整为空闲时间窗的开始时间。

移动后，判断移动解的有效性。其中，一个移动解是将原子任务T_i,b移动至一个空闲时间窗得到的，如果移动后团队1中内沟通无效的原子任务数量没有增加，且移动后原子任务T_i,b的团队间沟通时长TC_i,j,b大于移动前，则这个移动解有效。

(二)团队内沟通调整操作

团队内沟通调整操作包括两个团队内沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

团队内沟通算子1实际上是改变原子任务的开始执行时间节点，没有改变执行团队，团队内沟通算子2实际上是将两个原子任务(属于项目S_i)在两个团队(均执行项目S_i)之间进行交换。

如果当前变换操作为团队内沟通调整操作，则步骤C2包括以下步骤：

Cb21、获取团队内沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cb22、使用团队内沟通算子1或团队内沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

如图10所示，在步骤Cb21中随机选择的原子任务为项目a中的原子任务a2，由团队1执行，使用团队内沟通算子1，在团队1的任务执行序列中存在两个空闲时间窗，将原子任务a2移动至空闲时间窗①和空闲时间窗②，得到两个待调整候选解，原子任务a2的开始执行时间节点可以直接为空闲时间窗的开始时间，也可以考虑团队1与其他团队的团队间沟通时长，调整原子任务a2的开始执行时间节点。

如图11所示，使用团队内沟通算子2，自项目的原子任务集中随机选择两个由不同团队执行的原子任务，本实施例中团队1和团队2均执行项目b，选择两个原子任务b1和b3，直接交换这两个原子任务，得到一个待调整候选解。

Cb23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cb24；

Cb24、待调整候选解是对一个或两个原子任务进行调整得到的，选择该待调整候选解所对应的开始执行时间节点最早的原子任务，如果该待调整候选解所对应的所有原子任务均已经被选择，则执行步骤Cb23，否则，执行步骤Cb25；

Cb25、所选择的原子任务的执行团队记为团队G_j，如果该原子任务在团队G_j中满足团队内沟通约束，则执行步骤Cb251，否则，执行步骤Cb252；

Cb251、向前或向后调整该原子任务的开始执行时间节点，在满足团队内沟通的前提下，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最早，得到一个候选解，执行步骤Cb24；

Cb252、将该原子任务或者导致该原子任务不满足团队内沟通约束的原子任务的开始执行时间节点向后移动，直至该原子任务满足团队内沟通约束，如果调整后该原子任务的结束执行时间节点晚于其所属项目的交付日期，或者调整后导致该原子任务不满足团队内沟通约束的原子任务的结束执行时间节点晚于其所属项目的交付日期，则舍弃上述调整，执行步骤Cb24，否则，得到一个候选解，执行步骤 Cb24；

如图12所示，以图10中将原子任务a2移动至空闲时间窗①得到的待调整候选解为例，对团队内沟通调整操作进行说明。这个待调整候选解对应一个原子任务，即原子任务a2，此时在团队1中原子任务a2不满足团队内沟通约束，因此执行步骤Cb251，本实施例中，将使原子任务a2不满足内沟通约束的原子任务b1的开始执行时间节点后移，调整后原子任务a2的结束执行时间节点早于项目a的交付期日，原子任务b1的结束执行时间节点早于项目b的交付期日，因此得到一个候选解。

(三)团队间沟通调整操作

团队间沟通调整操作包括两个团队间沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

如果当前变换操作为团队间沟通调整操作，则步骤C2包括以下步骤：

Cc21、获取团队间沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cc22、使用团队间沟通算子1或团队间沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

本实施例中，团队间沟通算子1实际上与团队内沟通算子1相同，如图10所示，团队间沟通算子2实际上与团队内沟通算子2相同，如图11所示。

在其他实施方式中，可以进一步细化设计团队间沟通算子，如选择团队1和团队2，团队1执行了q1个属于项目S_i的原子任务，团队2至少执行了q2个属于项目S_i的原子任务，q1>1，q2>1，团队1和团队2执行项目S_i的原子任务时，两个原子任务的开始执行时间节点接近，则将这两个原子任务在团队1和团队2之间交互，此外，还可以考虑两个团队的单日工作量的差异、原子任务的工作量的差异等等。同理，优化分配算子和团队内沟通算子也可以进行个性化设计。

Cc23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cc24；

Cc24、待调整候选解是对一个或两个原子任务进行调整得到的，获取执行调整后的原子任务的全部团队，选择一个团队，如果所有团队均已经被选择，则执行步骤Cc23，否则，执行步骤Cc25；

Cc25、将所选择的团队记为团队G_j，选择团队G_j的任务执行序列中开始执行时间节点最晚的原子任务，如果所有原子任务均已经被选择，则执行步骤Cc24，否则，执行步骤Cc26；

Cc26、调整该原子任务的开始执行时间节点，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最晚(原子任务的开始执行时间节点向后移动的过程中，首先找到使得原子任务的团队间沟通时长最大的位置，如果位置有多个，则选择其中最晚的位置为原子任务的开始执行时间节点)，如果该原子任务调整后，不满足团队内沟通约束或该原子任务调整后的结束执行时间节点晚于原子任务所属项目的交付日期，则舍弃上述调整，执行步骤Cc25，否则，得到一个候选解，执行步骤Cc25。

如图13所示，以图11中交换原子任务b1和b3得到的待调整候选解为例进行说明，先选择团队1，将团队1中开始执行时间节点最晚的原子任务(即原子任务 b2)向后移动，再向后移动时，保证其团队间沟通时长最长、开始执行时间节点最晚，之后继续移动团队1的任务执行序列中除b2以外开始执行时间节点最晚的原子任务(即原子任务a2)，同理，原子任务a2向后移动，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最晚，原子任务b3向后移动，由于存在多个使团队间沟通时长最大的位置，因此选择最晚的位置为开始执行时间节点，原子任务a1的向后移动同理，使得该原子任务的团队间沟通时长最大。

步骤S5中，对当前解进行扰动操作具体为：

D1、获取当前解和备选解，选择一个团队G_j，团队G_j在当前解中的任务执行序列为L1，团队G_j在候选解中的任务执行序列为L2，如果L1和L2中存在重叠原子任务，则执行步骤D2，否则，执行步骤D3，重叠原子任务是指同时出现在L1和 L2内的原子任务；

D2、L1＝{Q0，Q1}，L2＝{Q0，Q2}，其中，Q0表示所有的重叠原子任务， Q1表示L1中除重叠原子任务外的所有原子任务，Q2表示L2中除重叠原子任务外的所有原子任务，使用优化分配算子2，将Q1中的各个原子任务分别插入到当前解中的其他团队的任务执行序列中，将Q2中的各个原子任务分别插入到备选解中的其他团队的任务执行序列中，将Q2中的各个原子任务插入到L1中，并将Q2 中的原子任务自当前解中的其他团队的任务执行序列中删除，将Q1中的各个原子任务插入到L2中，并将Q1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作；

D3、使用优化分配算子2，将L1中的各个原子任务插入到当前解中的其他团队的任务执行序列中，将L2的各个原子任务插入到备选解中的其他团队的任务执行序列中，将L2中的各个原子任务插入到L1中，并将L2中的原子任务自当前解中的其他团队的任务执行序列中删除，将L1中的各个原子任务插入到L2中，并将L1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作。

扰动操作的实质是将两个解中同一团队的任务执行序列进行交换，如果这一个团队在两个解中的任务执行序列有重叠，则执行步骤D2，如果没有重叠则执行步骤D3，可以看作是将一个解的片段交换到另一个解上，这种优良性状交互的扰动优于传统的随机扰动，不仅能控制扰动程度，还能促进算法收敛。

本申请的优点如下：

提出了团队合并的思想，减少了团队的数量，从而降低了解空间的规模，节约了计算资源，提高了求解速度；

生成了两个初始解，设计了两种执行顺序，相当于在解空间中从两个不同的起点按照不同的搜索方向进行搜索，大大避免了陷入局部最优解的可能，搜索效率更高；

设计了自适应搜索机制，通过评价矩阵来衡量算子的性能，指导解的搜索，避免了随机盲目搜索导致的资源浪费；

扰动操作交换两个解上的片段，能够保留优良性状，不仅能控制扰动程度，还能促进算法收敛；

设计了两个优化分配算子，设计了两个团队内沟通算子，设计了两个团队间沟通算子，能从不同角度进行优化分配操作，进一步提升解的质量。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。

Claims (10)

1.一种面向敏捷开发的需求任务规划算法，其特征在于，包括以下步骤：

S1、获取项目集合和团队集合，将多个团队进行团队合并，将合并后的团队集合作为新的团队集合；

S2、基于项目集合和团队集合生成两个初始解，将其中一个初始解作为当前解，将另一个初始解作为备选解，将两个初始解中的最优解作为全局最优解，预设置两种执行顺序，将其中一个执行顺序作为当前执行顺序，将另一个执行顺序作为备选执行顺序，如果两个初始解中存在可行解，则将两个初始解中可行且最优的解作为可行最优解，如果不存在可行解，则将可行最优解置零，任意解优于置零解；

S3、变换操作分为三类：优化分配操作、团队内沟通调整操作和团队间沟通操作，按照当前执行顺序，选择一类变换操作，对当前解进行变换操作得到多个候选解，将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

S4、如果满足预设置的终止条件，则输出可行最优解，否则，判断是否满足预设置的解切换条件，如果满足解切换条件，则交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5，如果不满足解交换条件，则直接执行步骤S5；

S5、如果满足预设置的扰动条件，则对当前解进行扰动操作，执行步骤S3，否则，直接执行步骤S3。

2.根据权利要求1所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤S1包括以下步骤：

A0、将待合并的多个团队放入待合并团队集合；

A1、如果待合并团队集合为空，则团队合并结束，执行步骤A4，否则，计算待合并团队集合中各个团队的可用时间窗的长度，自待合并团队集合中选择可用时间窗长度最大的待合并团队，记为团队G_j，团队G_j的可用时间窗的长度为(GE_j-GS_j)，将待合并团队集合中所有可用时间窗长度小于(R-(GE_j-GS_j))的团队放入团队G_j的候选集合，执行步骤A2；

其中，可用时间窗是一个时间段，各个团队在自己的可用时间窗内工作，团队G_j的可用时间窗的开始时间点预设置为GS_j，团队G_j的可用时间窗的结束时间点预设置为GE_j，R表示规划周期的长度，规划周期是一个预设置的时间段；

A2、如果团队G_j的候选集合为空，则从待合并团队集合中删除团队G_j并将团队G_j放入已合并团队集合，执行步骤A1，否则，自团队G_j的候选集合中选择(GE_j-GS_j)的值最大的团队，记为团队G_i，执行步骤A3；

A3、如果团队G_i与团队G_j的可用时间窗不重合，则执行步骤A31，如果团队G_i的可用时间窗完全落在团队G_j的可用时间窗内，则执行步骤A32，如果团队G_i的可用时间窗与团队G_j的可用时间窗部分重合，则执行步骤A33；

A31、若GS_j≥GE_i，则将团队G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若GE_j≤GS_i，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤A1；

A32、GS_j≤GS_i且GE_j≥GE_i，自团队G_j的候选集合中删除团队G_i，执行步骤A2；

A33、自项目集合中筛选出交付日期晚于GE_i的项目，自这些项目的所有原子项目集合中找出工作量最小的原子任务，将该原子任务的工作量记为TL，如果团队G_i与团队G_j在重合的可用时间窗内均能完成工作量为TL的原子任务，则自团队G_j的候选集合中删除团队G_i，执行步骤A2，否则，执行步骤A331；

其中，一个项目可以被拆分为多个原子任务，任意团队均可以执行任意原子任务，且原子任务不可再拆分，同一个项目的原子任务之间不存在执行时序上的依赖关系；

A331、若TL＞(GE_i-GS_j)·GD_j＞0或TL＞(GE_i-GS_j)·GD_i＞0，则将团队G_i与团队G_j合并成新的团队G_ij，将团队G_i与团队G_j从待合并团队集合中删除并将新的团队G_ij放入待合并团队集合，执行步骤A1，若TL＞(GE_j-GS_i)·GD_j＞0或TL＞(GE_j-GS_i)·GD_i＞0，则将团队G_j与团队G_i合并成新的团队G_ji，将团队G_j与团队G_i从待合并团队集合中删除并将新的团队G_ji放入待合并团队集合，执行步骤A1；其中，GD_i和GD_j分别表示团队G_i和团队G_j的单日工作量；

A4、输出已合并团队集合作为新的团队集合，在新的团队集合中添加虚拟团队G_*，虚拟团队G_*的可用时间窗与规划周期一致，且虚拟团队G_*的单日工作量GD_*趋于无限大。

3.根据权利要求2所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤A31中，

新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

步骤A331中，

新的团队G_ij的可用时间窗取团队G_i与团队G_j可用时间窗的并集，团队G_ij在其可用时间窗内的单日工作量GD_ij如下：

其中，SC表示项目集合，由所有待分配的项目组成，项目S_o被拆分成t个原子任务，项目S_o的t个原子任务组成原子任务集合TC^o，TS_o，k表示项目S_o的第k个原子任务T_o，k的开始执行时间节点，k＝1，2...t，t≥2，x_o，i，k∈{0，1}，当x_o，i，k＝1时表示由团队G_i执行项目S_o下的原子任务T_o，k；

原子任务T_o，k被分配给新的团队G_ij时，如果GS_i≤TS_o，k≤GS_j≤TS_o，k+((1+α)·TL_o，k/GD_i)≤GE_i，则原子任务T_o，k由团队G_i最终实际执行，如果GS_j≤TS_o，k且TS_o，k+((1+α)·TL_o，k/GD_j)≤GE_j，则原子任务T_o，k由团队G_j最终实际执行。

4.根据权利要求2所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤S2中，初始解的生成包括以下步骤：

B0、获取项目集合，设布尔型变量Switch＝Y，获取团队集合，将团队集合中各个团队的日程已规划时间点设置为团队的可用时间窗的开始时间点；

其中，可用时间窗是一个时间段，各个团队在自己的可用时间窗内工作，团队G_j的可用时间窗的开始时间点记为GS_j，团队G_j的可用时间窗的结束时间点记为GE_j，团队G_j的日程已规划时间点plan^j＝GS_j；

B1、如果项目集合中所有项目均已经被选择，则项目分配完成，输出包含各个团队的任务执行序列的初始解，否则，自项目集合中选出项目工作量最大的项目，记为项目S_i，执行步骤B2；

B2、将团队集合中所有GS_j＜SD_i的团队放入项目S_i的候选团队集，SD_i表示项目S_i的交付日期，项目S_i的候选团队集中至少包括两个团队，获取项目S_i的原子任务集合TCⁱ，执行步骤B3；

其中，一个项目可以被拆分为多个原子任务，任意团队均可以执行任意原子任务，且原子任务不可再拆分，同一个项目的原子任务之间不存在执行时序上的依赖关系，项目S_i的所有原子任务组成原子任务集合TCⁱ；

B3、计算项目S_i的候选团队集中各个团队与项目S_i的优先度值，选择优先度值最大的两个团队，记为团队G_a和团队G_b，执行步骤B4，其中，任意团队与任意项目的优先度值的最小值大于虚拟团队G_*与任意项目的优先度值的最大值；

其中，团队G_j的优先度值的计算公式为：(plan^j-GS_j)-|(SD_i-GE_j)|；

B4、若原子任务集合TCⁱ为空，则执行步骤B1，否则，自原子任务集合TCⁱ中选择工作量最大的原子任务，记为原子任务T_i，k，检查Switch的值，若Switch＝Y，则执行步骤B41，否则，执行步骤B42；

B41、如果原子任务T_i，k可分配给团队G_a，即plan^a+[(1+α)TL_i，k/GD_a]≤SD_i且plan^a+[(1+α)TL_i，k/GD_a]≤GE_a，则令x_i，a，k＝1，Switch＝N，plan^a更新为plan^a+[(1+α)TL_i，k/GD_a]，从原子任务集合TCⁱ中删除原子任务T_i，k，执行步骤B4，否则，检查Switch的值，若Switch＝Y，则执行步骤B42，否则，Switch＝N，执行步骤B3；

B42、如果原子任务T_i，k可分配给团队G_b，即plan^b+[(1+α)TL_i，k]/GD_b≤SD_i且plan^b+[(1+α)TL_i，k/GD_b]≤GE_b，则令x_i，b，k＝1，Switch＝Y，plan^b更新为plan^b+[(1+α)TL_i，k/GD_b]，从原子任务集合TCⁱ中删除原子任务T_i，k，执行步骤B4，否则，检查Switch的值，若Switch＝Y，则执行步骤B3，否则，Switch＝N，执行步骤B41；

其中，x_i，a，k∈{0，1}，当x_i，a，k＝1时表示由团队G_a执行项目S_i下的原子任务T_i，k，x_i，b，k同理，TL_i，k表示原子任务T_i，k的工作量，0＜α＜1，α表示预设置的内部沟通系数。

5.根据权利要求4所述的一种面向敏捷开发的需求任务规划算法，其特征在于，使用解评价函数计算解的适应度值，基于解的适应度值确定解的优劣，所述解评价函数＝X₁-X₂-X₃，其中，X₁表示项目集合中各个项目的提前完成时间之和，X₂表示团队集合中各个团队中内沟通无效的原子任务的总量，X₃表示团队集合中各个团队中外沟通无效的原子任务的总量；

其中，项目S_i被拆分成t个原子任务，k＝1，2...t，t≥2，项目S_i的t个原子任务组成原子任务集合TCⁱ，T_i，k表示项目S_i的第k个原子任务，x_i，j，k∈{0，1}，当x_i，j，k＝1时表示由团队G_j执行项目S_i下的原子任务T_i，k，TL_i，k表示原子任务T_i，k的工作量，GD_j表示团队G_j的单日工作量，原子任务T_i，k的开始执行时间节点为TS_i，k，原子任务T_i，k的结束执行时间节点为TE_i，k，TE_i，k＝TS_i，k+(TL_i，k/GD_j)，SD_i表示项目S_i的交付日期，项目S_i的提前完成时间为项目S_i最晚被完成的原子任务的结束执行时间节点与交付日期SD_i的差值；

如果一个原子任务不满足团队内沟通约束，则该原子任务为内沟通无效的原子任务，如果一个原子任务不满足团队间沟通约束，则该原子任务为外沟通无效的原子任务，在可行解中，各个原子任务既满足团队内沟通约束又满足团队间沟通约束，且各个项目的完成时间早于交付日期；

团队内沟通约束为：

团队G_j在执行项目S_i时，团队G_j完成原子任务T_i，k的开发后，需要继续完成团队内沟通，之后方可继续承担项目S_i的其它原子任务，团队内沟通的工作量为α·TL_i，k，α为内部沟通系数，0＜α＜1，原子任务T_i，k的结束执行时间节点TE_i，k＝TS_i，k+((1+α)·TL_i，k/GD_j)，项目S_i的任意两个原子任务T_i，a和T_i，b由团队G_j执行，如果两个原子任务满足下列公式，则这两个原子任务满足团队内沟通约束：

团队间沟通约束为：

TC_i，j，k表示原子任务T_i，k由团队G_j执行时的团队间沟通时长，TC_i，j，k的值等于团队G_j执行原子任务T_i，k的时间窗与其他团队执行项目S_i的原子任务的时间窗的重叠部分的并集，原子任务T_i，k满足团队间沟通约束即：

其中，β表示预设置的工作量比例，0＜β＜1，SC表示项目集合，由所有的项目组成，GC表示团队集合，由所有的团队组成；

由虚拟团队G_*执行的任意原子任务均不满足团队间沟通约束。

6.根据权利要求5所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤S3中每类变换操作包括多个算子，步骤S3包括以下步骤：

C0、选择当前执行顺序中第一个没有被标记的变换操作作为当前变换操作；

C1、获取当前解，随机选择一个项目S_i，自当前变换操作的多个算子中随机选择一个算子；

C2、从项目S_i的原子任务集中随机选择一个原子任务，在当前解中该原子任务是被分配给一个团队执行的，根据算子调整该原子任务的开始执行时间节点和/或执行该原子任务的团队，按照预设置的搜索次数重复步骤C2，得到多个候选解；

C3、将当前解和候选解中的最优解作为新的当前解，将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

如果步骤C3中，新的全局最优解相对于之前的全局最优解没有更优，则认为此次步骤S3的执行没有搜索到更优解；

统计步骤S3的每次执行是否搜索到更优解，如果步骤S3使用当前变换操作连续执行Kp次均没有搜索到最优解，Kp＞1，则标记当前变换操作；

步骤S4中预设置的解切换条件为：三类变换操作均被标记；

步骤S4中，如果满足预设置的解交换条件，则消除三类变换操作的标记，交换当前解和备选解，得到新的当前解和备选解，并交换当前执行顺序和备选执行顺序，得到新的当前执行顺序和备选执行顺序，执行步骤S5；

以步骤S4第一次执行至步骤S4中第一次满足解交换条件为第一个循环，以步骤S4中第p次满足解交换条件至步骤S4中第p+1次满足解交换条件为第p+1个循环，p＞0，记录每个循环结束时的全局最优解，步骤S5中预设置的扰动条件为：第p+1个循环和第p+2个循环得到的全局最优解均不优于第p个循环得到的全局最优解；

步骤S4中，预设置的终止条件为步骤S5中的扰动条件被满足Ki次，Ki＞1。

7.根据权利要求6所述的一种面向敏捷开发的需求任务规划算法，其特征在于，预设置两种执行顺序分别为：优化分配操作-＞团队内沟通调整操作-＞团队间沟通调整操作，团队间沟通调整操作-＞团队内沟通调整操作-＞优化分配操作。

8.根据权利要求6所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤S2中，还包括构建评价矩阵，所述评价矩阵的行数和列数是对应所有变换操作的算子数和项目集合中的项目数，评价矩阵中的元素的值表示一个项目算子组合的评价值，步骤S2中评价矩阵的元素初始化为0；

步骤S3的步骤C3中，还包括更新评价矩阵，具体为：

C31、将评价矩阵中的每个元素值加1；

C32、基于步骤C1中选择的项目和算子，在评价矩阵中找到对应的元素；

C33、将当前解和候选解中的最优解作为新的当前解，如果新的当前解优于步骤C1中的当前解，且为可行解，则将评价矩阵中该元素的值加u₁，如果新的当前解优于步骤C1中的当前解，但不是可行解，则将评价矩阵中该元素的值加u₂，如果新的当前解优于可行最优解，则将评价矩阵中该元素的值加u₃，否则，将评价矩阵中该元素的值加u₄，u₁＞u₂＞u₃＞0＞u₄；

C34、将新的当前解和全局最优解中的最优解作为新的全局最优解，将可行最优解和候选解中可行且最优的解作为新的可行最优解，执行步骤S4；

步骤C1中还包括项目算子重新选择，具体为：

C11、获取当前解，随机选择一个项目，自当前变换操作的多个算子中随机选择一个算子，得到当前的项目算子组合；

C12、将当前变换操作的多个算子与项目集合中的所有项目组合，得到多个项目算子组合，自评价矩阵中获取各个项目算子组合的评价值，将最大的评价值记为value_max，如果当前的项目算子组合的评价值大于(value_max-u₀)，u₀＞u₁则使用当前的项目算子组合，执行步骤C2，否则，选择评价值最大的项目算子组合，执行步骤C2。

9.根据权利要求6所述的一种面向敏捷开发的需求任务规划算法，其特征在于：

优化分配操作包括两个优化分配算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个执行项目S_i的团队的空闲时间窗中，该原子任务的原团队和该原子任务插入的团队均执行项目S_i；算子2为：获取原子任务，该原子任务属于项目S_i，将该原子任务自原团队的任务执行序列中删除，将该原子任务插入另一个不执行项目S_i的团队的空闲时间窗中；

如果当前变换操作为优化分配操作，则步骤C2包括以下步骤：

Ca21、获取优化分配算子，从项目S_i的原子任务集中随机选择一个原子任务T_i，a，在当前解中原子任务T_i，a是由团队1执行的；

Ca22、使用优化分配算子1或优化分配算子2调整原子任务T_i，a的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Ca23、选择一个待调整候选解，将团队1的任务执行序列中所有属于项目S_i且开始执行时间节点晚于原子任务T_i，a的原子任务放入待移动集合，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Ca24；

Ca24、自待移动集合中选出开始执行时间节点最早的原子任务T_i，b，自待移动集合中移除原子任务T_i，b，如果待移动集合为空，则执行步骤Ca23，否则，执行步骤Ca25；

Ca25、获取团队1的任务执行序列中所有早于原子任务T_i，b的开始执行时间节点的空闲时间窗，将原子任务T_i，b移动至各个空闲时间窗内，得到多个移动解，保留有效的移动解作为候选解，执行步骤Ca24；

其中，一个移动解是将原子任务T_i，b移动至一个空闲时间窗得到的，如果移动后团队1中内沟通无效的原子任务数量没有增加，且移动后原子任务T_i，b的团队间沟通时长TC_i，j，b大于移动前，则这个移动解有效；

团队内沟通调整操作包括两个团队内沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

如果当前变换操作为团队内沟通调整操作，则步骤C2包括以下步骤：

Cb21、获取团队内沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cb22、使用团队内沟通算子1或团队内沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Cb23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cb24；

Cb24、所述待调整候选解是对一个或两个原子任务进行调整得到的，选择该待调整候选解所对应的开始执行时间节点最早的原子任务，如果该待调整候选解所对应的所有原子任务均已经被选择，则执行步骤Cb23，否则，执行步骤Cb25；

Cb25、所选择的原子任务的执行团队记为团队G_j，如果该原子任务在团队G_j中满足团队内沟通约束，则执行步骤Cb251，否则，执行步骤Cb252；

Cb251、向前或向后调整该原子任务的开始执行时间节点，在满足团队内沟通的前提下，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最早，得到一个候选解，执行步骤Cb24；

Cb252、将该原子任务或者导致该原子任务不满足团队内沟通约束的原子任务的开始执行时间节点向后移动，直至该原子任务满足团队内沟通约束，如果调整后该原子任务的结束执行时间节点晚于其所属项目的交付日期，或者调整后导致该原子任务不满足团队内沟通约束的原子任务的结束执行时间节点晚于其所属项目的交付日期，则舍弃上述调整，执行步骤Cb24，否则，得到一个候选解，执行步骤Cb24；

团队间沟通调整操作包括两个团队间沟通算子，算子1为：获取原子任务，该原子任务属于项目S_i，将该原子任务移入其所属团队的任务执行序列中的空闲时间窗内；算子2为：获取两个原子任务，两个原子任务属于项目S_i，由两个不同的团队执行，在这两个团队的任务执行序列中交换上述两个原子任务；

如果当前变换操作为团队间沟通调整操作，则步骤C2包括以下步骤：

Cc21、获取团队间沟通算子，从项目S_i的原子任务集中随机选择一个原子任务或者随机选择两个由不同团队执行的原子任务；

Cc22、使用团队间沟通算子1或团队间沟通算子2调整所选择的原子任务的开始执行时间节点和/或执行该原子任务的团队，得到多个待调整候选解；

Cc23、选择一个待调整候选解，如果所有的待调整候选解均已经被选择，则输出所有的候选解，否则，执行步骤Cc24；

Cc24、所述待调整候选解是对一个或两个原子任务进行调整得到的，获取执行调整后的原子任务的全部团队，选择一个团队，如果所有团队均已经被选择，则执行步骤Cc23，否则，执行步骤Cc25；

Cc25、将所选择的团队记为团队G_j，选择团队G_j的任务执行序列中开始执行时间节点最晚的原子任务，如果所有原子任务均已经被选择，则执行步骤Cc24，否则，执行步骤Cc26；

Cc26、调整该原子任务的开始执行时间节点，使得该原子任务的团队间沟通时长最大，且开始执行时间节点最晚，如果该原子任务调整后，不满足团队内沟通约束或该原子任务调整后的结束执行时间节点晚于原子任务所属项目的交付日期，则舍弃上述调整，执行步骤Cc25，否则，得到一个候选解，执行步骤Cc25。

10.根据权利要求9所述的一种面向敏捷开发的需求任务规划算法，其特征在于，步骤S5中，对当前解进行扰动操作具体为：

D1、获取当前解和备选解，选择一个团队G_j，所述团队G_j在当前解中的任务执行序列为L1，所述团队G_j在候选解中的任务执行序列为L2，如果L1和L2中存在重叠原子任务，则执行步骤D2，否则，执行步骤D3，所述重叠原子任务是指同时出现在L1和L2内的原子任务；

D2、L1＝{Q0，Q1}，L2＝{Q0，Q2}，其中，Q0表示所有的重叠原子任务，Q1表示L1中除重叠原子任务外的所有原子任务，Q2表示L2中除重叠原子任务外的所有原子任务，使用优化分配算子2，将Q1中的各个原子任务分别插入到当前解中的其他团队的任务执行序列中，将Q2中的各个原子任务分别插入到备选解中的其他团队的任务执行序列中，将Q2中的各个原子任务插入到L1中，并将Q2中的原子任务自当前解中的其他团队的任务执行序列中删除，将Q1中的各个原子任务插入到L2中，并将Q1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作；

D3、使用优化分配算子2，将L1中的各个原子任务插入到当前解中的其他团队的任务执行序列中，将L2的各个原子任务插入到备选解中的其他团队的任务执行序列中，将L2中的各个原子任务插入到L1中，并将L2中的原子任务自当前解中的其他团队的任务执行序列中删除，将L1中的各个原子任务插入到L2中，并将L1中的原子任务自备选解中的其他团队的任务执行序列中删除，结束扰动操作。

Images