带有GPRs的前摄性资源受限项目调度建模与优化

魏亚锋，张梦茹，苏志雄

(南昌工程学院 工商管理学院，江西 南昌 330099)

资源受限项目调度问题(RCPSP)作为一类NP-hard问题一直备受项目管理人员和学者的关注。RCPSP主要研究在资源以及工期约束的情况下，如何合理地安排各个工序间的优先关系以实现预期的目标。现有的关于RCPSP的研究大多是在确定性环境下进行的[1]，即假设项目中各工序的工期、所需资源等都是确定的。然而，在实际执行过程中，由于受到各种不确定因素的影响，大多数的项目在实施过程中都存在一定程度的不确定性。例如工序工期的延期或中断、资源可用量的减少或者设备的维修等，都会干扰项目的正常进行，进而造成工序间优先关系以及资源流的变化，导致基准进度计划的推迟或者中断。因此，应考虑不确定因素的资源受限项目调度问题[2]，即在满足项目工期和资源约束的前提下，如何合理安排工序间的优先关系。在项目面对干扰时，生成一个具有较高的鲁棒性的调度计划逐渐成为项目调度领域研究的热点。现有的关于RCPSP的研究大多是基于CPM网络计划，但是在CPM网络计划中，工序间优先关系的表示方式单一，不能很好地描述工序间复杂的关系网络。广义优先关系(GPRs)[3]很好的弥补了CPM网络的这一不足，因此本文选择以广义优先关系作为网络计划的工具，进一步扩展了工序间优先关系的表示方法。

经过多年的发展，对项目调度问题的研究已经取得了不少研究成果。Herroelen[4]等根据项目所处的阶段，在制定项目计划时将不确定环境下项目调度分为两种情况，即前摄性项目调度问题和反应性项目调度问题。根据对扰动的处理方法的不同，何正文[5]等将现有的研究分为前摄性调度方法、反应性调度方法以及关键链方法等。除了对项目调度中的问题的研究之外，王凌[6]等根据不确定资源受限项目调度中存在的大规模、强约束、多目标和不确定性等诸多复杂性，导致模型求解困难的问题，对资源受限项目调度的求解算法进行的深入研究，提出了多种求解算法。

前摄性资源受限项目调度问题是在项目开始之前，在事先考虑各种不确定因素的影响下，在进度计划中加入一定的缓冲，生成一个具有鲁棒性的基准进度计划，使得项目在面临干扰时具有一定的稳定性。针对前摄性项目调度方法如今已经有了广泛的研究和应用，Lambrechts[7]等针对资源可用量问题研究了随机资源中断问题的前摄性和反应性调度策略。李雪[8]等考虑了鲁棒成本的多模式双目标问题并设计了相应的前摄性求解模型和算法。马咏[9]等对具有随机活动工期和柔性资源约束的前摄性项目调度优化问题进行了研究和求解。苏志雄[10]等针对在带有广义优先关系(简称GPRs)的项目中尚缺乏对这两类时差的分析计算，从多视角研究GPRs下工序共用时差的量化及特性。

在模型求解方面，包含不确定性的RCPSP问题求解主要由精确解算法和启发式算法组成。基于数学模型求解精确解的算法主要以分支定界算法为主，即将解空间用树形结构划分为多个子空间，不断通过各个子空间的最大或最小值来缩小搜索范围；由于不确定RCPSP问题的解空间随着项目中工序数量的增加呈指数增长。为了应对大规模问题的求解，除了求解精确解的方法之外采用启发式规则快速获得问题的解的启发式算法在大规模问题上得到了广泛的应用，其主要包括禁忌搜索算法[11]、蝙蝠算法[12]等，但是启发式算法只是得到相对的最优解，而不能得到实际意义上的最优解。

当前，国内外对广义优先关系(GPRs)条件下网络计划的研究主要集中在项目调度领域。Neumann[13]等利用分支定界方法对资源受限项目调度问题进行求解。苏志雄[14]等针对GPRs条件下的时间费用权衡问题，提出了相应的求解方法并对广义优先关系下的隐性时间、隐性时差和伪时差进行了研究并给出了参数值的正确算法。Wei[15]等对广义优先关系条件下的离散化时间成本权衡的截止时间问题进行了研究并提出了一种求解大规模复杂问题的有效算法。

本文基于项目调度理论，在广义优先关系条件下，考虑工期和其他因素的不确定性导致项目在执行过程中偏离基准进度计划甚至导致项目中断的问题。为了使基准进度计划在满足项目工期约束的前提下具有较高的抵御不确定性干扰的能力，本文在资源和优先关系的约束下，构建了以鲁棒性最大化以及项目工期最小化为目标的多目标前摄性资源受限项目调度模型。

1 问题描述

由于各种不确定因素的存在，项目在执行之前，项目管理人员会在考虑各种干扰的情况下，基于工序工期均值E(di)生成一个基准进度计划。假设一个项目中共有n+2个工序，其中工序0和工序n+1为虚工序，即项目的开始节点和结束节点。项目实施总共需要K种可更新资源，其中第k(k=1，2，…，K)种资源的总供应量为Rk，其中工序i对第k种资源的需求量为qik。由于在项目实际执行过程中各种不确定干扰的存在，可能会导致项目中工序的工期在一定范围内波动。因此，项目中各工序的工期并不是一个固定值。一般来说，工序i工期用其期望值E(di)来表示，用其标准差δi表示工序i的工期的波动，各工序工期的期望和标准差均是基于该工序的历史数据求得的。其中工序0和工序n+1工期的均值以及标准差均为0。

在GPRs网络中，工序间优先关系的表述方式不仅仅局限于“开始—结束”关系类型，GPRs网络对工序间优先关系的类型进行了进一步的扩展，具体类型如表1所示。

表1 GPRs下工序间优先关系的类型

2 模型构建

由于项目中各资源的总的供应量为Rk，并且虚工序0和n+1分别为项目的开始节点和结束节点，不同于以往文献中虚工序对于资源需求为零的假定。为了保证项目在各个时期各种资源流动的总量不高于各资源的总供应量，本文假定项目中各资源均从开始节点流出并最终流入结束节点，即虚工序0和n+1对各种可更新资源的需求量为各资源的总供应量Rk，即

(1)

现假定一个项目的基准进度计划为P=(S，D)，其中S=(s0，…，sn+1)和D=(d0，…，dn+1)分别为各工序计划开始时间si和工期均值E(di)的集合，其中s0=d0=dn+1=0。然而项目在实际执行过程中，项目中各工序工期的实际值并不一定完全等于期望值。因此，为了使生成的调度计划具有一定的稳定性，项目管理人员通常会采用加入缓冲的机制来增加基准进度计划的稳定性。在进度计划中加入的缓冲机制主要包括资源缓冲[16]和时间缓冲[17]两种。由于本文主要考虑资源受限情况下，对项目的基准进度计划的影响，因此本文采用在工序中加入时间缓冲的方法来增加项目基准进度计划的稳定性。

在GPRs网络中，项目中各工序的优先关系有多种表示方式，因此，各工序拥有多个时间参数。在考虑项目总工期最小化的前提下，为了增加基准进度计划的稳定性，本文用工序的计划最迟开始时间(LSi)减去其计划开始时间(si)，即在不影响项目预定的总工期的前提下工序i的开始时间最多能推迟的时间表示工序的时间缓冲Δi，其中

Δi=LSi-si.

(2)

项目在实际执行过程中，由于工期的波动或者其他预料之外的因素，会造成工序的实际结束时间偏离基准进度计划中的结束时间，只要其偏离程度不大于时间缓冲，其后续工序就仍可以按照基准进度计划正常执行。

(3)

在RCPSP的一般模型中，模型的目标函数为最小化项目的总工期。本文在总工期最小化的目标的基础上，增加了鲁棒性最大化的目标函数，其中项目中各工序的鲁棒性指标为robui，用工序的权重因子与该工序的时间缓冲的大小的乘积来表示，即

robui=ξiΔi，

(4)

进而对各个工序的鲁棒性的值进行求和得到整个项目的总的鲁棒性为

(5)

在上述对问题描述的基础上，针对本文所提问题构建如下的前摄性资源受限项目调度模型：

(6)

Minsn+1，

(7)

s.t.

sn+1≤LSn+1，

(8)

si+di≤sj+B(1-zij)(1-aij)∀i，j∈A∪R，

(9)

LSi+di+B(zij-1)(aij-1)≤LSj∀i，j∈A∪R，

(10)

rijk≤B(zij+aij)∀i，j∈A∀k，

(11)

(12)

(13)

di≥0；rijk≥0；

(14)

zij∈{0，1}

(15)

目标函数(6)为基准进度计划的总工期最小化；目标函数(7)为基准进度计划的鲁棒性指标最大化，使基准进度计划具有较高稳定性。约束条件(8)为项目工期的限制，保证基准进度计划的工期不超过项目的完工期限，其中项目的工期等于虚工序n+1的最迟结束时间；约束条件(9)为工序间优先关系约束；约束条件(10)为各工序的最迟开始时间约束；约束条件(11)为项目中各工序间优先关系以及资源流之间联系的约束，如果工序i和工序j之间有资源流动则zij=1，若zij=0则工序i和工序j之间的不存在资源流动；约束条件(12)为资源总量约束，保证项目的资源流入量等于项目的资源流出量等于各资源的总的可用量；约束条件(13)为资源流约束，保证各工序上各种资源的总流出量等于总流入量；约束条件(14)～(15)为决策变量的定义域，保证各工序的工期、资源流为非负整数。

本文所提出的模型可以看作为资源受限项目调度问题(RCPSP)，由于资源受限项目调度问题的NP-hard性质[18]，因此，本文所提出的模型必然为NP-hard问题。针对NP-hard问题的求解可以选择采用获得精确解的算法或者求得近似解的算法。由于模型中的决策变量为整数和0～1变量，因此本文提出的前摄性资源受限调度模型为整数规划模型。前摄性调度模型主要用来生成基准进度计划，基准进度计划的优劣会对整个项目在实际执行过程中的稳定性产生直接影响。因此，在对前摄性资源受限项目调度模型进行求解时，为了得到模型的最优解，本文采用线性松弛和分支定界算法，在可接受的求解时间内求得基准进度计划的精确解，然后对其进行可行性修正。

3 算例生成及测试

本文采用分支定界算法对所建立的模型进行求解，但是相比于启发式算法，分支定界等精确算法一般只适用于小规模问题的求解。为了进一步验证所建立模型的求解规模以及求解效率，本文首先对前摄性调度模型进行了算例测试。分别对含有不同数目的工序的项目，在可更新资源数目为一种和多种的情况下进行仿真实验，验证其在可接受的时间内能够求解的算例规模的大小，并选取固定的参数对模型进行多次求解实验，验证前摄性模型在求解时间方面的稳定性。本文中提出的前摄性调度模型的代码均采用MATLAB进行编码，并在计算机上运行求解。

由于所选的测试案例均为随机生成案例，在随机生成过程中，需要对资源总量、各工序工期的标准差及期望值等的范围进行确定，在进行案例测试时，对部分参数设置如表2所示。

表2 案例参数

首先对前摄性调度模型的最大求解规模进行实验，即在资源类型分别为1、2和4种的情况下，逐步增加项目中所包含工序的数目，在可允许的时间范围内得出可求解包含的工序的最大数目。在资源类型分别为1、2和4种的情况下，设定求解时间为1 000 s，可求解的最大规模的项目分别为210、200、180。

在得到模型的最大求解规模之后，为了进一步分析前摄性调度模型的稳定性，本文分别选取了包含工序数目为30、60、90的算例进行测试，在资源类型分别为1、2和4种的情况下，对每种情况进行30次求解运算，得到用分支定界算法求解不同组合情况下所需的时间，然后求出求解时间的平均值。实验结果如表3所示。

表3 求解时间的平均值

从表3可以看出对于含有相同工序的项目，平均求解时间随可更新资源种类的增加逐渐增大，并且随着项目中包含工序数目的增加，平均求解时间增加量逐渐增大。对于具有相同种类可更新资源包含不同工序数目的项目，平均求解时间随工序数目的增加明显增大。实验结果符合预期。

为了更加清晰全面地了解仿真实验的结果，根据表1中“包含工序的数目”和“可更新资源种类”的不同组合，采用分支定界算法分别进行30次实验，得出结果并绘制出相应的散点图，如图1～3所示。图1(a)～(c)为包含30个工序，资源类型分别为1，2，4种资源的散点图，图2(a)～(c)为包含60个工序，资源类型分别为1、2、4种资源的散点图，图3(a)～(c)为包含90个工序，资源类型分别为1、2、4种资源的散点图。

图1 包含30个工序的散点图

图2 包含60个工序的散点图

图3 包含90个工序的散点图

从散点图可以看出，随着可更新资源的增加，包含不同工序数量的项目的求解时间都随之增大。同样，对于具有相同种类的可更新资源的项目，随着其包含的工序数目的增加求解时间也随之增加。但是，对于具有相同工序和相同类型可更新资源的项目，求解时间分布较为均衡，波动起伏较小，稳定性较高。对于只含有30个工序的项目，可更新资源的种类的增加对模型的求解时间的影响并不显著，但是对于包含90个工序的项目而言，随着可更新资源种类的增加，模型的求解时间增加较为明显。

4 结束语

本文通过对带有广义优先关系的资源受限项目调度进行分析，在不确定环境下以工期最小化和鲁棒性最大化为目标构建了双目标的前摄性资源受限项目调度模型，考虑到所建立模型的NP-hard性质和前摄性项目调度对进度计划稳定性要求的性质，选用求解精确解的分支定界算法对模型进行求解。为了验证所建立模型的有效性和稳定性，分别对模型在可接受时间内的最大求解规模以及针对不同规模的算例的求解的稳定性进行了测试。结果显示随着项目中所包含的工序的数目和可更新资源的种类的增加，模型求得精确解所需要的时间随之增加，但是针对具有相同的工序数目和可更新资源类型的项目，求得精确解所需的时间的波动较小，稳定性较高。此外，随着项目中所包含工序数目的增加，可更新资源种类的多少对模型求解精确解的时间影响逐渐增大，可更新资源种类的增加会导致大规模项目求解精确解所需的时间增加较为明显。

本文在建立模型时仅考虑了工期以及鲁棒性，并未考虑加入时间缓冲造成的项目成本的增加以及其他不确定因素的干扰，并且模型中模型的时间缓冲的表示方式可能会导致部分工序的时间缓冲有所重叠，造成鲁棒性指标偏高。因此，在后续的研究中可以更进一步研究如何合理地表示工序的时间缓冲的大小，使鲁棒性指标更加合理。