由前述分析可知，PSM2模型的目标函数不是正则化的。因此，由前述进度产生方案得到的可行最早进度计划或可行最迟进度计划不一定是局部最优。在基于蚁群算法的项目支付进度安排模型中，搜索最优解的基本思路是，利用蚁群算法在各种工序进度安排顺序下的局部最优进度计划中搜索最优解。因此，根据FSSGS和BSSGS得到可行最早和最迟进度计划后，还需要用局部优化程序对其进行优化，以便得到在前向和后向两种工序进度安排顺序下的局部最优进度计划。
在Max-NPV问题的启发式方法求解中，为了提高NPV经常采用的策略是，将带正现金流的工序左移，带负现金流的工序右移；或者将带正现金流的工序尽可能早地安排进度，带负现金流的工序尽可能迟地安排进度。本书对支付进度安排问题研究时所考虑的局部优化程序也是受到这些思路的启发。本书采用的局部优化程序是对FSSGS或BSSGS得到的可行进度，通过“左移”或“右移”操作，在满足逻辑关系和资源约束的条件下，将部分工序的开始时间提前或拖后，以达到改善其目标函数的目的。局部优化程序的主要步骤包括对工序时间窗口进行分段，以及根据图3.5所示的“工序收益曲线”所反映的工序开始时间与目标函数值变化之间的关系来决定工序是“左移”还是“右移”，同时考虑可更新资源约束。
局部优化程序的具体步骤如下：首先根据支付周期将工序时间窗口分成若干段，即：
其中：
例如，假设一个工序的时间窗口为［3, 24］，其持续时间为7，支付周期为10，则w＝int［（3＋7－1）／10］＋1＝1,l＝int［（24＋7－1）／10］－1＝2，因此该工序的时间窗口可划分为：［3, 24］＝［3, 3］∪（3, 13］∪（13, 23］∪（23, 24］。
时间窗口的每一个分段表示该工序在这个时间段内的任何时刻开始，其支付时间保持不变。图3.5显示的“工序收益曲线”已经反映了工序开始时间和目标函数值变化之间的关系。从图3.5可知，在时间窗口的每一个分段内，目标函数值是开始时间的增函数，并在该时间段的上界达到最大。因此，在时间窗口分段后，将该工序的开始时间分别“左移”或“右移”到各个分段的上界，同时保持其他工序的开始时间不变；比较这些情况下的目标函数值就可以确定该工序的局部最优开始时间。鉴于工序的“左移”或“右移”还会受到可更新资源约束的影响，故在工序开始时间“左移”或“右移”之前，应该先检查各时间段的上界点是否满足可更新资源约束。如果不满足，则将上界点往前提前1天，继续检查，直至得到满足资源约束的上界。
由于工序时间窗口的确定是动态的，工序“左移”或“右移”的顺序也将直接影响所得到的局部最优进度计划，因此对工序“左移”或“右移”的顺序应该加以限制。对一个给定工序进度安排顺序下通过前向／后向进度产生方案得到的可行最早／最迟进度计划，局部优化程序将按照这种工序进度安排顺序的逆序进行。也就是说，对可行最早进度计划，局部优化程序是从结束工序开始，按照工序进度安排顺序的逆序，逐个将工序进行“右移”；对可行最迟进度计划，则是从起始工序开始，按照工序进度安排顺序的逆序，逐个将工序进行“左移”。
右移局部优化程序和左移局部优化程序见图3.12和图3.13所示。
右移局部优化程序
第1步：初始化
g＝J
第2步：选择右移工序
g＝g－1
IF g＝1 THEN END
选择工序前向进度安排顺序中第g个决策层次所选择的工序jg
第3步：更新剩余资源供应量
第4步：确定其时间窗口
第5步：计算w和l，对时间窗口进行分段
第6步：确定时间窗口各分段的可行上界，比较目标函数值
若ΔNPVcon＞0，则将工序开始时间移至该位置：
ELSE
t＝t－1；转到第6步
END IF
第7步：更新剩余资源供应量
转到第2步
END
图3.12 右移局部优化程序
左移局部优化程序
第1步：初始化
g＝J
第2步：选择左移工序
g＝g－1
IF g＝1 THEN END
选择工序后向进度安排顺序中第g个决策层次所选择的工序jg
第3步：更新剩余资源供应量
第4步：确定其时间窗口
第5步：计算w和l，对时间窗口进行分段
第6步：确定时间窗口各分段的可行上界，比较目标函数值
若ΔNPVcon＞0，则将工序开始时间移至该位置：
ELSE
t＝t－1；转到第6步
END IF
第7步：更新剩余资源供应量
转到第2步
END
图3.13 左移局部优化程序
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
