考虑人力资源排班的资源受限项目调度问题建模与优化

朱宏伟， 陆志强

(同济大学 机械与能源工程学院， 上海 201804)

资源受限项目调度(RCPSP)作为一类重要的调度模型，广泛存在于制造、建筑等领域，其最大的特点是考虑资源为可更新资源，即资源在任务结束后立即释放，同时项目进程中资源总量不发生改变.然而，在许多实际装配生产系统中，例如飞机移动装配中，人力资源以排班的形式进行装配生产活动，其可用量会在生产过程中会受到排班的影响，因此事先制定的调度计划与实际的生产进度存在很大差距.此时，调度的关键在于如何将人力资源进行合理的排班，以确定每个班次下的人力资源数量，并在排班决策下为任务安排合理的开始时间，以获得最小的装配时间.此问题称为考虑人力资源排班的资源受限项目调度问题(RCPSP-ET)，其本质上是资源受限项目调度与人力资源排班(ETP)的整合问题.由于RCPSP-ET问题与传统RCPSP问题的决策范围不同，现有的模型与算法无法直接应用，所以对RCPSP-ET问题的建模以及算法研究具有重要的实际与理论意义.

RCPSP作为车间调度问题的一般化，已经被证明是非确定性多项式困难问题[1]，RCPSP-ET作为其扩展问题，因此也是非确定性多项式困难问题.针对RCPSP，Brucker等[2-3]采用分支定界算法进行求解.虽然分支定界等精确算法能求得问题的精确解，但是其求解规模有限，因此许多文献关注于启发式和元启发式算法的研究，如遗传算法(GA)[4]，粒子群算法(PSO)[5-6]等.除此之外，Wang等[7-8]在求解RCPSP及其扩展问题时采用混合算法，通过将多种算法进行混合，或在原有算法框架上设计改进机制，来提升算法性能.

人力资源排班是为人员安排合适的工作时间窗以满足组织内部和外部需求的过程.Bergh等[9]根据问题决策的不同，认为研究可以分为5类：在满足一定条件下决策人员所分配的任务[10]；确定人员的工作班次[11]；决策人员之间的成组[12]；时间约束下确定人员的工作时间[13]以及其他一些决策.然而，Bergh等指出，当前研究人力资源排班的文献缺少人力资源排班与其他调度问题(如机器调度、生产调度)的结合.在特定的调度背景下，需将人力资源排班与其他调度问题统筹考虑，才能真正地反映系统的调度需求.

RCPSP-ET本质上是人力资源排班与RCPSP的整合问题，目前有极少文献对该问题进行研究.Drezet等[14]将软件开发过程抽象为资源受限项目调度问题，在给定人员排班的情况下考虑劳动法规等因素对任务安排的影响.由于RCPSP与生产调度又有一定的相似性，所以人力资源排班与生产调度结合的整合问题对于RCPSP-ET的研究具有参考意义.Artigues等[15]考虑工人排班与车间调度的整合问题，设计基于整数规划和约束规划的混合分支定界算法进行求解.Guyon等[16]在探究求解工人排班与生产排班整合问题的精确算法时，为了减小决策变量搜索空间，运用割生成求解该整合问题，将Benders分解以及CPLEX对比，验证了算法的效率.Ahmadi-Javid等[17]进一步提升整合问题的维度，提出结合加工车间调度、运输工具调度以及人力资源排班的整合问题.

综上所述，目前极少学者考虑将人力资源排班与RCPSP结合的整合问题，然而RCPSP作为一类重要的生产过程抽象，研究RCPSP-ET问题具有重要意义.除此之外，目前解决这些问题的算法主要是基于问题模型研究而设计的精确算法，缺少对混合算法等高效算法的研究.因此，本文考虑人力资源排班中存在的约束，以最小化完工时间为目标，建立了RCPSP-ET的整数规划模型.同时，本文设计了一种改进任务列表编码方式，并借鉴混合算法的思路，提出了一种基于分支定界搜索框架的遗传算法(BBGA)，并在此基础上提出支配规则，从而降低算法运算时间，提升算法的求解效率.

1 考虑人力资源排班的资源受限项目调度问题

1.1 问题描述

某一装配工位由N项任务组成，记任务集合为J={1,2,…,N}，j∈J为任务编号；第j项任务的紧前任务集合为Pj；i∈Pj为第j项任务的第i项紧前任务；任务j的执行时间为tj，任务一旦开始便无法中断.目标为最小化装配总工期T.

任务的执行需要满足其人力资源种类和数量的需求.所有任务共享人力资源，记人力资源集合、人力资源种类集合分别为E={1,2,…,B}，K={1,2,…,R}，e∈E为人力资源编号，k∈K为人力资源种类编号，Ek表示第k类人力资源集合，rjk表示执行任务j所需第k类人力资源的数量.人力资源无法抢占，即任务一旦开始，其执行过程不能更换执行的人力资源.

装配过程人力资源以n班制进行装配生产活动(如两班制，三班制分别对应n=2，n=3).记班次集合S={1,2,…,H}，s∈S为班次编号；对时间进行离散化处理，记离散时间集合为D={1,2,…,V}，d∈D为离散时间节点，Ds表示第s个班次所包含的离散时间集合.人力资源受到劳动法规的约束，在连续n个班次中最多能被安排1个班次.由于不允许人力资源抢占，而某一人力资源又无法安排相邻的班次，所以任务的执行期不允许跨班次.

1.2 数学模型

决策变量：

模型：

minT

(1)

s.t.

(2)

(3)

(9)

其中：式(1)表示调度以最小化装配工期为目标函数；式(2)表示为任意任务安排的执行时间必须等于其规定的执行时间；式(3)表示任意任务一旦开始则不能中断；式(4)为优先关系约束，表示任意任务只有在其所有的紧前任务执行结束后才能开始执行；式(5)表示任务的执行时间与装配总工期的关系；式(6)表示某类人力资源在某一时刻中的供应量必须满足该时刻所有任务对该类人力资源的需求量；式(7)为劳动力约束，表示任意人力资源在连续n个班次中最多能被安排1个班次；式(8)表示任务不允许跨班次执行；式(9)定义决策变量zjs与决策变量xjd之间的关系，其中M为无穷大的数.

2 算法设计

目前解决RCPSP及其扩展问题的算法大多数是基于任务列表编码的编码形式.所有任务在满足优先关系的前提下随机(或按规则)构成任务列表，每一条任务列表代表一个解空间，任务在任务列表中的顺序代表其执行顺序.在已知任务列表的情况下，一般采用串行调度进行解码，即在满足资源约束的情况下尽早安排任务开始时间.

然而，在求解RCPSP-ET问题时，由于串行调度未考虑任务开始时间对人力资源利用情况的影响，所以在任务列表编码方式对应的解空间下串行调度解码很难获得较优解.图1所示为一个仅考虑单种人力资源的示例，图中横坐标t为时间，纵坐标R为人力资源编号.根据图中的项目网络生成调度计划时，因为班次S1资源量充足，任务2、3和4通过串行调度均安排在d=0时刻开始执行，此时班次S1的资源使用量为5，班次S2的剩余资源量为1.由于不允许任务跨班次执行，同时班次S2的剩余资源量不足以执行任务5，所以任务5只能在之后的班次开始执行.容易发现，无论如何对换任务列表中任务2、3、4的顺序，班次S1的资源占用量始终为5，这几种情形下任务5都无法在班次S2中执行.

图1 任务列表与调度结果示例

针对上述任务列表编码不足的缺点，本文设计了一种改进任务列表编码方式，并在此基础上设计了BBGA.改进任务列表编码是在不改变原优先关系的基础上，通过添加析取弧的方式来描述部分待确定的优先关系，从而提升串行调度解码的邻域搜索能力.同时，针对遗传算法深度搜索能力弱的缺点，BBGA在遗传算法所得最优染色体的基础上，对其进行分段深度搜索，进一步提高算法的求解质量.

2.1 改进任务列表编码方式

改进任务列表编码方式借鉴车间调度中析取弧的思想，通过添加析取弧的方式，在原先无直接或间接优先关系的任务之间增加额外的优先关系，使得解码过程中部分并行执行的任务转换为先后执行，达到降低当前班次人力资源使用量和提升资源利用率的目的.改进任务列表将获得新的优先关系的任务组成一层，每一层对应染色体上的一个基因.编码过程要求：① 后一层中不得包含前一层任务的直接或间接紧前任务；② 同一层中的任务在添加析取弧之前不能存在优先关系；③ 同一层中析取弧方向由最左边的任务依次指向最右边的任务；④ 同一层中所有任务的工期和不能大于一个班次的工期之和.同一层中后序任务以前序任务的结束时间作为实际最早可开始时间.只有前一层中的所有任务都被执行完成后，后一层的任务才可以安排开始.

改进任务列表编码过程如图2所示.以图1中的项目网络为例，改进任务列表第1层和第2层分别选择任务1和4.进行第3层编码时，可选择任务为任务2和3.根据改进任务列表的性质，任务2和3工期之和为8，与班次时间跨度相等，因此第3层可选择编码为{2}、{3}、{2,3}和{3,2}.此时，随机选择{3,2}作为第3层编码.按照上述方法继续分层，得到的改进任务列表如图2(a)所示.根据染色体的编码，为项目网络添加3→2的析取弧.图2(b)给出了通过串行调度对改进任务列表进行解码所得的调度计划.相比图1中的调度计划，图2(b)中的调度计划能够通过延迟任务2的开始时间来降低班次S1中的人力资源使用量，使得班次S2有足够的资源来执行任务5.此时任务5的开始时间为8，项目工期T=15.

图2 改进任务列表与调度结果示例

2.2 BBGA

BBGA结合GA的广度搜索优势与分支定界算法的深度搜索优势，以改进任务列表编码方式作为GA染色体的表达方式，通过GA获得初始染色体.在此基础上，分支定界搜索框架将该染色体作为搜索树中的初始分支对该染色体进行分段局部回溯，并将每一阶段搜索得到的最优染色体作为下一阶段的初始染色体，通过这种邻域搜索机制进一步优化调度结果.

2.2.1遗传算法 标准GA分为5个步骤：① 初始化种群；② 交叉；③ 变异；④ 选择；⑤ 判断是否满足终止条件，不满足返回②，满足则终止算法.为保证进行交叉变异操作之后所得的改进任务列表仍满足编码要求，本文对传统的交叉变异算子进行改进，交叉操作与变异操作如图3所示.

交叉算子采用单点交叉，在染色体层与层之间随机生成交叉点位置.子代染色体保留父代交叉点前的编码顺序，剩余编码顺序根据母代剔除已选任务所保留的编码顺序决定.

变异算子采用对换变异，对换层允许进行变异操作的条件是两个对换层中间所有任务均不存在优先关系.

图3 交叉操作与变异操作

2.2.2启发式进度生成机制 根据改进任务列表编码方式的特点，本文设计新的启发式进度生成方法对相应的染色体(编码)进行解码.具体决策方法如下：按照层级从前往后选择任务，对于每层编码中的任务，按照顺序选择，第一个任务按尽早开始原则决策资源的选择，后序任务将前序任务的结束时间作为最早可开始时间进行安排.按此方法逐步确定每层中任务的开始时间，获得完整的调度计划.具体的算法步骤如下：

步骤1令染色体层级编号g=1.

步骤2读取第g层编码中的任务集合Ag.

步骤3按照顺序从小到大选择序号最小的任务jmin∈Ag，按尽早开始原则为任务jmin分配资源，计算开始时间，更新分配后的资源占有量，更新Ag=Ag-jmin.

步骤4如果Ag≠∅，转步骤5；否则，转步骤7.

步骤6如果Ag≠∅，转步骤5；否则，转步骤7.

步骤7如果调度计划未完成，g=g+1，转步骤2；否则结束算法.

2.2.3分支定界搜索框架 分支定界搜索框架将改进任务列表编码的层级关系转换为搜索树中的树节点关系，通过事先设定好的步长进行多阶段的局部分支(分支过程以深度优先)与回溯.其中，分支定界搜索框架以遗传算法所求得的最佳染色体作为第一阶段的初始解，之后保留每一阶段的最佳染色体作为下一阶段的初始解.

(1) 算法步骤.分支定界搜索框架的具体步骤如下所示：

步骤1初始化步长Q，分支起始层n=2，阶段s=1，初始染色体设为遗传算法中适应值最小的染色体.Lbest为该染色体任务列表，M为该染色体的适应值，W为染色体总层数，F为算法终止判断符号.

步骤2如果Q+n

步骤3令g=n-1.

步骤4确定节点g的候选任务组合集合Cg，从Cg中随机选择任务集合Ag生成新的节点g+1，更新Cg=Cg-Ag.通过支配规则判断能否截除，如果截除则转步骤6.

步骤5如果存在未分支的任务j∉Ag，则表明节点g可以继续分支，令g=g+1，转步骤4.否则，将得到的分支与步骤2所保留其余层的任务序列合并，组成新的染色体.调用启发式进度生成机制对该染色体进行解码.如果目标函数值优于M，则更新M并记录最优任务列表Lbest，转步骤6.

步骤6回溯搜索树，如果找到某节点g的Cg≠∅， 则转至步骤4；否则，结束分支，转步骤7.

步骤7若F为假，则更新s=s+1，n=Q+n，转至步骤2；否则满足终止条件，转步骤8.

步骤8若F为真，则满足终止条件，结束算法.

图4所示为分支定界搜索框架的示例，初始染色体编码为{1}、{4}、{3,2}、{5}、{6,7}、{8}，设定步长Q=2，分支起始层n=2.在阶段s=1时，回溯第2和第3层任务，回溯任务集合J1={2,3,4}，通过回溯分支得到阶段s=1的最优染色体为{1}、{4}、{2,3}、{5}、{6,7}、{8}.在阶段s=2时，将阶段s=1的最优染色体作为初始染色体，回溯第4和第5层任务，回溯任务集合J2={5,6,7}，通过回溯分支得到阶段s=2处的最优染色体为{1}、{4}、{2,3}、{5}、{6}、{7}、{8}.由于此时Q+n=6，满足终止条件，因此将分支定界算法得到的最优染色体输出.

图4 分支定界搜索框架示例

(2) 支配规则.为了提升分支定界算法的效率，本文提出2种支配规则，用于分支过程中剪除被支配的分支.为了方便支配规则的描述，事先给出以下定义：

定义1记节点q为当前节点，如果节点q由节点q′分支得到，则称节点q′为节点q的直接根节点.

根据定义1的描述，记直接根节点调度的任务集合为Aq′，当前节点调度的任务集合为Aq，所有任务i∈Aq′的工期之和为dq′，所有任务j∈Aq的工期之和为dq，班次跨度为ds.

定义2若当前节点q中的所有任务j∈Aq均可以合并入其直接根节点q′，且合并后的任务列表与合并前的任务列表解码所得的调度计划相同，则称节点q为重复节点.

图5 条件3示例

依据上述定义，给出2种支配规则的描述：

规则1(重复节点规则) 当前节点q与其直接根节点q′满足以下3个条件时，节点q为重复节点，不再对节点q进行分支.

条件1对于任意节点q与其直接根节点q′，如满足条件dq+dq′>ds，则当前节点为不重复情况.

证明如果满足dq+dq′>ds，则表明两节点中所有任务的工期和大于班次时间，当前节点中的任务无法全部合并入其直接根节点，因此当前节点不为重复情况.

条件2如果任务j∈Aq与任意任务i∈Aq′存在时序约束关系，则当前节点不为重复情况.

证明如果两节点中的任务间存在时序约束关系，则当前节点调度的任务无法全部合并入其根节点，因此当前节点不为重复情况.

规则2(高界规则) 如果当前节点的任务的完成时间超过目前所得最优解，则该节点不再分支.

记目前所得的项目最短工期为MUB.如果任务j∈Ag的完成时间Fj>MUB，则节点g不再分支.新的完整调度计划完成时，如果满足FJ

3 数据实验

本文算法运用C#(Visual Studio 2015)编程实现，测试实验在Internet Core i7处理器，3.4 GHz主频，8 GB内存的测试平台上进行.本文的测试算例选取自PSPLIB算例库，由于人力资源排班引入的资源不可行期会造成项目工期较长，所以需对算例进行改造.改造参数包括对班次n、资源系数F、班次长度S和分支定界步长Q进行设定，其中资源系数F指实际使用资源量与算例库原始资源量的比值，即F=R/R0.对于小规模算例规模(J10，J12，J14，J16，J18)，本文设定参数n、F、S和Q分别为3、1、8、4.对于中大规模算例(J30，J60，J90)，本文设定参数n、F、S和Q分别为3、2、11、5.

3.1 与CPLEX的对比

为了验证算法的有效性，本文将BBGA与CPLEX和GA进行对比，如表1所示.每个规模均取30个算例，每5个算例组成一组进行对照试验，设定CPLEX的运行阈值为 7 200 s.Gvalue表示计算结果；Gtime表示算法的运算时间；Ggap表示不同算法所得解与本组最优解间的差值.

表1 小规模算例数值实验结果

从表1看出，在小规模算例实验中，BBGA 在可接受时间内能够求得较优的结果.对于大多数J10和J12规模的算例，CPLEX可求得问题的最优解，而GA与CPLEX之间的Ggap值小于4.0%，BBGA 与CPLEX之间的Ggap值小于2.4%.并且随着算例规模以及复杂度的增加(J14～J18)，CPLEX在许多情况下无法求得最优解，而GA和BBGA仍可求得较优解.虽然BBGA计算时间有所提升，但是相比较GA，其求解质量能够提升2%左右，表现出一定的优势.

3.2 与现有文献的对比

由于CPLEX无法求解中大规模问题，同时关于人力资源调度与RCPSP结合问题的算法研究又十分有限，所以对于大规模算例，本文借鉴文献[18]中基于插入操作的领域搜索思想，设计了基于局部搜索(LS)的改进启发式算法作为对比来验证本文算法的有效性.其中启发式规则选取最早开始时间(EST)规则和最短执行时间(SPT)规则.表2给出不同算法对于大规模问题的实验结果对比，其中每组包括10个算例.

表2 中大规模算例数值实验结果

由表2可知，在求解大规模算例时，分支定界搜索框架对于遗传算法能够取得2%以上优化效果，同时，基于局部搜索的改进启发式算法与BBGA的偏差约为6%，证明了BBGA的优越性.但是，随着算例规模的增加，BBGA计算时间增长较快，并且每个算例的计算时间差异较大，其原因是回溯集合的数目随着算例规模的增加而增长，同时不同算例下回溯集合的任务数目差异较大.

3.3 支配规则效率分析

支配规则作为BBGA的重要组成部分，需要验证其对算法运算效率的影响.表3给出J12中Q=12时，本文算法分别同时使用规则1和规则2(Rule 1&2)、仅使用规则1(Rule 1)、仅使用规则2(Rule 2)和不使用支配规则(None)时的运行时间以及搜索树的分支数目.其中设定参数n、F、S和Q分别为3、1、8、4，每组实验包含3个算例，Gnum栏表示在某一规则下搜索树的分支数目.图6显示了不同支配规则下算法的运行时间相对不使用支配规则时算法计算时间所占的百分比.

由表3可知，规则1和规则2均能够通过有效减少搜索树分支数目来降低算法的运算时间，且当规则1和规则2同时使用时算法的运算时间最短.由图6可知，使用单一规则时，算法计算时间能够缩减到无分支规则时计算时间的60%以下(最低为14%)；当同时使用两种规则时，算法计算时间能够缩减到无分支规则时计算时间的30%以下(最低为6%)，验证了本文设计的支配规则能够有效地降低算法的计算时间，提高算法的计算效率.

表3 不同支配规则效率分析结果

图6 不同支配规则下计算时间相对无分支规则下计算时间的百分比

3.4 集成决策有效性分析

由表4可知，基于RCPSP-ET集成决策的GA以及BBGA较基于“人员-任务”顺序决策的GA-SD分别能够取得均值约为5%和7%的优化效果.同时，相比GA，GA-SD计算时间没有明显的缩短.因此，RCPSP-ET集成决策在决策方式上优于传统的“人员-任务”顺序决策，更加适用于实际装配生产中装配计划制定以及人力资源排班.

3.5 实例分析

为了更直观地阐明本文方法的有效性，本节以某大型工业品装配过程中某一部分任务为例进行分析.该部分共计16项装配任务，装配任务优先关系如图7所示.其中，企业根据任务之间的顺序关系为各任务安排编号，括号内的数字分别表示任务所需操作时间和任务执行时所需的装配人员数量，例如“H03A(2,4)”表示任务H03A的操作时间为2，所需装配人员数量为4.任务H00和任务H05分别表示虚拟开始任务和虚拟结束任务，其任务所需操作时间和装配人员需求量均为0.装配人员以两班制的形式执行装配任务，其总数为11人，每一班次的长度为8 h.假定开始阶段有4名装配人员处于休息状态.

根据上述装配任务优先关系图以及问题描述，采用本文BBGA和传统任务列表编码的遗传算法(GA-AL)生成不同的任务调度计划，结果分别如图8和9所示.图中阴影表示装配人员受劳动法规约束而产生的人员不可行期， 即装配人员处于休息状态.

表4 中大规模算例数值实验结果

图7 某大型工业品部分装配任务优先关系图

可以看出，该实例下BBGA所求得的装配任务总工期T=27，而GA-AL求得的装配任务总工期T=29.通过进一步分析，发现图8和9中于班次S1内执行的任务相同，其中图9中班次S1的人员使用量为7，而图8中班次S1的人员使用量为6.该情况的出现是因为GA-AL采用的传统任务列表编码方式仅考虑了原始的任务优先关系，所以采用串行调度解码时任务H01C只能在T=0时刻开始.而BBGA采用的改进任务列表编码能够在任务H01A和任务H01C之间添加析取弧，因此任务H01C能够延迟到H01A后开始.班次S1内人员使用量的降低使得班次S2中处于不可行期的人员减少，从而为班次S2保留了更多的人员可用量，使得任务H03C和任务H03B能够提前至班次S2中同时执行.该结果直观地验证了本文 BBGA 的有效性.

图8 BBGA求得的调度计划

图9 GA-AL求得的调度计划

4 结语

本文以考虑人力资源排班的资源受限项目调度问题为研究对象，建立离散时间下考虑劳动力约束的数学模型.针对问题的特点，提出了改进任务列表编码方式.为了提升算法的深度搜索能力，根据编码特点设计分支定界搜索框架，对遗传算法得到的染色体进行分段深度搜索.在支配规则中，通过分析判断重复节点剪除被支配的分支，避免计算不必要的分支，提高算法的计算时间.数据实验表明，对于小规模算例，本文算法与CPLEX最优解的差值保持在3.2%以下，部分算例相比遗传算法能提高2%优化效果；对于大规模算例，分支定界算法能够在遗传算法所得解的基础上取得2%以上优化效果；在计算时间方面，本文设计的支配规则能够将算法计算时间降低到未使用支配规则的30%以下；与此同时，相比较传统的“人员-任务”顺序决策，RCPSP-ET集成决策能够更加有效地优化决策过程，获得更好的人员排班计划和任务执行计划.未来可以在考虑人力资源排班的资源受限项目问题中进一步研究人力资源多技能对排班和项目工期的影响.