求解多技能人力资源约束的项目调度问题的两阶段算法
王一帆，刘士新，陈 迪
【摘 要】摘 要:针对一类多技能人力资源约束的项目调度问题(PSPMSWC)，提出了一种两阶段优化算法，并按算法步骤对模型进行了分解.算法针对分解后的子模型，应用遗传局域搜索及CPLEX优化软件对模型进行求解，并设计了整体迭代求解策略，从而确保所有问题案例都能够进行求解.通过引用基于标准问题库中的典型问题，生成了大量随机算例，并对算法进行了求解实验.实验结果显示，所有案例均能够迅速求解，部分案例可达到最优，从而证明该方法是一种求解PSPMSWC的有效方法，具有较强的实际意义. 【期刊名称】东北大学学报（自然科学版） 【年(卷),期】2014(035)002 【总页数】6
【关键词】关键词:项目调度;多技能人力资源;两阶段求解方法;遗传局域搜索;指派问题
随着知识经济社会的到来，项目管理中的人力资源分配与项目调度已经成为决定项目成本、工期、质量等项目指标的关键因素之一.由此引出的多技能人力资源约束的项目调度问题(project scheduling problems with multi-skilled workforce constraints，PSPMSWC)开始引起学术界和业界人士的关注和研究，成为项目管理领域新的研究热点.目前的研究以人力资源成本最低、全部工作完成时间最短等单目标优化为主［1-5］，少数文献考虑了多目标优化问题［6-7］;优化算法以数学规划为主［1-2，6-7］，此外也有元启发式算法［3］和混合算法［4-5］;问题的应用背景以针对日常运作任务进行人力资源分配为
主［2-3，5-6］，针对项目中的人力资源分配与调度优化问题的研究相对较少［1，4，7］.对于多技能人力资源约束的项目调度问题(PSPMSWC)，求解大规模问题的针对性方法尚未得到广泛深入的研究.
本文针对项目调度与多技能人力资源分配优化问题，给出了优化模型的描述，并设计了两阶段的遗传局域搜索(genetic local search，GLS)算法，采用由Wang等［8］提出的PSPMSWC案例生成器得到的问题案例作为基准案例，对不同规模的问题案例进行了求解，并与CPLEX的求解情况进行了对比.
1 问题描述及模型
PSPMSWC可以简要描述如下:一个项目中包含J项工作，某些工作之间存在着一般性的时间约束关系［6］;项目的结构由一张有向网络图表示，图中节点代表工作，弧线代表工作间的时间约束关系.工作1是唯一最早开始的工作，工作J是唯一最晚完成的工作，且均为虚工作(不消耗资源且执行时间为0)，用以表示整个项目的开始和结束.项目可用的技能工人数量为S，涉及的技能种类数为K.每位技能工人在同一时刻只能应用其掌握的多种技能中的一种.需要指派技能工人完成项目的各项工作，并确定各工作的开始时间，在满足人力资源约束及工作时间约束的条件下实现最优.本文以项目工期最小化为优化目标，引入如下符号.
j:项目中的工作编号，j=1，…，J; τj:工作 j的执行时间，j=1，…，J; k:技能种类编号，k=1，…，K; s:技能工人编号，s=1，…，S;
Sk:掌握技能 k的工人集合，Sk∈{1，…，S};
Kj:完成工作 j需要的技能种类集合，Kj∈{1，…，K}; r jk:完成工作j需要掌握技能k的工人数量; cs:技能工人s的单位时间成本;
T:整个项目的工期上限.分别表示工作j开始时间晚于工作i开始时间和完成时间的最小值(最大值);分别表示工作j完成时间晚于工作i开始时间和完成时间的最小值(最大值).
模型中的决策变量如下.
PSPMSWC的数学模型(P0)可以描述如下: 其中 i，j=1，…，J;s=1，…，S;k∈Kj，下同.
目标函数(1)为最小化项目工期;约束(2)保证在工作j执行期间对各种技能的需求都得到满足;约束(3)限定对于同一项工作j，一个员工最多被指派到其中的一种技能需求;约束(4)～(7)表示工作间的时间约束关系;约束(8)限定如果一个员工被指派参与两项工作，则这两项工作的执行时间不能重叠;约束(9)表示如果工作i在工作j前执行，则要求工作j在工作i完成后才能开始，其中的M 为足够大的正数［9］;约束(10)表示两项工作间最多只能存在一种优先顺序;约束(11)～(13)限定了决策变量的取值范围，其中，EST j和LST j分别为工作j的最早开始时间和最晚开始时间，可以通过时间约束网络［10］推理得到.
2 两阶段分解模型
2.1 算法总体思想
在过去的几十年里，经典资源受限项目调度问题(resource-constrained project scheduling problems，RCPSP)已经得到广泛的研究，众多学者针对RCPSP提出了很多高性能的算法［11-13］，这些算法值得在设计PSPMSWC
求解多技能人力资源约束的项目调度问题的两阶段算法
