局部最优进度计划

PSM2模型的目标是使承包商的NPV最大化，这个目标函数不是一个正则化的目标函数（Regular Performance）。对正则化目标函数的项目进度安排问题，其最优解一定是可行最早或最迟进度计划^［5,130］。因此对于这类问题（如工期最小化问题），在一种工序进度安排顺序下，利用前向或后向进度产生方案产生的可行最早或最迟进度计划就是该种工序进度安排顺序下的局部最优进度计划，最优解只需在这些局部最优进度计划构成的解空间中进行搜索。但是对于非正则化目标函数的项目进度安排问题却不能这样，因为这类问题的最早或最迟可行进度计划不一定就是局部最优进度计划。例如对于图3.2所示的可行最早进度计划，按照NPV最大的标准，它不是一个局部最优进度计划，因为如果将工序4的开始时间推迟到第19天进行，承包商成本现值将进一步减少，其净现值将得到增加。从这个意义上说，在确定了工序进度安排顺序，并利用前向或后向进度产生方案产生可行最早或最迟进度计划后，需要对其进行局部优化，以得到该种工序进度安排顺序下的局部最优进度，进而找出最优解。本节将探讨对最早或最迟进度计划进行局部优化的基本思路。

观察给定工序进度安排顺序下的可行进度计划，每个工序的开始时间分布在可行的时间窗口范围内。如图3.4所示的工序j，其开始的时间窗口为［ES_j, LS_j］。如果按最早时间进度安排，工序j的开始时间为ES_j（如图3.4中（a）所示）。当工序j的开始时间推迟到ST₂时，其直接成本支出的现值将由于发生时间的推迟而减小（如图3.4中（b）所示）。但其支付的时间点依然在wT，因此其支付现值不会发生变化。此外由于开始时间依然在时间窗口内，因此它不会改变项目的工期，即其间接成本支出的现值也不会发生变化。由承包商NPV的计算公式（2.10）可知，若其他工序的开始时间不变，工序j开始时间的推迟将使目标函数增加。继续推迟工序j的开始时间，目标函数将继续增加，直到支付时间发生变化为止（如图3.4中（c））。也就是说，在时间段［ES_j, ST₃］中，其中ST₃＝wT－d_j，目标函数值随着工序j开始时间的推迟而增加，当工序j的开始时间为ST₃时，目标函数达到最大。继续推迟工序j的开始时间，将会改变工序j的支付时间（图3.4中从wT变为（w＋1）T）。此时支付现值将由于支付时间的推迟而减少。因此这个推迟（如图3.4中（d））对目标函数的影响需要通过比较支付现值的减小量和直接成本现值的减小量得到。设工序j开始时间推迟到进行，其支付时间变为，则目标函数的变化为：

当ΔNPV_con大于0，则工序j开始时间的推迟将使目标函数增加，反之则减少。而对于时间段［ST₃, LS_j］中，工序j的支付时间在（w＋1）T，因此目标函数是随着工序j开始时间的推迟而增加，最终在LS_j达到最大（如图3.4中（e））。

图3.4　工序开始时间的变化

因此，我们可以以支付时间为边界将工序开始的时间窗口分为若干段，在每一段内，目标函数均是工序开始时间的增函数，即在每一段的上界达到局部最大。通过比较每一段的局部最大点可以找到在当前工序进度安排顺序下，工序的局部最优开始时间。图3.5显示了图2.2所示项目中工序3开始时间的变化如何影响目标函数。假设合同工期为40天，支付周期长度为10。工序3开始的时间窗口为［3, 27］。承包商NPV的变化以工序3在时间窗口下界，即第3天开始时的目标函数值为比较标准。从图中可以看出，在以支付时间为边界的各个时间段内，承包商NPV为开始时间的增函数，并在各个时间段的上界达到局部最大。通过比较各个局部最大点，当工序3在第5天开始时承包商NPV达到局部最大。

图3.5显示了工序开始时间与承包商NPV变化之间的关系，描述这种关系的图形可称为“工序收益曲线（activity profit curves）”，最早由Kazaz和Sepil^［82］提出，其后被Vanhoucke等^［83］沿用。不过，与本书不同的是，他们将“工序收益曲线”定义为显示工序现金流的NPV与工序结束时间之间关系的图形。

当每个工序均安排在其局部最优开始时间开始时，所得到的进度计划就是当前工序进度安排顺序下的局部最优进度计划。通过比较各种工序进度安排顺序下的局部最优进度计划，即可得到PSM2模型的全局最优解。因此，在定义了工序进度安排顺序下的局部最优进度计划后，对PSM2模型最优解的搜索就可从对工序时间窗口各个可行位置的搜索，转变为对各种工序进度安排顺序的搜索，搜索范围将显著减少，搜索效率将大大提高。

图3.5　工序开始时间的变化对目标函数的影响