并行进度生成的机制与优化

并行进度生成机制以时间为阶段变量，最多包括J个阶段。在每一阶段g，需要确定一个时段tg。然后根据当前的进度计划区分三个任务集合：（1）在时段tg处于完成状态的任务集合，称为已完成任务集合（complete set），记为Cg；（2）Cg在时段tg处于工作状态的任务集合，称为执行任务集合（active set），记为Ag；（3）与SSGS不同，候选任务集合（decision set）包括所有满足紧前关系和资源约束并可以在时段tg开始的任务，记为Dg：

其中，Rk（tg）为资源k在时段tg的剩余资源供应量。

在每一个阶段，PSGS包括两个步骤：（1）设定该阶段的当前时间tg，将集合Ag中所有完成时间等于tg的任务剔除出Ag，并加入已完成任务集合Cg，然后据此更新候选任务集合Dg。（2）根据指定的任务优先规则，从集合Dg中选择一项任务j*，并安排该任务从当前时段tg开始执行；然后该任务j*从候选任务集合Dg迁入集合Ag。重复执行步骤（2）直到候选任务集合Dg为空集，然后转入下一个阶段。当所有任务都属于已完成任务集合Cg或执行任务集合Ag时，PSGS完成调度并终止。

PSGS的伪代码如下所示：

初始化时，设定任务j=1的完成时间为0。每阶段分两步，第一步确定当前时段tg以及三个任务集合；第二步从候选任务集合Dg中选取一个任务，并安排该任务在时段tg开始。然后更新候选任务集合Dg，并继续选取和安排任务，直到候选任务集合Dg为空。在此过程中，每选中一个任务j*，都需要重新计算各资源k的剩余资源供应量：

对于图5.1中的资源受限项目，可以利用并行SGS及任意优先规则产生该项目的可行进度计划。假设选用最多后续任务（most total successor，MTS）优先规则。在任务1完成分配之后，在第二个阶段，当前时段t2=0，候选任务集合D2={2，3，8}。根据MTS规则，选择任务3并安排其开始时间为s3=t2=0。因此，新的执行任务集合A2={3}，并根据式（5.6）更新资源剩余供应量。更新之后，重新计算得到D2={8}。选择任务8，并安排其开始时间为s8=t2=0。继续更新资源剩余供应量，并重新计算得到D2=Φ。于是进入第三个阶段。在第三个阶段，计算得到当前时间t3=3，A3=Φ，C3={1，3，8}，D3={2，4，6}。选择任务2并安排其开始时间为s2=t3=3。因此，新的执行任务集合A3={2}，更新资源剩余供应量，重新计算得到D3={4}。选择任务4并安排其开始时间为s4=t3=3。因此，新的执行任务集合A3={2，4}，更新资源剩余供应量，重新计算得到D3=Φ。第三个阶段结束，进入第四个阶段。计算得到当前时间t4=4，D4=Φ。于是转入第五个阶段，计算得到当前时间t5=6，D5={5，6}。如此继续，逐步产生完整的项目进度计划，如图5.4所示。(www.xing528.com)

图5.4　基于PSGS及MTS的项目进度计划

如果采用MINSLK优先规则，则PSGS得到如图5.3所示的最优进度计划。

PSGS生成的是非延迟进度计划。非延迟进度计划（non-delay schedule，NDS）是指，如果将一个可行进度计划中的每一项任务均拆分成以工期为单位时间的若干子任务，在保持紧前关系和资源约束的要求下，拆分所得的进度计划仍然是积极的，也就是说没有任一子任务可以在满足约束条件的要求下提前开始时间（Sprecher et al.，1995）。显然，一个非延迟进度计划必然是一个积极进度计划。如此，可以确立不同类型项目进度计划之间的关系。对于某一个项目，用S表示所有进度计划的集合，FS表示可行进度计划集合，SAS表示半积极进度计划集合，AS表示积极进度计划集合，NDS表示该项目的非延迟进度计划集合，则有如下关系（Sprecher et al.，1995）：

Kolisch（1996a）证明，利用PSGS与任意优先规则产生的项目进度计划，必然是非延迟进度计划。值得指出的是，对于目标函数为常规目标函数的资源受限项目调度问题来说，PSGS的搜索空间要小于SSGS，但是PSGS所能给出的非延迟进度计划集合有可能不包括问题的最优解。PSGS的时间复杂度为O（J2，K）。