提升算法性能：逆向正向改进算法优化

Tormos和Lova（2001）将正向逆向迭代方法与基于后悔值的偏倚随机抽样（RBRS）方法（Drexl，1991）结合起来，构成所谓的抽样逆向正向（sampling backward-forward）调度算法。

算法主体分为两个部分。第一部分，使用SGS和MINLFT作为优先规则，利用RBRS生成可行的进度计划，包括每个任务的开始时间sj和结束时间cj，以及按照任务结束时间降序排列形成任务列表BL。RBRS的两个参数α和ε均取值1。

第二部分，分别采用逆向调度和正向调度方法对RBRS生成的进度计划进行改进。该方法基于拓扑进度生成机制（topological schedule generation scheme，TSGS）。所谓TSGS就是一种特殊的SSGS，只是预先构造了一个符合紧前关系要求的任务列表，对任何一个任务，其紧前任务都排在前面。如此，在SGS从决策集中选取任务时，只需要挑选任务列表中最靠前的任务即可。因为不需要计算任务优先值，所以TSGS运行速度快于通常的SSGS。在进行迭代优化时，首先根据RBRS所得到的任务列表BL，采用TSGS进行逆向调度，安排每一个任务尽可能晚地开始，并根据任务开始时间的升序构造任务列表FL。随后，在任务列表FL基础上，采用TSGS进行正向调度，安排每一个任务尽可能早地开始。

如此反复进行，直到循环次数或CPU时间超过初始设定值。该算法的伪代码如下所示：(www.xing528.com)

基于PSPLIB算例库的算法测试表明，Tormos和Lova（2001）所提的基于RBRS的迭代算法能取得良好的调度效果。Tormos和Lova（2003）进一步改进了正向逆向迭代方法与RBRS的结合方式，加入了选择机制，提出了抽样选择逆向正向调度（sampling selective backward-forward scheduling）方法。该方法只有当随机抽样所产生的调度方案优于之前抽样调度方案的均值时，才应用正向逆向迭代方法。

上述两种改进型算法的核心思想是把随机抽样和正向逆向迭代方法结合起来。随机抽样给出了多种可能的调度方案，但这些方案质量不一定很好，因此可以再用正向逆向迭代方法进行优化。对于那些容易过早收敛的搜索算法，随机抽样与正向逆向迭代方法的结合方式是一个值得借鉴的算法设计。

Tormos和Lova（2001）所采用的迭代方法与双向调整方法（Valls et al.，2005）非常类似，差别只是在于：（1）双向调整采用SSGS，而Tormos和Lova（2001）的方法采用TSGS；（2）双向调整基于任务完成时间进行调整，而Tormos和Lova（2001）的方法则在正向逆向调度中分别采用任务开始时间和结束时间。因此，这两种方法都被Kolisch和Hartmann（2006）称为正向逆向改进（forward-backward improvement，FBI）方法。