构造多项目调度算例库的方法及资源需求分布

Tsai和Chiu（1996）提供了一种构建多项目调度算例库的基本思路。首先，Tsai和Chiu（1996）从文献中搜集了7个项目网络，通过组合这7个项目网络，可以得到多项目网络。Tsai和Chiu（1996）将多项目网络中的独立网络数量限定在4个以内，因此一共得到个多项目网络。然后，为每个任务分配工期和资源需求，分别独立服从区间［1，9］内的均匀分布。最后，再设定资源容量，其取值为区间内的所有整数。如此，一共产生4941个多项目调度问题用于算法测试。但是，这样的构造方法存在明显的不足，一方面项目网络不足以覆盖各种拓扑结构（Tsai and Chiu，1996），另一方面无法实现各种典型的项目特征参数，不利于算法绩效的评估。

Goncalves等（2008）采用了类似的思路。组成多项目调度问题的项目网络随机选自J120单项目调度算例库（Kolisch and Sprecher，1996），而资源容量则设定为各单项目调度问题实例中资源容量之和。但是，由于组合了多个J120项目实例，已经很难保证资源特征参数符合合理的分布。

Lawrence和Morton（1993）从研究多项目延迟成本优化的角度出发构造了所需的算例库。研究设定4种资源数量水平，分别为1、2、3、5。每种资源水平下均构造40个多项目调度实例。每个实例包括5个项目，每个项目的任务数量服从［25，50］之间的均匀分布。每个项目的延迟成本系数服从［1，10］之间的均匀分布。任务工期为服从［1，10］之间均匀分布的整数。每个任务所需资源种类数量不超过3种。任务的最大资源需求比例服从［0.3，1.0］之间的均匀分布；而每个任务的资源需求和最大需求的比例则服从［0.5，1.0］之间的均匀分布。每个项目网络的次序强度OS服从［0.05，0.15］之间的均匀分布[2]。此外，为每个实例设定3个不同的截止时间。因此，一共产生480个延迟成本最小化多项目调度实例。Lawrence和Morton（1993）为多项目算例库构造提供了另一种思路，即不是从单项目算例库中抽取实例进行组合，而是直接进行构造。但是他们的方法未充分考虑多项目调度问题特征参数，因此尚不足以有效分析特征参数对于算法绩效的影响。(www.xing528.com)

Lova等（2000）基于AUF等特征参数进行了实验设计。每个多项目调度实例包括4或8个项目，每个项目包括30或60个任务。每个项目的网络复杂度NC固定为3。AUF取值为0.8或1.2。每个项目涉及5种可更新资源，每个任务平均需要调用2或4种资源，资源系数RF取值为0.4或0.8。因此，一共有2×2×2×2＝16个单元，每个单元产生两个实例，共得到32个多项目调度实例。之后，Lova和Tormos（2001）采用了同样的构造方法。这种构造方法由于采用了全因子设计，且考虑了多项目资源特征参数，相对而言较为成熟。不足之处在于没有将网络复杂度纳入设计参数。此外，如果多项目调度问题的目标函数涉及加权平均，还需要考虑项目权重（刘士新、王梦光，1997）。