蘇志雄，魏漢英，涂遠(yuǎn)芬

(1.南昌工程學(xué)院工商管理學(xué)院，江西 南昌 330099；2. 江西省水安全與可持續(xù)發(fā)展軟科學(xué)研究基地，江西 南昌 330099)

1 引言

在工程項(xiàng)目實(shí)施過(guò)程中，資源限制廣泛存在，甚至不可避免。很多現(xiàn)代項(xiàng)目管理問題就源于資源受限，其中最具代表性的包括資源約束下的應(yīng)急管理問題、資源受限項(xiàng)目調(diào)度問題(resource-constrained project scheduling problem，簡(jiǎn)稱RCPSP)等。其中前者重點(diǎn)考慮資源調(diào)度，石彪等[1]新近研究了多類突發(fā)事件并發(fā)或次生時(shí)，通過(guò)在線重構(gòu)方式生成應(yīng)急預(yù)案資源調(diào)度方案的方法；而后者重點(diǎn)考慮工序調(diào)度，要求在滿足項(xiàng)目各工序間的緊前關(guān)系和資源約束的條件下，合理地安排工序執(zhí)行的先后順序，從而使項(xiàng)目工期最小化。本文主要針對(duì)RCPSP進(jìn)行研究。

RCPSP是典型的組合優(yōu)化問題，更是NP-hard[2]。我們可以將RCPSP用另一種方式描述，首先假設(shè)資源不受限，確定一個(gè)初始任務(wù)安排(例如可安排各工序都在其最早開始時(shí)間開始)及項(xiàng)目工期，然后再加入資源約束，從而調(diào)整各工序以滿足資源約束，并使項(xiàng)目工期延遲最小。顯然，此時(shí)的調(diào)整就是將原先相互獨(dú)立的平行工序(即可以同時(shí)進(jìn)行的工序)排列為相互關(guān)聯(lián)的順序工序(即只能前后進(jìn)行的工序)，減少工序的重疊，從而降低相應(yīng)時(shí)段內(nèi)對(duì)資源的消耗量，滿足資源約束。因此，從排序的視角看RCPSP，可等同于平行工序順序優(yōu)化問題，其基本情況包括將若干個(gè)平行工序調(diào)整為1條或多條順序工序鏈，以及多個(gè)順序工序?qū)Φ取?/p>

根據(jù)工序情況的不同，RCPSP可分為多種類型，如確定型、不確定型(包括模糊型等)、工序工期不變型、以及工序工期可變型(包括多模式型和可分解型等)問題。不同類型問題的特點(diǎn)不同，求解時(shí)所需的理論和方法也各有不同，并且每類問題都具有很高的難度，其有效的解決均有助于更好地解決總體問題。本文針對(duì)的是確定型、且工序工期不變的RCPSP。根據(jù)現(xiàn)有文獻(xiàn)，求解該問題的主要途經(jīng)是數(shù)學(xué)建模和算法設(shè)計(jì)。模型是問題的數(shù)學(xué)描述，其性質(zhì)和特點(diǎn)決定了求解效率、可行性和準(zhǔn)確性等。目前用于描述RCPSP的數(shù)學(xué)模型主要包括整數(shù)規(guī)劃模型[3-4]、魯棒模型[5-6]、約束規(guī)劃模型[7-8]、基于可變強(qiáng)度的模型[9]、以及時(shí)間索引模型[10]等。特別是，Bianco和Caramia[11]建立的新模型中，開發(fā)了3個(gè)與工序開始時(shí)間、工序結(jié)束時(shí)間、以及某指定時(shí)刻的工序數(shù)量相關(guān)聯(lián)的新變量，使得該模型優(yōu)于已知的多數(shù)數(shù)學(xué)模型。張立輝等[12]將項(xiàng)目調(diào)度的研究范圍擴(kuò)展到重復(fù)性項(xiàng)目，發(fā)現(xiàn)了重復(fù)性項(xiàng)目與傳統(tǒng)項(xiàng)目在工序時(shí)差方面的區(qū)別和聯(lián)系，提出了適用于重復(fù)性項(xiàng)目的新時(shí)差概念體系，進(jìn)而建立了更精確的重復(fù)性項(xiàng)目調(diào)度模型。對(duì)于這些模型的求解算法，包括精確算法和啟發(fā)式算法，其中精確算法主要以分支定界法[13]為代表。鑒于RCPSP的難度，對(duì)于大規(guī)模的問題，精確算法通常耗時(shí)巨大，因此，啟發(fā)式算法成為重要途徑。最新文獻(xiàn)中，用于求解RCPSP的啟發(fā)式算法主要包括遺傳算法[14-15]、粒子群算法[16]、魚群算法[17]、蟻群算法[18]、過(guò)濾器算法[19]、和聲搜索算法[20]、以及熵算法[21]等。然而，啟發(fā)式算法尚無(wú)法確定最優(yōu)解，因此難以徹底解決RCPSP。

從排序的角度分析，求解RCPSP過(guò)程中，只有相互平行的工序才需要考慮將其調(diào)整為順序進(jìn)行?，F(xiàn)有研究主要從全局視角入手，即對(duì)于任一工序，其他某工序只要和它是平行關(guān)系，就需考慮是否將它們排列為順序工序?？紤]到工程實(shí)踐中，所需資源類型眾多，很多情況下資源并非全部或全程受限，而是部分、局部、以及指定性的受限，特別是意外的資源受限情況，某些資源受限可能只影響部分工序，即需將部分平行工序調(diào)整為順序工序。處理這樣的情況可能與處理全局情況有顯著差異，但在目前鮮有研究。因此，針對(duì)上述情況，本文從新的視角——局部視角入手，考慮將項(xiàng)目中指定的部分平行工序調(diào)整為相應(yīng)的順序工序，并使項(xiàng)目工期延遲量最小。這些問題雖然是局部性問題，但在工程項(xiàng)目實(shí)踐中廣泛存在，且求解難度同樣很大，包括一些NP-hard問題。

本文重點(diǎn)研究其中一類具有代表性的問題——將項(xiàng)目中某2n個(gè)平行工序排列為對(duì)項(xiàng)目工期影響最小的n個(gè)順序工序?qū)ΑＴ搯栴}也稱為平行工序順序?qū)?yōu)化問題。例如，原計(jì)劃安排4名員工完成4個(gè)平行且相似的工序，但實(shí)施時(shí)2人被臨時(shí)調(diào)走，要求剩余的2人完成這4個(gè)工序；假設(shè)個(gè)人的能力和精力限制每人最多只能完成2個(gè)工序，因此需要考慮如何將這4個(gè)平行工序兩兩排列成2個(gè)順序工序?qū)?，從而能使?xiàng)目工期所受影響最小。該調(diào)度問題具有如下特征：(1)可行方案數(shù)為(2n!)/n!，隨著n增加，可選方案呈階乘急劇增加；(2)各平行工序都有大量前繼工序和后繼工序，因此調(diào)整時(shí)幾乎會(huì)影響項(xiàng)目中的所有工序，可謂“牽一發(fā)而動(dòng)全身”，更增加了求解難度。該問題可視作RCPSP的特殊子問題，因此可借助通用RCPSP模型進(jìn)行表述和求解。然而，本文的目標(biāo)是建立更為簡(jiǎn)單高效的數(shù)學(xué)模型。

本文針對(duì)該問題提出更具針對(duì)性的理論，主要借助網(wǎng)絡(luò)計(jì)劃技術(shù)中的關(guān)鍵路線法(critical path method，簡(jiǎn)稱CPM[22-23])，通過(guò)分析CPM網(wǎng)絡(luò)的新特性——時(shí)間參數(shù)與路線之間的關(guān)系[24-25]，利用時(shí)間參數(shù)提出了平行工序順序化對(duì)項(xiàng)目工期影響的簡(jiǎn)化公式。該公式對(duì)問題的簡(jiǎn)化十分重要：雖然調(diào)度平行工序會(huì)影響其大量前繼和后繼工序，但該公式只用2個(gè)參數(shù)就量化了該調(diào)度與項(xiàng)目工期之間的關(guān)系，實(shí)現(xiàn)了對(duì)問題的顯著化簡(jiǎn)。在此公式基礎(chǔ)上，本文提出了該問題的簡(jiǎn)單純0-1規(guī)劃模型。相關(guān)文獻(xiàn)顯示，混合整數(shù)規(guī)劃是描述項(xiàng)目調(diào)度問題的基本模型，多數(shù)確定型RCPSP模型以混合整數(shù)規(guī)劃為主[26-27]。然而與其相比，0-1規(guī)劃模型通常更為簡(jiǎn)單高效[28]，且本文的純0-1規(guī)劃模型是建立在該問題的化簡(jiǎn)公式基礎(chǔ)上，因此在計(jì)算效率和準(zhǔn)確性上具備優(yōu)勢(shì)。實(shí)驗(yàn)驗(yàn)證，運(yùn)用該模型可以在極短的時(shí)間內(nèi)求得較大規(guī)模問題(如數(shù)百個(gè)平行工序的順序?qū)?yōu)化)的最優(yōu)解。該結(jié)論為進(jìn)一步求解RCPSP提供了新的理論和途徑。

2 問題描述

假設(shè)工程項(xiàng)目中工序之間只存在嚴(yán)格優(yōu)先關(guān)系，即任何工序只能在其緊前工序結(jié)束后才能開始，可用CPM網(wǎng)絡(luò)表示，并計(jì)算相應(yīng)的時(shí)間參數(shù)(如項(xiàng)目工期等)[22]，如圖1所示，圖中符號(hào)ETi和LTi分別表示節(jié)點(diǎn)(i)的時(shí)間上限(earliest time)和下限(latest time)。如果某些工序之間沒有任何優(yōu)先關(guān)系，則稱它們相互平行，即平行工序。在CPM網(wǎng)絡(luò)中，平行工序不在同一條路線上。

假設(shè)項(xiàng)目中，已知某2n個(gè)平行工序(記為A1,A2,…,A2n)面臨資源受限。具體表述為：初始計(jì)劃是安排相應(yīng)2n個(gè)資源(可重復(fù)利用的資源)，且每個(gè)工序只需要1個(gè)資源；然而，由于突發(fā)資源限制，使得可用資源比計(jì)劃缺少一半，即只有n個(gè)資源能夠用于完成這2n個(gè)工序，另外，1個(gè)資源1次只能用于完成1個(gè)工序，且最多能順序完成2個(gè)工序；因此，需要將這2n個(gè)平行工序兩兩排列成n個(gè)順序工序?qū)?，如Ai→Aj，i≠j。將平行工序調(diào)整為順序工序后，很可能、甚至必然會(huì)導(dǎo)致項(xiàng)目工期延遲，因此，該調(diào)整的目標(biāo)就是使項(xiàng)目工期的延遲量最小。

圖1 CPM網(wǎng)絡(luò)

圖2 平行工序順序?qū){(diào)整后的網(wǎng)絡(luò)

3 理論分析及建模

3.1 理論分析

工序的基本時(shí)間參數(shù)包括其最早開始時(shí)間(earliest start time，簡(jiǎn)稱ES)、最早結(jié)束時(shí)間(earliest finish time，簡(jiǎn)稱EF)、最遲開始時(shí)間(latest start time，簡(jiǎn)稱LS)、以及最遲結(jié)束時(shí)間(earliest start time，簡(jiǎn)稱LF)，本文主要使用EF和LS，可用CPM法計(jì)算[22]。將項(xiàng)目中某兩平行工序A和B調(diào)整為順序工序?qū)→B，可能導(dǎo)致項(xiàng)目工期延遲，其延遲量記為DAB。為便于表述，我們亦稱DAB為工序?qū)→B的延遲量，并給出DAB的簡(jiǎn)單計(jì)算公式，如定理1所述：

定理1將項(xiàng)目中平行工序A和B調(diào)整為順序工序?qū)→B，造成項(xiàng)目工期延遲量，即DAB為：

DAB=max{EFA-LSB,0}

(1)

(2)

DAB=0

(3)

所以：

(4)

根據(jù)CPM法可知[22]：

帶入式(4)可得：

所以：

=EFA-LSB

DAB=max{EFA-LSB,0}

式(1)正確。證畢。

圖3 經(jīng)過(guò)A→B的新增路線

由定理1及公式(1)可知，雖然平行工序的順序化過(guò)程在項(xiàng)目中的影響范圍很廣，改變了諸多其他工序的進(jìn)程，但是對(duì)項(xiàng)目工期的影響卻只由其兩個(gè)參數(shù)決定，從而實(shí)現(xiàn)了問題的簡(jiǎn)化。

根據(jù)定理1，我們可以將其拓展，推導(dǎo)出將項(xiàng)目中某2n個(gè)平行工序調(diào)整為n個(gè)順序工序?qū)螅?xiàng)目工期延遲量的計(jì)算方法，如推論1所示：

推論1 將2n個(gè)平行工序A1,A2,…,A2n調(diào)整為n個(gè)順序工序?qū)i→Aj，i,j=1,2,…,2n，i≠j造成的項(xiàng)目工期延遲量等于這n個(gè)工序?qū)Φ难舆t量DAiAj中的最大值，即maxDAiAj。

證明根據(jù)式(1)的證明過(guò)程，如果?DAiAj>0，則：

即：

而若?DAiAj=0，則：

=maxDAiAj

證畢。

3.2 純0-1規(guī)劃模型

定理1和推論1的公式簡(jiǎn)化了工程項(xiàng)目中平行工序順序化與項(xiàng)目工期的量化關(guān)系。在此基礎(chǔ)上，我們建立了將項(xiàng)目中某2n個(gè)平行工序調(diào)整為n個(gè)順序工序?qū)?，并且?duì)項(xiàng)目工期影響最小的0-1規(guī)劃模型，過(guò)程如下：

(1)引入0-1決策變量，用于決定是否將這2n個(gè)平行工序中的某兩個(gè)Ai和Aj排列成順序工序?qū)i→Aj，即：若yAiAj=1，表示將工序Ai和Aj調(diào)整為順序工序?qū)i→Aj；否則，yAiAj=0。

(2)考慮是否將平行工序Ai和Aj排列成順序工序?qū)i→Aj(亦可簡(jiǎn)寫為AiAj)，以及排列后對(duì)項(xiàng)目工期的影響，根據(jù)定理1和0-1決策變量yAiAj的含義，可表示為yAiAj(EFAi-LSAj)。引入變量z，使其滿足：

z≥yAiAj(EFAi-LSAj)，AiAj∈Ω

(5)

其中，Ω表示這2n個(gè)平行工序中的任意兩個(gè)組成的順序工序?qū)Φ募?，且所有yAiAj=1的工序?qū)χ胁荒苡邢嗤墓ば?，即任一工序只能和另一工序組成一個(gè)順序工序?qū)?。?5)表示z≥?DAiAj，AiAj∈Ω，即：

z≥maxDAiAj，AiAj∈Ω

從而可得：

minz=maxDAiAj，AiAj∈Ω(6)

根據(jù)推論1，minz表示將2n個(gè)平行工序調(diào)整為n對(duì)順序工序?qū)?，?dǎo)致項(xiàng)目工期的推遲量，因此模型的目標(biāo)函數(shù)是：

minz

(7)

而式(5)是其約束條件。

(3)約束條件式(5)中，AiAj和Ω均是不確定的。為了更加簡(jiǎn)便和明確，我們借助上述0-1變量yAiAj來(lái)表述。

令A(yù)*表示2n個(gè)平行工序的集合，要將這2n個(gè)平行工序調(diào)整為n對(duì)順序工序?qū)?，各工序Ai∈A*只能和A*中所有剩余工序中的一個(gè)(記為Aj)排成順序唯一的工序?qū)?Ai→Aj或Aj→Ai)，即?yAiAj和?yAjAi(?Aj∈A*)中有且只有一個(gè)變量等于1，因此可用如下約束表示：

(8)

基于該約束, 可以將式(5)改寫如下：

z≥yAiAj(EFAi-LSAj)，Ai,Aj∈A*，i≠j

(9)

根據(jù)上述式(5)、(7)-(9)，該問題的完整模型如下：

minz

s.t.z≥yAiAj(EFAi-LSAj)，Ai,Aj∈A*，i≠j

yAiAj={0,1}

該調(diào)度問題可視為一類特殊的RCPSP，而其上述模型是純0-1規(guī)劃模型。與混合整數(shù)規(guī)劃模型等相比，0-1規(guī)劃模型的求解效率更高[28]，因此上述模型比RCPSP混合整數(shù)規(guī)劃模型等通用模型更為簡(jiǎn)單有效。

4 實(shí)驗(yàn)分析

我們將上述0-1規(guī)劃模型用MATLAB (R2015b)編程，在配置為Intel?Core (TM) i5-2450M CPN @ 2.50GHz，內(nèi)存4.00 Gb RAM的電腦上運(yùn)行，運(yùn)用CPLEX MIN Solver (Version 12.6)求解。首先，運(yùn)用該方法模擬求解將大型工程項(xiàng)目中某100個(gè)平行工序調(diào)整為50對(duì)順序工序?qū)? 并使項(xiàng)目工期延遲量最小的問題，共模擬60個(gè)案例，CPU運(yùn)行時(shí)間平均為0.2605秒，最短為0.17秒，如圖4所示。

圖4 將100個(gè)平行工序調(diào)整為50對(duì)最優(yōu)順序工序?qū)Φ膶?shí)驗(yàn)結(jié)果

進(jìn)一步地，我們逐步擴(kuò)大該實(shí)驗(yàn)規(guī)模，運(yùn)用該模型分別模擬求解了將工程項(xiàng)目中的某200、300、400和500個(gè)平行工序調(diào)整為對(duì)項(xiàng)目工期影響最小的100、150、200和250對(duì)平行工序?qū)Φ膯栴}，每個(gè)問題模擬60個(gè)案例，其結(jié)果如圖5所示。表1總述了上述各問題的模擬運(yùn)算結(jié)果?？梢钥闯觯词箤?duì)于500個(gè)平行工序規(guī)模的問題，運(yùn)用該純0-1規(guī)劃模型也僅平均耗時(shí)10.66秒(最短耗時(shí)7.74)即可求得最優(yōu)解，具有較高的求解效率。

表1 實(shí)驗(yàn)?zāi)M結(jié)果

圖5 將200, 300, 400, 500個(gè)平行工序調(diào)整為100, 150, 200, 250對(duì)最優(yōu)順序工序?qū)Φ膶?shí)驗(yàn)結(jié)果

5 結(jié)語(yǔ)

當(dāng)工程項(xiàng)目受到預(yù)期之外的資源短缺時(shí)，需要考慮將原計(jì)劃中的許多平行工序調(diào)整為順序工序，而這樣會(huì)導(dǎo)致項(xiàng)目工期延遲，因此需要考慮能使項(xiàng)目工期延遲最小的調(diào)度方案。該平行工序順序優(yōu)化問題是特殊的或局部型RCPSP，也是組合優(yōu)化問題，而本文主要針對(duì)其代表性子問題之一——將工程項(xiàng)目中某2n個(gè)平行工序調(diào)整為n對(duì)順序工序?qū)?，且?duì)項(xiàng)目工期影響最小。該問題的可行方案數(shù)可達(dá)(2n!)/n!，因此要實(shí)現(xiàn)更有效的求解效果，需要新的更具針對(duì)性的理論和方法。

本文借助CPM網(wǎng)絡(luò)解決該平行工序順序優(yōu)化問題，從路線角度分析了工序時(shí)間參數(shù)與該調(diào)度問題之間的關(guān)系。借助這一關(guān)系，可以僅用工序的兩個(gè)參數(shù)量化“平行工序順序化”對(duì)項(xiàng)目工期的影響，顯著降低了求解難度。進(jìn)一步地，建立了該問題的純0-1規(guī)劃模型，并通過(guò)實(shí)驗(yàn)?zāi)M驗(yàn)證了該模型的效率。研究結(jié)果顯示，本文所揭示的工序時(shí)間參數(shù)與項(xiàng)目工期之間的關(guān)系及規(guī)律是簡(jiǎn)化和求解平行工序順序優(yōu)化問題的關(guān)鍵。在未來(lái)的研究中，我們將以此為基礎(chǔ)，進(jìn)一步研究該類型項(xiàng)目調(diào)度問題的其他子問題，進(jìn)而推進(jìn)總問題的有效解決。