单项目调度问题的特征参数优化建议

第2章已经详细描述了项目调度问题数学模型需要分析的主要参数，包括任务工期、紧前关系、资源约束等。但是，这些参数的具体实现及不同组合，会对实际的项目调度产生极大的影响。Davis（1975）提出，对于项目调度问题需要分析的网络特征参数包括以下几类：描述项目网络规模、形状及逻辑结构（紧前关系）的特征参数；项目的时间特性；项目资源需求与供给特征。

现有文献中存在大量刻画项目调度问题的特征参数，根据Zhu和Padman（1997）的统计，主要有30多个参数，可以整理为五大类参数，即项目规模、基于关键路线法的参数、资源、现金流、项目网络结构。但是，其中所列的多数参数对项目调度算法的效率并无直接影响。从计算复杂性的角度出发，现有文献中最广为接受的有以下特征参数。

1.网络复杂度

网络复杂度（network complexity，NC）被定义为AON网络G=（V，E）中每个节点的平均箭线数量（Davis，1975）：

Kolisch等（1995）进一步指出，在估算网络复杂度时应事先剔除冗余箭线。

Browning和Yassine（2010）提出对NC进行规范化：

其中，Emax（Emin）表示具有J个节点的网络的理论最大（最小）箭线数量。因此，网络复杂度NC可以采用式（3.3）进行计算：

不过，目前大多数文献仍然采用式（3.1）计算网络复杂度NC。

上述测度指标被批评为忽略了网络结构的差异性。具有相同NC值的项目网络拓扑结构可能存在巨大差异，因而对应的项目调度问题的计算复杂性也会有明显差别（Demeulemeester，et al.，2003）。因此，一些学者提出了其他复杂度指标来替代NC。De Reyck和Herroelen（1996）对于AOA网络图在约简复杂性（reduction complexity，RC）基础上提出用复杂度指数（complexity index，CI）来取代网络复杂度指标NC。Mastor（1970）在分析生产线平衡问题时，用次序强度（order strength，OS）来刻画网络拓扑结构的复杂度。次序强度定义为网络中有效逻辑关系数量与逻辑关系理论上限的比值。其中，有效逻辑关系不仅指紧前关系，一项任务与其所有前导任务之间也被认为存在逻辑关系。因此，对于一个包括J个非虚拟任务的项目网络图，其有效逻辑关系的理论上限为J×（J−1）/2。例如，图3.1所示的项目AON网络图中，任务1和任务7为虚拟任务，项目一共有5个非虚拟任务，有效逻辑关系数量为5，因此其次序强度OS=5/10=0.5。De Reyck和Herroelen（1996）的分析表明，次序强度OS是比NC等其他测度指标更优的指标。

图3.1　项目网络图次序强度

2.资源系数

资源系数（resource factor，RF）反映任务对各类资源的需求状况（Cooper，1976）。资源系数的计算公式为（Kolisch et al.，1995）：

其中，sgn（·）为符号函数：(www.xing528.com)

资源系数反映了任务资源需求矩阵rjk的密度。如果RF=1，说明每一个任务都需要用到每一种资源；如果RF=0，则表示没有任务需要用到资源，项目调度问题退化成资源不受限项目调度问题，可以采用传统的关键路线法进行求解。

3.资源强度

资源强度（resource strength，RS）用于描述任务资源需求与资源供给之间的关系，即资源的稀缺状况（Cooper，1976）。对某一可更新资源k，其资源强度的计算公式为：

但是，Kolisch等（1995）指出式（3.6）存在缺陷。首先，式（3.6）给出的资源强度没有标准化到［0，1］区间；其次，资源强度较低可能导致无法获得可行进度计划；最后，该公式忽略了项目网络结构对资源需求的影响。因此，需要对式（3.6）进行修正。

在给定项目网络结构（紧前关系）和各任务资源需求的条件下，可以计算各可更新资源的最低供应量和最高供应量。最低供应量仅能满足项目执行的最低资源要求：

而最高供应量则提供了充分的资源，以至于额外的资源供应量并不能加速项目进度，即在增加边际供应量后该资源已不成为约束条件。因此，资源强度可采用（3.8）的计算公式，以反映当前资源供应量的相对稀缺程度（Kolisch et al.，1995）：

Kolisch等（1995）分析了网络复杂度NC、资源系数RF及资源强度RS三个参数对计算复杂性的影响，指出网络复杂性NC的影响最小，而资源系数RF和资源强度RS对计算复杂性的影响都非常显著。在资源系数RF上升时，计算时间明显增加；而在资源强度RS增加时，计算时间明显下降。不过，Demeulemeester等（2003）认为，之所以Kolisch等（1995）的统计分析指出网络复杂性对计算复杂性不具有显著影响，是因为传统的网络复杂性指标NC不足以全面反映网络拓扑结构。

4.资源受限程度

资源受限程度（resource constrainedness，RC）也用于描述资源的稀缺程度，其计算公式为（Demeulemeester et al.，2003）：

其中，为资源k的平均需求量：

对于资源强度RS和资源受限程度RC，现有文献中有很多争论（De Reyck and Herroelen，1996；Kolisch et al.，1995）。因此，有些项目生成软件在设计上采用资源强度RS作为特征参数（Kolisch et al.，1995），有些软件采用资源受限程度RC作为特征参数（刘士新、王梦光，1997），而有些软件则同时提供这两种参数供用户选择（Demeulemeester et al.，2003）。