支付进度安排问题的求解

支付进度安排问题的求解方法主要可以分为三类：精确求解方法（exact solution method）、启发式方法（heuristic method）和后启发式方法（meta-heuristic method）。精确求解方法是指通过数学规划或图论的方法求出问题的精确最优解；启发式方法是指基于经验规则（rules of thumb）求出近似最优解或最优解；后启发式方法是指采用全局搜索的方法求出近似最优解或最优解。支付进度安排问题大多数属于NP-hard问题，尤其是资源限制下的、多模式的问题，更是难以求得精确解，所以目前文献中关于这个问题的精确求解方法的关注很少，这类方法的适用范围也比较狭小；大多数文献关注的是启发式方法和后启发式方法的研究。

一、精确求解方法

Kazaz和Sepil^［82］引入了“工序收益曲线（activity profit curves）”的概念，这是目前关于支付问题精确求解方法的理论基础。工序收益曲线反映的是工序现金流的净现值和工序结束之间的关系，它是关于工序结束时间和折现率的非线性函数。但是当折现率较小时，这个函数可以用一个分段线性函数来近似。项目净现值实际上是各个工序收益曲线上点的叠加，由此他建立了一个混合整数规划模型，并用Lindo软件进行了求解。其后，Vanhoucke等^［83］以“工序收益曲线”为基础，提出了一个分支定界程序，并引入了两个规则减少搜索树的节点数。这个算法在随机产生的3600个测试实例集上得到了测试。上述两个方法所处理的模型均为资源不受限单模式问题。

Dayanand和Padman^［59］从承包商角度建立的5个数学模型都属于非线性整数规划或混合整数线性规划，其中后者得到了最优进度计划。但是他们提出的这些模型都没有考虑资源的约束，且工序实施按单模式考虑。Dayanand和Padman在文章的最后也指出，这5个模型都不适用于求解真实世界项目的最优支付进度，因为实际项目的持续时间长、网络计划的规模大。Vanhoucke等^［86］研究了带固定工期限制和可更新资源约束的问题，他们引入了深度优先分支定界算法（depth-first branch-and-bound algorithm），该方法使用一种快速回归搜索算法计算Max-NPV问题的上界，并利用一种额外逻辑关系约束求解资源冲突。这种快速递归算法借助了这样的概念：在满足逻辑关系约束的情况下，带正现金流的工序尽早安排，带负现金流的工序尽晚安排。他们将这个方法对两个测试问题集进行了验证。

此外，分支定界法还被应用于从业主角度研究支付进度问题^［97,99］，他们都考虑了资源不受约束的情况，对小规模项目进行了求解。一般而言，数学规划方法虽然可以求出最优解，但它存在这样两个问题：一是这类方法往往将项目的网络模型转化为数学模型，这对于具有大量工序和资源的问题而言是一件繁琐的事情；二是对于复杂的非线性优化问题，这类方法往往不能适用。

二、启发式方法

启发式方法在支付进度安排问题中的应用主要是从承包商角度的研究，包括Smith-Daniels和Aquilano^［88］、Icmeli和Erenguc^［85］和马蒙蒙等^［89］。Smith-Daniels和Aquilano将最迟开始关键路径进度与最早开始关键路径进度的工期与NPV进行了比较。他们假设现金流出发生在工序开始时，唯一的项目支付在项目完成时收到，他们提出了一个建立最迟开始进度的启发式规则，并在550个测试问题中进行了测试。作者发现最迟开始进度比最早开始进度得到更高的平均NPV和更小的平均工期。

Icmeli和Erenguc提出的启发式程序中嵌入了3种优先权规则，包括折现现金流权重（DCFW）、进度安排的机会成本、立即释放（IOCS）和净边际利润（NMG）。其中前两个规则已经在Max-NPV问题中证实是有效的，第三个规则是作者新提出的。对380个测试问题的计算显示，通过适度的计算时间，所有3个规则都提供了质量“好的”解，但没有一个优先规则对所有测试问题产生一致的较好解。

马蒙蒙等提出了一种Min｛L&F｝启发式算法，用于求解一次性付款模式下以NPV最大化为目标的进度安排。Min｛L&F｝算法的基本思想是，将可行工序在某决策时刻的最迟可能开始时间与在该时刻把此工序加入正在进行工序集合所形成的完工时间进行比较，选择两者中较小的值作为该工序的Min｛L&F｝值，首先规划可行工序集中Min｛L&F｝值最小的工序。他们对一个包含19个工序的算例进行了计算。

启发式方法的主要优点是不需要将项目网络模型转化为数学模型，省去了数学建模的繁琐过程，而且它适用于具有非线性目标函数和约束的复杂模型的求解，所以对于大规模的项目而言，启发式方法求解问题是一个不错的选择。但由于这个方法是建立在经验规则的基础上，所以尽管它可以得到好的解，但并不能保证一定是最优解；此外大多数规则只是着眼于局部的信息，缺乏全局性的思考，因而这个方法容易陷入局部最优。

三、后启发式方法

后启发式方法主要着眼于解决启发式方法易陷入局部最优的缺陷而设计的，其主要思路是利用一些具有全局搜索功能的方法进行求解。这些方法包括：模拟退火算法（simulated annealing algorithm, SA）、遗传算法（genetic algorithm, GA）、禁忌表搜索算法（tabu search algorithm, TS）、蚁群算法（ant colony optimization algorithm, ACO）、微粒群算法（particle swarm optimization algorithm, PSO）等。

Dayanand和Padman^［74］提出了一个两阶段搜索启发式方法求解项目支付进度问题。在求解的第一阶段，他应用了模拟退火算法进行进度的安排，通过一个30个测试问题的计算实验验证了算法的有效性。结果表明模拟退火是一个有效的启发式方法，即使算法不进行第二阶段的工作，所得到的解的质量也是相当好的。但他所研究的问题是单模式和资源不受限的。

Ulusoy等^［80,81］运用遗传算法对多模式、资源受限下的支付进度安排问题进行了求解，在两篇文章中分别考虑了不同的支付模式，其不足之处在于他们仅利用这个算法研究了不同支付模式对问题求解的影响，但缺乏与其他算法的对比分析。Mika等^［84］应用模拟退火算法和禁忌表搜索两种后启发式算法对带正现金流、多模式、资源受限的支付进度安排问题进行求解，并在一个用ProGen项目产生器建立的测试问题集上进行了测试。测试的结果表明，在固定工序数的条件下，禁忌表搜索算法在折现率较大的问题上的表现优于模拟退火算法；在支付次数较少时模拟退火算法的表现要优于禁忌表搜索算法。

浙江大学管理学院的Shou^［90］于2006年在第五届机器学习与控制论国际会议上发表的文章中提出采用蚁群算法求解一次性支付模式下的支付进度安排问题，他将蚁群算法和串行进度产生方案（SSGS）相结合，蚁群算法的作用是为SSGS的每一步产生工序进度安排的顺序。他考虑的问题是从承包商角度进行的，并没有涉及双方联合角度。西安交通大学管理学院的何正文等^{［75-79,101,102］}采用了一种双模块模拟退火启发式算法来求解承包商角度、业主角度或双方联合角度的支付进度安排。这种算法分为支付事件集合搜索模块和事件进度搜索模块，前者负责在给定事件进度下搜索满意支付事件集合，后者负责在给定事件集合下搜索满意事件进度。通过两个模块间的迭代循环，获得项目的满意支付进度安排。

从业主和承包商双方联合角度研究支付进度问题的另外两篇文献都采用了后启发式策略。Ulusoy和Cebelli^［98］设计了一个双重循环的遗传算法，其中外环表示业主，内环表示承包商。内环对应的问题是多模式的RCPSP，其目标是在给定支付分布下最大化承包商的NPV。当搜索“公平解”时，有关事件节点上支付分布及其发生时间的信息流在外环和内环之间传递。他们求解和分析了一个实例问题，并对由93个问题组成的测试集进行了计算。Kavlak^［100］提出通过使用非劣解集合的解搜索方法，并提出了模拟退火算法和遗传算法作为求解程序，还对模拟退火定义了两种不同的应用方法。这四种方法的计算结果相比，遗传算法得到的结果最佳。此外，作者对模型中的不同参数包括利润率、折现率和议价权重进行了敏感性分析。