文|苏荨墨

编辑|苏荨墨

前言

软件项目过程不是一个严格的工程过程，因为调度方案会受到各种动态因素的影响，包括工程师的技能、这些技能的增长以及团队合作等。

为了解决这个问题，研究人员开发了几种方法来有效地将员工分配给任务，然而，大多数资源受限调度技术关注的是资源的可用性而不是资源生产率，软件开发人员之间确实存在显着的生产力差异。

因此，要做出更现实、更合理的进度表，在软件项目管理中还应考虑学习、进度压力等生产力因素。

当因素发生变化或状态对项目不利时，将采取项目控制措施，并且必须修改进度表以适应变化，防止无效的项目控制，这也是项目超预算和进度落后的主要原因，需要精心设计一种高效的重新调度方法，使项目重回正轨。

然而，在调度模型的文献中没有充分强调重新调度问题。据我们所知，以前的研究未能充分解释人类克服软件项目管理的复杂性和动态性的能力。

软件项目计划的改良

一些研究人员比较了启发式和元启发式技术在解决资源受限调度问题时的结果，启发式方法通常是解决大规模问题的首选方法。

从那时起，遗传算法就被许多研究人员用来研究调度问题及其变体，在软件项目优化领域，随机搜索方法也得到了广泛的应用。

可以找到对基于搜索的软件工程近期成就的一般介绍和调查，包括基于搜索的软件项目调度，其中 GA 被认为是流行的方法。

由于没有一种单一的 GA 方法可以始终如一地在所有问题中表现最佳，因此应该针对软件项目调度问题设计和调整不同的 GA。

我们之前的基于任务的模型可以被认为是在软件项目管理环境中应用 GA 的早期努力，就像基于时间轴的模型所做的那样。

将遗传算法应用于自动化任务分配，表明遗传算法在软件项目调度方面具有灵活准确的特点，是自动化项目管理的重要工具。

在工作中，使用实例生成器进行了深入分析，在软件项目管理中解决了 48 个不同的项目场景。

模型中很少考虑人力资源因素，为了在现实环境中获得更好的性能，需要更复杂的模型。最近有一些关于软件项目调度问题的研究工作。

一种多目标决策支持方法来帮助软件工程师平衡项目风险和工期与加班，他们进行了大量实验来证明他们方法的有效性。

提出了一种基于合作共同进化的方法来优化开发人员的团队人员配置和工作包调度，以实现早期的整体完成时间，这与我们的研究有不同的目标。

以上工作都是处理软件项目情况下的调度问题。然而，他们都没有考虑在调度执行期间重新调度问题。

软件工作在现实中的实现

我们提出的团队生产力建模和调度/重新调度优化过程的方法在图1。

图1 具有动态因素的软件项目计划和重新计划框架

在这个框架中，“基于GA和HC的调度优化器”是关键组成部分，它有助于在项目开始时生成项目进度表，或者在任务团队成员发生变化或项目执行与计划之间的差异变大时重新生成进度表。

优化器的输入包括详细任务和员工信息的模型参数、通过模拟实现的每个任务的持续时间以及根据管理目标和控制动作的适应度函数。

“任务和员工模型”包括任务模型（即任务预估工作量、任务惩罚模型和所需任务技能列表等）和员工模型（即技能列表、支付模型等）的静态部分。

在项目执行之前，“排班优化器”根据计划任务和分配的员工生成初始最优排班，在项目执行期间，将实际项目进度与初始计划进行比较。

当管理人员采取控制措施时，会重新安排时间并相应地更改模型参数，将进行重新计算以生成剩余项目的新进度表。

新生成的调度通过考虑稳定性和效率的“重新调度”目标函数进行评估。虚线说明了项目控制活动中涉及的过程。

将进行重新计算以生成剩余项目的新进度表。新生成的调度通过考虑稳定性和效率的“重新调度”目标函数进行评估，虚线说明了项目控制活动中涉及的过程。

任务在团队中的生成

任务和员工模型包括有关项目任务和分配给该任务的员工的信息，一个项目被表示为一个任务优先级图。

一个由一组任务组成的无环有向图V = { T 1 , T 2 ,…, T n } 其中T k代表项目的任务k ，以及优先级关系P = {( P ij ); i < > j , 1 ≤ i ≤ n , 1 ≤ j ≤ n }, 其中P ij = 1 如果T i必须在T j开始之前完成，否则P ij = 0。

与每个任务Tk相关联的是估计的工作量、所需技能和截止日期，项目团队成员E = { E 1 , E 2 ,…, E n } 是项目的资源，其中E代表员工k。

每个Ek _与他/她拥有的一系列技能以及相应的熟练程度、工资率、最大工作量（可以分配给他们的工作量的限制）和学习因素（反映他们技能熟练程度提高的因素）相关联工作期间）。

团队生产力决定了软件开发过程中的整体项目绩效。图 2对这个关键组件及其相关因素进行建模。

图2 团队生产力模型。

“个人生产力”和“沟通开销”是影响“团队生产力”的主要因素，当“个人生产力”受到“日程压力”、“技能适应度”和“学习”因素的影响。

尽管员工积极性等其他因素对个人生产力也至关重要，但出于展示关键概念的目的，我们不会将所有这些因素都包含在本文中。

这些因素也可以由项目经理通过值为 0 或 1 的控制参数打开或关闭来控制。

结合 GA 的全局优化能力和 HC 的局部优化能力，将 GA 与 HC 相结合的混合算法可能是一个理想的选择根据分块理论，在遗传算法计算的初期，由于存在很多高效的小分块，在交叉算子的作用下，小分块合并为大分块的概率很高。

因此，人口素质迅速提高。但是在GA后期，当big block越来越相似的时候，交叉运算符的效率就越来越低了。

那个时候很多个体的素质无法提升很多，导致后期的遗传算法效率低下，所以选择在早期阶段使用 GA，然后使用 HC。

我们的优化器的过程在图 3. 第一步是设置模型的参数，例如 GA 的变异概率、交叉概率、世代数和种群大小。

图3

然后将任务和员工信息加载到 GA 中。如果是重调度过程，还需要加载初始调度计划。在这些初始化步骤之后，GA 运行直到世代数达到先前设置的世代数。HC 从上一代 GA 产生的最佳个体开始，运行得到最优调度。

基因组表征在优化过程中，候选解表示 S 表示为 {A, L}。A 部分是一维任务-员工分配数组，存储从二维任务-员工分配数组派生的任务-员工分配信息。

对于分配的任务，员工可以在 0%、25%、50%、75% 或 100% 的负荷下工作。例如，50% 的承诺意味着如果员工 1 通常每周工作 40 小时，他每周可以工作 20 小时。

根据任务-员工技能匹配生成的“可能”分配矩阵，可以将二维任务-员工分配数组压缩为一维数组。例如，在图 4，两名员工被分配到 6 个任务。

它的任务-员工可能分配矩阵是根据他们的技能匹配得出的，其中 1 代表可能的分配，0 代表没有可能的分配。

由于这个可能的分配矩阵总是在初始任务-员工技能匹配计算后存储在模型中，因此可以通过取出不可能的分配元素（即“0”元素）将任务-员工分配二维数组压缩为一维数组。

在本例中，任务-员工分配一维数组中有 9 个元素，元素顺序与任务-员工可能分配矩阵中的行顺序相同。

第二部分L是优先级列表，通过它可以导出表示调度中任务执行顺序的某个拓扑排序向量。

当提出的基于优先级的编码可以利用任务优先级信息来决定任务的特定顺序。给定有向无环图 (DAG) G = ( V , E )，拓扑排序是所有顶点的顺序，并且对于每个 ( u , v )∈ E，u出现在v之前在名单上。

每个 DAG 可能有不止一种拓扑排序。当有两个任务竞争一个位置时，优先级高的任务获胜。

例如，对于包含 3 个任务的项目，即T 1到T 3，其中T 1是起始任务，它是T 2和T 3的直接优先级，任务优先级列表示T 3其优先级值为3的优先级高于值为1 的T 2。

拓扑排序 { T 1 , T 3 , T 2} 可以生成满足任务优先级关系的。在我们的调度问题中直接使用任务顺序作为基因组可能会生成不符合 DAG 的无效个体。

但是基于优先级的排序只处理优先级信息，这些优先级信息必须与项目 DAG 信息结合才能被解释为项目执行。因此，不会产生无效个体。

遗传算子为了操纵候选解 S 的两个结构，选择以下运算符。初始化算子从可能值（0、0.25、0.50、0.75、1）中随机选择任意值作为一维任务-员工数组（A）初始种群的等位基因（即个体某属性的可能设置）。

优先级列表（L）被初始化为从 1 到任务总数的随机顺序。当需要重新安排时，首先更新配置文件发生变化的任务和员工，然后将之前的安排设置为新 GA 计算的初始人口。

S 的交叉算子根据随机数P为复合基因组中的每个基因组调用交叉算子，如中所示图 5。

图5

基因组的 A 部分应用标准的单点交叉函数，L 部分使用顺序交叉。由于基因组表示的两个结构是独立的，并且 1D 数组基因组是从可能分配矩阵派生的，后代交叉运算符始终有效。

根据突变概率，随机选择两个基因组之一进行实验如图所示的突变，图 6. 在一维数组结构中，我们只改变某些元素，而某些元素在任务优先级向量中交换。

图6 适应度函数计算在我们用于软件项目调度的 GA 方法中，适应度函数计算是最复杂的部分。

结语

通过加载任务-员工分配来初始化系统，设置时间单位的个数，从拓扑排序列表中获取下一个任务；通过验证所有的来检查任务是否可以在这个时间单位内开始。

优先任务已经完成，所有员工都可以，所有员工都可以；不超限工作，否则转；对每项任务进行系统动力学仿真。

在每个任务执行结束时，计算成本、罚款并更新员工的；整体经验和一定的技能熟练程度；如果所有任务完成，返回适应度分数；从开始另一个循环，所以这就是 在最终的实验结果。