資源受限下平行工序順序?qū)?yōu)化的0-1規(guī)劃模型

蘇志雄，魏漢英，涂遠芬

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

1 引言

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

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

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

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

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

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

2 問題描述

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

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

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

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

3 理論分析及建模

3.1 理論分析

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

定理1將項目中平行工序A和B調(diào)整為順序工序?qū)→B，造成項目工期延遲量，即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)過A→B的新增路線

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

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

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

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

即：

而若?DAiAj=0，則：

=maxDAiAj

證畢。

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

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

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

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

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

(5)

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

z≥maxDAiAj，AiAj∈Ω

從而可得：

minz=maxDAiAj，AiAj∈Ω(6)

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

minz

(7)

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

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

令A(yù)*表示2n個平行工序的集合，要將這2n個平行工序調(diào)整為n對順序工序?qū)?，各工序Ai∈A*只能和A*中所有剩余工序中的一個(記為Aj)排成順序唯一的工序?qū)?Ai→Aj或Aj→Ai)，即?yAiAj和?yAjAi(?Aj∈A*)中有且只有一個變量等于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ī)劃模型等通用模型更為簡單有效。

4 實驗分析

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

圖4 將100個平行工序調(diào)整為50對最優(yōu)順序工序?qū)Φ膶嶒灲Y(jié)果

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

表1 實驗?zāi)M結(jié)果

圖5 將200, 300, 400, 500個平行工序調(diào)整為100, 150, 200, 250對最優(yōu)順序工序?qū)Φ膶嶒灲Y(jié)果

5 結(jié)語

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

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