基于局部搜索的迭代算法优化

Ozdamar和Ulusoy（1996）对正向逆向迭代算法进行了改进，与Li和Willis（1992）的算法相比，该算法有以下三个特点：

（1）不采用SSGS，而是采用PSGS。

（2）逆向调度从时段0开始生成可行进度计划，然后再与前一次正向调度所得的进度计划相比较，选择较短的总工期。

（3）采用局部约束分析（local constraint based analysis，LCBA）（Ulusoy and Ozdamar，1994）替代任务优先规则从决策集Dg中选择任务，而且在LCBA中采用当前时段tg与LFTj的间隔[tg，LFTj]作为时间窗，其中LFTj为当前项目总工期cJ与上一次进度计划中的任务开始时间sj之差，从而建立其正向调度与逆向调度之间的联系。(www.xing528.com)

算法过程如下：首先，采用PSGS和LCBA生成可行的进度计划。然后用项目总工期减去任务j的开始时间sj作为LFTj。然后采用BPSGS，在每一个调度阶段tg在时间窗[tg，LFTj]内采用LCBA进行任务选择，并逐步生成逆向进度计划。对正向进度计划与逆向进度计划进行比较，并保留较优的计划。如此迭代，直到项目工期无法进一步改进。

该算法的伪代码如下所示：

Ozdamar和Ulusoy（1996）把改进后算法与最小松弛时间（minimum slack，MINSLK）、最晚结束时间（LFT）、加权资源利用率与紧密关系（weighted resource utilization and precedence，WRUP）及Li和Willis（1992）提出的算法相比较，发现改进算法有更好的调度效果。Ozdamar和Ulusoy（1996）在计算测试中发现，正向逆向迭代过程通常只需要3次或4次迭代就能完成改进。