逆向调度算法解析与应用

逆向调度算法一样可以采用SSGS或PSGS。对于逆向SSGS来说，共包括J个阶段，从最后一个任务逐步向前调度。在每一阶段g都存在两个互不相交的任务集合：（1）已调度任务集合（scheduled set），记为Sg，包括所有已经被安排了开始时间并分配了所需资源的任务；（2）候选任务集合，也就是待决策任务集合（decision set），记为Dg，包括所有尚未安排开始时间，同时其所有紧后任务都属于Sg的任务，即：

在每一个阶段，SSGS采用特定的优先规则从Dg中选取一个任务，然后为该任务设定尽可能晚的开始时间，并分配相应的所需资源。随着调度阶段的推进，SSGS逆向地扩展进度计划，从而完成整个项目的调度。

逆向SSGS的伪代码如下所示：

初始化时，设定任务j=J的完成时间为项目工期上限T。在每一阶段开始时，计算候选任务集合Dg，然后从候选任务集合Dg中根据特定优先规则选取一个任务j*。接着，在符合紧后关系和当前资源供应情况的前提下，为任务j*安排一个尽可能晚的完成时间cj*。由于任务j*需要满足紧后关系，因此其完成时间cj*的上限为：

同时，该完成时间还需要满足资源约束，所以实际可行的完成时间cj*为：

其中，EFj为任务j*根据CPM确定的最早完成时间；为第g个阶段中可更新资源k在时段t上的剩余供应量。在确定任务j*的完成时间之后，需要分配相应的资源，并更新后续可供分配的资源供应量。因此，对于可更新资源k，在第g个阶段分配了任务j*之后，其剩余资源供应量为：

图6.1展示了一个J=9的项目。该项目只有一种可更新资源（K=1），资源容量R=4。每个任务的工期与资源需求量均标注在AON网络图中。设定项目工期上限为T=18。任务1和任务9为虚拟任务。

图6.1　资源受限项目示例(www.xing528.com)

利用逆向SSGS及任意优先规则即可产生该项目的可行进度计划。例如，选定最短工期（SPT）为任务优先规则。如此，在任务9完成分配之后，在第二个阶段，任务5、7、8构成候选任务集合D2，这三个任务的工期分别为2、3、3，因此选择任务5。在满足紧后任务和资源约束的前提下，设定任务5的结束时间c7=18。由于任务5需要3个单位的资源，因此剩余资源供给量在时段16和时段17均下降3个单位，其余时段保持不变。之后逆向SSGS进入第三个阶段。此时任务2、4、7、8构成新的候选任务集合D3。根据上述优先规则，选择任务4进行调度。因为任务5为任务4的紧后任务，因此任务4的开始时间下限为16。因为资源供给充分，因此设定任务4的完成时间为c4=16。由于任务4需要2个单位的资源，因此剩余资源供给量在时段15下降2个单位，其余时段保持不变。如此，可以逐步完成各阶段的计算，最终完成所有任务的调度，从而产生整个项目的逆向进度计划，如图6.2所示。

图6.2　基于逆向SSGS及SPT的项目进度计划

按照选择的顺序，上述进度计划也可以表示为一个任务列表：（9，5，4，2，7，6，3，8，1）。逆向SSGS在构造任务列表的过程中也不考虑资源约束，而是在为每个任务分配完成时间时才考虑资源约束。

如果将图6.2中所有任务左移7个时段，则得到如图6.3所示的进度计划。

图6.3　调整开始时间后的逆向项目进度计划

将图6.3和图5.2、图5.3进行对比可以发现，虽然采用了相同的任务优先规则SPT，但是逆向SSGS和正向SSGS生成了完全不同的进度计划。采用SPT规则的正向SSGS生成的进度计划需要14个时段，而采用相同规则的逆向SSGS所生成的进度计划只需要11个时段。与采用MINSLK规则的正向SSGS所生成的进度计划相比，两者在项目工期上完全一致，但是非关键任务4的开始时间推迟了3个时段。由于项目中间任务的净现值通常为负值，推迟任务4的开始时间将有助于改善项目净现值。

类似地，可以构造基于PSGS的逆向调度算法。其伪代码如下所示：