进度产生方案

进度产生方案（schedule generation scheme, SGS）的基本思路是从一个局部进度出发，通过将其逐步扩展的方式建立一个可行进度。所谓局部进度是指项目的所有工序中，只有一个工序已经确定开始时间的进度。进度产生方案的每一步都需要对两个工序集合进行更新，这两个工序集合分别为已安排进度的工序集合SJ_g和有资格安排进度的工序集合EJ_g。在进度产生方案的每一步中，首先需要从有资格安排进度的工序集合EJ_g中按照某种规则选择一个或若干个工序，并考虑逻辑关系和资源约束为其安排开始时间；接着对SJ_g和EJ_g进行更新，通过这样的方式逐步建立起一个可行进度。根据工序安排进度的推进方向的不同，进度产生方案可以分为前向进度产生方案和后向进度产生方案；按照工序安排进度的推进增量不同，进度产生方案则又可以分为串行进度产生方案和并行进度产生方案。进度产生方案的分类参见表3.3。

表3.3　进度产生方案的分类

前向进度产生方案与后向进度产生方案的主要区别在于进度安排的推进方向不同。前向进度产生方案是按照前向进度安排顺序，即按照逻辑关系的顺序，通过逐步扩展的方式产生可行进度。后向进度产生方案则是遵循后向进度安排顺序，即按照逻辑关系的逆序，通过逐步扩展的方式产生可行进度。前向串行进度产生方案用于产生可行最早进度计划，后向进度产生方案则用于产生可行最迟进度计划。可行最早进度计划是指在给定的工序进度安排顺序下，满足工序间的逻辑关系约束和资源约束，将工序安排在尽可能早的时间开始。可行最迟进度计划则是指在给定的工序进度安排顺序下，工序在满足逻辑关系和资源约束下尽可能迟地安排开始时间。

对于正则化目标函数的问题，其最优解是一类可行最早进度计划。但对于那些非正则化目标函数的问题，从可行最早进度计划中搜索，往往不能得到最优解。因为在这一类问题中，可行最早进度计划往往不是最优，而可行最迟进度计划往往优于可行最早进度计划。然而，前向进度安排是不可能产生最迟进度计划的，最迟进度计划是由后向进度安排产生的。因此，同时从前向和后向两个方向安排进度，可以产生不同类型的进度计划，从而使算法可以搜索可行域的各个部分，避免某些潜在最优解的丢失。

串行进度产生方案和并行进度产生方案的主要区别在于进度安排的推进增量上。串行进度产生方案是以工序为推进增量，即每一步只安排一个工序的开始时间，同时更新有资格安排进度的工序集合。这样，一个包含n个工序的项目需要n步才能完成可行进度的建立。并行进度产生方案则是以时间作为推进增量，在每一步确定当前的进度安排时间t_g，更新有资格安排进度的工序集合，为所有在当前进度安排时间上可以安排进度的工序确定开始时间。这两种进度产生方案推进增量的不同导致了在每一步安排进度时，选择的工序数目存在差别。串行进度产生方案的每一步只安排一个工序的开始时间，而并行进度产生方案的每一步可能安排不止一个工序的开始时间。

鉴于有研究表明串行进度产生方案优于并行进度产生方案^［146］，同时考虑到项目支付进度安排问题可行解空间的搜索特点，本书主要采用串行进度产生方案。同时为了改善所生成的进度计划的性能，采用结合了前向和后向两种顺序的双向计划进行进度安排。其中，前向进度产生方案用于生成可行最早进度计划；后向进度产生方案则用于生成可行最迟进度计划。前向／后向串行进度产生方案分别按照前向／后向工序进度安排顺序为工序安排开始时间。

一、前向串行进度产生方案

前向串行进度产生方案（forward serial schedule generation scheme, FSSGS）的流程如图3.10所示。它是从一个局部进度PS₁开始，通过n次迭代建立一个可行进度。PS₁中只有起始工序确定了开始时间ST₁＝0。在每一个决策层次g，按照前文所阐述的前向工序进度安排顺序选择工序j_g，在满足逻辑关系约束和资源约束的前提下，确定其最早的开始时间ST_jg，并更新剩余资源的供应量。重复这一过程直至所有工序均确定了开始时间，从而建立起可行最早进度计划。

图3.10中，表示第k种可更新资源在时刻t的剩余供应量；ES_j表示工序j的最早开始时间；UT为项目的工期上限，根据式（3.8）确定：

图3.10　前向串行进度产生方案的流程

二、后向串行进度产生方案

后向串行进度产生方案（backward serial schedule generation scheme, BSSGS）与前向串行进度产生方案的工作原理基本类似，其主要区别在于安排进度的顺序不同。BSSGS是从项目的结束工序开始进行迭代，初始的局部进度是指仅有结束工序已确定开始时间，其他工序均未确定开始时间的进度。BSSGS从这个局部进度开始，通过n次迭代建立可行进度，在每一次迭代中按照后向工序进度安排顺序选择一个工序，在满足逻辑关系约束和资源约束的前提下，尽可能迟地安排其开始时间。通常，按照这样的方式得到的进度将不是从计划时限的起点开始，所以BSSGS还需要对产生的可行进度进行“左移”操作，即将各工序的开始时间减去起始工作的开始时间。BSSGS的流程如图3.11所示。

图3.11　后向串行进度产生方案的流程