研究历史及演化

支付进度安排问题（payment scheduling problem）是指在一定的支付模式下，通过对项目工序的进度安排，确定支付的时间和数额，使项目的净现值最大。支付进度安排问题是项目进度安排问题（project scheduling problem）的一个重要分支，也是该问题的一个研究前沿，近年来得到了国内外研究学者的广泛关注。

作为项目管理的一项重要内容，项目进度安排问题历来是国内外研究人员关注的重点，近年来也有许多调查文献对这方面的文章进行了概括汇总^{［1,2,3,4,5］}。经过多年的发展，目前对项目进度安排问题的研究已经形成了一个庞大的研究体系，这些研究可以从资源是否受限、目标函数、工序的实施模式、逻辑关系和工序是否允许中断等方面进行分类。从项目的资源是否受到约束，可以将问题分为资源不受限的进度安排和资源受限的进度安排；项目进度安排的目标包括工期最小化、净现值最大化、质量最大化、成本最小化等；工序的实施模式包括单模式和多模式；按工序的逻辑关系则可以分为零时距结束—开始关系和一般关系；按工序是否允许中断则可以分为工序不允许中断（preemptive）和工序允许中断（non-preemptive）等。对上述因素进行不同的设定即产生了项目进度安排问题的不同研究分支。

早期的项目进度安排问题考虑的目标主要是工期最小化，在资源不受限的确定型项目网络中，将每个工序安排在满足逻辑关系的最早可能开始时间^［6］。当考虑了资源约束后，即称为资源受限项目进度安排问题（resource constrained project scheduling problems, RCPSP）。RCPSP问题已被证明是NP-hard问题（组合膨胀问题）^［7］，即求解这类问题的计算量随着问题规模的增加呈现指数级增长。以工期最小化为目标的RCPSP采用的求解方法包括精确求解法和启发式方法（heuristic），其中，精确求解法即最优化方法（optimization）包括动态规划^［8］、0—1规划^{［9,10,11］}和带分支定界的隐枚举法^［12,13］；启发式方法基本上包括四种不同的求解方法：基于优先权规则的进度安排^{［14,15,16］}，截尾分支定界（truncated branch-and bound）^［17］，分离弧概念（disjunctive arc concepts）^［18,19］和后启发式方法^{［20,21,22］}。以质量最大化（quality maximization）为目标的项目进度安排研究包括文献^［23,24］，而以成本最小化的研究将成本目标分解为工序成本和资源成本目标，对应的问题分别是时间—成本均衡问题^{［25,26,27］}和资源均衡问题^{［28,29,30］}。

以工期最小化为目标的项目进度安排忽略了项目财务方面的信息，这样的项目进度安排在实施过程中可能会因为资金供应的问题而导致失败，或者即使可以实施但在经济上不合算。Doersch和Patterson^［31］已经表明，包含进度款支付的项目按最小化工期制定的最优进度可能不会产生最高的净现值或公司财务回报的最大化。进度安排问题的财务方面内容是指在项目实施过程中的一系列现金流（正的和／或负的）。正现金流（即现金流入）对应于工序和项目实施的支付，负现金流（即现金流出）包括劳动力、设备、材料等的支出。通过现金流的折现考虑资金的时间价值。

当考虑项目的现金流与资金时间价值时，净现值（net present value, NPV）最大化将是一个较为合适的目标，由此形成的问题称为带折现现金流的项目进度安排问题（project scheduling problem with discounted cash flows, PSPDCF），也称为Max-NPV问题^［32］。自A. H. Russell^［33］开创性地将NPV准则引入项目进度安排问题以来，Max-NPV问题激起了研究人员的广泛兴趣，这类研究文献此起彼伏、层出不穷。鉴于项目支付进度安排问题是在Max-NPV问题的基础上逐渐演化发展而来，因此下面将对资源不受限与资源受限下Max-NPV问题的研究模型和求解方法等进行简要的回顾。

一、资源不受限的Max-NPV问题

A. H. Russell^［33］首先在网络中考虑现金流的净现值（NPV）最大化目标。他考虑了一个资源不受限的问题，假设项目用双代号网络表示，不管是正现金流还是负现金流都与事件相关联。他提出了一个连续复利折现的非线性规划模型，使用了一个泰勒序列近似为一个线性的目标函数。这个线性规划模型的对偶形式可以解释为一个网络流问题，由此导出了优化程序。A. H. Russell表明了当考虑资金目标时，成本—关键路径与时间—关键路径是截然不同的。

Grinold^［34］通过增加一个项目完工期限将A. H. Russell的研究进行了扩展，他将具有线性逻辑关系约束和指数目标函数的非线性规划转化为一个具有加权分布问题结构的等价的线性规划。这个特殊结构的求解方法是，通过搜索项目网络上的可行树集合来确定最优解，以此所有工序都具有零时差。和A. H. Russell的论文一样，除了一个小的计算实例外，Grinold也没有进行广泛的计算实验。

Elmaghraby和Herroelen^［35］使用Russell模型开发了一个简化的算法，为带NPV目标的项目进度安排问题提供了最优进度。他们显示，在通常情况下，在满足网络结构约束的条件下，将带正现金流的事件尽早安排和负现金流的事件尽晚安排是最优的。他们也阐明了净现金流取决于现金流节点的实现时间，以及在不存在项目完工期限的情况下，如果NPV小于零，项目将被不确定的拖延。Herroelen和Gallens^［36］给出了这个方法的计算实验结果，结果显示这个方法对资源不受限问题是有效的。

Demeulemeester等^［37］提出了一个新的最优算法，在部分树结构上执行回归搜索，它利用的概念是将带来支付的工序尽早安排，引起支出的工序推迟安排。对比Grinold方法，这个计算测试提供的结果令人鼓舞。Möhring等^［38］提出一个多项式算法，用于最小化与工序开始时间相关的数值之和。这个方法可用于解决NPV最大化的特例，其中由于折现的原因，对于最迟开始时间，当现金流出工序的数值单调递增时，现金流入工序的数值单调递减。Schwindt和Zimmermann^［39］为带最小和最大时差的净现值问题提出了一个最陡上升算法（steepest ascent algorithm）。

二、资源受限的Max-NPV问题

当考虑实际资源的约束时，Max-NPV问题的求解可以采用精确求解方法、启发式方法和后启发式方法。精确求解方法包括0—1整数规划^［40,41,］、动态规划^［42］、分支定界算法^［43,44］等。Doersch和Patterson^［40］采用0—1整数规划方法，考虑的模型中包括对项目中工序的支出所需资金的约束，项目的可用资金随进度款支付的发生而增加。目标函数包括与工序完成相关联的现金流，以及延误完成的任何罚金。模型为包括15—25个工序的项目求得了最优解。结果显示，当资金成本较高时或项目工期较长时，在安排工序时计算奖励／惩罚以及资金约束是非常重要的。

Smith-Daniels和Smith-Daniels^［41］扩展了Doersch和Patterson模型，引入了材料约束和成本。在满足材料和资金约束的情况下最大化NPV，并求得了小规模问题的最优解。他们得出结论，定购和控制成本不仅确实迫使具有一般需求的工序同时开始或在相近的时间开始，附加的约束也导致项目总成本的降低，即使他们可能导致工序乃至项目的延误。

Tavares^［42］提出一个新的动态规划方法和求解方法，对一个相互联系的项目集合使用变分微积分（calculus of variations）推导出最优条件。最大化的目标函数包括计划实施过程中产生的收益折现之和、项目支出成本的折现之和与超期罚金的净额。这个方法成功应用于葡萄牙的一个大型铁路建设项目。

Baroum和Patterson^［43］提出一个分支定界方法，直接用于求解带NPV目标的项目进度安排问题。Icmeli和Erenguc^［44］开发的分支定界算法使用了最小延误方案的概念，并对来自Patterson集的50个测试问题（工序数在7—51个之间）和使用ProGen产生的具有32个工序的40个问题进行了测试，至多有3种资源类型，结果显示对比文献中的结果，算法是有效的。Yang等^［45］则为NPV目标开发了一个整数规划方法，然而他们所提出的方法仅求解了工序数很少的问题。为了求解具有许多工序的较大规模问题，优化方法需要的计算时间过多，于是很多学者采用启发式方法进行研究。

与上述优化方法不同，启发式方法基于一定的优先权规则安排工序进度。它由两个要素组成：进度产生方案和优先权规则。当有一组工序，按照逻辑关系可以在当前时刻开始，但由于资源的约束只能安排部分工序时，就出现了工序安排进度的优先顺序问题。不同的优先顺序导致不同的进度产生。优先顺序的确定可以依据很多经验规则，如按照持续时间的长短、按照时差的多少，等等，由此产生了很多的启发式规则。最基本的进度产生方案则主要有两种：串行进度产生方案（serial schedule generation scheme, SSGS）和并行进度产生方案（parallel schedule generation scheme, PSGS）^［46］。最初的进度产生方案都是前向的，后来发展为后向和双向。所谓前向是指按照工序逻辑关系的先后顺序安排工序进度，工序被安排在尽可能早的位置上；后向是指按照工序逻辑关系的逆序安排工序进度，这种方式下工序被安排在尽可能迟的位置上；双向则是指分别从前后两个方向安排工序进度，前半部分工序按前向安排，后半部分工序按后向安排，最后通过将后半部分工序左移形成最终的进度^［47］。

Max-NPV问题的启发式程序通常根据资源不受限下Max-NPV模型的解开发单向启发式规则，或使用来自于关键路径和现金流的信息，如后续路径的现金流之和，来开发优先规则。相关的文献包括^{［48,49,50,51,52,53,54］}，常见的优先规则见表1.1。

表1.1　资源受限Max-NPV问题的常用优先权规则

第一个用于资源受限Max-NPV问题的启发式方法是R. A. Russell^［48］提出的，他激起了一股关于NPV目标的RCPSP的启发式方法的研究热潮。根据来自资源不受限NPV目标的启示，以及为工期最小化问题设计的方法，他开发了5个单向启发式规则和一个随机进度安排规则，其中有3个规则来自于资源不受限Max-NPV问题的解。这些规则对80个问题进行了测试，这些问题分布在30个工序的小规模问题到1461个工序的大规模问题之间。研究发现，没有一个启发式规则在所有情况下都表现最佳。对小规模问题，这些启发式规则具有相似的表现，找到5％～10％的最优解。随着项目规模的增加，资源受限的水平决定了启发式规则的效率。当资源约束不紧时，带最小工序数的最小时差规则在大项目中证实表现最好。相反，当资源约束较紧时，使用来自不受限问题最优解的信息的启发式规则表现最好。但是，这些规则之间的差异在统计上并不显著。

Padman等^［49］也使用来自资源不受限NPV目标的解的启示，开发了启发式方法用于带多个约束资源的项目进度安排。他们表明，一个带嵌入优先规则的启发式程序增加了项目的净现值，这个优化导向的启发式程序和9个不同的嵌入优先规则在许多项目环境下进行了测试，这些项目环境考虑了不同网络结构、资源受限的程度，以及称为PSD数据集的现金流参数。对PSD数据集的广泛测试显示，新的启发式方法优于使用来自CPM信息的启发式规则，并且在大多数情况下表现优于之前研究的启发式方法。

Padman和Smith-Daniels^［50］扩展了前人的工作，在工序进度安排中，使用放松的优化模型计算在提前惩罚和拖延惩罚之间的权衡。他们在文献^［49］中讨论的贪婪程序中嵌入了8个启发式规则，测试是否只要紧前工序都完成就将工序释放到进度序列中可以导致项目NPV的改善。对PSD数据集的广泛测试显示了这个方法是成功的。

Ulusoy和Özdamar^［51］提出一个迭代进度安排算法，其目标是同时改善项目工期和净现值。这个迭代算法进行连续的前向／后向进度安排，导致了非常平滑的资源分布，再加上工序的右移，使得项目工期与NPV同时改善。在这个现金流模型中，假设工序支出在其开始时间发生，支付在项目完成时发生。这个算法对相关文献的2个问题集进行了测试，结果证明在假设的现金流模型下，这个迭代进度安排算法同时改善了这两个准则。

Yang等^［52］使用9种随机进度安排规则最大化项目的净现值，其中有8个随机规则为相应单向启发式进度安排规则的简单扩展。这些规则对一个由1440个问题组成的大型数据集进行了评价，这些问题代表了项目的5个特征包括资源约束水平、资源需求的偏斜、成本与所需资源的相关性、进度款收入的频率和奖励的可得性。研究结果显示，在确定的环境下，两种先前研究过的规则——序列位置权重（rank positional weight）和折现累计现金流权重（discounted cumulative cash flow weight）规则表现较好，产生了较高的净现值。

Baroum和Patterson^［53］评价了项目和合同经理所使用的几个启发式方法，包括单向和多向程序。他们的单向程序使用的优先权重基于所有后续工序的累计未来现金流，多向程序是在得到的单向解基础上的改善。在每个启发式程序产生初始进度后，应用多向、右移和左移程序进行改进。他们使用一个全因子试验设计来评价这些启发式程序的业绩。计算结果证实折现现金流、位置权重启发式规则（positional weight heuristics）的功效优于许多传统方法。

Özdamar等^［54］则以NPV最大化和延误最小化为准则，开发了多向混合启发式规则，他们提出的规则基本是工序时差、后续事件现金流的NPV这两个典型概念的加权评价。将提出的4个混合启发式规则嵌入在一个进度安排迭代算法中，并对85个问题进行了测试。结果显示所有启发式规则都可以得到平均NPV与延误值的3组均衡值，以供决策者选用。

后启发式方法（meta-heuristic approaches）^{［52,55,56,57,58］}使用全局搜索方法引导工序进度安排，主要包括禁忌搜索方法、模拟退火方法等，近年来取得了相当大的成功。Icmeli和Erenguc^［55］对一个初始的可行解使用了禁忌搜索方法，这个初始可行解产生于一个简单的单向算法。初始解通过几次迭代得到改进，每次迭代将每个工序从当前完成时间提前或推后一个时间单位，约束条件是迭代后得到的完成时间不应该突破工序的最早和最迟完成时间。他们也研究了禁忌搜索中长期记忆的使用以改善结果。来自Patterson集的50个问题的计算结果显示，这些方法都是有效的，并且接近最优解。

Yang等^［52］使用的9种随机进度安排规则中包含了一个模拟退火规则。通过对1440个测试问题的计算表明，这个模拟退火进度安排方法对于大多数问题产生了最高的净现值。Zhu和Padman^［56］在使用禁忌搜索改善进度时，也研究了一种局部搜索增强策略的设计、实施和试验。这个方法使用基于现金流的移动产生策略，克服了相关的陷入局部最优问题的缺陷，它作为一种修补启发式规则相当有用。计算结果显示，后启发式方法在超过85％的PSD问题中占优势，相关文献都比启发式方法有显著改善。研究结果表明，相比通常使用的单向、基于参数、依赖问题的启发式规则，不依赖于问题的（problem-independent）后启发式方法更能反映RCPSP的许多关键参数之间的复杂的相互作用。

Zhu和Padman^［57］通过使用一种异步队组（Asynchronous Team, A-Team）方法，将分布计算概念应用于RCPSP。A-Team是一个软件组织，推动了在多个启发式算法之间的合作，因此它们产生了比单独使用时更好的解。在A-Team的迭代、并行结构中，他们嵌入了几个简单启发式规则求解了RCPSP。对一些小规模的、随机产生的项目网络的初步计算结果显示，多个简单的启发式规则的组合优于文献中提出的单向、复杂的、基于优化的启发式方法。张颖等^［58］则采用了遗传算法与模拟退火算法相结合的混合遗传算法来求解RCPSP，通过一个简单的仿真实例计算显示了算法的有效性。

上述Max-NPV模型的目标是使承包商的净现值最大化，并且基于的假设是与工序完成相关的现金流已知。然而，当项目投标时，支付的数量和时间是重要的变量，这些变量可以通过协商以提供财务绩效。在实践中，承包商通常清楚与项目工序相关的支出，他可以使用这个信息和其他的项目参数知识如工序持续时间与业主协商已完工作的支付款，以使项目取得最大的财务回报^［5］。Dayanand和Padman^［59］也认为进度款支付的时间和数额对承包商而言是两个重要的变量，承包商可以通过与业主协商以提高自己的财务回报。为此他们提出了5个基于事件和基于工序的模型，用于在资源不受限时以NPV最大化为目标的环境下同时确定支付的时间和数额。由此产生了支付进度安排问题（payment scheduling problem, PSP）。这个问题与Max-NPV问题相比，更符合实际工程的需要。