优化串行进度生成机制的方法

SSGS包括J个阶段。在每一阶段g中，需要在满足紧前关系和资源约束的前提下选取一个任务，并安排该任务尽快开始。因此，可以认为在每一阶段g都存在两个互不相交的任务集合：（1）已调度任务集合（scheduled set），记为Sg，包括所有已经被安排了开始时间并分配了所需资源的任务；（2）候选任务集合，也就是待决策任务集合（decision set），记为Dg，包括所有尚未安排开始时间，同时其所有紧前任务都属于Sg的任务，即：

在SSGS的早期阶段，通常会存在一些既不属于Sg也不属于Dg的任务，这些任务由于其某个紧前任务尚未安排开始时间，因而无法进入候选任务集合。

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

SSGS的伪代码如下所示：

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

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

其中，LSj为任务j*根据项目时间上限T及CPM确定的最晚开始时间；为第g个阶段中可更新资源k在时段t上的剩余供应量。在确定任务j*的开始时间之后，需要分配相应的资源，并更新后续可供分配的资源供应量，因此对于可更新资源k，在第g个阶段分配了任务j*之后，其剩余资源供应量（residual availability）为：

图5.1展示了一个J=9的项目。该项目只有一种可更新资源（K=1），资源容量R=4。每个任务的工期与资源需求量均标注在AON网络图中。任务1和任务9为虚拟任务。(www.xing528.com)

图5.1　资源受限项目示例

利用串行SGS及任意优先规则即可产生该项目的可行进度计划。例如，可选定最短工期（shortest processing time，SPT）为任务优先规则。如此，在任务1完成分配之后，在第2个阶段，任务2、3、8构成候选任务集合D2，这三个任务的工期均为3，因此需要有打破平局的补充规则（tie-breaker）进一步进行选择，通常在缺省情况下设定补充规则为任务编号越小越优先，如此则在第2阶段选择任务2。在满足紧前任务和资源约束的前提下，设定任务2的开始时间s2=0。由于任务2需要2个单位的资源，因此剩余资源供给量在时段0和时段1均下降2个单位，其余时段保持不变。之后SGS进入第3个阶段。此时任务3、8构成新的候选任务集合D3。根据上述优先规则，选择任务3进行调度。任务3的开始时间下限为0，但是从时段0到时段2的剩余资源供给量无法满足任务3的资源需求，因此必须设定任务3的开始时间为s3=0。由于任务3需要3个单位的资源，因此剩余资源供给量在时段3到时段5均下降3个单位，其余时段保持不变。如此，可以逐步完成各阶段的计算，最终完成所有任务的调度，从而产生整个项目的进度计划，如图5.2所示。

图5.2　基于SSGS及SPT的项目进度计划

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

如果选用最小总时差（minimum slack，MINSLK）优先规则，则SSGS产生的项目进度计划如图5.3所示，为最优进度计划。其对应的任务列表为：（1，3，6，7，4，2，5，8，9）。由此可见，不同优先规则会构造出不同的任务列表，从而对项目调度质量产生直接影响。

图5.3　基于SSGS及MINSLK的项目进度计划

SSGS产生项目进度计划的均为积极进度计划。积极进度计划（active schedule，AS）是指这样的可行项目进度计划：在满足紧前关系和资源约束的要求下无法左移（left shift）任一任务的开始时间而不必延迟其他任务（Sprecher et al.，1995）。也就是说，对于一个积极进度计划，要提前某一任务，必然需要延迟其他某些任务。Kolisch（1996a）证明，利用SSGS与任意优先规则产生的项目进度计划，必然是积极进度计划。对于任意一个积极进度计划，还必然是半积极进度计划。所谓半积极进度计划（semi-active schedule，SAS）是指该进度计划中的任何任务都无法进一步局部左移（Sprecher et al.，1995）。对大部分常规的项目调度目标函数，例如最小化项目总工期等，SSGS是比较合适的方法。SSGS的时间复杂度为O（J2，K）。