考慮公有與私有資源約束的多項(xiàng)目調(diào)度規(guī)則對(duì)比研究

杜宏飛，王小明，陳慶新，毛 寧

(廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006)

隨著產(chǎn)品和服務(wù)定制化需求的增長(zhǎng)，越來(lái)越多企業(yè)將項(xiàng)目管理方法應(yīng)用于生產(chǎn)運(yùn)營(yíng)過(guò)程中。項(xiàng)目調(diào)度的核心內(nèi)容是通過(guò)合理調(diào)配有限資源，使得項(xiàng)目盡可能按期完工。傳統(tǒng)項(xiàng)目調(diào)度研究主要關(guān)注單個(gè)項(xiàng)目的分析和決策，然而工程實(shí)際中一個(gè)企業(yè)往往同時(shí)管理多個(gè)項(xiàng)目。在諸如定制裝備制造等行業(yè)在進(jìn)行多項(xiàng)目管理時(shí)，需要協(xié)調(diào)的資源不僅包括安排給各個(gè)項(xiàng)目的私有資源，還包括所有項(xiàng)目共享的公有資源[1-2]。根據(jù)Lova 等[3]的調(diào)查，84%的企業(yè)是運(yùn)營(yíng)在多項(xiàng)目環(huán)境中。Engwall等[4]指出多項(xiàng)目管理最主要的挑戰(zhàn)來(lái)自于資源分配，因?yàn)榇嬖诙鄠€(gè)項(xiàng)目之間的資源競(jìng)爭(zhēng)與沖突。當(dāng)前企業(yè)主要是憑借管理者的經(jīng)驗(yàn)進(jìn)行項(xiàng)目調(diào)度決策，在項(xiàng)目數(shù)較多的時(shí)候很容易出現(xiàn)決策不合理的現(xiàn)象，導(dǎo)致大量項(xiàng)目拖期。

在過(guò)去十幾年，國(guó)內(nèi)外學(xué)者對(duì)資源受限多項(xiàng)目調(diào)度問(wèn)題(resource-constrained multi-project scheduling problem，RCMPSP)進(jìn)行了一定研究，相關(guān)研究見(jiàn)綜述文獻(xiàn)[5]和[6]。當(dāng)前面向RCMPSP的方法主要有2類(lèi)，一類(lèi)是基于多智能體的協(xié)調(diào)算法，另一類(lèi)是調(diào)度規(guī)則。在基于多智能體的協(xié)調(diào)算法方面，Homberger[7]以及Fink等[8]提出一種重啟進(jìn)化策略，并將其集成到多智能體系統(tǒng)中，用于求解分散RCMPSP。類(lèi)似的，Adhau等[9]也提出基于多智能體拍賣(mài)的RCMPSP調(diào)度方法。在基于優(yōu)先規(guī)則的調(diào)度方法方面，其首先利用優(yōu)先規(guī)則對(duì)任務(wù)進(jìn)行排序，接著借助調(diào)度生成機(jī)制獲得最終調(diào)度方案。Kolisch[10]詳細(xì)描述了串行和并行2種資源受限項(xiàng)目調(diào)度生成機(jī)制。當(dāng)前已有一些學(xué)者對(duì)確定和隨機(jī)RCMPSP環(huán)境下的優(yōu)先規(guī)則表現(xiàn)進(jìn)行對(duì)比分析。Kurtulus等[11]最早提出平均資源負(fù)荷系數(shù)(average resource load factor，ARLF)和平均利用系數(shù)(average utilization factor，AUF)2種衡量指標(biāo)，并據(jù)此對(duì)比9種優(yōu)先規(guī)則在求解決策目標(biāo)為最小化平均項(xiàng)目拖期的確定性RCMPSP時(shí)的表現(xiàn)。Browning等[12]同樣針對(duì)決策目標(biāo)為最小化項(xiàng)目拖期的確定性RCMPSP，對(duì)比分析20種經(jīng)典優(yōu)先規(guī)則在不同項(xiàng)目復(fù)雜度、AUF及ARLF下的表現(xiàn)，其實(shí)驗(yàn)數(shù)據(jù)設(shè)定每個(gè)算例包含3個(gè)項(xiàng)目，每個(gè)項(xiàng)目包含20個(gè)任務(wù)。Wang等[13]針對(duì)考慮隨機(jī)任務(wù)工期的RCMPSP，提出衡量項(xiàng)目拖期的質(zhì)量指標(biāo)和衡量規(guī)則表現(xiàn)穩(wěn)定性的魯棒指標(biāo)，并據(jù)此對(duì)比分析與Browning等[12]研究中相同的20種優(yōu)先規(guī)則的表現(xiàn)，其實(shí)驗(yàn)設(shè)定每個(gè)算例包含3個(gè)項(xiàng)目，每個(gè)項(xiàng)目包含30個(gè)任務(wù)。來(lái)凱等[14]以考慮隨機(jī)任務(wù)工期和新項(xiàng)目隨機(jī)到達(dá)的模具項(xiàng)目群調(diào)度為背景，在拖期成本和拖期天數(shù)指標(biāo)下對(duì)比分析15種優(yōu)先規(guī)則的表現(xiàn)。通常來(lái)說(shuō)，各個(gè)優(yōu)先規(guī)則都是單獨(dú)與調(diào)度生成機(jī)制相結(jié)合用于求解RCMPSP。然而，也有部分學(xué)者指出將多種優(yōu)先規(guī)則進(jìn)行組合求解，能夠獲得更好結(jié)果。例如，Wang等[15]面向隨機(jī)RCMPSP提出的多規(guī)則組合前攝調(diào)度策略比單一規(guī)則策略結(jié)果更優(yōu)。

盡管當(dāng)前國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)比分析多種優(yōu)先規(guī)則在確定和隨機(jī)RCMPSP環(huán)境下的表現(xiàn)，但是這些研究還可以從以下幾個(gè)方面加以完善：1) 現(xiàn)有文獻(xiàn)僅考慮公有資源，而工程實(shí)際中可能同時(shí)存在公有和私有資源；2) 現(xiàn)有文獻(xiàn)假定所有項(xiàng)目具有相同的權(quán)重，而工程實(shí)際中不同項(xiàng)目的權(quán)重往往因客戶(hù)、金額等因素而不同；3) 現(xiàn)有文獻(xiàn)僅關(guān)注項(xiàng)目拖期目標(biāo)，而工程實(shí)際中還可能關(guān)注最大完工時(shí)間和總加權(quán)拖期等決策目標(biāo)；4) 現(xiàn)有文獻(xiàn)的實(shí)驗(yàn)算例僅考慮少量并行項(xiàng)目，而工程實(shí)際中可能存在幾十個(gè)并行項(xiàng)目。這些問(wèn)題導(dǎo)致現(xiàn)有研究結(jié)論未必適用于工程實(shí)際。為此，本文以考慮公有和私有資源約束的多項(xiàng)目調(diào)度問(wèn)題為研究對(duì)象，分析決策目標(biāo)、單項(xiàng)目任務(wù)數(shù)、并行項(xiàng)目數(shù)、AUF值等因素對(duì)優(yōu)先規(guī)則表現(xiàn)的影響。

1 問(wèn)題描述

本文所研究的問(wèn)題包含一個(gè)項(xiàng)目集φ={1, 2, ···,n}， 可更新公有資源集Rc={1, 2, ···,kc}以及可更新私有資源集Rp={1, 2, ···,kp} 。 其中，n表示項(xiàng)目總數(shù)；kc和kp分別表示可更新公有資源和私有資源類(lèi)型數(shù)量。第k∈Rc∪Rp種公有或私有資源的總量為Mk。

基于上述問(wèn)題及符號(hào)定義，本文考慮式(1)所示最小化最大完工時(shí)間、式(2)所示最小化總拖期以及式(3)所示最小化總加權(quán)拖期3種調(diào)度目標(biāo)。若第i個(gè)項(xiàng)目的第j個(gè)任務(wù)在時(shí)刻t在制，令二進(jìn)制變量xijt=1，否則，令xijt=0。在調(diào)度過(guò)程中，任務(wù)需要滿(mǎn)足式(4)所示的緊前約束及式(5)所示的公有和私有資源約束。

2 項(xiàng)目調(diào)度算法

RCMPSP求解算法大體可以分成精確算法和近似算法兩大類(lèi)。精確算法主要是基于分支定界、動(dòng)態(tài)規(guī)劃等方法，這類(lèi)方法受問(wèn)題的NP難特性限制，只能求解非常小規(guī)模的問(wèn)題。近似算法主要包括各類(lèi)優(yōu)先規(guī)則、智能算法等，這類(lèi)方法的簡(jiǎn)單高效特性對(duì)于工程實(shí)際而言十分重要。優(yōu)先規(guī)則需要結(jié)合調(diào)度生成機(jī)制才能構(gòu)造完整的調(diào)度方案。本節(jié)將對(duì)這2個(gè)內(nèi)容分別加以描述。

2.1 調(diào)度生成機(jī)制

資源受限項(xiàng)目調(diào)度問(wèn)題常用的調(diào)度生成機(jī)制分為串行調(diào)度生成機(jī)制(serial schedule generation scheme,SSGS)和并行調(diào)度生成機(jī)制(parallel schedule generation scheme, PSGS)[10]。Lova等[3]的研究表明，PSGS相比SSGS更適用于RCMPSP。該方法同樣被應(yīng)用于Wang等[3]和Browning等[12]的研究中。因此，本文也將采用PSGS。

2.2 優(yōu)先規(guī)則

國(guó)內(nèi)外學(xué)者在過(guò)去幾十年里面向各種調(diào)度和排序問(wèn)題提出大量高效的優(yōu)先規(guī)則，其中一些規(guī)則可以被應(yīng)用于RCMPSP中。結(jié)合所考慮的3種項(xiàng)目調(diào)度目標(biāo)，本文從現(xiàn)有文獻(xiàn)中選擇了25種表現(xiàn)較好的經(jīng)典優(yōu)先規(guī)則，如表1所示，其中大多數(shù)規(guī)則都已在Browning等[12]、Wang等[13]以及來(lái)凱等[14]的研究中進(jìn)行對(duì)比。本文主要補(bǔ)充了面向總加權(quán)拖期目標(biāo)的規(guī)則，包括ATC[16-17]、COVERT[18]、R&M[17]、MDD[19]和WMDD[20]，其中，R&M[17]是在A(yíng)TC[16]基礎(chǔ)上提出的，而WMDD[20]則是在MDD[19]基礎(chǔ)上提出。

表1 所選25種優(yōu)先規(guī)則的形式化描述Table 1 Formalization of selected 25 priority rules

其中，

Wij表示當(dāng)前時(shí)刻項(xiàng)目i中 的任務(wù)j的剩余百分比，本文不考慮任務(wù)中斷，因此取值為1。

需要注意的是，Browning等[12]、Wang等[13]是以L(fǎng)Si j作為任務(wù)的交貨期來(lái)計(jì)算優(yōu)先級(jí)，而來(lái)凱等[14]采用的是 LFi j。 本文對(duì)比了采用 LSi j和 LFij作為任務(wù)交貨期時(shí)各規(guī)則的表現(xiàn)，結(jié)果發(fā)現(xiàn)，以 LFij為任務(wù)交貨期時(shí)各規(guī)則的表現(xiàn)總體更好，因此以 LFi j作為任務(wù)交貨期。此外，規(guī)則SOF、MOF、WSOF是基于任務(wù)工期dij計(jì)算優(yōu)先級(jí)，而來(lái)凱等[14]提出的SRL、LRL、WSRL是以任務(wù)剩余關(guān)鍵路徑長(zhǎng)度來(lái)計(jì)算優(yōu)先級(jí)的。

3 計(jì)算實(shí)例

為了評(píng)估表1所示25種優(yōu)先規(guī)則在求解考慮公有和私有資源約束的多項(xiàng)目調(diào)度問(wèn)題時(shí)的表現(xiàn)，本節(jié)基于標(biāo)準(zhǔn)測(cè)試集MPSPLIB (multi-projiect scheduling problem library)設(shè)計(jì)相應(yīng)計(jì)算實(shí)驗(yàn)。調(diào)度計(jì)算程序采用C#編程實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果由該程序運(yùn)行在一臺(tái)配置為CPU 2.60G Hz、8 G RAM的個(gè)人電腦上所得。

3.1 算例數(shù)據(jù)

標(biāo)準(zhǔn)測(cè)試集MPSPLIB (http://www.mpsplib.com)是 由Homberger[7]基 于Kolisch等[21]的PSPLIB(project scheduling problem library)測(cè)試集構(gòu)建出來(lái)的。MPSPLIB包含60個(gè)RCMPSP算例，每個(gè)算例由多個(gè)PSPLIB算例構(gòu)成。該算例分3種任務(wù)規(guī)模(j30，j90和j120各有20個(gè))，每種任務(wù)規(guī)模包含4種并行項(xiàng)目數(shù)量(P2，P5，P10和P20各有5個(gè))。每個(gè)RCMPSP算例的信息記錄在一個(gè)XML文件中，包括各個(gè)項(xiàng)目對(duì)應(yīng)的PSPLIB文件名稱(chēng)(該文件定義了每個(gè)項(xiàng)目的交貨期、網(wǎng)絡(luò)結(jié)構(gòu)、任務(wù)工期、私有資源種類(lèi)和數(shù)量)、項(xiàng)目到達(dá)時(shí)間、公有資源種類(lèi)和數(shù)量。在這60個(gè)算例中，高AUF(大于1)的算例有29個(gè)，低AUF(小于1)的算例有31個(gè)。

3.2 評(píng)價(jià)指標(biāo)

由于3種決策目標(biāo)對(duì)應(yīng)的目標(biāo)函數(shù)值相差很大，為了更為規(guī)范地對(duì)比各規(guī)則表現(xiàn)，本文采用如式(6)所示相對(duì)偏差指數(shù)(relative deviation index，RDI)來(lái)衡量各個(gè)規(guī)則的表現(xiàn)。某規(guī)則對(duì)應(yīng)的RDI值越小，說(shuō)明其表現(xiàn)越好，反之，則表現(xiàn)越差。

其中， RDIIM表示規(guī)則M在算例I的RDI數(shù)值；FOIM表示規(guī)則M在算例I的目標(biāo)函數(shù)值； WorstI和BestI分別表示所有規(guī)則求解該算例所得最差和最好的目標(biāo)函數(shù)數(shù)值。

基于RDI指標(biāo)，本文將分析25種優(yōu)先規(guī)則的表現(xiàn)與決策目標(biāo)、單項(xiàng)目任務(wù)數(shù)、并行項(xiàng)目數(shù)、AUF值等因素之間的關(guān)系。在計(jì)算過(guò)程中發(fā)現(xiàn)，算例j30_a5_nr4和j90_a2_nr1資源設(shè)置的充足，無(wú)論采用何種規(guī)則調(diào)度都不存在資源約束，導(dǎo)致無(wú)法計(jì)算RDIIM。因此，本文在后續(xù)實(shí)驗(yàn)結(jié)果分析中去除這2個(gè)算例。

3.3 結(jié)果分析

首先，采用表1所示25種優(yōu)先規(guī)則求解剩余58個(gè)算例，得到3種決策目標(biāo)下各規(guī)則的平均RDI，如表2 ～ 4所示。接著，采用圖基法(Tukey's Method)從多個(gè)維度分析不同因素對(duì)規(guī)則表現(xiàn)的影響。具體來(lái)說(shuō)，首先在圖1(a)中，基于平均RDI的圖基95%置信區(qū)間評(píng)價(jià)25種規(guī)則的總體表現(xiàn)；接著分別在圖1(b)～(d)中，基于不同因素水平下的平均RDI的圖基95%置信區(qū)間分析單項(xiàng)目任務(wù)數(shù)、并行項(xiàng)目數(shù)、AUF值對(duì)各個(gè)規(guī)則表現(xiàn)的影響。

圖1 最小化最大完工時(shí)間決策目標(biāo)下的圖基95%置信區(qū)間Figure 1 Tukey 95% confidence intervals with the decision objective of minimizing maximum completion time

表2 最小化最大完工時(shí)間決策目標(biāo)下各規(guī)則的平均RDI對(duì)比Table 2 Comparison of rules on average RDI with the decision objective of minimizing maximum completion time

3.3.1 最小化最大完工時(shí)間結(jié)果

在決策目標(biāo)為最小化最大完工時(shí)間時(shí)，25種調(diào)度規(guī)則的平均RDI對(duì)比結(jié)果如表2和圖1所示。

由圖1(a)可以看出，在最小化最大完工時(shí)間目標(biāo)下表現(xiàn)相對(duì)較好的規(guī)則是MDD、FCFS、LRL、MINSLK、MTS、MINLFT、MAXSP。其中，LRL表現(xiàn)最好，其平均RDI接近0；其次表現(xiàn)較好的是經(jīng)典規(guī)則MINLFT與MINSLK。在圖1(b) ～ (d)中，將僅對(duì)這些表現(xiàn)較好的規(guī)則進(jìn)一步分析。

由圖1(b)可以看出，除FCFS和MTS之外，其余規(guī)則在3種任務(wù)規(guī)模下所呈現(xiàn)出的規(guī)律幾乎一致，也就是在j90下表現(xiàn)最好，j120次之，j30最差。此外，各規(guī)則的置信區(qū)間寬度在不同任務(wù)規(guī)模下也發(fā)生了不同的變化。例如，LRL規(guī)則的置信區(qū)間相對(duì)于其余規(guī)則更窄，在j90和j120下尤其如此。這表明，單項(xiàng)目任務(wù)規(guī)模對(duì)規(guī)則表現(xiàn)具有顯著影響，且對(duì)不同規(guī)則的影響程度是不同的。

由圖1(c)可以看出，并行項(xiàng)目數(shù)量對(duì)各規(guī)則的表現(xiàn)也具有顯著影響。其中，MINSLK、MINLFT、MAXSP在P2下的表現(xiàn)接近甚至優(yōu)于LRL。然而，這幾個(gè)規(guī)則在其他項(xiàng)目數(shù)下的表現(xiàn)則明顯差于LRL。此外，各個(gè)規(guī)則在不同項(xiàng)目數(shù)量下的表現(xiàn)波動(dòng)較大，未呈現(xiàn)出明顯的規(guī)律。

由圖1(d)可以看出，AUF值同樣對(duì)規(guī)則的表現(xiàn)具有顯著影響。規(guī)則FCFS、LRL、MTS在高AUF下的表現(xiàn)優(yōu)于低AUF，而在低AUF值表現(xiàn)更好的規(guī)則為MDD、MINSLK、MINLFT、MAXSP。其中，規(guī)則FCFS在高低AUF值下的表現(xiàn)差異比較大，而LRL在高低AUF值下的表現(xiàn)較為穩(wěn)定。

3.3.2 最小化總拖期結(jié)果

決策目標(biāo)為最小化總拖期時(shí)，25種調(diào)度規(guī)則的平均RDI對(duì)比結(jié)果如表3和圖2所示。由于Browning等[15]僅考慮該目標(biāo)，因此這里將重點(diǎn)分析本文結(jié)果與其結(jié)果的異同。

表3 最小化總拖期決策目標(biāo)下各規(guī)則的平均RDI對(duì)比Table 3 Comparison of rules on average RDI with the decision objective of minimizing total tardiness

由圖2(a)可以看出，在最小化總拖期目標(biāo)下，總體表現(xiàn)較好的規(guī)則有ATC、EDD、WMDD、MINSLK、TWK-EST、TWK-LST、MINLFT、MAXSP。其中，表現(xiàn)最好的是TWK-LST，表現(xiàn)次之的規(guī)則是MINLFT和MINSLK。此外，ATC、WMDD、MAXSP、EDD、TWK-EST表現(xiàn)雖不如上述規(guī)則，但是相對(duì)其余規(guī)則要明顯更好。Browning等[12]的結(jié)論為T(mén)WK-LST表現(xiàn)最好，MAXTWK次之，EDD、MAXSP、MINLFT以及TWK-EST表現(xiàn)也較好，MINSLK表現(xiàn)一般。本文與之結(jié)論總體一致，但是也存在顯著的區(qū)別。一方面，MAXTWK在本文所研究問(wèn)題環(huán)境下的表現(xiàn)較差，而MINSLK表現(xiàn)較好。另一方面，本文還發(fā)現(xiàn)ATC和WMDD在最小化總拖期目標(biāo)下表現(xiàn)較好。在圖2(b) ～ (d)中，將對(duì)這些表現(xiàn)較好的規(guī)則進(jìn)一步說(shuō)明。

圖2 最小化總拖期決策目標(biāo)下的圖基95%置信區(qū)間Figure 2 Tukey 95% confidence intervals with the decision objective of minimizing total tardiness

由圖2(b)可知，不同規(guī)則在不同任務(wù)規(guī)模下的表現(xiàn)存在一定差異，但是這種差異相對(duì)于最小化最大完工時(shí)間目標(biāo)下的結(jié)果要小一些。例如，EDD和TWK-EST在j90算例中的表現(xiàn)顯著差于其他規(guī)則，但是在j30和j120算例中與其他規(guī)則差別不太大；TWK-LST在j90算例下表現(xiàn)不如MINLFT和MINSLK，但是在j30和j120算例中則顯著優(yōu)于其他規(guī)則。

由圖2(c)可以看出，項(xiàng)目數(shù)量對(duì)各規(guī)則的表現(xiàn)具有波動(dòng)較大，未呈現(xiàn)出明顯的規(guī)律。其中，規(guī)則ATC和WMDD在不同項(xiàng)目數(shù)下的表現(xiàn)較為穩(wěn)定，且項(xiàng)目數(shù)越多表現(xiàn)越好；規(guī)則MINSLK和MINLFT在P2和P5算例下的表現(xiàn)接近甚至優(yōu)于TWK-LST，但是在P10和P20算例下則表現(xiàn)較差。

由圖2(d)可以看出，AUF值同樣對(duì)規(guī)則的表現(xiàn)具有顯著影響。在高AUF值下表現(xiàn)較好的規(guī)則有TWK-LST、TWK-EST、EDD。該結(jié)論與Browning等[15]的結(jié)論是一致的。在低AUF值下表現(xiàn)較好的規(guī)則有ATC、WMDD、MINSLK、MINLFT、MAXSP。其中，MINSLK、MINLFT和MAXSP與Browning等[12]的研究結(jié)論一致， 而ATC和WMDD則是本文補(bǔ)充的規(guī)則。

3.3.3 最小化總加權(quán)拖期結(jié)果

在決策目標(biāo)為最小化總加權(quán)拖期時(shí)，25種調(diào)度規(guī)則的平均RDI對(duì)比結(jié)果如表4和圖3所示。

表4 最小化總加權(quán)拖期決策目標(biāo)下各規(guī)則的平均RDI對(duì)比Table 4 Comparison of rules on average RDI with the decision objective of minimizing total weighted tardiness

由圖3(a)可以看出，在最小化總加權(quán)拖期目標(biāo)下，總體表現(xiàn)較好的規(guī)則有ATC、WEDD、WMDD、WSASP、MINSLK、TWK-LST、MINLFT、MAXSP。總體來(lái)說(shuō)，考慮了項(xiàng)目權(quán)重的規(guī)則表現(xiàn)優(yōu)于不考慮項(xiàng)目權(quán)重的規(guī)則。其中，表現(xiàn)最好的規(guī)則是WMDD；規(guī)則TWK-LST次之；規(guī)則ATC和MINLFT的表現(xiàn)也較好。同樣的，在圖3(b) ～ (d)中對(duì)這些表現(xiàn)較好的規(guī)則作進(jìn)一步說(shuō)明。由于圖3(b) ～(d)所顯示的規(guī)律與圖2(b) ～ (d)較為相似，受篇幅限制，本文不再贅述3種因素對(duì)各規(guī)則表現(xiàn)的具體影響。

圖3 最小化總加權(quán)拖期決策目標(biāo)下的圖基95%置信區(qū)間Figure 3 Tukey 95% confidence intervals with the decision objective of minimizing total weighted tardiness

3.4 應(yīng)用指導(dǎo)

在上一節(jié)中，對(duì)比分析了各個(gè)規(guī)則在不同調(diào)度環(huán)境下的表現(xiàn)優(yōu)劣，重點(diǎn)分析3種因素對(duì)規(guī)則表現(xiàn)的影響。在此基礎(chǔ)上，將表現(xiàn)較好的規(guī)則總結(jié)在表5中(從上到下為表現(xiàn)由好到差)，用于指導(dǎo)項(xiàng)目管理者在工程實(shí)際中選擇合適的優(yōu)先規(guī)則進(jìn)行項(xiàng)目調(diào)度決策。

表5 不同調(diào)度環(huán)境下表現(xiàn)較好的優(yōu)先規(guī)則匯總Table 5 Summary of the best priority rules under different scheduling environments

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

本文以考慮公有與私有資源約束的多項(xiàng)目調(diào)度問(wèn)題為研究對(duì)象，在最小化最大完工時(shí)間、最小化總拖期、最小化總加權(quán)拖期3種決策目標(biāo)下，對(duì)比分析25種優(yōu)先規(guī)則的表現(xiàn)?；跇?biāo)準(zhǔn)測(cè)試集MPSPLIB的實(shí)驗(yàn)結(jié)果表明，各規(guī)則在不同調(diào)度環(huán)境下的表現(xiàn)差異較大。具體來(lái)說(shuō)，各規(guī)則的表現(xiàn)與決策目標(biāo)、單項(xiàng)目任務(wù)數(shù)、并行項(xiàng)目數(shù)、AUF值等因素之間具有顯著相關(guān)性。盡管本文在最小化總拖期目標(biāo)下所得實(shí)驗(yàn)結(jié)論與Browning等[12]的結(jié)論總體相一致，但是個(gè)別規(guī)則(如MAXTWK和MINSLK)的表現(xiàn)卻有著顯著差異。此外，與現(xiàn)有研究相比，本文從優(yōu)先規(guī)則與決策目標(biāo)兩個(gè)方面都進(jìn)行了補(bǔ)充和完善。本文對(duì)不同調(diào)度環(huán)境下表現(xiàn)較好的優(yōu)先規(guī)則進(jìn)行總結(jié)，以作為企業(yè)項(xiàng)目管理人員選擇合適調(diào)度規(guī)則的參考。在下一步研究中，將基于本文所得的研究結(jié)論，構(gòu)建一種能夠發(fā)揮各規(guī)則優(yōu)勢(shì)的組合迭代調(diào)度策略。