计算实验设计

一、测试问题集

为了测试求解PSM2模型的内环蚁群算法的有效性，需要将其应用于大量的工程实例之中。而工程实例的收集是一件耗时费力的工作，目前的研究经费及时间限制不允许该工作的开展。但是从PSM2模型的本质上看，它是资源受限项目进度安排问题（RCPSP）的一个分支。而在对RCPSP问题的研究中，已经积累了大量的测试实例。因此对PSM2模型的内环蚁群算法的测试可以借鉴RCPSP问题的测试实例来进行。尽管目前能够得到的RCPSP问题的测试实例集均是针对工期最小化目标的，这些测试实例集与本书提出的PSM2模型存在一些区别，但是两者在网络的拓扑结构、资源约束的特点等方面的要求是一致的。因此对于RCPSP的测试实例集，只要依照PSM2模型的特点加以适当修改，就可以应用于对PSM2模型的内环蚁群算法的有效性的测试中。

如前文所述，在RCPSP问题的测试实例集中，应用最广泛的是由Kolisch等^［129］创建的项目进度安排问题库PSPLIB。这个问题库中的测试实例是通过一个称为ProGen的项目进度安排问题实例产生器产生。在对RCPSP问题的长期研究中，学者们发现算法的有效性和问题本身的复杂性密切相关，一个好的算法应该能够适应不太复杂的问题。而问题的复杂性主要由一些反映问题本身特征的参数所决定，这些参数包括：反映网络拓扑结构的工序数、非冗余弧的数目、工序持续时间、反映资源约束特征的资源因子和资源强度等。因此ProGen通过一个全系数的设计，依照这些参数来产生各种复杂程度的测试实例，以保证所产生的项目实例可以代表整个项目空间。也正是基于这样的特点，PSPLIB为广大致力于研究RCPSP问题的研究人员所接受，并将其作为测试所提出的各种算法的标准测试问题库。PSPLIB目前已经形成了完整的测试问题分类体系，例如MRCPSP子库用于多模式RCPSP问题的测试；RCPSP/max子库用于带一般逻辑关系的RCPSP问题的测试；RLP/max子库用于资源均衡问题的测试等等。遗憾的是，PSPLIB目前尚没有建立支付进度安排问题的测试实例子库。因此在应用于本书提出的内环蚁群算法有效性的测试过程中，需要对PSPLIB中的测试问题进行必要的修改。

本书选取的测试实例主要来源于PSPLIB的RCPSP子库中的j30-files、j60-files和j120-files三个测试问题集。这三个测试问题集中每个测试问题的工序数分别为30、60和120个（不包括虚拟的起始和结束工序）。其他基本问题特征参数如表3.8所示。

表3.8　测试问题集的基本问题特征参数

表3.8中的可更新资源强度根据下式计算：

式中，表示使项目保持可行的最小资源需求（即每个工序必须按顺序实施所需的资源供应量），由下式确定：

表示使项目保持最早开始进度的需求峰值，由下式确定：

资源强度的定义最早由Cooper^［147］于1976年引入，后被认为是影响资源受限项目进度安排问题求解的一个重要问题特征参数，并被用于ProGen中。资源强度是一个用归一化的数表示资源“紧”的程度的指标。若RS_ρ＝0时表示当可更新资源的供应量取最小值时，项目仍然是可行的。若RS_p＝1表示资源供应量必须足够大才能使资源不再制约进度的安排。

对测试问题集的修改主要包括增加各个问题的现金流参数，以使问题可以适用于支付进度安排问题的求解。各测试问题的现金流参数主要通过随机的方法生成。其中，各工序的直接成本支出由工序所需可更新资源数量乘上相应的资源价格的方法得到。资源价格通过随机方法生成，并假设资源价格为均布在［50, 200］的随机整数。因此资源价格的随机抽样公式如公式（3.21）所示。

式中，R为［0, 1］均布随机数。其他现金流参数的概率分布假设及其随机抽样公式如表3.9所示。

表3.9　一些现金流参数的概率分布假设和随机抽样公式

业主从项目获得的收益和项目直接成本支出总和之比假设为一常数u，因此业主从项目获得的收益由如下公式计算：

其中常数u假设为均布在［1.5, 5］的随机数，因此u由如下的随机抽样公式产生：

项目合同工期与项目在不考虑资源约束下最短工期之比假设为一常数v，因此项目合同工期由如下公式产生：

其中ES_J为在不考虑资源约束下，按照CPM技术计算得到的结束工序的最早开始时间。v假设为均布在［1.1, 2］的随机数，因此v由如下的随机抽样公式产生：

二、对比方法的设计

尽管PSM2模型本质上属于承包商角度下的支付进度安排模型，但它和其他文献中提到的模型还是存在一些区别：如支付内容上的修正、间接成本的考虑等。因此很多文献中提到的一些承包商角度下的支付进度安排问题的求解方法并不适用于PSM2模型的求解，尤其是一些如遗传算法、模拟退火算法等的后启发式方法，因为这些方法需要根据模型进行一些算子的设计。但一些启发式方法经过修改后仍然可以适用。正如前文所述，启发式方法的结构主要是由进度产生方案和优先规则构成，不管模型做了什么样的变化，进度产生方案和优先规则均不会有什么变化，变化的只是对产生的可行解的评价准则。因此，本书主要采用启发式方法作为对比方法，来评估所提出的求解PSM2模型的内环蚁群算法的性能。

文献中提到了一些求解承包商角度下支付进度安排问题的启发式方法，如LFT（最小最迟结束时间规则）、MINSLK（最小时差规则）、CFW（现金流权重方法）等。有很多文献对这些启发式方法进行了对比研究，例如R. A. Russe11^［48］对带现金流的资源受限项目进度安排问题的启发式方法进行了对比实验研究；Özdamar等^［54］对求解以净现值为准则的项目进度安排问题的启发式方法进行了对比实验研究等。这些研究的结果不尽相同，甚至有些结论相互矛盾。本书从中选取意见较为一致的两种启发式方法作为对比方法。这两个方法分别为：现金流权重方法和Rand-50算法。

现金流权重方法是Baroum和Patterson^［53］首先提出的。一个工序的现金流权重（cash flow weight, CFW）是指该工序的现金流加上该工序所有后续工序（在逻辑关系上有联系）的现金流。现金流权重越大的工序越优先安排进度。现金流权重赋予工序以“前视（forward looking)”能力。例如，一个负现金流的工序应尽可能迟地安排进度，但如果它之后跟着一个具有很大正现金流的工序，那么如果将这个负现金流的工序尽可能早地安排进度，其后的那个大正现金流的工序就有可能安排在更早的时间上开始，从而使净现值增加。Baroum和Patterson提出了两种现金流权重：不考虑资金时间价值的现金流权重和折现现金流权重（discounted cash flow weight, DCFW）。本书采用的是DCFW。Baroum和Patterson并没有给出DCFW的计算公式，本书依据其基本思想，推导出DCFW的计算公式，以供后续的研究作为参考。

定义US_j为工序j及其后续工序的集合，它采用后向迭代的方法确定。项目结束工序的US_J就是它本身，其他工序的US_j为该工序和其所有紧后工序的US_h（h∈S_j）并集，即：

则工序j的折现现金流权重为：

式中，NPV_j为工序j的折现现金流，由下式确定：

由于本书提出的PSM2模型与Baroum和Patterson所求解的问题模型的区别，本书仅采用他们提出的折现现金流权重，而没有采用他们提出的算法。本书采用的进度产生方案为前向／后向混合迭代算法。考虑到目标函数的非正则性，在获得可行进度计划后，采用前述的局部优化程序对其进行局部优化。在初始状态下，工序的折现现金流权重的计算采用不考虑资源约束下的工序最早开始时间ES_j进行计算，按照这个权重采用前向进度产生方案产生可行最早进度计划，利用右移局部优化持续对其进行局部优化；然后采用所得到的工序进度安排时间ST_j更新工序现金流权重，按照这个权重采用后向进度产生方案产生可行最迟进度计划，利用左移局部优化程序对其进行局部优化；重复这一过程直至产生的解的目标函数不再改变。

Rand-50算法属于随机搜索的启发式方法，它通常用于产生问题解的上界。此外，还可以用于在缺乏对比方法的计算实验中作为对比方法。R. A. Russell^［48］通过计算实验认为这个方法对于工序数小于200的问题是十分有效的。因此本书将其作为另一个对比方法。该方法通过随机的方法产生工序的进度安排顺序。若第g决策层次的有资格工序集合EJ_g有n个元素，则该方法首先通过以下随机抽样公式产生一个均布在［1,n］的随机数m。

接着在EJ_g中选择第m个元素作为当前层次进度安排的工序。然后按照前述的前向／后向进度产生方案产生可行最早／最迟进度计划，再利用局部优化程序对其进行局部优化，以得到一个可行解。通过这样的方式产生50个可行解，从中选择最好的一个解作为问题的最优解。为考察各种进度安排方向下可行解的性能，将50个可行解的产生等分为两个部分：其中25个用前向进度安排产生，另25个用后向进度安排产生。

三、性能指标的选取

衡量一个算法的有效性主要考虑两个方面的因素：最优目标函数值和求解时间。前者反映算法寻优的性能，后者反映算法寻优的效率。因此本书主要依据这两个因素考察所提出的算法的有效性，并将最优目标函数值作为各种算法进行对比的主要指标，而求解时间从实际工程实时性要求进行考察。

对最优目标函数值，本书以内环蚁群算法和对比方法确定的最优解的目标函数值之比作为对比性能指标。它反映了相对于对比方法，本书提出的方法所得到的最优目标函数值的改进。