项目调度中的测试问题集选取研究

田文迪，许 静，别 黎，崔南方

(1.武汉纺织大学管理学院，湖北 武汉 430073；2.中南民族大学管理学院，湖北 武汉 430074；3.华中科技大学管理学院，湖北 武汉 430074)

1 引言

项目调度问题PSP(Project Scheduling Problems)研究如何在满足资源和紧前关系约束前提下，合理安排项目任务使得某特定目标函数达到最优，它是项目管理中经典的核心内容[1,2]。该问题广泛存在于企业新产品开发、工程建筑、软件开发、飞机及轮船制造等项目中[3]，有着显著的实践价值。项目调度问题自20世纪中期被提出以来，一直受到国内外专家学者的广泛关注，已取得大量研究成果[4～6]，尤其是求解算法得到了深入而广泛的研究，如确定性算法、启发式算法、元启发式算法等[6]。为了测试和比较算法的性能，就需要测试问题集对算法进行测试和比较。

迄今为止，已有大量专家学者从事测试问题集的相关研究。Patterson J[7](1984)最早提出测试单项目资源受限项目调度问题的Patterson问题集，该问题集在国际上一直采用至今。但由于该问题集中的调度问题不是通过设定符合要求的参数生成的，所以不能有效代表项目调度的各种可能性。此外，该问题集中问题已被证明能较易通过精确算法进行求解[8,9]。为了克服这些缺点，许多专家学者开始从事开发用于测试调度问题的软件。Demeulemeester E等人[10](1993)开发了第一个随机问题集生成器，但该生成器仅能够设置项目任务节点数和项目网络结构中的紧前关系，不能用于设定其它某些特定衡量指标，如网络结构复杂度、资源指标等。Agrawal M K等人[11](1996)在此基础上开发了DAGEN问题集生成器，能够设定项目网络结构的复杂度。Kolisch R等人[12,13](1992, 1995)设计出另一问题集生成器ProGen，可以通过设定网络基本结构(网络任务节点数、紧前关系以及网络复杂度)和两个资源指标(资源因子和资源强度)生成相应的问题。Schwindt C等人[14～16](1995, 1996, 1998)对ProGen进行扩展，引入时间约束的概念，设计最小、最大时间滞后调度问题集生成器ProGen/Max。Tavares L V[17](1998)通过设定六项网络结构指标生成调度问题的网络结构，但由于其网络结构不是来自于可行网络结构，所以生成的网络结构不具有强随机性。Demeulemeester E等人[18](2003)开发RanGen问题集生成器，生成的调度问题具有强随机性网络结构，从而能满足所需要的复杂度指标。随后，Vanhoucke M等人[19](2008)在此基础上，扩展RanGen问题集生成器，得到RanGen2问题集生成器。Gutiérrez M等人[20](2004)设计HierGen用于生成多层次项目问题集。Browning T R等人[21](2010)开发了第一个用于生成多项目问题集生成器RCMPSP。

本文主要介绍国际上常用的两套标准问题集(Patterson问题集[7]和PSPLIB标准问题库[12～16])和两款用于生成问题集的软件(单项目调度问题集生成器RanGen[18,19]和多项目调度问题集生成器RCMPSP[20])，并在此基础上提出项目调度中选取测试问题集的一般流程及其问题集构建的一般方法。

2 Patterson 问题集

Patterson问题集是由Patterson J于1984年提出的。该问题集由110个单一模式单项目资源受限项目调度问题组成，其中7～23个任务节点的问题有55个，27～35个任务节点的问题有45个，51个任务节点的问题有10个(见表1)；四个问题只涉及一种可更新资源，三个问题涉及两种可更新资源，其余103个问题涉及三种可更新资源。Patterson问题集可在PSPLIB标准问题库网站中的“other benchmarks”中下载，其问题集中问题的表现形式见表2(以Pat1为例)。

Table 1 No. of problems in Patterson sets表1 Patterson问题集中问题个数分布

Table2 Pat1 problem in Patterson sets表2 Patterson问题集中Pat1问题

第一行中的14表示该问题共有14个任务节点数，3表示涉及三种可更新资源；第二行中的2、1和2分别表示三种不同类型的可更新资源的可用资源量；第三行至第十六行表示Pat1问题所对应网络结构及其特征参数，其中第一列表示各任务节点对应的工期，第二列至第四列表示各任务节点对应三种不同类型的可更新资源的所需资源量，第五列表示各任务节点的后续节点数，第六列至第八列表示各任务节点的后续节点。Patterson问题集虽然过去被广泛使用，但这110个问题不能有效代表项目调度的各种可能性，慢慢被PSPLIB标准问题库所取代。

3 PSPLIB标准问题库

PSPLIB标准问题库，全称Project Scheduling Problem Library(见http://129.187.106.231/psplib/)，是由Kolisch R等人(1992, 1995)采用实验设计的方法设计ProGen软件，通过该软件设定项目调度问题的参数，产生符合参数要求的具有不同目标的调度问题。随后，Schwindt C(1995年、1996年、1998年)在此基础上，对ProGen进行扩展，为适应新模型扩展的需要，增加了对部分可更新资源、倒换时间、模式一致性以及模式一致性集合等概念的支持，设计一套新软件ProGen/Max，从而形成PSPLIB标准问题库。该标准问题库包含以下五种不同类型问题的问题集及其解决方案：(1)资源受限项目调度问题RCPSP(Resource Constrained Project Scheduling Problem)问题集;(2)最小最大时间滞后资源受限项目调度问题RCPSP/Max(Resource Constrained Project Scheduling Problem with minimal and Maximum time lags)问题集;(3)多模式资源受限项目调度问题MRCPSP(Multi-mode Resource Constrained Project Scheduling Problem)问题集;(4)最小最大时间滞后多模式资源受限项目调度问题MRCPSP/Max(Multi-mode Resource Constrained Project Scheduling Problem with minimal and Maximum time lags)问题集;(5)最小最大时间滞后资源投资问题RIP/Max(Resource Investment Problem with minimal and Maximum time lags)问题集。其中，RCPSP问题集和MRCPSP问题集可直接在PSPLIB标准问题库的网站上下载，而RCPSP/Max问题集、MRCPSP/Max问题集和RIP/Max问题集则链接到另一网址http://www.wior.uni-karlsruhe.de/LS_Neumann/Forschung/ProGenMax/下载。

RCPSP问题集中包含任务节点数分别为30、60、90和120，四个子问题集J30、J60、J90和J120，涉及四种可更新资源，每个子问题集中含有480个项目调度问题。MRCPSP问题集中包含字母开头为c、j、m、n和r五组子问题集。其中c开头的问题集包含c15和c20两个子问题集，涉及两种可更新资源和两种不可更新资源，任务节点数都为16，执行模式都为3。j开头的问题集包含任务节点数分别为10、12、14、16、18、20和30的七个子问题集J10、J12、J14、J16、J18、J20和J30，都涉及两种可更新资源和两种不可更新资源，三种执行模式。m开头的问题集包含执行模式分别为1、2、4和5的四个子问题集m1、m2、m4和m5，都涉及两种可更新资源和两种不可更新资源，任务节点数为16。n开头的问题集包含不可更新资源数分别为0、1和3的三个子问题集n0、n1和n3，执行模式都为3，可更新资源数都为2。r开头的问题集包含可更新资源数分别为1、3、4和5的四个子问题集r1、r3、r4和r5，执行模式都为3，不可更新资源数都为2。RCPSP/Max问题集包含cd、UBO和来自于文献[22]的三类子问题集，其中cd问题集包含任务节点数为100、资源数为5的1 080个子问题；UBO问题集则包含任务节点数分别为10、20、50、100、200、500和1 000的七个子问题集testset-ubo10、testset-ubo20、testset-ubo50、testset-ubo100、testset-ubo200、testset-ubo500和testset-ubo1000，每个子问题集都含有90个问题，涉及五种资源；来自于文献[22]的问题集包含任务节点数分别为10、20和30的三个子问题集sm-j10、sm-j20和sm-j30。MRCPSP/Max问题集包含MM和来自于文献[22]的两类子问题集，其中MM问题集包含任务节点数分别为30、50和100的三个子问题集testset-mm30、testset-mm50和testset-mm100；而来自于文献[22]的问题集包含任务节点数分别为10、20和30的子问题集mm-j10、mm-j20和mm-j30，含有2、3或5个执行模式，涉及五种可更新资源和两种不可更新资源。RIP/Max问题集是来自于文献[22]的问题集，包含任务节点数分别为10、20和30的子问题集rip-j10、rip-20和rip-30，都涉及1、3或5个可更新资源。此外，这些问题集中问题的表现形式在下载文件中有详细说明，在此不一一阐述。

4 RanGen问题集生成器

RanGen问题集生成器，包含Demeulemeester E(2003)开发的RanGen1和Vanhoucke M(2008)开发的RanGen2，其开始界面见图1(见网站http://www.projectmanagement.ugent.be/rangen.html)。这两个问题集生成器都包含两类参数：网络拓扑结构和资源。它们的唯一区别在于设定网络拓扑结构的参数不同，这需要在开始界面加以选择。下面分别介绍RanGen问题集生成器需设定的相关参数。

Figure 1 Welcome page of RanGen图1 RanGen问题集生成器开始界面

4.1 RanGen1网络拓扑结构参数

RanGen1问题集生成器表示网络拓扑结构参数有以下三种：

(1)调度问题的任务节点数n(Number of activities)。

(2)排序强度OS(Order Strength)：网络结构中实际紧前关系数除以理论上最大紧前关系数(不包含虚拟节点)，其取值范围为(0,1)。OS越大，表示网络中存在紧前关系约束越多。

(3)复杂度系数CI(Complexity Index)：度量网络结构趋于串行/并行结构的程度。

在开始界面选择RanGen1问题集生成器后，需在“Max#Networks”窗口设置生成问题集的时间限制(Time limit)和问题集中调度问题个数的限制(Maximum number of generated networks)，见图2，再在“Input Parameters”窗口设置问题集中调度问题的任务节点数n和排序强度OS，见图3。随后，RanGen1问题集生成器将在规定时间内迅速计算复杂度系数CI。

Figure 2 “Max#Networks” of RanGen1图2 RanGen1 “Max#Networks”窗口

Figure 3 “Input Parameters” of RanGen1图3 RanGen1 “Input Parameters”窗口

4.2 RanGen2网络拓扑结构参数

RanGen2问题集生成器表示网络拓扑结构参数有以下六种：

(1)网络大小指标I1(Network size indicator)：调度问题的任务节点数I1=n；

(2)串行/并行指标I2(serial/parallel indicator)：

用于度量网络结构是否接近串行网络结构(所有任务节点都在一条链上)或接近并行网络结构(不存在前置任务)，取值范围为[0,1]。当I2=0，表示项目中所有任务节点并行(m=1)；当I2=1，表示项目中所有任务节点串行(m=n)。

(3)任务节点分布指标I3(Activity distribution indicator)：

度量网络结构中在渐进水平上任务节点的分布，取值范围为[0,1]。当I3=0，表示所有任务节点在渐进水平上服从均匀分布；当I3=1，表示渐进水平为m-1的网络宽度为1，渐进水平为1的网络宽度为n-(m-1)。

(4)最短弧指标I4(Short arcs indicator):

度量渐进水平中尾节点与各弧开始节点之间存在差异的短弧的所有紧前关系数，取值范围为[0,1]。当I4=0，表示网络中最短弧的最小数为n-w1；当I4=1，表示网络中各任务节点与下一级任务节点都相连。

(5)最长弧指标I5(Long arcs indicator):

度量渐进水平中尾节点与各弧开始节点之间存在差异的长弧的所有紧前关系数，取值范围为[0,1]。当I5=0，表示网络中有n-w1条弧的长度为1，其它弧的最长长度为m-1；当I5=1，表示网络中所有弧的长度为1。

(6)拓扑浮动指标I6(Topological float indicator):

用于度量项目网络结构中渐进和回归水平之间存在差异的任务节点的拓扑浮动因子，取值范围为[0,1]。当I6=0，表示网络中所有任务节点的拓扑浮动因子为0；当I6=1，表示网络中有m个串行任务节点的拓扑浮动因子为0，有n-m个并行任务节点的拓扑浮动因子为m-1。

在开始界面选择RanGen2问题集生成器后，同样需在“Max#Networks”窗口设置生成问题集的时间限制(Time limit)和问题集中调度问题个数的限制(Maximum number of generated networks)，同图2，然后再在“Input Parameters”窗口设置问题集中调度问题的任务节点数I1和串行/并行指标I2，见图4。随后，RanGen2问题集生成器将在规定时间内迅速计算I3、I4、I5和I6，见图5。

Figure 4 “Input Parameters” of RanGen2图4 RanGen2 “Input Parameters”窗口

Figure 5 “Morphological Measures” of RanGen2图5 RanGen2 “Morphological Measures”

4.3 RanGen1和RanGen2资源参数

RanGen1和RanGen2问题集生成器中“Resource Related Measures”窗口设置三大类资源参数：资源类型数(Number of resources)、资源要求量(Resource requirement measures)和资源需求量(Resource demand measures)，见图6。其中资源要求量是用来决定各任务节点的资源类型，它有两个备选指标参数：

(1)资源因子RF(Resource Factor):

(2)资源使用量RUi(Resource Use):

而资源需求量则是确定各任务节点的资源可用量，也有两个备选指标参数：

(1)资源强度RSk(Resource Strength):

(2)资源约束度RCk(Resource constrainedness):

Figure 6 “Resource Related Measures” window图6 “Resource Related Measures”窗口

5 RCMPSP问题集生成器及其问题集

RCMPSP问题集生成器是由Browning T R等人于2010年在Microsoft office excel平台上设计而成的，设定参数见表3。

Table 3 Input parameters in RCMPSP generator表3 RCMPSP问题集生成器输入参数

Figure 7 Test Bank in the Excel sheet图7 Excel工作簿中概括性工作表“Test Bank”

RCMPSP问题集可在网站http://sbuweb.tcu.edu/tbrowning/RCMPSPinstances.htm下载。该问题集共包含12 320个子问题，每个子问题含有三个子项目，每个子项目有20个任务节点和四种资源，并且子项目是用设计结构矩阵DSM(Design Structure Matrix)的形式表示。RCMPSP问题集分别存放在20个文件夹中(由于这20个文件夹是复制而成的，所以含有相同的电子表格结构和VBA代码，仅仅随机生成的问题不同)，即每个文件夹包含616个子问题，这616个子问题分别存放在八个Excel工作簿中，每个Excel工作簿含有77个独立的子问题工作表和一个位于首端的概括性工作表“Test Bank”(见图7)。此外，每个Excel工作簿还含有RCMPSP问题集生成器代码，当按概括性工作表中的“Generate TestBank”键或启动宏文件时，将重新生成不同的子问题。这八个Excel工作簿的区别在于复杂度期望值(四个等级：“HHH”、“HHL”、“HLL”或“LLL”)和MAUF期望方差(两个等级：0或0.25)的不同，而工作簿中77个独立子问题的区别在于NARLF期望值([-3，3]之间七个不同整数等级)和MAUF期望值([0.6，1.6]之间以0.1为递增的11个不同等级)的不同。用户可以根据自己的需要设置上述参数生成相应的问题集。

6 测试问题集选取一般流程及测试问题集构建方法的有效性分析

6.1 测试问题集选取一般流程及测试问题集构建方法

项目调度中测试问题集选取的一般流程如下(见图8)：

Step1根据需测试PSP确定项目的个数，判断其是单项目PSP还是多项目PSP。若为单项目PSP，转Step 2；反之，若为多项目PSP，转Step 3。

Step2在确定需测试PSP是单项目PSP后，判断PSP的类型：单模式或多模式PSP。若为单模式PSP，转Step 4；反之，若为多模式PSP，转Step 5。

Step3在确定需测试PSP是多项目PSP后，判断所需测试问题集是否能由RCMPSP问题集生成器生成。若能，转Step 6；反之，转Step 12。

Step4在确定需测试PSP是单模式单项目PSP后，判断所需测试问题集是否能直接采用现成问题集(Patterson问题集或PSPLIB标准问题库中相应问题集)，若能，转Step 7；若不能，转Step 8。

Step5在确定需测试PSP是多模式单项目PSP后，判断所需测试问题集是否能直接采用PSPLIB问题库中相应问题集，若能，转Step 9；若不能，转Step 10。

Step6利用RCMPSP问题集生成器生成满足相关要求的多项目调度问题的测试问题集。

Step7选用Patterson问题集或PSPLIB标准问题库中相应问题集。

Step8是否能直接采用ProGen、ProGen/Max或RanGen问题集生成器生成问题集，若能，转Step11；若不能，转Step 12。

Step9选用PSPLIB标准问题库中问题集。

Step10是否能直接采用ProGen、ProGen/Max或RanGen问题集生成器生成问题集，若能，转Step 11；若不能，转Step 12。

Figure 8 Flow chat of instances sets selection in project scheduling problems图8 项目调度中测试问题集选取流程图

Step11根据需求，利用ProGen、ProGen/

Max问题集生成器或RanGen问题集生成器生成满足相关要求的单项目PSP的测试问题集。

Step12根据需求，构建合适的、满足要求的测试问题集。

在测试问题集选取的一般流程中发现：当不能从现有国际上常用问题库中选用合适问题集时，或不能采用常用问题集生成器生成合适问题集时，就需要构建合适、满足测试需求的问题集。通常，构建测试问题集一般分两步：第一，根据需求构建问题集的网络结构(包括大小、形状、复杂度等)；第二，根据需求构建其它参数(可用资源量、资源需求量等)。

6.2 有效性分析及应用前景

下面分别以文献[23]和文献[24]中所采用的测试问题集来说明测试问题集选取一般流程与测试问题集构建方法的有效性。

文献[23]研究MRCPSP的反应式调度算法，作者选用PSPLIB标准问题库中MRCPSP子问题库中问题集作为测试问题集。下面根据测试问题集选取的一般流程进行分析。Step1：判断研究的问题是属于单项目PSP，转Step2；Step2：判断其为多模式PSP，转Step5；Step5：判断可能直接从PSPLIB标准问题库选取合适问题集，转Step9；Step9：选用PSPLIB标准问题库中MRCPSP子问题库中问题集。

文献[24]为了进行离散时间/资源权衡问题DTRTP(Discrete Time/Resource Trade-off Problem)中调度策略比较研究，构建了DTRTP问题集。下面根据测试问题集选取的一般流程进行分析。Step1：判断研究的问题是属于单项目PSP，转Step2； Step2：由于DTRTP是MRCPSP子问题，判断其为多模式PSP，转Step5；Step5：判断不能直接从PSPLIB标准问题库中MRCPSP子问题库中选取合适问题集(虽然DTRTP是MRCPSP子问题，但DTRTP区别于MRCPSP有两个方面：DTRTP仅含有一种可更新资源，而MRCPSP问题集中问题至少含有两种资源；MRCPSP中任务的执行模式数以及在此执行模式下任务工期和所需资源量都是已知的，而DTRTP仅已知工作量，需由工作量转化成工期和所需资源量，并计算相应模式数)，转Step10；Step10：同理不能直接采用ProGen、ProGen/Max或RanGen问题集生成器生成问题集，转Step12；Step12：需根据需求构建合适的、满足要求的测试问题集。文献[24]首先选用PSPLIB标准问题库中MRCPSP子问题库中任务节点为10的网络结构作为测试DTRTP问题集的网络结构；然后，DTRTP工作量的均值及方差分别来自于[10,50]和[1,5]均匀分布；最后，由于需比较可用资源量的影响，所以选取10、15、20三种不同层次的可用资源量，这就意味着会生成可用资源量分别为10、15和20的三类测试问题集。

通过对文献[23]和文献[24]所采用的测试问题集的分析，说明本文提出的测试问题集选取一般流程与测试问题集构建方法是有效的，该方法可以广泛应用于项目调度问题中测试问题集的选取与构建。这不仅为今后项目调度问题中进行算法测试所需问题集的选取及构建提供了一种思路，而且还对采用的测试问题集起到规范作用。

7 结束语

测试问题集的提出及研究是为了更好比较项目调度问题中求解算法的性能。本文在介绍国际上常用的两套标准问题集和两款用于生成问题集的软件的基础上，提出测试问题集选取的一般流程及其问题集构建方法，为算法测试所需问题集提供思路。

[1] Tavares LV. A review of the contribution of operational research to project management [J]. European Journal of Operational Research, 2002,136(1):1-18.

[2] Zhang Jing-wen, Xu Yu, He Zheng-wen, et al. A review on the time/cost trade-offs problem in project scheduling [J]. Journal of Industrial Engineering and Engineering Management, 2007, 21(1):92-97. (in Chinese)

[3] De Reyck B. Scheduling project with generalized precedence relations:Exact and heuristic approach [D]. Leuven:Katholieke Universiteit Leuven, 1998.

[4] Brucker P, Drexl A, Möhring R, et al. Resource-constrained project scheduling:Notation, classification, models and methods [J]. European Journal of Operational Research, 1999,112:3-41.

[5] Herroelen W,De Reyck B,Demeulemeester E.Resource constrained scheduling:A survey of recent developments [J]. Computers and Operations Research, 1998, 25:279-302.

[6] Demeulemeester E, Herroelen W. Project scheduling-A research handbook [M].Boston:Kluwer Academic Publishers, 2002.

[7] Patterson J. A comparison of exact procedures for solving the multiple constrained resource project scheduling problem [J]. Management Science, 1984, 30:854-867.

[8] Demeulemeester E, Herroelen W. A branch-and-bound procedure for the multiple resource-constrained project scheduling problem[J]. Management Science, 1992, 38(12):1803-1818.

[9] Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems[J]. Management Science, 1995, 41(10):1693-1703.

[10] Demeulemeester E, Dodin B, Herroelen W. A random activity network generator [J]. Operations Research, 1993, 41(5):972-980.

[11] Agrawal M K, Elmaghraby S E, Herroelen W S. DAGEN:A generator of test sets for project activity nets [J]. European Journal of Operational Research, 1996, 90(2):376-382.

[12] Kolisch R, Sprecher A, Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems[R]. Kiel, Germany, 1992.

[13] Kolisch R,Sprecher A.PSPLIB-A project scheduling library [J]. European Journal of Operational Research, 1996, 96:205-216.

[14] Schwindt C. A new problem generator for different resource constrained project scheduling problems with minimal and maximal time lags [R]. WIOR-Report-449, Karlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, 1995.

[15] Schwindt C.Generation of resource-constrained project scheduling problems with minimal and maximal time lags [R]. WIOR-Report-489,VKarlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, 1996.

[16] Schwindt C.Generation of resource-constrained project scheduling problems subject to temporal constraints [R]. WIOR Report-543, Karlsruhe, Germany:Institut für Wirtschaftstheorie und Operations Research, Universität Karlsruhe, 1998.

[17] Tavares L V.Advanced models for project management [M].Boston:Kluwer Academic Publisher,1998.

[18] Vanhoucke M, Demeulemeester E, Herroelen W. RanGen:A random network generator for activity-on-the-node networks [J]. Journal of Scheduling, 2003, 6(1):13-34.

[19] Vanhoucke M,Coelho J,Tavares L,et al.An evaluation of the adequacy of network generators with systematically sampled networks [J]. European Journal of Operational Research, 2008, 187(2):521-524.

[20] Gutiérrez M, Durán A, Alegre D, et al. Hiergen:a computer tool for the generation of activity-on-the-node hierarchical project networks [C]∥Proc of the Computational Science and Its Applications—ICCSA, Part III, Assisi, 2004:857-866.

[21] Browning T R,Yassine A A.A random generator of resource-constrained multi-project network problems [J]. Journal of Scheduling, 2010, 13(2):143-161.

[22] Weglarz J. Project scheduling:Recent models, algorithms and applications[M]. Boston:Kluwer Academic Publisher, 1999.

[23] Deblaere F,Demeulemeester E,Herroelen W.Reactive schedu-

ling in the multi-mode RCPSP[J]. Computers and Operations Research, 2011, 38(1):63-74.

[24] Tian W,Demeulemeester E.On the interaction between roadrunner or railway scheduling and priority lists or resource flow networks [J]. Flexible Services and Manufacturing Journal, 2012, DOI:10.1007/s10696-012-9145-4.

附中文参考文献：

[2] 张静文, 徐渝, 何正文，等, 项目调度中的时间/费用权衡问题研究综述 [J]. 管理工程学报，2007，21(1):92-97.