考虑人格因素的软件项目调度模型与算法_李洪波.pdf

第 28 卷 第 2 期2023 年 4 月工业工程与管理Industrial Engineering and ManagementVol.28 No.2Apr.2023考虑人格因素的软件项目调度模型与算法李洪波，惠千容*（上海大学 管理学院，上海 200444）摘要:软件项目的成功离不开对技能型人力资源的合理调度，而项目团队中员工的人格特质往往会影响其执行任务的效果。研究了多技能条件下考虑人格因素的软件项目调度问题，旨在满足技能、优先关系等约束条件下，将具有不同技能和人格特质的员工进行有效调度，从而最小化项目总成本。建立了该问题的混合整数线性规划模型，设计了基于双重优先规则的启发式调度算法。基于全因子试验设计构建基准数据集，利用计算实验分析了所提算法的性能。将所提算法同CPLEX和遗传算法进行了对比，结果表明所提算法在求解效率和效果上均具备优秀的竞争力。关键词:软件项目调度；混合整数规划；启发式算法；人格因素；试验设计中图分类号:C 931 文献标识码:AModels and Algorithms for Software Project Scheduling Considering PersonalityLI Hongbo，HUI Qianrong*（School of Management，Shanghai University，Shanghai 200444，China）Abstract:Effective scheduling of multi-skilled human resources is essential to the success of software projects.In software development，employees personality traits often affect the performance of their work.The software project scheduling problem with multi-skilled employees considering employees personality was studied.The proposed problem aimed at assigning employees with different skills and personality traits to suitable tasks，and determining the start time of each task under the constraints of skills and precedence relations，such that the total cost of the project was minimized.A mixed integer linear programming model was formulated and a double priority rules based heuristic algorithm was proposed.Based on a benchmark dataset that was generated using full factorial design of experiment，computational experiments were conducted to analyze the performance of the proposed algorithm.The algorithm was compared with the commercial solver CPLEX and genetic algorithm.The results show that the algorithm is competitive in terms of efficiency and effectiveness.Key words:software project scheduling;mixed integer programming;heuristic algorithm;personality;design of experiment1 引言 软件产业作为我国的战略性高技术产业，是社会信息化的重要支撑。2020年，我国软件业务收入已突破8万亿元，增幅创五年来新高1。然而，由于软件开发的业务逻辑日益复杂、项目团队跨国跨地文章编号：1007-5429（2023）02-0010-09DOI：10.19495/ki.1007-5429.2023.02.002收稿日期：2021-07-06基金项目：国家自然科学基金（71602106）;上海市“科技创新行动计划”软科学重点项目（20692192400）作者简介：李洪波（1985），山东东营人，副研究员，博士，主要研究方向为项目管理与调度。E-mail：。*通信作者：惠千容，硕士研究生，主要研究方向为项目调度。E-mai：。-10第 2期工 业 工 程 与 管 理区协作渐成常态、用户需求复杂易变，导致软件开发项目成功率较低，大量软件开发项目难以在预算内按时交付。牛津大学与麦肯锡公司对预算规模1 500万美元以上的软件开发项目的调查显示，平均每个被调查项目的预算超支45%，交付日期比预计日期延迟7%2。许多软件开发项目失败的根源可以追溯到缺乏有效的调度3-4。软件项目调度旨在满足任务优先关系、人力资源技能约束等条件的前提下，获取一个基线进度计划。该计划指明了每个项目成员需在何时执行何种任务，从而使得具有某些技能的员工与所需这些技能的任务形成最佳匹配，并最小化项目的工期、成本等绩效指标。学术界已对软件项目调度问题做了大量深入的研 究。作 为 早 期 的 代 表 性 研 究，ALBA 和CHICANO 5 在对软件项目调度的研究中，利用遗传算法为员工指派任务和工作量，后续的软件项目调度研究大都在这项研究的基础上进行扩展 6-8。LI和WOMER 9 研究了软件项目调度问题的混合整数线性规划模型及其Benders分解算法。RODRIGUEZ等 10 在ALBA和CHICANO 5 模型的基础上考虑了技能水平，用非支配排序遗传算法优化项目的工期、成本和效率等多个目标。GARCA和GMEZ 11 则对具有不同技能水平的员工设定不同的薪资。CHICANO等 12 的研究考虑了员工工作效率的差异。JANIAK 和 RUDEK 13、KUO 和 YANG 14、WANG X Y和WANG J J 15、NIU等 16 以及LIN 17 考虑了项目调度过程中员工的学习效应。郭一楠等18结合学习/遗忘模型，模拟员工技能的学习-遗忘-再学习的现象，设计了非支配排序遗传算法，从而最小化项目的工期和成本。MINKU等19将员工的投入上限设定为1，考虑资源的有限性，设计了改进的进化算法。SHEN等20将员工的满意度作为项目的优化目标之一，设计了基于Q学习的多目标双存档模因算法。HEIMERL和KOLISCH21考虑了员工使用技能的效率、工作负荷和内外部员工情况，针对多技能人力资源的多项目调度问题，建立了混合整数规划模型。刘振元等22针对可抢占软件项目调度问题，建立了整数规划模型，并设计了分支定界算法。虽然已有研究从人力资源的诸多角度对软件项目调度问题做了大量扩展研究，但少有研究将员工的人格因素纳入软件项目的调度过程，这无疑影响了具有显著智力密集型特点的软件项目调度模型与算法的有效性23-24。人格综合反映了人的行为模式、思维模式和情绪反应，它会影响员工的工作绩效25。DHANI和 SHARMA26的实证研究结果表明，人格特质对 IT员工的工作绩效具有显著影响，可以作为员工工作绩效的预测因子。此外，员工工作绩效相关的风险是项目风险中的一个重要因素27，提高员工的工作绩效是降低项目风险、提高项目成功率的有效措施28-29。因此，在软件项目调度过程中，考虑员工人格特质与不同类型任务的匹配度，有助于提升员工的工作绩效，进而提高软件项目的成功率。因此，本文提出并研究了考虑员工人格因素的软件项目调度问题。主要贡献在于：（1）针对考虑员工人格因素的软件项目调度问题，建立了混合线性规划模型。模型中考虑了人格因素以及多任务、加班、任务工作量可变等多种因素对调度目标的影响。（2）为了高效求解本文的问题，设计了一个基于双重优先规则的启发式调度算法。（3）基于试验设计和大规模计算实验，将本文算法与CPLEX和遗传算法进行了对比，对比结果体现了本文算法的有效性和高效性。2 考虑员工人格因素的软件项目调度问题 本文研究的问题描述如下。用有向图G=(N，A)表示一个软件项目，其中：N=0，1，n+1为节点的集合，表示项目中的任务；ANN为有向弧的集合，表示任务之间的优先关系，即对于任意(i，j)A，任务j需在任务i完成后方可开始，称i为j的紧前任务，j为i的紧后任务。IPj和ISj分别表示任务j的紧前和紧后任务集合。任务 0 和n+1为虚任务，分别代表项目的开始和结束。每个任务j的工期为整数dj，开始时间为整数stj。任务不可抢占，即任务开始执行后不允许中途停止，则任务j的完成时间为stj+dj。虚任务的工期为0。项目的截止日期为-d。具备各种技能的人力资源是软件项目中的核心资源。用集合E表示项目中涉及的所有员工，将员工eE具备的技能集合表示为SeS，S为项目所需的所有技能集合。具备技能s的员工集合为EsE。每个任务j在执行时，需要向其安排员工，且这些员工具备的技能必须涵盖任务j所需的技能集合SjS。任务j在每个时段q对技能s投入的工作量需求为rjqs。若员工e被安排执行任务j，则xjtse-11第 28 卷 李洪波，等：考虑人格因素的软件项目调度模型与算法表示该员工在时段t使用技能s投入到任务j的工作量。虚任务不消耗任何资源。此外，将所有员工需要承担的平均工作量表示为项目的工作强度：=jNsSE(rjqs)eERmaxe（1）其中，E(rjqs)表示单位时间内任务j对于各种技能的平均工作量需求。(0，1)，其值越大，意味着员工的工作负荷越重。对于同一种技能，不同员工的熟练程度不同。用se表示员工e掌握技能s的效率，则1 se表示员工e使用技能s完成单位工作量所需的时间。当员工e不具备技能s时，se=0。单位时间内员工e可承受的 工 作 量 不 能 超 出 其 单 位 时 间 内 的 最 大 工作量Rmaxe。同时，员工的人格特质对其工作效果有影响。比如，用户需求分析这类任务，外向型的员工往往更为擅长。因此，本文引入匹配系数se 0，2 表示员工e和需要技能s的任务之间在人格上的匹配程度，其计算依据主要基于SANTOS等30的框架，并将人格特质引入计算过程。首先，基于大五人格法，从N（神经质性）、E（外倾性）、O（开放性）、A（宜人性）、C（严谨性）五个维度对软件项目中员工的人格特质进行测量，测量结果为pie 0，10，其表示员工e在维度i上的得分。pis1，4，7 表示技能s在维度i上的需求等级，取值1、4、7分别代表低、中、高水平。然后，引入is表示维度i对技能s的影响程度，其值可通过专家打分法获得。那么，指派员工e使用技能s的匹配程度系数se可以表示为：se=i=15iiise（2）其中，ise衡量了员工e和技能s在各维度i上的差异，其计算方式为：ise=0，piepis|pis-pie|，piepis（3）i为修正系数，描述了不匹配程度在各维度i上的叠加效应，权重较高的维度上，不匹配造成的叠加效应更大，其计算方式30为：i=|i-1，piepisi-1+wii=15wi，piepis（4）可见，se越大，表示员工e和需要技能s的任务之间在人格上的不匹配程度越高。基于上述分析，安排员工e执行任务j时，因人格不匹配成本导致的成本cpjtse=wsexjtse，其中，w表示由于不匹配导致的单位工作量额外成本，该参数可由项目经理基于已有项目的实施经验进行估计，将其量化为以资金为单位的值。考虑员工人格因素的软件项目调度的任务是，在满足技能匹配、优先关系和项目截止日期等约束下，将具有不同技能和人格特质的员工合理安排不同的任务，确定每项任务的开始时间，以形成一个有效的项目进度计划，从而最小化项目的总成本。项目的总成本由以下三项构成：（1）员工的总基本工资eEcestn+1，其中ce为员工e在单位时间内的基本工资，虚终止任务n+1的开始时间stn+1对应了项目的完工时间。无论是否安排员工至某项具体任务，都要向员工支付基本工资。（2）员工的总绩效工资eEsSet=1-djN(1 sexjtsec)，其中，c为员工e在单位时间内的绩效工资，1 sexjtse为员工e的实际工作时长。员工只有在参与任务时，才会获得绩效工资。（3）人格与任务不匹配导致的总惩罚成本eEsSet=1-djNcpjtse。3 混合整数线性规划模型 本节建立考虑员工人格因素的软件项目调度问题的混合整数线性规划模型。在上一节的决策变量xjtse基础上，进一步引入决策变量yjt 0，1，用于确定任务j在第t个时段是否开始。yjt=1，任务j在t时段开始执行0，否则（5）则任务j的开始时间stj=t=1-dyjtt。进而构建如下混合整数线性规划模型：Min eEsSet=1-djN(1 sexjtsec+se wxjtse)+eEcestn+1（6）s.t.t=1-dyjt=1,jN（7）t=1-dyjttt=1-dyitt+di，(i，j)A（8）-12第 2期工 业 工 程 与 管 理eEsxjtserjqsyj，jN；=1，-d-dj；q=1，dj；t=+q；sSj（9）jNsS1sexjtseRmaxe，eE；t=1，-d（10）yjt 0，1，jN；t=1，-d（11）xjtse0，jN；t=1，-d；sS；eE（12）在上述模型中，目标函数式（6）最小化项目的总成本。约束式（7）限制任务j在整个项目过程中有且仅有一个开始时间。约束式（8）描述的是优先关系约束。约束式（9）表示，对于任意时段=1，-d-dj，如果任务j在时段开始（rjqsyjt0），则依次对任务j在阶段q=1，dj对于技能s的工作需求rjqs进行分配。根据任务j的开始时段和任务j的进程q，可以确定分配工作量rjqs的时段为t=+q，分配的对象为具备技能s的员工e，即eEs，分配的工作量为xjtse。eEsxjtserjqsyj限制了所安排的员工可以满足任务j在q时段对技能s的工作量需求，保证该进度计划下项目的所有任务可以全部完成。约束式（10）是资源约束，任意时段t内任意员工e完成被分配的工作量所需的时间不能超过该员工单位时间内的工作上限。约束式（11）和式（12）定义了决策变量yjt和xjtse的取值范围。考虑本问题的一个特例：首先，令每个任务的工期均为1；其次，假设每名员工只具备一种技能，且技能效率相同，每名员工的工作量上限均相同，即|Se|=1，se=1，Rmaxe=1；然后，令每名员工单位时间的基本工资为1，不考虑员工的绩效工资和人格不匹配惩罚成本，即ce=1，c=0，w=0。在上述条件下，本文的问题便成为经典的以项目工期最小化为目标的资源受限项目调度问题（resource constrained project scheduling problem，RCPSP）。而RCPSP为NP难问题31，因此，作为RCPSP的泛化，本文研究的问题也是NP难问题。为了实现对大规模问题实例的高效求解，本文将在下一节设计一个基于双重优先规则的启发式调度算法。4 基于双重优先规则的启发式调度算法 分析本文的问题和模型可以发现，以下三个因素对软件项目的总成本有重要影响：（1）项目工期。项目工期越小，意味着员工的基本工资总额越小。（2）员工效率。如果能优先安排效率高的员工，有助于压缩项目工期，从而减少员工绩效工资所占用的成本。（3）员工人格与任务的匹配程度。显然，如果员工的人格与其承担的任务越匹配，则越有助于减小不匹配导致的惩罚成本。基于上述分析，设计了一个基于双重优先规则的启发式调度算法，该算法通过任务选择和员工指派这两类优先规则，充分利用上述三种因素来构造能够尽可能降低项目总成本的进度计划。在本文的启发式调度算法中，可以灵活嵌入各种不同的任务选择与员工指派相关的优先规则。算法的整体框架包含以下步骤。步骤1 初始化：令虚起始任务的开始时间st0=0；令已调度任务集合Skd=0；令可调度任务集合D为空集；初始化资源可用量矩阵RES-d|E|，该矩阵中的每个元素RES t e 表示员工e在时段t的可用工作量；从表1中选择一个任务调度优先规则，从表2中选择一个员工指派优先规则。步骤2 更 新 可 调 度 任 务 集 合D：D=j|j Skd IPj Skd。步骤3 任务选择：基于任务调度优先规则，计算集合D中每个任务的优先值，从中选择优先值最高的任务j*。步骤4 员工指派：基于面向单任务的员工指派算法对任务j*进行调度（详见下文），确定其开始时间stj*及员工指派方案。步骤5 更 新 已 调 度 任 务 集 合Skd：Skd=Skd j*。步骤6 重复步骤25，直到全部任务调度完成（此时Skd=N）。输出项目进度计划。在上述步骤3中，可以使用多种优先规则进行任务选择，为了尽可能最小化项目的总成本，本文算法中包含了6种不同的优先规则，各规则的定义见表1。在上述算法运行过程中，表1中的任何一个优先规则都可以放入步骤3。此外，当出现多个任务具有相同优先值时，选择编号最小的任务。面向单任务的员工指派算法的伪代码如表3所示。该算法针对需要指派员工的某个具体任务，首先基于优先规则确定员工的指派顺序，进而在满足各类约束的前提下尽可能早地确定该任务的开始时间。在算法1中，给定一个任务j*，从其最早开始时间开始（stj*=esj*），对任务j*的每一单位时段q，按照技能稀缺程度（|Es|）由高到低依次满足任务j*对于各项技能的需求。对于需求rj*qs，按照优先规则（表-13第 28 卷 李洪波，等：考虑人格因素的软件项目调度模型与算法2）进行员工指派（算法1第721行）。若指派过程中发现资源不足（RESEs=0时，技能需求rj*qs仍不能满足），则令时间延迟lag的取值加1（算法1第1921行，lag与esj*之和决定了任务j*的最早可行开始时间），直到找到合适的开始时间使得任务j*的工期内全部技能需求均得到满足。算法最后输出任务j*的开始时间、向其指派的员工及员工的工作量情况。表2展示了用于算法1中进行员工指派的优先规则。在算法1执行时，可以从表2中任选一个优先规则。在员工指派过程中，有两个方式可以减小项目成本：优先指派效率更高的员工和优先指派人格匹配程度高的员工。为此设计最大技能效率优先规则（pRA1）和最小匹配系数优先规则（pRA2）。为综合上述两个因素，本文还设计了混合优先规则：最小单位资源分配成本优先规则（pRA3）。另外，随机优先规则pRAr从上述三种优先规则中随机抽取一个优先规则来使用。当出现多个员工具有相同优先值时，本文将选择编号最小的员工。最后分析本文启发式算法在最坏情形下的计算时间复杂度。在本文算法中，根据优先规则计算任务调度优先顺序的时间复杂度为O(|N|+|A|+n)，计 算 员 工 指 派 优 先 顺 序 的 时 间 复 杂 度 为O(|S|+|E|(log|E|+1)，算法1的时间复杂度为O(SLd|S|E|)，其中，SL和d分别为所有活动的自由时差和工期的最大值。5 计算实验 通过计算实验分析本文调度算法的性能。本文算法用 Python 3.7 编程实现，计算实验在配备Intel Core i5 3.20 GHz CPU 和 Windows 7 64-bit的计算机上实施。接下来首先介绍计算实验使用的基准数据集，其次探讨有效优先规则的选取，然后通过与CPLEX和已有元启发算法对比的方式分析本文算法的性能，最后基于灵敏度分析讨论本文算法的性能。表1任务选择优先规则优先规则最短工期优先最多紧后任务优先最早开始时间优先最晚结束时间优先最大资源需求优先随机规则代号pAL1pAL2pAL3pAL4pAL5pALr定义Min djMax|ISj|Max esjMax lfjMax q=1djsSrjqs从上述规则中随机选择一个规则表3 算法1 面向单任务的员工指派算法输入:任务j*，esj*,lsj*)，RES，pRA1234567891011121314151617181920212223242526输出:stj*，xj*tse，RES初始化：lag=0;stj*=esj*;基于关键路径法计算j*的最早/最晚开始时间esj*和lsj*stj*=stj*+lagWhile stj*lsj*RES=RES For q=1 to dj*For s=1to|S|根据技能调度顺序从S中选择技能s require=rj*qs While require0 根据优先规则pRA从Es中选择员工e*If RES stj*+q e*se*require RES stj*+q e*=RES stj*+q e*-require se*xj*tse*=xj*tse*+require require=0 Else xj*tse*=xj*tse*+RES stj*+q e*se*require=require-RES stj*+q e*se*RES stj*+q e*=0 If RESEs=0 and require0 任务j*不能在stj*时刻开始 lag=lag+1 End while End for End for 返回当前开始时间stj*和资源可用量RESEnd while表2员工指派优先规则优先规则最大技能效率优先最小匹配系数优先最小单位资源分配成本优先随机规则代号pRA1pRA2pRA3pRAr定义Max seMin seMin 1sec+wse从上述规则中随机选择一个规则-14第 2期工 业 工 程 与 管 理5.1基准数据集基于全因子试验设计构造用于计算实验的基准数据集。首先，利用项目调度问题实例生成软件RanGen生成具有不同任务数量n和次序强度（order strength，OS）的项目网络32，其中OS(0，1)，反映了项目网络中优先关系的多少，OS越大表明优先关系越多。然后，对于RanGen生成的每个项目网络，确定其工作强度及其涉及的每个员工拥有的技能数量|Se|。这样，对n、OS、和|Se|这4个特征参数设置不同的取值（表4），每种参数组合下生成10个实例，一 共 生 成4 2 2 2 10=320个 项 目实例。进一步，对于上述每个项目实例，令员工总数|E|=40。员工e在单位时间内的工作上限Rmaxe从 0.8，1.2 随机抽取。技能效率se从截断正态分布TN0.5，1.5(1.0，0.25)中抽取。人格匹配系数se从截断正态分布TN0，2(1.0，0.25)中抽取。单位时间内的基本工资ce从截断正态分布TN8.75，13.75(11.25，2.5)中抽取。令单位绩效工资c=100，人格不匹配的单位惩罚成本w=50。每个项目涉及的技能总数|S|=8。每个任务最多需要这些技能中的4种，从所有技能中随机抽取。每个任务的每项技能需求量rjqs，从均值为E(rjqs)、标准差=0.1E(rjqs)的正态分布中抽取，其中，E(rjqs)基于式（1）推导计算可得。对于上述基准数据集，用 CPLEX 12.9求解每个实例的时间上限为600秒。根据CPLEX的求解结果，将基准数据集分为3个子集：Seto、Setf和Seti，分别代表求得最优解的数据集、仅求得可行解的数据集和未求得可行解的数据集。这些集合的基本信息见表5。需要说明的是，在任务数量为30的数据集中，有1个实例无解，故将其从基准数据集中删除。这样，后续实验中使用的数据集中包含实例数量为319。5.2优先规则讨论本文的调度算法可以使用多种不同的优先规则。基于Seto确定有效的优先规则组合。首先定义平均相对偏差（average relative deviation，ARD）：ARD=iSeto(obji-opti)opti|Seto（13）其中，obji 表示本文算法求得的数据集Seto中第i个实例的目标函数值，opti是CPLEX求得的实例i的最优目标函数值。然后，对于本文的算法，组合不同的任务调度和员工指派优先规则，从而形成20种不同的调度算法。用这些算法求解Seto中的实例，将求解结果与CPLEX进行对比，结果如表6所示。表6展示了不同优先规则组合下本文调度算法的ARD值。表4基准数据集的主要参数设置参数nOS|Se|取值10,20,30,600.3,0.72,40.3,0.7表5CPLEX对基准数据集的求解结果数据子集SetoSetfSeti任务数量1010203060实例数量5129807980表6不同优先规则组合下本文调度算法的ARD值任务调度优先规则pALrpAL1pAL2pAL3pAL4pAL5平均值极差员工指派优先规则pRA18.15%8.10%8.17%8.08%8.24%8.15%8.15%0.16%pRA20.13%0.13%0.13%0.13%0.13%0.13%0.13%0.00%pRA32.70%2.72%2.70%2.71%2.72%2.70%2.71%0.01%pRAr3.26%3.29%3.29%3.30%3.33%3.24%3.28%0.09%平均值3.56%3.56%3.57%3.56%3.60%3.56%3.57%0.05%极差8.02%7.97%8.03%7.95%8.12%8.02%8.02%0.17%-15第 28 卷 李洪波，等：考虑人格因素的软件项目调度模型与算法观察表6可以发现：选用不同的任务调度优先规则时，ARD没有明显差别（其均值的极差仅为0.05%）；极差显示本文启发式算法的性能受员工指派优先规则的影响更大，其中，混合优先规则pRA3明显优于其他单一优先规则和随机优先规则。因此，在后续的实验中，调度算法使用pAL5作为任务调度优先规则，pRA3作为员工指派优先规则。5.3实验结果利用本文算法，求解数据集Seto和Setf，将求解结果与CPLEX的结果进行比较，具体结果如表7和表 8 所示。在这两个表中，展示了本文算法与CPLEX结果的平均相对偏差ARD，以及两种算法的平均计算时间。观察两表结果可以发现，本文算法用远小于CPLEX的计算时间，取得了非常接近CPLEX的计算结果。而且对于任务数量为30的实例，本文算法取得了优于CPLEX的结果。总之，实验结果表明了本文调度算法可以在短时间内获得优良的项目进度计划，体现了本文算法的有效性和高效性。5.4与已有元启发算法的对比结果本节将本文算法与项目调度领域广泛采用的遗传算法进行比较。在Python 3.7中编程实现所对比的遗传算法。在该遗传算法中，染色体的编码包含两部分：任务列表AL和员工-技能分配列表RA=(ra1，ras，ra|S)，其中，RA中的每个元素ras表示具备技能s的员工构成的子列表（表示员工的指派顺序）。初始种群随机生成，共包含40个染色体。对染色体采用两点交叉和单点变异，交叉和变异的概率分别为1.00和0.05。算法迭代25次后终止。用本文算法与遗传算法分别求解基准数据集，然 后 比 较 两 种 算 法 的 平 均 相 对 偏 差ARD=-()iSeti|objHAi-objGAiobjGAi|Seti和平均计算时间，其中，objHAi和objGAi分别表示本文所提算法与遗传算法求得实例i的目标函数值。ARD的取值反映了本文所提算法在目标值上优于遗传算法的比例，该值越大，意味着本文算法的优势越明显。算法对比结果如表9所示。观察表9可以发现，本文算法在求解质量和计算时间上均优于遗传算法，而且本文算法对于人力资源复杂度（|Se|）的敏感度更低。此外，考察上述遗传算法在最坏情形下的计算时间复杂度。该遗传算法生成初始种群的时间复杂度为O(POP(n+|S|E|)，其中，POP为种群中包含个体的数量。交叉和变异算子的时间复杂度均为O(GENPOP(n+|S|E|)，解码过程的时间复杂度约为O(GENPOPn-dd|S|E|)，其中，GEN表示遗传算法迭代次数。在遗传算法的选择操作中，使用快速排序，其时间复杂度为O(POP(2logPOP+1)。第 4 节末尾已经给出了本文启发式算法的计算复杂度，将该遗传算法的计算复杂度与本文启发式算法对比可以发现，本文启发式算法优于该遗传算法。表7数据集Seto上的计算结果|Se|24平均值ARD0.19%0.07%0.13%计算时间（秒）本文算法0.290.310.30CPLEX82.6267.6275.12表8数据集Setf上的计算结果n102030平均值|Se|242424ARD0.47%0.25%0.03%0.05%0.07%0.00%0.12%计算时间（秒）本文算法0.280.280.780.801.351.430.82CPLEX615.99608.57635.63627.26660.84642.21631.75表9本文算法与遗传算法的对比结果数据集SetoSetfSeti平均值n1010203060|Se|2424242424ARD2.11%3.29%2.94%4.31%1.32%3.07%1.97%2.57%2.03%4.12%2.77%计算时间（秒）本文算法0.290.310.280.280.780.801.351.433.914.132.08遗传算法1.391.401.771.722.522.623.603.737.537.743.40-16第 2期工 业 工 程 与 管 理5.5灵敏度分析本节基于能够获得最优解的实例集合，考察次序强度、员工的工作强度和人格的匹配系数对于所提算法性能的影响。图1展示了工作强度和次序强度对本文算法的影响，其中，纵轴表示ARD（同5.2节）。当工作强度给定时，次序强度越大，算法的求解效果越好，表明本文算法能较为有效地处理优先关系数量较多的项目。而工作强度对本文算法的性能有负向影响。然后，考察人格匹配系数对本文算法的影响。由于每个项目实例中涉及多个员工与技能的人格匹配系数，为了获取每个项目中人格匹配系数的代表性取值，首先计算项目中每个员工与其掌握技能的平均匹配系数e=()sSese|Se，以所有员工的e的中位数作为项目中人格匹配系数的代表性取值。对算法的影响如图2所示，其中，每个条形对应一个项目实例，将它们按照从小到大的顺序排列，横 轴 下 方 为 每 个 实 例 的 文 件 名（格 式 为“OS_num”，其中，num1，2，3，10 为实例编号）。观察图2可以发现：当人格匹配系数大于均值时（1），算法的整体求解效果较好；对于1和1两种情形，均为的取值处于中间位置时，算法的求解效果最好。6 结论与展望 本文提出并研究了考虑员工人格因素的软件项目调度问题，建立了该问题的混合整数线性规划模型，设计了基于双重优先规则的启发式调度算法。基于包含320个项目实例的基准数据集，利用计算实验分析了所提算法的性能，将所提算法同数学优化求解器CPLEX和遗传算法进行了对比。实验结果表明：对于中小规模算例，本文算法能够在很短时间内求得接近于CPLEX最优解的结果；对于大规模算例，本文算法的求解效率和效果均优于遗传算法。灵敏度分析的结果还表明了本文算法的鲁棒性。未来的研究将进一步考虑软件项目的其他重要特性，如任务的抢占性、多模式和资源利用的均衡性33-34，并开发有效的精确和元启发调度算法。参考文献：1 工信部.2020年软件和信息技术服务业统计公报 N.中国电子报，2021-01-29.2 BLOCH M，BLUMBERG S，LAARTZ J.Delivering large-scale IT projects on time，on budget，and on value J.McKinsey Quarterly，2011，27：2-7.3 PMI（Project Management Institute）.Pulse of the profession 2016：the high cost of low performance R.2016.图1工作强度和次序强度对本文算法的影响图2人格匹配系数对本文算法的影响-17第 28 卷 李洪波，等：考虑人格因素的软件项目调度模型与算法 4 李洪波，林俏，曹依武.考虑技能因素的软件项目关键链缓冲区大小计算方法 J.工业工程与管理，2021，26（4）：195-201.5 ALBA E，CHICANO J F.Software project management with GAs J.Information Sciences，2007，177（11）：2380-2401.6 CRAWFORD B，SOTO R，JOHNSON F，et al.A max-min ant system algorithm to solve the software project scheduling problem J.Expert Systems with Applications，2014，41（15）：6634-6645.7 XIAO J，AO X T，TANG Y.Solving software project scheduling problems with ant colony optimizationJ.Computers&Operations Research，2013，40（1）：33-46.8 VEGA-VELZQUEZ M ，GARCA-NJERA A，CERVANTES H.A survey on the software project scheduling problem J.International Journal of Production Economics，2018，202：145-161.9 LI H，WORMER K.Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm J.Journal of Scheduling，2009，12（3）：281-298.10 RODRIGUEZ D，RUIZ M，RIQUELME J C，et al.Multi-objective simulation optimization in software project management C/13th Annual Conference on Genetic and Evolutionary Computation.Dublin：ACM，2011：1883-1890.11 GARCA A，GMEZ M.A multi-objective genetic algorithm for the software project scheduling problemC/13th Mexican International Conference on Artificial Intelligence.Switzerland：Springer，2014：13-24.12 CHICANO F，CERVANTES A，LUNA F，et al.A novel multi-objective formulation of the robust software project scheduling problem C/15th European Conference on the Applications of Evolutionary Computation.Switzerland：Berlin，2012：497-507.13 JANIAK A，RUDEK R.Experience-based approach to scheduling problem