马 咏，何正文，郑维博

(1.西安交通大学管理学院，陕西 西安 710049；2.过程控制与效率工程教育部重点实验室(西安交通大学)，陕西 西安 710049)

1 引言

现有的项目调度问题研究很多是在确定型环境下进行的。然而现实中，大多数项目的执行会受到不同程度不确定因素的干扰[1]，若是在制定进度计划的过程中不将这一特点进行考虑，那么在项目的执行过程中进度计划可能会因为受到不确定因素的影响而需不断的调整，使其失去有效性进而导致项目不能顺利实施[2]。而如果资源具备柔性，即资源具备活动实施所需的多种技能，则可以增加制定进度计划时的灵活性，进而获得一个鲁棒性更大的进度计划。因此，如何利用柔性资源制定能在不确定环境中稳定执行的进度计划就显得十分重要。

项目进度计划的鲁棒性是指在内外部环境因素干扰的情况下，进度计划能不受影响与保持其稳定执行的能力。对于处在不确定环境中的项目而言，鲁棒性较高的进度计划可以帮助其抵御内外部不确定因素带来的扰动，确保项目目标的稳定实现。为了得到应对活动工期扰动而不需要重大调整的稳定基准计划，Herroelen和Leus[3]开发了几种启发式算法并对算法进行了评价。Van de vonder等[4]研究了解鲁棒性和质量鲁棒性之间的权衡关系，并对时间缓冲在项目中的使用方式进行了分析。Al-Fawzan和Haouari[5]考虑了在制定进度计划时同时兼顾鲁棒性和工期的问题。Lambrechts等[6]为生成能抵御由资源可用量变化带来的扰动的稳定基准计划，设计了一种禁忌搜索算法。Hazr等[7]研究了鲁棒离散时间成本均衡问题，并提出了几种度量进度计划鲁棒性的方式。寿涌毅和王伟[8]将RCPSP(Resource Constrained Project Scheduling Problem)向不确定方向进行了拓展，构建了问题的鲁棒优化模型，并针对模型设计了遗传算法。何正文等[9]对活动工期具有随机性、以鲁棒性为目标的资源约束项目调度问题进行了研究，在受到项目工期和可更新资源限制的情况下对活动开始时间进行安排，以得到具有最大鲁棒性的进度计划。崔南方等[10]对不确定环境下的Max-npv项目鲁棒性调度问题进行了研究。王建军等[11]为解决并行机环境下工件加工时间可控情况中机器随机发生故障而使初始调度方案性能下降的问题，以最小化机器故障造成的期望成本为目标，提出了内外两层嵌套式鲁棒调度策略。陶莎等[12]等研究了带有不确定项目收益交互和资源交互作用的项目组合选择问题，并构建了鲁棒性可调节的鲁棒优化模型。Chakrabortty等[13]根据不确定性的特征提出了6种启发式方法将不确定活动工期转化为鲁棒优化模型中确定性的约束，并对问题进行求解。Bruni等[14]针对活动工期不确定情况下的资源约束项目调度问题构建了可调整的鲁棒优化模型，并用一种分解方法求解问题。崔南方和梁洋洋[15]为构建具有较大鲁棒性的项目进度计划，将鲁棒性资源分配和时间缓冲插入两种策略进行结合，设计了一种两阶段集成优化算法。

在经典的RCPSP中，一种资源被认定为只能具备一种能力，即提供一种技能。然而在现实中很多情形下，一种可使用的资源往往能够表现出多种能力，尤其是涉及到人力资源或工业机器人的情况。工业机器人是综合机械、电子、控制、计算机、传感器、人工智能等多种学科的先进技术于一体的复杂智能机器[16]。工业机器人能够借助编程操作来处理各种零件、材料和工具，以执行各种任务，具有可编程的输出能力。多技能的人员也可根据所具备的能力用于执行不同的任务。资源柔性的增加产生了多技能资源约束项目调度问题MSRCPSP(Multi-Skill Resource Constrained Project Scheduling Problem)，目前国内外已有学者对其进行了研究。Li和Womer[17]考虑了多技能人力资源约束项目调度问题，研究在满足工期约束的情况下最小化人力资源使用所带来的成本。黄敏镁和罗荣桂[18]针对柔性资源约束下的产品开发项目调度问题进行了分析，提出改进的遗传算法并运用最大流理论求解出每项任务的柔性资源分配方案。王一帆等[19]提出了一种两阶段优化算法用于解决多技能人力资源约束的项目调度问题。Correia和Saldanha-da-Gama[20]研究了在MSRCPSP中资源固定成本和可变成本带来的影响。Almeida等[21]提出一种基于并行调度机制的启发式算法，通过给资源赋予权重和对活动进行分组两个策略将启发式算法运用于MSRCPSP的求解。李明和徐哲[22]考虑了项目多技能人力资源调度与指派问题，针对该问题提出了一种优化方法并通过算例实验验证了方法的有效性。任逸飞和陆志强[23]以最小化资源投入成本为目标，研究了大型工业品移动装配过程中的多技能人力资源投入项目调度问题。陈蓉等[24]对存在人员随机离职环境下的新产品研发项目组合多技能人员调度问题进行了分析和研究。Myszkowski等[25]设计了一种混合微分进化贪婪算法来求解MSRCPSP。Wang Ling和Zheng Xiaolong[26]对同时考虑工期和成本最小化的MSRCPSP进行了研究，并提出了一种知识导向的多目标果蝇优化算法。

资源柔性的考虑使得RCPSP变得更加复杂和符合实际。与此同时，柔性资源可以实现资源间的相互替代，并且允许项目在制定进度计划时有更多的选择，以此应对由活动工期变化带来的不确定性，提高项目的抗干扰能力与执行效率。基于以上项目调度理论和研究现状，以及考虑不确定因素带来的扰动终将反映在活动工期的变化上，本文研究具有随机活动工期的柔性资源约束下的前摄性项目调度优化问题，即在柔性资源及项目计划工期的约束下，通过对项目各活动的开始时间进行安排以得到具有最大鲁棒性的进度计划。

2 问题界定

在本文中使用AoN(Activity-on-Node)网络对项目进行表示。若该项目有N个实活动，则在网络的表述中需添加两个虚活动：活动0和活动N+1，分别表示项目的开始和结束。在不确定环境中，非虚活动n(n=1,2,…,N)的工期是一个随机变量，用μ(dn)和σ(dn)来表示其均值与标准差。虚活动0和N+1工期都为0。因为各活动工期是不确定的，所以项目实际工期是一个随机变量。项目计划工期D在项目实施的过程中可能会被突破，但在制定项目进度计划的时候必须将工期约束加以考虑及遵守。

在根据已知活动工期均值μ(dn)所制定的进度计划中，第n个活动的开始时间为sn。然而在进度计划的执行过程中，各活动的实际工期可能会偏离均值，从而导致各活动不能按照所制定的进度计划中的开始时间实施，破坏了进度计划的稳定性。对于这种情况，可采取给活动留出适当时间缓冲的措施来减轻或吸收由于活动工期变化带来的扰动，阻止扰动在整个进度计划上的传播。因此，本文在活动n(n=1,2,…,N)的计划完成时间后设置一定时间缓冲Bn，借此提高进度计划抵抗工期扰动的能力。在已知sn的前提下，Bn可按照下式计算:

Bn=minm∈Un{sm}-[sn+μ(dn)]n=1,2,…,N

其中，Un为活动n的所有紧后活动的集合。在为每个活动设置Bn的时间缓冲后，只要活动的实际工期超过该活动均值工期的幅度不大于Bn，那么活动n工期发生的变化就不会对后续进度计划的执行产生影响，其紧后活动m也可以按照进度计划中的开始时间sm实施。

基于上述的讨论，可以知道项目进度计划的鲁棒性取决于给各活动制定的开始时间，而活动开始时间又受制于各种资源在项目开始前技能的选择。因此，本文所研究的问题有两组决策变量：

n=0,1,…,N+1;t=0,1,…,D

k=1,2,…,K;l=1,2,…,L

为了后文表达需要，进一步定义如下两个决策向量：

Y=(t:ynt=1,n=0,1,…,N+1)

注意，在这里需要指出的是由于资源的使用是不可分割的，当第k种资源选择使用第l种技能时，该资源全体都只能用于提供第l种技能。至此，本文研究的问题可以界定为：在满足柔性资源可用量Rk以及项目计划工期D约束的条件下，利用已知的资源技能选择与活动工期参数(包括均值μ(dn)和标准差σ(dn))来确定各活动的开始时间sn，最终实现项目进度计划鲁棒值Robu的最大化目标。

3 模型构建

在对研究问题完成界定及说明的基础上，构建所研究问题的优化模型，具体表述如下：

MaxRobu

(1)

(2)

m∈Unt=0,1,…,D

(3)

(4)

(5)

l=1,2,…,LT=0,1,…,D-1

(6)

n=0,1,…,N+1;t=0,1,…,D

k=1,2,…,K;l=1,2,…,L

(7)

其中，ST为在T时刻正在进行的活动集合，En与Ln分别表示活动n最早开始时间与最晚开始时间。

在上述的优化模型中，式(1)为目标函数式，要求最大化进度计划的鲁棒值Robu；式(2)指在活动开始时间窗内为其确定一个开始时间；式(3)为活动之间的优先关系约束，用于保证紧后活动m的开始时间sm不能早于其紧前活动n的计划完成时间；式(4)为计划工期约束，即虚结束活动N+1的计划开始时间不能超过项目计划工期D；式(5)保证对于每种资源，只选择一种技能进行使用；式(6)为可更新资源技能约束，保证在项目实施过程中的任意一个时刻T，所有正在进行的活动对第l种技能的需求总量不超过资源对该技能的总供给量；式(7)为变量的定义域约束。上述模型中，柔性资源可以通过变换技能的选择来使技能的供应和项目的需求更好的进行匹配，使得资源能得到更好的利用，并提高制定进度计划时活动开始时间调整的自由度。在满足资源和工期约束的情况下，通过对各活动开始时间的不断调整，各活动会被分配到与其权重系数匹配的时间缓冲，进而得到拥有最大鲁棒性的进度计划。

4 算法设计

RCPSP已被证明为NP-hard问题[27]。本文所研究的问题为具有随机活动工期的柔性资源约束下的前摄性项目调度问题，是RCPSP向不确定方向的一种扩展。因此，本文所研究的问题也必然为一个NP-hard问题。对于NP-hard问题，因其复杂性较高和求解的难度大，在项目调度问题的研究中一般采用启发式算法进行求解，包括禁忌搜索算法[5-6,9]和遗传算法[8,11,18,23-24,28-29]等。本文选择使用禁忌搜索算法对问题进行求解，具体设计如下。

4.1 算法设计思路

鉴于研究问题的特性，算法总体分为内外两层嵌套搜索。外层搜索是对资源技能分配方案的满意解搜索，内层搜索是在给定的资源技能分配方案前提下对于项目进度计划满意解的搜索。对于每种资源技能分配方案，运用禁忌搜索算法求得相应的进度计划满意解，然后继续进行资源技能分配方案的禁忌搜索迭代，两者交互进行，直到达到算法的终止条件，最终目的是为了寻找到使目标函数值最优的资源技能分配方案与项目进度计划的满意组合。

内外两层搜索的具体执行步骤如图1和图2所示，其中AL为活动优先次序列表，SL为工期增量列表。

图2 内层搜索流程图

4.2 内层搜索算法设计

在给定资源技能分配方案的情况下，所研究的问题转化成资源约束项目调度问题。设计禁忌搜索启发式算法对其进行求解。

4.2.1 解的表示及初始可行解构造

解的表示:内层搜索是对活动开始时间安排满意解的搜索。活动开始时间安排若直接使用活动开始时间进行解的表示，需要多次进行活动优先关系与资源技能关系的判断，增加了计算的复杂性。因此，在本研究中，用具有满足活动优先关系的活动次序列表AL与活动工期增量列表SL结合来表示解。

活动次序列表AL：该列表{p0,p1,…,pN+1}由N个实活动和两个虚活动的序号组成。在制定进度计划时，活动被安排的先后次序取决于该活动对应序号在列表中的位置。这里需要注意的是pi所对应的活动可能不是活动i，列表中的活动只需满足优先关系即可。

活动工期增量列表SL：该列表{w0,w1,…,wN+1}由N+2个值组成，每个值表示所对应活动添加的工期增量。与活动次序列表不同的是，在该列表中值wi对应活动i。

基于已知的AL和SL组合，生成进度计划的具体过程如下：首先，在SL定义的基础上，令μ(di)′=μ(di)+wi，将μ(di)′作为活动i新的工期；其次，按照AL中所定义的活动优先次序，基于μ(di)′利用串行进度生成机制SSGS(serial schedule generation scheme)可以将一个活动次序列表AL转换为一个可行的项目进度计划。

初始可行解构造:步骤1按照活动序号从小到大的顺序排列，得到一个满足活动间优先关系的活动次序列表ALinit。

步骤2为每个活动在指定区间内随机生成工期增量，并由这些工期增量构成工期增量列表SLinit。

步骤3基于活动次序列表ALinit与工期增量列表SLinit，在满足资源技能约束的前提下，利用串行进度生成机制SSGS生成一个活动开始时间安排。

步骤4检查是否满足项目工期约束，如果满足约束条件，则将该活动开始时间安排作为初始解；否则，返回步骤2并继续生成可行活动开始时间安排的操作。

4.2.2 邻点生成机理

当前可行解ALcurr、SLcurr的邻点ALneig、SLneig可由如下算子得到：

活动交换算子：在活动优先关系的约束下，随机选择ALcurr上的两个活动并交换活动位置，得到一个新的活动次序列表ALneig。将SLcurr直接记为SLneig。然后基于SLneig和ALneig，利用SSGS生成新的活动开始时间安排。检查是否满足项目工期约束，如果满足约束条件，则将SLneig和ALneig作为一可行邻点；否则，重新开始生成可行邻点的操作。

工期增量算子：将ALcurr直接记为ALneig。在SLcurr中，随机选择一个活动的工期增量，将该值随机地变化一个单位，得到一个新的工期增量列表SLneig。然后基于ALneig和SLneig，利用SSGS生成新的活动开始时间安排。检查是否满足项目工期约束，如果满足约束条件，则将SLneig和ALneig作为一可行邻点；否则，重新开始生成可行邻点的操作。

4.2.3 禁忌对象

活动交换禁忌TLA：活动交换的禁忌表达式为(Apv,v)。其中，Apv表示pv所对应的活动，v表示活动Apv在交换前列表中的位置。例如，活动次序列表中位置2上的活动3和位置5上的活动4进行交换，则禁忌对象为(3,2)和(4,5)。

工期增量禁忌TLS：工期增量的禁忌表达式为(Ai,wi)。其中，Ai表示工期增量发生变化的活动i，wi表示该活动变化前的增量值。如活动3的工期增量为1，变化后为2，则在工期增量迭代中的禁忌对象为 (3,1)。

4.2.4 算法搜索过程

算法的具体搜索步骤如下：

步骤1构造初始可行解ALinit、SLinit并计算其鲁棒值Robuinit；设置算法停止条件：搜索Nummax个可行解;初始化TLA和TLS；初始化计数器Num=0；解的初始化：ALcurr=ALbest=ALinit，SLcurr=SLbest=SLinit，Robucurr=Robubest=Robuinit。

步骤2从两个算子中随机地选择一个，生成一个可行邻点ALneig、SLneig，计算其对应鲁棒值Robuneig。判断生成邻点的移动是否在TLA或TLS中，若在TLA或TLS中，转步骤4；否则，转步骤3。

步骤3 将邻点解作为新的当前解：ALcurr=ALneig，SLcurr=SLneig,Robucurr=Robuneig；令Num=Num+1，更新禁忌列表。若Robuneig>Robubest，进一步令ALbest=ALneig，SLbest=SLneig,Robubest=Robuneig,转步骤5。

步骤4 若Robuneig>Robubest，激活生成该邻点的禁忌状态，并对解进行更新：ALcurr=ALbest=ALneig，SLcurr=SLbest=SLneig，Robucurr=Robubest=Robuneig，令Num=Num+1，更新禁忌列表，转步骤5；否则，转步骤2。

步骤5判断Num≥Nummax是否成立，若成立转步骤6；否则，转步骤2。

步骤6输出当前最好解，即ALbest、SLbest和Robubest。

本文中，设计两个禁忌列表TLA和TLS，分别对应活动次序列表AL和工期增量列表SL。在搜索过程中，禁忌列表按照“先进先出”原则进行管理。禁忌列表的长度通过实验法确定。

4.3 外层搜索算法设计

4.3.1 解的表示及初始可行解构造

解的表示:资源技能分配方案由所有资源的技能决策向量组成：X=(Xk;k=1,2,…K)。

4.3.2 邻点生成机理

在本文的研究中，每种资源只能选择使用一种技能，为了满足所有的技能需求，可用资源种类数K必须不小于项目所需技能种类数L。根据K与L的大小关系，邻点生成方式分别如下：

K=L：随机选择两种资源，对这两种资源所选择的技能进行变化，得到新的资源技能分配方案，判断所得资源技能分配方案能否生成可行进度计划，如能生成可行进度计划则得到可行邻点Xneig；否则，重新开始生成可行邻点的操作。

K>L：随机选择一种资源，对其当前选择的技能进行变化，得到新的资源技能分配方案，判断所得资源技能分配方案能否生成可行进度计划，如能生成可行进度计划则得到可行邻点Xneig；否则，重新开始生成可行邻点的操作。

4.3.3 禁忌对象

资源技能变换禁忌表达式为(R,La,Lb)。其中，R表示变换技能的资源，La表示变换后的技能，Lb表示变换前的技能。根据邻点生成方式分为两种情形。

K=L：对于两种所选择的资源1和资源2，资源1选择的技能由技能1变为技能2，资源2选择的技能由技能2变为技能1，则禁忌对象为(1,2,1)和(2,1,2)。

K>L：当前技能分配方案中，资源1选择技能2，对其选择的技能进行变换，变换后选择技能3，则禁忌对象为(1,3,2)。

4.3.4 算法改进措施

改进措施1：当K=L时，对生成新的资源技能分配方案过程中变化技能的两种资源进行以下判断：①两种资源是否有相同的技能数且至少有两种相同技能。②两种资源变化前后的两种技能是否为双方都具备的技能。如果满足以上两个条件，生成新的进度计划，并判断是否满足约束条件；否则，重新选择两种资源生成资源技能分配方案并继续上述操作，直到得到可行计划为止。

改进措施2：当K>L时，对生成新的资源技能分配方案过程中选择的资源进行以下判断：①是否有其它资源与所选资源提供相同的技能。②该资源是否至少具备两种技能。如果满足以上两个条件，生成新的进度计划，并判断是否满足约束条件；否则，重新选择一种资源继续上述操作，直到得到可行计划为止。

4.3.5 算法搜索过程

算法的具体搜索步骤如下：

步骤1将初始可行解Xinit作为参数输入到内层搜索中，将所得到的满意解ALbest、SLbest和Robubest作为外层搜索的ALinit、SLinit和Robuinit；设置算法停止条件：搜索Nummax个可行解;初始化禁忌列表；初始化计数器Num=0；资源技能分配方案的初始化：Xcurr=X*=Xinit；外层搜索解的初始化：AL*=ALinit，SL*=SLinit，Robu*=Robuinit。

步骤2如果K=L(K>L),在生成一个可行邻点Xneig的过程中使用改进措施1(改进措施2)，将Xneig输入到内层搜索中得到对应的ALneig、SLneig和Robuneig。判断生成邻点Xneig的移动是否在禁忌列表中，若是转步骤4；否则，转步骤3。

步骤3将邻点解作为新的当前解：Xcurr=Xneig；令Num=Num+1，更新禁忌列表。若Robuneig>Robu*，进一步令AL*=ALneig，SL*=SLneig,Robu*=Robuneig,转步骤5。

步骤4若Robuneig>Robu*，激活生成该邻点的禁忌状态，并对解进行更新：Xcurr=X*=Xneig，AL*=ALneig，SL*=SLneig，Robu*=Robuneig，令Num=Num+1，更新禁忌列表，转步骤5；否则，转步骤2。

步骤5判断Num≥Nummax是否成立，若成立转步骤6；否则，转步骤2。

步骤6输出当前最好解，即X*、AL*、SL*和Robu*。

5 实际案例

5.1 项目背景与数据提炼

ZSY西南二期软件开发项目是SST公司为ZSY西南销售分公司开发的管理信息系统。该软件开发项目旨在项目实施前，在分析项目活动开始时间延迟所产生损失的基础上制定出鲁棒性高的项目进度计划，以保证项目在内外部条件发生变化时所受的扰动最小。项目从2008年6月1日开始，计划于2008年12月30日完工，项目工期为150天。

该项目在实施过程中需要用到三类人力资源：需求人员、开发人员与实施人员。现有的人力资源有需求人员、开发人员、实施人员以及市场人员，可用量分别为4、8、7和4。需求人员主要负责系统需求的调研和分析；开发人员主要负责系统架构设计、组件设计以及程序的编写和调试等；实施人员主要负责对用户实施系统进行教育以及咨询和技术服务等。在SST公司中，各类人员分别具有多种技能。需求人员和实施人员同属于软件业务部，能相互承担对方的工作。开发人员除了能完成自身工作外，还能胜任需求人员和实施人员的工作。市场人员在完成与客户建立联系和合同管理等本职工作后，还能协助需求人员或实施人员共同完成任务。

随着公司业务范围的拓宽，西安SST有限责任公司经常会有多个项目同时进行的情况发生。每多进行一个项目，就要在当前人力资源分配的基础上进行调整，这会使其他正在进行项目的人力资源可用量发生变动，人力资源不足会使活动的工期变长，进而导致进度计划频繁的调整，活动无法按时开始和完成，甚至项目实际完工时间会超过项目截止工期，给公司带来损失。多技能的人力资源使得不同种类资源间的相互替代成为可能，一种资源可在另一种资源短缺时派上用场。同时，具有多技能的人力资源能够在制定进度计划时提供更大的灵活性，可以提高资源的利用效率和实现进度计划鲁棒性最大化。

该项目共有33个活动组成，需3种技能。项目AoN网络图见图3，其中活动0和活动32分别为虚的开始和结束活动，其余为实活动。各活动的相关参数见表1，其中各活动的标准差是根据历史数据和实际情况估算得到的。

图3 ZSY西南二期软件开发项目网络图

表1 算例活动的相关参数

5.2 计算结果

5.2.1 不考虑资源柔性时的技能分配方案

在资源无柔性的情况下，四种人力资源都只具备一种技能，参与项目的有需求人员、开发人员和实施人员，市场人员不会参与到项目中。参与项目的三种人力资源的技能向量分别为(1,0,0)、(0,1,0)和(0,0,1)。利用本文提出的禁忌搜索算法，可求得该项目的满意进度计划如下：Y=(0,0,5,6,8,41,9,14,22,38,41,43,48,53,70,53,53,110,114,77,96,101,118,91,96,103,133,70,101,121,143,146,150);Robu=3.76;X=((1,0,0),(0,1,0),(0,0,1))。

由所求得的满意解可知，项目实际完工时间为149天，进度计划的鲁棒值为3.76，技能分配方案为((1,0,0),(0,1,0),(0,0,1))，即由需求人员提供第一种技能L1，开发人员提供第二种技能L2，实施人员提供第三种技能L3。

5.2.2 考虑资源柔性时的技能分配方案

根据上文对人力资源的描述，一种人力资源可能具备多种技能，具体技能分布情况如表2所示。

表2 资源技能分布情况

由表2可知，只有开发人员具备技能L2，而技能L1和技能L3所有人力资源都具备。为了研究各种人力资源技能拥有情况对进度计划鲁棒性的影响，可在表2的基础上对资源技能分布进行进一步的细分。因为技能L2为开发人员独有，只能由开发人员提供技能L2，所以在进一步分析时默认开发人员只具备技能L2。具体细分情况如下：

1)需求人员具备技能L1和L3，实施人员具备技能L3，市场人员具备技能L1。

2)需求人员具备技能L1和L3，实施人员具备技能L3，市场人员具备技能L3。

3)需求人员具备技能L1和L3，实施人员具备技能L3，市场人员具备技能L1和L3。

4)需求人员具备技能L1，实施人员具备技能L1和L3，市场人员具备技能L1。

5)需求人员具备技能L1，实施人员具备技能L1和L3，市场人员具备技能L3。

6)需求人员具备技能L1，实施人员具备技能L1和L3，市场人员具备技能L1和L3。

7)需求人员和实施人员具备技能L1和L3，市场人员不具备上述技能。

8)需求人员和实施人员具备技能L1和L3，市场人员具备技能L1。

9)需求人员和实施人员具备技能L1和L3，市场人员具备技能L3。

10)需求人员、实施人员和市场人员都具备技能L1和L3。

上述10种组合情况对应的资源技能向量及求得的满意解如表3所示。

表3 各组合技能向量及满意解

根据上表中各种组合的鲁棒值可知，相比资源无柔性情况下的进度计划而言，资源具有柔性后安排得到的进度计划鲁棒值有了大幅提高，最大值为7.42，进度计划如下：Y=(0,0,5,7,9,10,10,15,24,37,40,47,52,54,69,54,54,127,131,78,87,98,116,85,90,96,112,69,96,116,137,140,150);Robu=7.42;X=((1,0,0),(0,1,0),(0,0,1),(1,0,0))。

其中，组合1和组合2、组合4和组合5、组合8和组合9这三组组合的对比都表明市场人员具备技能L1较技能L3而言能给进度计划鲁棒性带来更大的提升；组合3、组合6和组合10中市场人员同时具备技能L1和技能L3，而所得满意解的资源技能分配方案中市场人员都用于提供技能L1，进一步表明市场人员用于提供技能L1是更好的选择；组合7是无市场人员参与的情况，同组合8、组合9和组合10对比可知，市场人员的参与能得到一个鲁棒性更大的进度计划。产生以上结果的原因是：市场人员的参与增加了技能的可用量，提高了活动开始时间调整的灵活性，总缓冲时间增加的同时能将缓冲时间更合理地进行分配，进而提高进度计划鲁棒性，而在项目中技能L1的可用量相对技能L3是匮乏的，因此市场人员用于提供技能L1会给进度计划鲁棒性带来更大的提升。从满意解的资源技能分配方案可知，最优的资源技能分配情况为：需求人员、开发人员和实施人员分别用于提供技能L1、技能L2和技能L3，市场人员用于提供技能L1。

通过对比以上两种情况下资源技能分配方案的结果可以知道，SST公司的市场人员具备技能L1使得ZSY西南二期软件开发项目实际完工时间由149天缩短为143天，进度计划的鲁棒值由3.76提高到7.42，增幅达97.34%。这表明在不确定环境中，资源柔性的增加能缩短项目工期进而帮助项目制定一个鲁棒性更高的进度计划，提高项目抵御不确定因素干扰的能力。

5.3 关键参数的敏感性分析

由本文所构建的优化模型可以知道，项目进度计划的鲁棒性受一些关键参数的影响，主要有项目工期D、资源可用量Rk和资源柔性。在假定其它因素不变的情况下，单一因素变化对项目进度计划鲁棒性的影响如图4所示(初始资源技能分配方案为((1,0,0), (0,1,0), (0,0,1), (0,0,1)))。需要指出的是资源可用量的增加为四种资源可用量在原有基础上同步增加，资源柔性的提高体现在四种资源具备的技能数同步增加。

图4 进度计划鲁棒性随关键参数变化曲线

各参数的变化情况具体解释如下:

随着项目工期的延长，进度计划的鲁棒性近似的呈线性增加。因为项目工期的延长会使项目网络中所有路径上的时间缓冲均同步增加，进度计划拥有的总缓冲变大，进而使得计划的鲁棒性提高。

随着资源可用量的增加，进度计划的鲁棒性虽在增加，但有减缓的趋势。因为资源可用量的增加允许活动开始时间能以更大的自由度进行调整，总时间缓冲增加的同时能将缓冲更合理地分配在活动上，进度计划鲁棒性提高。但当资源可用量增加到一定程度时，受项目网络的约束，活动开始时间调整的灵活性被限制，计划鲁棒性的上升速度减缓。

随着资源具备的技能数越多，资源的柔性就越大，进度计划鲁棒性也不断增加。因为资源具备柔性后有更多的技能选择，可以根据项目的网络结构和活动对技能的需求量来对应的提供技能，在提高技能利用率的同时缩短了项目工期，给项目留出了更多的缓冲时间在活动中进行分配，进而提高进度计划鲁棒性。

6 结语

本文研究了具有随机活动工期的柔性资源约束下的前摄性项目调度优化问题。在文中，首先对问题进行界定，将柔性资源定义为具备多种技能但在项目实施前只能选择一种技能且不可分割使用的可更新资源，采用给活动添加时间缓冲的方式提高进度计划鲁棒性并定义了度量进度计划鲁棒性的方式。研究目标是在满足柔性资源和项目计划工期约束的条件下，借助对活动开始时间合理地进行安排进而得到拥有最大鲁棒性的进度计划。随后，构建了研究问题的优化模型，并根据问题NP-hard属性和模型特点设计了问题求解的双层嵌套禁忌搜索启发式算法，通过内外两层搜索交互迭代求得满意解。最后通过一个实际案例对研究问题进行了说明，并分析了项目工期、资源可用量、资源柔性等关键参数分别对项目进度计划鲁棒性的影响。研究结果表明：相对于资源无柔性情况下的项目进度计划而言，资源具备柔性后安排得到的项目进度计划的鲁棒性更高，提高了项目的抗干扰能力，保证项目稳定执行；项目进度计划鲁棒性随着项目工期的延长、资源可用量的增加或资源柔性的提高而上升。本文的研究将柔性资源约束项目调度问题向鲁棒性方向进行了扩展，对在不确定环境中如何制定项目进度计划可给予决策支持。