如何优化多项目调度问题的特征参数？

与单项目调度问题不同，多项目调度问题涉及多个独立的项目，而这些项目之间又存在资源竞争。目前对多项目调度问题特征参数的研究相对较少。现有文献中主要存在以下几个多项目特征参数（Kurtulus and Davis，1982；Kurtulus and Narula，1985；Kurtulus，1985）。

1.资源平均负载系数

平均负载系数（average load factor，ALF）用于测度每类资源的高峰需求对项目调度算法绩效的影响。在不考虑资源约束的情况下，利用CPM产生项目的进度计划，则在时段t对资源k的总需求可以表示为：

因此，对于可更新资源k而言，其最大需求为：

用表示发生最大资源需求的时段的相对位置，即其与关键路线长度（critical path length，CPL）的比例；用wζ表示赋予该时段的权重，设定如下（Kurtulus and Davis，1982）：

假设最大资源需求在整个项目执行期间共发生Q次，则利用加权平均对资源k定义如下的最大负载系数（maximum load factor，MLF）：

MLF对于项目调度问题中的任务数量较为敏感。例如，考虑以下两个项目调度问题。问题I包含一个项目，问题II包含两个相同的项目。则问题I的MLF值是问题II的MLF值的一半。因此，将MLF除以调度问题中包含的任务数量，得到平均负载系数（average load factor，ALF），这是一个更合理的指标：

对于涉及多种资源的多项目调度问题，其平均负载系数是如下的向量：

ALF取决于项目网络、任务工期以及任务的资源需求。图3.2给出了常见的几种项目网络形状（Kurtulus and Narula，1985）。如多项目调度问题所包含的项目均类似于图3.2（a）所示的网络结构，则ALF值接近于－3。如多项目调度问题所包含的项目均类似于图3.2（b）所示的网络结构，则ALF值接近于＋3。不同的项目网络的组合，可以产生中间状态的ALF值。

图3.2　项目结构与资源需求

但是，Browning和Yassine（2010）的分析指出，ALF尚不足以全面刻画多项目问题资源分布状况。因此，他们提出采用规范化平均资源负载系数（normalized average resource load factor，NARLF）：

其中，wijt表示相当位置权重，相对式（3.13）而言做了简化，其取值为：(www.xing528.com)

2.资源平均利用系数

另一个资源特征参数是Kurtulus和Davis（1982）提出的平均利用系数（average utilization factor，AUF）。对于某特定资源，其在某特定时段的资源稀缺程度，可以用总的资源需求量与可获得资源量的比值加以衡量。如在任何时段，任何资源的稀缺程度都没有超过1，即说明项目资源并未构成实际约束，那么该多项目问题可以利用CPM产生项目进度计划，在执行过程中也不会因为资源约束造成项目延迟。但是，这样衡量资源稀缺程度有重要的缺陷。首先，对于大项目而言，计算非常烦琐；其次，也无法针对整个项目（或多项目）给出整体测度。因此，需要用某种平均量来表征资源稀缺程度。Kurtulus和Davis（1982）提出根据关键路线来划分整个项目工期。将关键路线按照不严格的升序排列，使得：

其中，CPLi是项目i在不考虑资源约束时按照CPM计算所得的关键路线长度，CPL0则定义为0。

对于资源k，其平均利用系数AUFk为：

其中，Wik是所有项目在区间（CPLi−1，CPLi）内对资源k的总需求量：

对于涉及多种资源的多项目调度问题，AUF是如下的向量：

上述AUF指标也存在不足，当各个项目的关键路线长度比较接近时，AUF不足以很好地刻画资源状况。因此，Browning和Yassine（2010）建议以单位时段取代式（3.19）给出的按关键路线长度划分的时间区段，并将据此计算所得的系数称为修正平均利用系数（modified average utilization factor，MAUF）。

3.其他特征参数

Kurtulus和Narula（1985）将网络复杂度NC作为一个重要的特征参数。但是，根据De Reyck和Herroelen（1996）的分析，次序强度OS可能是更合适的指标。由于多项目调度问题中的各项目相互独立，因此可以分别计算各项目网络的次序强度OS。

另一个常用的项目特征参数是项目规模（project size），即全部项目所包含的任务数量。一般而言，随着项目规模的上升，项目调度问题的复杂度也相应增加，调度算法所需的计算量也就越高。值得注意的是，多数研究事实上采用两个参数来确定项目规模，一是项目数量，另一是任务数量。

资源数量（number of resource types）是另一个项目特征参数。资源种类的多少和资源系数RF有关，也会影响项目调度问题的复杂度。在单项目调度算例库中，并未涉及对资源数量的深入讨论。对于多项目调度问题而言，资源数量尤其重要，因为对不同资源的竞争构成了多项目调度问题的主要矛盾。