多项目调度中逆向算法的优化方案

上述算法都是针对单项目调度设计的。当多个项目之间存在资源竞争时，无法直接应用这些算法到单个的项目中，因此就需要经过改进的、针对多项目调度的迭代算法。Lova等（2000）将Wies（t1964）提出的任务移动技术拓展到了多项目，但只是在任务的时差范围内对已有多项目进度计划进行调整。事实上，也可以直接将FBI技术拓展到多项目调度。

如上所述，由于逆向算法的特性，某些任务可能被安排了负的开始时间，Li和Willis（1992）建议将这些任务的开始时间修改为0，但这样必然导致这些任务与其紧后任务之间的约束关系遭到破坏，同时也可能突破项目的资源限制。因此，这样修正过的逆向进度计划很可能是不可行的，也就无法用来更新项目调度问题的上界。在多项目调度中，不同项目之间存在资源竞争的关系，那么Li和Willis（1992）提出的方法还可能突破项目间的资源约束。

参考上述的单项目FBI技术（Tormos and Lova，2001；Valls et al.，2005），可以设计如下的多项目正向逆向改进（MPFBI）算法（寿涌毅，2004b）：(www.xing528.com)

其中，串行多项目进度生成机制（SMPSGS）见第5章。可以类似地设计逆向多项目进度生成机制，在此不再赘述。迭代过程反复进行，直到循环次数或CPU时间超过初始设定值。参考DJ的设定，一般可以取循环次数为1。