多项目进度生成机制的分析介绍

前面介绍了单项目调度的进度生成机制，包括串行SGS与并行SGS。并行SGS给出的是非延迟进度计划（non-delay schedule），其搜索空间要小于串行SGS，但是有可能不包括项目调度问题的最优解（Kolisch，1996；Sprecher et al.，1995）。接下来则进一步介绍串行多项目SGS，对应并行SGS可以做类似的扩展。

考虑N个并行项目，其中一共包含∑Ji个任务。因此，对串行SGS来说，需要∑Ji个阶段。在任一阶段g中，同样包括两个互不相交的任务集合：（1）已调度任务集合（scheduled set），记为Sg，包括所有已经被安排了开始时间并分配了所需资源的任务；（2）可行任务集合，也就是候选任务集合（decision set），记为Dg，该集合包括所有尚未安排进度，同时其所有紧前任务都属于Sg的任务，即：

在每一个阶段，根据给定的优先规则，从Dg中选取任务，并在满足紧前关系和资源约束的条件下安排中选任务尽早开始。对于多项目问题来说，在初始阶段，候选任务集合D1包含了每个项目的起始任务，之后每个阶段逐步更新候选任务集合，从而完成多项目的进度安排。

串行多项目进度生成机制（serial multi-project schedule generation scheme，SMPSGS）的伪代码如下所示：

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

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

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

图5.5展示的多项目共包含2个项目，只涉及一种可更新资源（K=1），资源容量R=4。每个任务的工期与资源需求量均标注在AON网络图中。(www.xing528.com)

图5.5　资源受限多项目示例

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

图5.6　基于SSGS及SOF的多项目进度计划

按照任务选择的顺序，上述进度计划也可以表示为一个多项目任务列表：（1，2），（1，3），（2，2），（2，3），（2，4），（2，5），（1，4），（1，5），（1，6）。与单项目SSGS类似，多项目SSGS在构造任务列表时也不考虑资源约束，而是在为每个任务分配开始时间时才考虑资源约束。因此，从上述的任务列表可以对应到一个特定的进度计划；但是，给定如图5.6所示的一个项目进度计划，并不只对应一个特定的任务列表。例如，如果交换上述任务列表中任务（1，2）和（2，2）的顺序，所对应的进度计划并无差异。从图5.6中还可以观察到，项目2的进度计划实际上就是CPM计划，但是项目1由于存在着和项目2之间的资源竞争，任务（1，3）和（1，4）无法并行开展，导致整个项目相对其CPM计划来说有一定的延长。

如果选用最长项目任务优先（longest activity from longest project，LALP）规则（参见表5.3），则SSGS产生的任务列表为：（1，2），（1，4），（1，3），（1，5），（1，6），（2，2），（2，3），（2，4），（2，5），其对应的项目进度计划如图5.7所示。显然，这一多项目进度计划劣于图5.6所示的进度计划。由此可见任务优先规则对调度质量的影响。

图5.7　基于SSGS及LALP的多项目进度计划