测试问题集

为了测试算法的求解效果和运行效率，在资源受限项目进度安排（RCPSP）问题中，研究人员通常需要对大量的问题实例进行测试和验证。早期的测试问题主要由作者自己生成，比如Davis^［125］、Patterson^［9］和Talbot^［126］，他们在以工期最小化为目标的RCPSP研究中最早生成了测试问题用于计算和验证。其后，Patterson^［127］对他们的实例进行了搜集并添加了一些实例，从而形成了由110个测试问题组成的、被后人称为Patterson问题集的测试问题库。

当以NPV最大化作为项目进度安排的优化目标时，典型的Patterson问题集不再能够满足需要，于是Russell^［48］对其进行了修改，为工序添加了现金流的数据表示工序的支出和已完工的支付。Padman等^［49］则产生了1440个例子用于对该问题的优化导向的启发式方法进行测试。这1440个例子来自144个项目，它们根据项目规模、网络结构、现金流的发生频率、资源受限程度、利润率和资金成本这六个参数的不同设置而生成。这个数据集称为PSD问题集，后来被许多文献所采用^{［50,56,97］}。

除了上述测试问题集，一些研究者还设计了资源受限项目进度安排问题的生成器，以产生更加丰富、更具有代表性的问题实例作为优化算法的检验标准。其中，比较知名的、应用较为广泛的是Kolisch等^［128］提出的ProGen项目生成器。比如在支付进度安排问题的研究中，Vanhoucke等^［83］和Mika等^［84］都用ProGen项目生成器产生的测试问题进行了计算实验。

如今，越来越多的研究人员利用高速发展的Internet作为学术交流的工具，一些内容丰富、代表性极强的测试问题库已经在Internet上出现。PSPLIB（project scheduling problem library）^［129］就是一个相当知名的测试问题库，该题库可以在http://www.bwl.uni-kiel.de/bwlinstitute/Prod/psplib上获得。研究者除了可以从该题库下载测试问题实例，还可以得到工期最小化问题的最优解或近似最优解，以及某些问题的上界／下界。如果研究人员运用一些新方法求得了问题的最新解，也可以在该网页上传研究成果，以便更好地与国外同行进行交流。

本书从业主和承包商双方交互角度构建项目支付进度安排模型，并提出用双环蚁群算法进行求解。为了检验该算法的求解效率和验证其有效性，需要通过大量的实例问题进行测试。鉴于可以通过Internet非常便捷地从PSPLIB获取测试问题集，本研究将从中选取若干实例进行测试。但是，PSPLIB提供的测试问题包含的参数主要适用于求解工期最小化问题，它不包括诸如现金流、折现率等数据。因此，在后面章节进行计算实验时，将对这些测试问题进行必要的参数补充。