基于改进NSGA-II的多项目多技能人力资源调度研究

王莹莹，吴立云

(河南理工大学 能源科学与工程学院，河南 焦作 454000)

许多企业在日常生产及研发过程中经常多个项目并行开展，这使得企业管理难度加大。合理进行多项目管理和人力资源分配，不仅能提高生产效率、降低劳动成本，还能提升员工的满意度和公平性。因此，如何在多项目中合理安排各项目调度及分配人力资源对增强企业的竞争力至关重要。

在多项目环境中，Wu等[1]研究了考虑学习效果的项目进度和人员分配的决策问题。Fang等[2]研究了多项目进度优化管理问题，基于列生成法和启发式方法，采用免疫遗传算法进行求解。肖菁等[3]在多项目并行的调度问题研究中考虑了各项目之间存在的优先级别对调度过程的影响。

员工技能和熟练度是人力资源管理中需要考虑的重要特性。Heimerl等[4]、Myszkowski等[5]和Yannibelli等[6]将员工技能分为单技能、多技能和全技能，研究了不同技能的工作效率对作业时间的影响。Barz等[7]在决策模型中对具有不同技能水平员工的分配问题展开了研究。陈蓉等[8]研究新产品研发项目的多技能人力资源调度问题时，在模型中考虑了多技能工离职的情况。刘振元等[9]研究了多技能资源时间窗约束下的可中断项目调度问题。

目前项目调度的优化目标主要为追求工期、成本、资源等方面的最优解。Myszkowski等[5]、Hanne等[10]、Chen等[11]和陈俊杰等[12]以最小化项目的总工期和总成本为目标函数。Yannibelli等[6]考虑了为项目分配人力资源的有效水平的最大化和工期最小化2个具有相互冲突的优化目标。伊雅丽[13]考虑了人力成本以及项目的延期惩罚成本。传统的项目调度优化研究主要集中于提高资源配置效率和降低成本，很少考虑因不均衡的任务分配会造成工作量差异引起多能工的不满情绪，而影响到员工的工作效率，进而影响项目的完成。廉洁等[14]研究了生产系统中以多能工工作量均衡为目标的多能工分配问题。廖婷婷[15]对软件开发项目的资源分配进行优化，提高了员工工作量分配的均衡水平。

人力资源是一种具有多技能性、异质效率性等特点的动态资源。现有相关研究成果缺乏对多项目和多技能的全面考虑，未能体现多能工技能差异以及工作量均衡对项目进度的影响。因此，本文提出的以多项目总工期最短和多能工间工作量均衡为目标的多项目多技能人力资源调度问题，具有重要的理论意义和现实意义。

1 问题描述

假设共有J个项目并行开展，I个多能工可供分配。项目j有Nj项任务，项目j中的任务k需要具备技能的多能工来完成。其中，任务1和任务Nj为虚拟任务，分别表示项目的开始和结束，不消耗时间和人力资源。每个多能工i的技能集合为其技能熟练度水平集合为(pi1,pi2,···,pis)。技能熟练度系数rik的倒数(1/rik)作为作业时间系数wik，wik＜1表示多能工i完成任务k的时间少于标准作业时间。一项任务的实际工作时间是该任务的标准作业时间tjk和负责该任务的多能工Yijk的工作时间系数wik的乘积。

图1描述了本文研究的问题。图中包含3个项目、9位多能工，不同的项目包含不同的任务且任务需要的技能也不同，而9名多能工都具备多种技能，现将9名多能工分配至项目的任务中。以项目1为例，项目1的任务列表为(W2,W3,W4,W5,W7,W8)，任务需要的技能分别为(k3,k1,k2,k4,k3,k1)，仅多能工-项目分配方案就有35 280种。图中将多能工1、3、8分配至项目1，分别负责的任务为I1:(W3,W8)、I3:(W4,W5)、I8:(W2,W7)。

图1 多项目的多能工分配示例Figure 1 Example of multi-skilled assignment for multi-project

因此，本问题包含以下关键决策，以达到多项目总工期最短和多能工工作量最均衡。1) 给每个项目分配哪些多能工；2) 给已分配至项目中的多能工分配哪些任务；3) 项目中每个任务的开始时间及结束时间。

1.1 基本假设

1) 每个多能工同一时间只能使用一项技能；

2) 任务一旦开始，不允许抢占、不能中断；

3) 多能工一旦被分配到某个项目中，只能做这个项目；

4) 一个任务只能由一个多能工来完成；

5) 多能工的技能熟练水平是固定的，不考虑学习和遗忘。

1.2 符号定义

多能工的总数；Nj表示项目j的任务总数(1≤k≤Nj)；

1)变量参数。J表示项目总数(1≤j≤J)；I表示tjk表示项目j的任务k的标准工作时间系数；rik表示多能工i对任务k技能熟练度水平；wik表示多能工i进行任务k时的工作时间系数wik=1/rik；Qk表示任务k的紧前任务集合；m为Qk的任意紧前任务；sjk表示项目j中任务k的开始工作时间；fjk表示项目j中任务k的工作结束时间。

2) 变量定义。

2 数学模型

第1个目标函数(式(1))表示多项目总工期T最小，其中，表示项目j中Nj个任务的工作结束时间；第2个目标函数(式(2))表示所有多能工工作量的方差B最小，即多能工间工作量最均衡；式(3)保证一个多能工仅能分配到一个项目中；式(4)表示多能工必须具备分配的任务所需技能；式(5)避免项目间的多能工调度；式(6)表示每项任务必须被完成且只被完成一次；式(7)约束了任务的开始时间不得早于其紧前任务的结束时间；式(8)定义了项目中每个任务的结束时间等于开始时间与工作时间之和。

3 算法设计

本文研究的问题属于NP-hard问题，因此选取第2代非支配排序遗传算法(non-dominated sorting genetic algorithm II,NSGA-II)作为求解算法，并在

NSGA-II的基础上，根据问题的特点开发了适用于本文模型的算法。

3.1 编码规则

本文参考Vila Goncalves Filho等[16]的编码方式，将编码结构设计为便于交叉操作的双层染色体编码结构。第1层染色体包含I个基因位，I为多能工数，每个基因位的值为多能工编号，第1层染色体可分为J段，J为项目数，每段表示一个项目，项目之间用“|”分隔，每1段的值表示项目-多能工分配结果。第2层染色体的基因位为所有项目的任务数总和，每个基因位的值为多能工编号，表示任务-多能工分配结果。第2层染色体的基因值的分配范围由第1层基因值决定。图2为染色体编码结构示例。

图2 染色体编码结构示例Figure 2 Example of chromosome coding structure

3.2 创建初始种群

为保证生成的每个染色体都满足约束条件，本文根据模型特点，提出了一种启发式规则来生成染色体。

第1阶段，将多能工分配至各项目。首先给每个项目分配若干位多能工，保证项目正常运转，然后将剩余未分配的多能工根据多技能水平随机分配到各项目中，如图3所示。

图3 多能工项目分配Figure 3 Allocation of multi-workers for projeccts

第2阶段，给项目中的多能工分配任务。首先给每个多能工分配1项任务，使每一位多能工至少负责一项任务；然后将剩余未分配的任务随机分配至具备任务所需技能的多能工，如图4所示。

图4 任务分配Figure 4 Allocation of multi-workers for tasks

所有分配过程都必须考虑多能工是否具备相关技能。

3.3 适应度值计算

在非支配排序之前根据数学模型中的目标函数计算染色体的适应度。目标函数(式(1))的求解过程可视为求解资源约束项目调度问题RCPSP (resourceconstrained project scheduling problem)，项目由一系列相互关联的任务组成，调度决策需要同时满足项目任务之间的时序约束和资源约束，以使项目调度目标最优。选取蚁群算法去搜寻当前分配方案下的最短工期。本文蚁群算法的启发项矩阵中的值为多能工在该任务工作时长的倒数ℓ(ijk)=信息素矩阵初始化所采用的策略为品质因子与任务数的比值ρ=Q/activity_num，其中，Q为品质因子，初始化时Q=1，表示蚂蚁在走完一条路径后留下的信息素总量，为总任务数。状态转移策略采取轮盘赌策略。决定下一个任务选取的概率为activity_num η=其中，α 是信息素重要程度因子，β是启发函数重要程度因子。信息素的局部更新式为其中，r ho=0.2，表示信息素的挥发速度。精英蚂蚁策略计算公式为

由于本算法中产生的所有染色体均符合约束条件，不存在不可行解的情况，所以不用对染色体进行惩罚，适应度函数即为目标函数的映射。根据式(1)，通过上述的蚁群算法可计算得出每个项目的最短工期，求出每个染色体的适应度值eval1和eval2。

3.4 遗传操作

采用Deb等[17]提出的非支配排序方法对种群中的个体进行分层，并计算同一层染色体间的拥挤距离；采用锦标赛选择法选出父代个体；使用基于项目的两点杂交法对父代个体进行杂交，如图5所示。

图5 杂交算子操作示例Figure 5 Example of hybrid operator operation

为保证杂交出的子代染色体中项目信息的完整性，采用交换项目信息来进行杂交，但杂交产生的子代染色体仍会出现信息冗余或缺失。

为解决杂交后子代个体的染色体信息不完整问题，本文提出一个子代个体调整流程，具体步骤如下。

1) 删除冗余基因。若子代染色体中有基因重复，则保留“新”基因，删除“旧”基因，即删除非杂交区域的重复基因[18]。删除员工-项目的基因时，同时删除员工负责的活动信息。

2) 填补第1层空白信息。删除冗余基因后，判断每个项目中的员工是否能够保证项目顺利运行，若不能顺利运行，给该项目分配员工，以最少的员工保证项目运行。若每个项目都能运行，仍有部分员工未分配，则将该员工随机分配到其能工作的项目中。

3) 填补第2层空白信息。根据填补完成的第1层基因信息将员工随机分配到各活动中，分配之前需判断员工是否具有该活动所需技能。

本文的变异操作先应用于染色体的第1层基因，染色体的第2层基因随第1层的基因变异信息而发生变异。变异操作根据变异概率随机选取染色体的基因位，然后将基因位对应的多能工信息从当前项目转移至其他项目。变异后的染色体需进行调整，调整流程如图6所示。最后使用精英策略规则从父代种群和子代种群中挑选出最好的N个染色体进行下一代遗传操作。

图6 子代个体调整流程图Figure 6 Flow chart of offspring individual adjustment

4 算例研究

4.1 数值算例

某研发企业有3个项目需同时进行，共需要6种技能来完成项目。每个项目所包含的任务、任务所需技能、标准工时、任务间时序约束分别如表1、图7～9所示。现有14位多能工，每位多能工具备不同的技能，且对所掌握技能也有不同的作业时间系数，如表2所示。

表2 多能工作业时间系数Table 2 Time coefficient of multi-tasking work

图7 项目1网络计划图Figure 7 Network plan of project 1

表1 项目信息Table 1 Project information

4.2 参数设置及实验结果

算法采用Python编程，环境为Python3.7，编译器为Spyder，运行环境为2.5 GHz主频的CPU,Intel Core i5处理器。遗传算法参数值如表3所示。为保证解的质量，算例运算10次，选取最好的结果。表4列出了算例的非支配解集。表5以解1为例给出了各个项目的具体分配方案，其中，项目下任务编号顺序表示任务优先级，碰到人力资源约束或任务时序约束时，优先级高的任务优先分配和使用人力资源。

表3 遗传算法参数Table 3 Parameters of the genetic algorithm

表4 非支配解集Table 4 Non-dominated solution set

表5 解1中的项目调度方案Table 5 Project scheduling scheme in solution 1

算例中初始种群所有个体及末代种群中帕累托前沿个体的比较如图10所示。图11为遗传算法进化过程中每一代种群中最优解的均值变化情况。图12为不同迭代次数得到的帕累托最优解集间的关系。

图10 初始种群和末代种群适应度对比Figure 10 Comparison of adaptability between initial and last population

图11 双目标随迭代次数的变化趋势Figure 11 Trend of doublel targets with the number of iterations

图12 不同迭代次数的收敛结果Figure 12 Convergence results of different iteration times

为进一步验证NSGA-II算法的稳定性，将算法运行10次，产生10个帕累托解集，如表6所示。采用解集覆盖度C[19]来比较帕累托解集之间的相互支配关系，解集相互覆盖度的定义如式(9)所示，其中，a′≻a′′表示a′支配a′′。

表6 10次运行解集覆盖度比较结果Table 6 Comparison results of solution set coverage for 10 runs

图8 项目2网络计划图Figure 8 Network plan of project 2

图9 项目3网络计划图Figure 9 Network plan of project 3

式中，X1、X2为2个不同的帕累托解集；C(X1,X2)为X1中的解能支配或等于X2解的比例，C(X1,X2)∈[0,1]；C(X1,X2)=1表示X2中的所有解都能在X1中找到支配解或等于该解的解；C(X1,X2)=0则表示X2中的任何解都不会被X1中的解所支配，即X1的解中所有解的质量都不会比X2中的任何一个解差。这可以直观地比较出每一次计算所得解集的优劣性，即验证算法的稳定性。

4.3 结果分析

本文提出的算法能得到一系列帕累托解。在图10和表4中，无法根据2个目标选出最优解，因为它们都是非劣解。决策人员可以根据自己的诉求来选择满足自己需求的解决方案。若他们认为员工工作量均衡比项目总工期更重要，可选择非支配解5；若认为项目总工期更重要，可选择非支配解1。

从图10可以看出帕累托最优解集的适应度明显高于初始种群的适应度，这也充分证明本算法的有效性。从图11可以看出，种群在进化过程中2个目标值的均值均呈下降趋势，这说明在求解的过程中最优解的质量在不断提高，且解集在迭代60次左右就稳定下来。为了验证迭代100次就能得到很好的解集，本文分别迭代了20次、100次、500次，比较其解集的支配关系。从图12可以看出，迭代20次求得帕累托最优解的质量不如迭代100次的结果，而迭代500次得到的帕累托最优解集虽然比迭代100次的情况多了2个非支配解，但迭代500次并没有得到更高质量的解，这充分说明本文算法具有较好的收敛速度，在迭代100次时解的质量就很稳定。

从表6可以看出，算法运行10次得到的10个非支配解集质量很稳定。例如，C(1,2)=0表示第2次运行生成的解集不被第1次运行生成的解集所支配；C(4,3)=0.15则表示第3次生成的解中15%被第4次运行生成的解集所支配。而10次运行出来的解集仅有C(4,3)不为0，由此说明本文提出的NSGAII算法性能稳定。

5 结论

为解决多项目并行环境下多技能人力资源多目标调度问题，本文提出了基于NSGA-Ⅱ和蚁群算法的多目标优化方法，得出如下结论。

1) 综合考虑多能工的多技能及其技能熟练水平对任务作业时间的影响，建立了以多项目总工期最短和多能工间工作量均衡为目标的多目标整数非线性规划模型。

2) 提出了系列启发式规则生成初始种群，避免不可行解的产生，提高了算法效率。采用蚁群算法搜寻当前分配方案下的最短工期。在进行杂交和变异操作时，为了避免陷入局部最优，采取“保新删旧”策略进行基因调节。

3) 通过数值算例证明了所提出的多目标优化方法能够在可接受时间内得到有效、稳定的人力资源调度方案集(pareto解集)供调度人员决策。

本文研究多能工的技能熟练度水平是固定的，没有考虑学习和遗忘。在未来的研究中，可考虑技能熟练度随着经验累积或遗忘而变化的异质性多能工分配问题。