PSPLIB算例库：优化与实践

由于Patterson算例库存在上述缺陷，因此Kolisch等（1995）开发了一套项目调度问题生成软件ProGen，可以事先指定项目特征参数，然后由ProGen软件产生符合参数要求的具体项目实例。这样，就可以采用实验设计方法产生适用于算法比较分析的大样本算例库。之后，Kolisch和Sprecher（1996）进一步扩展了ProGen的应用，产生了一整套涉及多任务模式的调度问题，从而形成了新的项目调度算例库（project scheduling problem library，PSPLIB）。

PSPLIB包括一系列不同项目规模的算例库。项目规模以任务数量J区分。对于单模式RCPSP问题而言，J30算例库即指任务数量J=30的算例库。单模式项目调度算例库的基本参数如表3.1所示，其中所有项目实例均只涉及可更新资源。

表3.1　单模式项目调度问题库基本参数设定

在表3.1中，J表示项目所包含的实际任务数量（不包括虚拟任务）；Mj为任务j执行模式的数量；pj为任务工期；K是可更新资源种类；R为可更新资源的容量；rj为任务j对资源的需求量；|Sj|为任务j的紧后任务数量；|S1|为虚拟任务1的紧后任务数量，即项目实际上的启动任务数量；|Pj|为任务j的紧前任务数量；|PJ|为虚拟任务J的紧前任务数量，即项目实际上的结束任务数量。

项目实例的详细构造过程参见文献（Kolisch et al.，1995）。为保证所生成的算例库具有足够的代表性，Kolisch和Sprecher（1996）采用全因子实验设计（full factorial design）方法构造算例库。网络复杂度NC、资源系数RF及资源强度RS作为三个控制变量，其取值水平见表3.2。实验一共产生3×4×4＝48个单元（cell）。每个单元分别产生10个项目实例。因此，一共得到480个实例，构成J30算例库。

表3.2　单模式项目调度算例库控制参数设定(www.xing528.com)

类似地，可以设计生成项目规模更大的算例库。J60、J90及J120即指由ProGen产生的项目任务数分别为60、90及120的RCPSP算例库。目前，J30算例库的所有实例均已通过精确算法求得最优项目工期。

如果将问题拓展到多模式项目调度问题，还可以用ProGen计算产生多模式项目调度算例库。Kolisch和Sprecher（1996）在设计MRCPSP算例库时，采用的基本参数与表3.1所列参数略有不同。

Schwind（t1995）在ProGen软件的基础上进行扩展，编制了ProGen/max软件，使其可以在产生的项目实例中包括时间窗约束。Drexl等（2000）进一步同时考虑到部分可更新资源（Bottcher et al.，1999）和任务搭接关系（minimal time-lag），编制了扩展版的项目调度问题生成软件ProGen/πx。

Demeulemeester等（2003）指出上述ProGen等软件的项目调度问题生成机制在构造项目网络时随机性都不够高，而且以上软件均采用传统的网络复杂度指标NC，而该指标无法有效评估项目网络图的拓扑结构复杂性。因此，Demeulemeester等（2003）设计了新的RanGen软件，该软件可以事先指定项目网络图的次序强度OS，并计算项目网络图的复杂度指数CI，在构造过程中则不限定紧前（紧后）任务的最大数量以及开始（结束）任务的最大数量，因此所生成的网络图具有更大随机性。

本章所提及的各算例库均可在PSPLIB网站下载[1]。