田文迪，許 靜，別 黎，崔南方

(1.武漢紡織大學(xué)管理學(xué)院，湖北 武漢 430073；2.中南民族大學(xué)管理學(xué)院，湖北 武漢 430074；3.華中科技大學(xué)管理學(xué)院，湖北 武漢 430074)

1 引言

項(xiàng)目調(diào)度問(wèn)題PSP(Project Scheduling Problems)研究如何在滿足資源和緊前關(guān)系約束前提下，合理安排項(xiàng)目任務(wù)使得某特定目標(biāo)函數(shù)達(dá)到最優(yōu)，它是項(xiàng)目管理中經(jīng)典的核心內(nèi)容[1,2]。該問(wèn)題廣泛存在于企業(yè)新產(chǎn)品開發(fā)、工程建筑、軟件開發(fā)、飛機(jī)及輪船制造等項(xiàng)目中[3]，有著顯著的實(shí)踐價(jià)值。項(xiàng)目調(diào)度問(wèn)題自20世紀(jì)中期被提出以來(lái)，一直受到國(guó)內(nèi)外專家學(xué)者的廣泛關(guān)注，已取得大量研究成果[4～6]，尤其是求解算法得到了深入而廣泛的研究，如確定性算法、啟發(fā)式算法、元啟發(fā)式算法等[6]。為了測(cè)試和比較算法的性能，就需要測(cè)試問(wèn)題集對(duì)算法進(jìn)行測(cè)試和比較。

迄今為止，已有大量專家學(xué)者從事測(cè)試問(wèn)題集的相關(guān)研究。Patterson J[7](1984)最早提出測(cè)試單項(xiàng)目資源受限項(xiàng)目調(diào)度問(wèn)題的Patterson問(wèn)題集，該問(wèn)題集在國(guó)際上一直采用至今。但由于該問(wèn)題集中的調(diào)度問(wèn)題不是通過(guò)設(shè)定符合要求的參數(shù)生成的，所以不能有效代表項(xiàng)目調(diào)度的各種可能性。此外，該問(wèn)題集中問(wèn)題已被證明能較易通過(guò)精確算法進(jìn)行求解[8,9]。為了克服這些缺點(diǎn)，許多專家學(xué)者開始從事開發(fā)用于測(cè)試調(diào)度問(wèn)題的軟件。Demeulemeester E等人[10](1993)開發(fā)了第一個(gè)隨機(jī)問(wèn)題集生成器，但該生成器僅能夠設(shè)置項(xiàng)目任務(wù)節(jié)點(diǎn)數(shù)和項(xiàng)目網(wǎng)絡(luò)結(jié)構(gòu)中的緊前關(guān)系，不能用于設(shè)定其它某些特定衡量指標(biāo)，如網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜度、資源指標(biāo)等。Agrawal M K等人[11](1996)在此基礎(chǔ)上開發(fā)了DAGEN問(wèn)題集生成器，能夠設(shè)定項(xiàng)目網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜度。Kolisch R等人[12,13](1992, 1995)設(shè)計(jì)出另一問(wèn)題集生成器ProGen，可以通過(guò)設(shè)定網(wǎng)絡(luò)基本結(jié)構(gòu)(網(wǎng)絡(luò)任務(wù)節(jié)點(diǎn)數(shù)、緊前關(guān)系以及網(wǎng)絡(luò)復(fù)雜度)和兩個(gè)資源指標(biāo)(資源因子和資源強(qiáng)度)生成相應(yīng)的問(wèn)題。Schwindt C等人[14～16](1995, 1996, 1998)對(duì)ProGen進(jìn)行擴(kuò)展，引入時(shí)間約束的概念，設(shè)計(jì)最小、最大時(shí)間滯后調(diào)度問(wèn)題集生成器ProGen/Max。Tavares L V[17](1998)通過(guò)設(shè)定六項(xiàng)網(wǎng)絡(luò)結(jié)構(gòu)指標(biāo)生成調(diào)度問(wèn)題的網(wǎng)絡(luò)結(jié)構(gòu)，但由于其網(wǎng)絡(luò)結(jié)構(gòu)不是來(lái)自于可行網(wǎng)絡(luò)結(jié)構(gòu)，所以生成的網(wǎng)絡(luò)結(jié)構(gòu)不具有強(qiáng)隨機(jī)性。Demeulemeester E等人[18](2003)開發(fā)RanGen問(wèn)題集生成器，生成的調(diào)度問(wèn)題具有強(qiáng)隨機(jī)性網(wǎng)絡(luò)結(jié)構(gòu)，從而能滿足所需要的復(fù)雜度指標(biāo)。隨后，Vanhoucke M等人[19](2008)在此基礎(chǔ)上，擴(kuò)展RanGen問(wèn)題集生成器，得到RanGen2問(wèn)題集生成器。Gutiérrez M等人[20](2004)設(shè)計(jì)HierGen用于生成多層次項(xiàng)目問(wèn)題集。Browning T R等人[21](2010)開發(fā)了第一個(gè)用于生成多項(xiàng)目問(wèn)題集生成器RCMPSP。

本文主要介紹國(guó)際上常用的兩套標(biāo)準(zhǔn)問(wèn)題集(Patterson問(wèn)題集[7]和PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)[12～16])和兩款用于生成問(wèn)題集的軟件(單項(xiàng)目調(diào)度問(wèn)題集生成器RanGen[18,19]和多項(xiàng)目調(diào)度問(wèn)題集生成器RCMPSP[20])，并在此基礎(chǔ)上提出項(xiàng)目調(diào)度中選取測(cè)試問(wèn)題集的一般流程及其問(wèn)題集構(gòu)建的一般方法。

2 Patterson 問(wèn)題集

Patterson問(wèn)題集是由Patterson J于1984年提出的。該問(wèn)題集由110個(gè)單一模式單項(xiàng)目資源受限項(xiàng)目調(diào)度問(wèn)題組成，其中7～23個(gè)任務(wù)節(jié)點(diǎn)的問(wèn)題有55個(gè)，27～35個(gè)任務(wù)節(jié)點(diǎn)的問(wèn)題有45個(gè)，51個(gè)任務(wù)節(jié)點(diǎn)的問(wèn)題有10個(gè)(見表1)；四個(gè)問(wèn)題只涉及一種可更新資源，三個(gè)問(wèn)題涉及兩種可更新資源，其余103個(gè)問(wèn)題涉及三種可更新資源。Patterson問(wèn)題集可在PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)網(wǎng)站中的“other benchmarks”中下載，其問(wèn)題集中問(wèn)題的表現(xiàn)形式見表2(以Pat1為例)。

Table 1 No. of problems in Patterson sets表1 Patterson問(wèn)題集中問(wèn)題個(gè)數(shù)分布

Table2 Pat1 problem in Patterson sets表2 Patterson問(wèn)題集中Pat1問(wèn)題

第一行中的14表示該問(wèn)題共有14個(gè)任務(wù)節(jié)點(diǎn)數(shù)，3表示涉及三種可更新資源；第二行中的2、1和2分別表示三種不同類型的可更新資源的可用資源量；第三行至第十六行表示Pat1問(wèn)題所對(duì)應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)及其特征參數(shù)，其中第一列表示各任務(wù)節(jié)點(diǎn)對(duì)應(yīng)的工期，第二列至第四列表示各任務(wù)節(jié)點(diǎn)對(duì)應(yīng)三種不同類型的可更新資源的所需資源量，第五列表示各任務(wù)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)數(shù)，第六列至第八列表示各任務(wù)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)。Patterson問(wèn)題集雖然過(guò)去被廣泛使用，但這110個(gè)問(wèn)題不能有效代表項(xiàng)目調(diào)度的各種可能性，慢慢被PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)所取代。

3 PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)

PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)，全稱Project Scheduling Problem Library(見http://129.187.106.231/psplib/)，是由Kolisch R等人(1992, 1995)采用實(shí)驗(yàn)設(shè)計(jì)的方法設(shè)計(jì)ProGen軟件，通過(guò)該軟件設(shè)定項(xiàng)目調(diào)度問(wèn)題的參數(shù)，產(chǎn)生符合參數(shù)要求的具有不同目標(biāo)的調(diào)度問(wèn)題。隨后，Schwindt C(1995年、1996年、1998年)在此基礎(chǔ)上，對(duì)ProGen進(jìn)行擴(kuò)展，為適應(yīng)新模型擴(kuò)展的需要，增加了對(duì)部分可更新資源、倒換時(shí)間、模式一致性以及模式一致性集合等概念的支持，設(shè)計(jì)一套新軟件ProGen/Max，從而形成PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)。該標(biāo)準(zhǔn)問(wèn)題庫(kù)包含以下五種不同類型問(wèn)題的問(wèn)題集及其解決方案：(1)資源受限項(xiàng)目調(diào)度問(wèn)題RCPSP(Resource Constrained Project Scheduling Problem)問(wèn)題集;(2)最小最大時(shí)間滯后資源受限項(xiàng)目調(diào)度問(wèn)題RCPSP/Max(Resource Constrained Project Scheduling Problem with minimal and Maximum time lags)問(wèn)題集;(3)多模式資源受限項(xiàng)目調(diào)度問(wèn)題MRCPSP(Multi-mode Resource Constrained Project Scheduling Problem)問(wèn)題集;(4)最小最大時(shí)間滯后多模式資源受限項(xiàng)目調(diào)度問(wèn)題MRCPSP/Max(Multi-mode Resource Constrained Project Scheduling Problem with minimal and Maximum time lags)問(wèn)題集;(5)最小最大時(shí)間滯后資源投資問(wèn)題RIP/Max(Resource Investment Problem with minimal and Maximum time lags)問(wèn)題集。其中，RCPSP問(wèn)題集和MRCPSP問(wèn)題集可直接在PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)的網(wǎng)站上下載，而RCPSP/Max問(wèn)題集、MRCPSP/Max問(wèn)題集和RIP/Max問(wèn)題集則鏈接到另一網(wǎng)址http://www.wior.uni-karlsruhe.de/LS_Neumann/Forschung/ProGenMax/下載。

RCPSP問(wèn)題集中包含任務(wù)節(jié)點(diǎn)數(shù)分別為30、60、90和120，四個(gè)子問(wèn)題集J30、J60、J90和J120，涉及四種可更新資源，每個(gè)子問(wèn)題集中含有480個(gè)項(xiàng)目調(diào)度問(wèn)題。MRCPSP問(wèn)題集中包含字母開頭為c、j、m、n和r五組子問(wèn)題集。其中c開頭的問(wèn)題集包含c15和c20兩個(gè)子問(wèn)題集，涉及兩種可更新資源和兩種不可更新資源，任務(wù)節(jié)點(diǎn)數(shù)都為16，執(zhí)行模式都為3。j開頭的問(wèn)題集包含任務(wù)節(jié)點(diǎn)數(shù)分別為10、12、14、16、18、20和30的七個(gè)子問(wèn)題集J10、J12、J14、J16、J18、J20和J30，都涉及兩種可更新資源和兩種不可更新資源，三種執(zhí)行模式。m開頭的問(wèn)題集包含執(zhí)行模式分別為1、2、4和5的四個(gè)子問(wèn)題集m1、m2、m4和m5，都涉及兩種可更新資源和兩種不可更新資源，任務(wù)節(jié)點(diǎn)數(shù)為16。n開頭的問(wèn)題集包含不可更新資源數(shù)分別為0、1和3的三個(gè)子問(wèn)題集n0、n1和n3，執(zhí)行模式都為3，可更新資源數(shù)都為2。r開頭的問(wèn)題集包含可更新資源數(shù)分別為1、3、4和5的四個(gè)子問(wèn)題集r1、r3、r4和r5，執(zhí)行模式都為3，不可更新資源數(shù)都為2。RCPSP/Max問(wèn)題集包含cd、UBO和來(lái)自于文獻(xiàn)[22]的三類子問(wèn)題集，其中cd問(wèn)題集包含任務(wù)節(jié)點(diǎn)數(shù)為100、資源數(shù)為5的1 080個(gè)子問(wèn)題；UBO問(wèn)題集則包含任務(wù)節(jié)點(diǎn)數(shù)分別為10、20、50、100、200、500和1 000的七個(gè)子問(wèn)題集testset-ubo10、testset-ubo20、testset-ubo50、testset-ubo100、testset-ubo200、testset-ubo500和testset-ubo1000，每個(gè)子問(wèn)題集都含有90個(gè)問(wèn)題，涉及五種資源；來(lái)自于文獻(xiàn)[22]的問(wèn)題集包含任務(wù)節(jié)點(diǎn)數(shù)分別為10、20和30的三個(gè)子問(wèn)題集sm-j10、sm-j20和sm-j30。MRCPSP/Max問(wèn)題集包含MM和來(lái)自于文獻(xiàn)[22]的兩類子問(wèn)題集，其中MM問(wèn)題集包含任務(wù)節(jié)點(diǎn)數(shù)分別為30、50和100的三個(gè)子問(wèn)題集testset-mm30、testset-mm50和testset-mm100；而來(lái)自于文獻(xiàn)[22]的問(wèn)題集包含任務(wù)節(jié)點(diǎn)數(shù)分別為10、20和30的子問(wèn)題集mm-j10、mm-j20和mm-j30，含有2、3或5個(gè)執(zhí)行模式，涉及五種可更新資源和兩種不可更新資源。RIP/Max問(wèn)題集是來(lái)自于文獻(xiàn)[22]的問(wèn)題集，包含任務(wù)節(jié)點(diǎn)數(shù)分別為10、20和30的子問(wèn)題集rip-j10、rip-20和rip-30，都涉及1、3或5個(gè)可更新資源。此外，這些問(wèn)題集中問(wèn)題的表現(xiàn)形式在下載文件中有詳細(xì)說(shuō)明，在此不一一闡述。

4 RanGen問(wèn)題集生成器

RanGen問(wèn)題集生成器，包含Demeulemeester E(2003)開發(fā)的RanGen1和Vanhoucke M(2008)開發(fā)的RanGen2，其開始界面見圖1(見網(wǎng)站http://www.projectmanagement.ugent.be/rangen.html)。這兩個(gè)問(wèn)題集生成器都包含兩類參數(shù)：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和資源。它們的唯一區(qū)別在于設(shè)定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的參數(shù)不同，這需要在開始界面加以選擇。下面分別介紹RanGen問(wèn)題集生成器需設(shè)定的相關(guān)參數(shù)。

Figure 1 Welcome page of RanGen圖1 RanGen問(wèn)題集生成器開始界面

4.1 RanGen1網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)參數(shù)

RanGen1問(wèn)題集生成器表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)參數(shù)有以下三種：

(1)調(diào)度問(wèn)題的任務(wù)節(jié)點(diǎn)數(shù)n(Number of activities)。

(2)排序強(qiáng)度OS(Order Strength)：網(wǎng)絡(luò)結(jié)構(gòu)中實(shí)際緊前關(guān)系數(shù)除以理論上最大緊前關(guān)系數(shù)(不包含虛擬節(jié)點(diǎn))，其取值范圍為(0,1)。OS越大，表示網(wǎng)絡(luò)中存在緊前關(guān)系約束越多。

(3)復(fù)雜度系數(shù)CI(Complexity Index)：度量網(wǎng)絡(luò)結(jié)構(gòu)趨于串行/并行結(jié)構(gòu)的程度。

在開始界面選擇RanGen1問(wèn)題集生成器后，需在“Max#Networks”窗口設(shè)置生成問(wèn)題集的時(shí)間限制(Time limit)和問(wèn)題集中調(diào)度問(wèn)題個(gè)數(shù)的限制(Maximum number of generated networks)，見圖2，再在“Input Parameters”窗口設(shè)置問(wèn)題集中調(diào)度問(wèn)題的任務(wù)節(jié)點(diǎn)數(shù)n和排序強(qiáng)度OS，見圖3。隨后，RanGen1問(wèn)題集生成器將在規(guī)定時(shí)間內(nèi)迅速計(jì)算復(fù)雜度系數(shù)CI。

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

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

4.2 RanGen2網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)參數(shù)

RanGen2問(wèn)題集生成器表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)參數(shù)有以下六種：

(1)網(wǎng)絡(luò)大小指標(biāo)I1(Network size indicator)：調(diào)度問(wèn)題的任務(wù)節(jié)點(diǎn)數(shù)I1=n；

(2)串行/并行指標(biāo)I2(serial/parallel indicator)：

用于度量網(wǎng)絡(luò)結(jié)構(gòu)是否接近串行網(wǎng)絡(luò)結(jié)構(gòu)(所有任務(wù)節(jié)點(diǎn)都在一條鏈上)或接近并行網(wǎng)絡(luò)結(jié)構(gòu)(不存在前置任務(wù))，取值范圍為[0,1]。當(dāng)I2=0，表示項(xiàng)目中所有任務(wù)節(jié)點(diǎn)并行(m=1)；當(dāng)I2=1，表示項(xiàng)目中所有任務(wù)節(jié)點(diǎn)串行(m=n)。

(3)任務(wù)節(jié)點(diǎn)分布指標(biāo)I3(Activity distribution indicator)：

度量網(wǎng)絡(luò)結(jié)構(gòu)中在漸進(jìn)水平上任務(wù)節(jié)點(diǎn)的分布，取值范圍為[0,1]。當(dāng)I3=0，表示所有任務(wù)節(jié)點(diǎn)在漸進(jìn)水平上服從均勻分布；當(dāng)I3=1，表示漸進(jìn)水平為m-1的網(wǎng)絡(luò)寬度為1，漸進(jìn)水平為1的網(wǎng)絡(luò)寬度為n-(m-1)。

(4)最短弧指標(biāo)I4(Short arcs indicator):

度量漸進(jìn)水平中尾節(jié)點(diǎn)與各弧開始節(jié)點(diǎn)之間存在差異的短弧的所有緊前關(guān)系數(shù)，取值范圍為[0,1]。當(dāng)I4=0，表示網(wǎng)絡(luò)中最短弧的最小數(shù)為n-w1；當(dāng)I4=1，表示網(wǎng)絡(luò)中各任務(wù)節(jié)點(diǎn)與下一級(jí)任務(wù)節(jié)點(diǎn)都相連。

(5)最長(zhǎng)弧指標(biāo)I5(Long arcs indicator):

度量漸進(jìn)水平中尾節(jié)點(diǎn)與各弧開始節(jié)點(diǎn)之間存在差異的長(zhǎng)弧的所有緊前關(guān)系數(shù)，取值范圍為[0,1]。當(dāng)I5=0，表示網(wǎng)絡(luò)中有n-w1條弧的長(zhǎng)度為1，其它弧的最長(zhǎng)長(zhǎng)度為m-1；當(dāng)I5=1，表示網(wǎng)絡(luò)中所有弧的長(zhǎng)度為1。

(6)拓?fù)涓?dòng)指標(biāo)I6(Topological float indicator):

用于度量項(xiàng)目網(wǎng)絡(luò)結(jié)構(gòu)中漸進(jìn)和回歸水平之間存在差異的任務(wù)節(jié)點(diǎn)的拓?fù)涓?dòng)因子，取值范圍為[0,1]。當(dāng)I6=0，表示網(wǎng)絡(luò)中所有任務(wù)節(jié)點(diǎn)的拓?fù)涓?dòng)因子為0；當(dāng)I6=1，表示網(wǎng)絡(luò)中有m個(gè)串行任務(wù)節(jié)點(diǎn)的拓?fù)涓?dòng)因子為0，有n-m個(gè)并行任務(wù)節(jié)點(diǎn)的拓?fù)涓?dòng)因子為m-1。

在開始界面選擇RanGen2問(wèn)題集生成器后，同樣需在“Max#Networks”窗口設(shè)置生成問(wèn)題集的時(shí)間限制(Time limit)和問(wèn)題集中調(diào)度問(wèn)題個(gè)數(shù)的限制(Maximum number of generated networks)，同圖2，然后再在“Input Parameters”窗口設(shè)置問(wèn)題集中調(diào)度問(wèn)題的任務(wù)節(jié)點(diǎn)數(shù)I1和串行/并行指標(biāo)I2，見圖4。隨后，RanGen2問(wèn)題集生成器將在規(guī)定時(shí)間內(nèi)迅速計(jì)算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資源參數(shù)

RanGen1和RanGen2問(wèn)題集生成器中“Resource Related Measures”窗口設(shè)置三大類資源參數(shù)：資源類型數(shù)(Number of resources)、資源要求量(Resource requirement measures)和資源需求量(Resource demand measures)，見圖6。其中資源要求量是用來(lái)決定各任務(wù)節(jié)點(diǎn)的資源類型，它有兩個(gè)備選指標(biāo)參數(shù)：

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

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

而資源需求量則是確定各任務(wù)節(jié)點(diǎn)的資源可用量，也有兩個(gè)備選指標(biāo)參數(shù)：

(1)資源強(qiáng)度RSk(Resource Strength):

(2)資源約束度RCk(Resource constrainedness):

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

5 RCMPSP問(wèn)題集生成器及其問(wèn)題集

RCMPSP問(wèn)題集生成器是由Browning T R等人于2010年在Microsoft office excel平臺(tái)上設(shè)計(jì)而成的，設(shè)定參數(shù)見表3。

Table 3 Input parameters in RCMPSP generator表3 RCMPSP問(wèn)題集生成器輸入?yún)?shù)

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

RCMPSP問(wèn)題集可在網(wǎng)站http://sbuweb.tcu.edu/tbrowning/RCMPSPinstances.htm下載。該問(wèn)題集共包含12 320個(gè)子問(wèn)題，每個(gè)子問(wèn)題含有三個(gè)子項(xiàng)目，每個(gè)子項(xiàng)目有20個(gè)任務(wù)節(jié)點(diǎn)和四種資源，并且子項(xiàng)目是用設(shè)計(jì)結(jié)構(gòu)矩陣DSM(Design Structure Matrix)的形式表示。RCMPSP問(wèn)題集分別存放在20個(gè)文件夾中(由于這20個(gè)文件夾是復(fù)制而成的，所以含有相同的電子表格結(jié)構(gòu)和VBA代碼，僅僅隨機(jī)生成的問(wèn)題不同)，即每個(gè)文件夾包含616個(gè)子問(wèn)題，這616個(gè)子問(wèn)題分別存放在八個(gè)Excel工作簿中，每個(gè)Excel工作簿含有77個(gè)獨(dú)立的子問(wèn)題工作表和一個(gè)位于首端的概括性工作表“Test Bank”(見圖7)。此外，每個(gè)Excel工作簿還含有RCMPSP問(wèn)題集生成器代碼，當(dāng)按概括性工作表中的“Generate TestBank”鍵或啟動(dòng)宏文件時(shí)，將重新生成不同的子問(wèn)題。這八個(gè)Excel工作簿的區(qū)別在于復(fù)雜度期望值(四個(gè)等級(jí)：“HHH”、“HHL”、“HLL”或“LLL”)和MAUF期望方差(兩個(gè)等級(jí)：0或0.25)的不同，而工作簿中77個(gè)獨(dú)立子問(wèn)題的區(qū)別在于NARLF期望值([-3，3]之間七個(gè)不同整數(shù)等級(jí))和MAUF期望值([0.6，1.6]之間以0.1為遞增的11個(gè)不同等級(jí))的不同。用戶可以根據(jù)自己的需要設(shè)置上述參數(shù)生成相應(yīng)的問(wèn)題集。

6 測(cè)試問(wèn)題集選取一般流程及測(cè)試問(wèn)題集構(gòu)建方法的有效性分析

6.1 測(cè)試問(wèn)題集選取一般流程及測(cè)試問(wèn)題集構(gòu)建方法

項(xiàng)目調(diào)度中測(cè)試問(wèn)題集選取的一般流程如下(見圖8)：

Step1根據(jù)需測(cè)試PSP確定項(xiàng)目的個(gè)數(shù)，判斷其是單項(xiàng)目PSP還是多項(xiàng)目PSP。若為單項(xiàng)目PSP，轉(zhuǎn)Step 2；反之，若為多項(xiàng)目PSP，轉(zhuǎn)Step 3。

Step2在確定需測(cè)試PSP是單項(xiàng)目PSP后，判斷PSP的類型：?jiǎn)文Ｊ交蚨嗄Ｊ絇SP。若為單模式PSP，轉(zhuǎn)Step 4；反之，若為多模式PSP，轉(zhuǎn)Step 5。

Step3在確定需測(cè)試PSP是多項(xiàng)目PSP后，判斷所需測(cè)試問(wèn)題集是否能由RCMPSP問(wèn)題集生成器生成。若能，轉(zhuǎn)Step 6；反之，轉(zhuǎn)Step 12。

Step4在確定需測(cè)試PSP是單模式單項(xiàng)目PSP后，判斷所需測(cè)試問(wèn)題集是否能直接采用現(xiàn)成問(wèn)題集(Patterson問(wèn)題集或PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中相應(yīng)問(wèn)題集)，若能，轉(zhuǎn)Step 7；若不能，轉(zhuǎn)Step 8。

Step5在確定需測(cè)試PSP是多模式單項(xiàng)目PSP后，判斷所需測(cè)試問(wèn)題集是否能直接采用PSPLIB問(wèn)題庫(kù)中相應(yīng)問(wèn)題集，若能，轉(zhuǎn)Step 9；若不能，轉(zhuǎn)Step 10。

Step6利用RCMPSP問(wèn)題集生成器生成滿足相關(guān)要求的多項(xiàng)目調(diào)度問(wèn)題的測(cè)試問(wèn)題集。

Step7選用Patterson問(wèn)題集或PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中相應(yīng)問(wèn)題集。

Step8是否能直接采用ProGen、ProGen/Max或RanGen問(wèn)題集生成器生成問(wèn)題集，若能，轉(zhuǎn)Step11；若不能，轉(zhuǎn)Step 12。

Step9選用PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中問(wèn)題集。

Step10是否能直接采用ProGen、ProGen/Max或RanGen問(wèn)題集生成器生成問(wèn)題集，若能，轉(zhuǎn)Step 11；若不能，轉(zhuǎn)Step 12。

Figure 8 Flow chat of instances sets selection in project scheduling problems圖8 項(xiàng)目調(diào)度中測(cè)試問(wèn)題集選取流程圖

Step11根據(jù)需求，利用ProGen、ProGen/

Max問(wèn)題集生成器或RanGen問(wèn)題集生成器生成滿足相關(guān)要求的單項(xiàng)目PSP的測(cè)試問(wèn)題集。

Step12根據(jù)需求，構(gòu)建合適的、滿足要求的測(cè)試問(wèn)題集。

在測(cè)試問(wèn)題集選取的一般流程中發(fā)現(xiàn)：當(dāng)不能從現(xiàn)有國(guó)際上常用問(wèn)題庫(kù)中選用合適問(wèn)題集時(shí)，或不能采用常用問(wèn)題集生成器生成合適問(wèn)題集時(shí)，就需要構(gòu)建合適、滿足測(cè)試需求的問(wèn)題集。通常，構(gòu)建測(cè)試問(wèn)題集一般分兩步：第一，根據(jù)需求構(gòu)建問(wèn)題集的網(wǎng)絡(luò)結(jié)構(gòu)(包括大小、形狀、復(fù)雜度等)；第二，根據(jù)需求構(gòu)建其它參數(shù)(可用資源量、資源需求量等)。

6.2 有效性分析及應(yīng)用前景

下面分別以文獻(xiàn)[23]和文獻(xiàn)[24]中所采用的測(cè)試問(wèn)題集來(lái)說(shuō)明測(cè)試問(wèn)題集選取一般流程與測(cè)試問(wèn)題集構(gòu)建方法的有效性。

文獻(xiàn)[23]研究MRCPSP的反應(yīng)式調(diào)度算法，作者選用PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中MRCPSP子問(wèn)題庫(kù)中問(wèn)題集作為測(cè)試問(wèn)題集。下面根據(jù)測(cè)試問(wèn)題集選取的一般流程進(jìn)行分析。Step1：判斷研究的問(wèn)題是屬于單項(xiàng)目PSP，轉(zhuǎn)Step2；Step2：判斷其為多模式PSP，轉(zhuǎn)Step5；Step5：判斷可能直接從PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)選取合適問(wèn)題集，轉(zhuǎn)Step9；Step9：選用PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中MRCPSP子問(wèn)題庫(kù)中問(wèn)題集。

文獻(xiàn)[24]為了進(jìn)行離散時(shí)間/資源權(quán)衡問(wèn)題DTRTP(Discrete Time/Resource Trade-off Problem)中調(diào)度策略比較研究，構(gòu)建了DTRTP問(wèn)題集。下面根據(jù)測(cè)試問(wèn)題集選取的一般流程進(jìn)行分析。Step1：判斷研究的問(wèn)題是屬于單項(xiàng)目PSP，轉(zhuǎn)Step2； Step2：由于DTRTP是MRCPSP子問(wèn)題，判斷其為多模式PSP，轉(zhuǎn)Step5；Step5：判斷不能直接從PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中MRCPSP子問(wèn)題庫(kù)中選取合適問(wèn)題集(雖然DTRTP是MRCPSP子問(wèn)題，但DTRTP區(qū)別于MRCPSP有兩個(gè)方面：DTRTP僅含有一種可更新資源，而MRCPSP問(wèn)題集中問(wèn)題至少含有兩種資源；MRCPSP中任務(wù)的執(zhí)行模式數(shù)以及在此執(zhí)行模式下任務(wù)工期和所需資源量都是已知的，而DTRTP僅已知工作量，需由工作量轉(zhuǎn)化成工期和所需資源量，并計(jì)算相應(yīng)模式數(shù))，轉(zhuǎn)Step10；Step10：同理不能直接采用ProGen、ProGen/Max或RanGen問(wèn)題集生成器生成問(wèn)題集，轉(zhuǎn)Step12；Step12：需根據(jù)需求構(gòu)建合適的、滿足要求的測(cè)試問(wèn)題集。文獻(xiàn)[24]首先選用PSPLIB標(biāo)準(zhǔn)問(wèn)題庫(kù)中MRCPSP子問(wèn)題庫(kù)中任務(wù)節(jié)點(diǎn)為10的網(wǎng)絡(luò)結(jié)構(gòu)作為測(cè)試DTRTP問(wèn)題集的網(wǎng)絡(luò)結(jié)構(gòu)；然后，DTRTP工作量的均值及方差分別來(lái)自于[10,50]和[1,5]均勻分布；最后，由于需比較可用資源量的影響，所以選取10、15、20三種不同層次的可用資源量，這就意味著會(huì)生成可用資源量分別為10、15和20的三類測(cè)試問(wèn)題集。

通過(guò)對(duì)文獻(xiàn)[23]和文獻(xiàn)[24]所采用的測(cè)試問(wèn)題集的分析，說(shuō)明本文提出的測(cè)試問(wèn)題集選取一般流程與測(cè)試問(wèn)題集構(gòu)建方法是有效的，該方法可以廣泛應(yīng)用于項(xiàng)目調(diào)度問(wèn)題中測(cè)試問(wèn)題集的選取與構(gòu)建。這不僅為今后項(xiàng)目調(diào)度問(wèn)題中進(jìn)行算法測(cè)試所需問(wèn)題集的選取及構(gòu)建提供了一種思路，而且還對(duì)采用的測(cè)試問(wèn)題集起到規(guī)范作用。

7 結(jié)束語(yǔ)

測(cè)試問(wèn)題集的提出及研究是為了更好比較項(xiàng)目調(diào)度問(wèn)題中求解算法的性能。本文在介紹國(guó)際上常用的兩套標(biāo)準(zhǔn)問(wèn)題集和兩款用于生成問(wèn)題集的軟件的基礎(chǔ)上，提出測(cè)試問(wèn)題集選取的一般流程及其問(wèn)題集構(gòu)建方法，為算法測(cè)試所需問(wèn)題集提供思路。

[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.

附中文參考文獻(xiàn)：

[2] 張靜文, 徐渝, 何正文，等, 項(xiàng)目調(diào)度中的時(shí)間/費(fèi)用權(quán)衡問(wèn)題研究綜述 [J]. 管理工程學(xué)報(bào)，2007，21(1):92-97.