資源受限下平行工序順序對優化的0-1規劃模型

蘇志雄，魏漢英，涂遠芬

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

1 引言

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

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

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

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

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

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

2 問題描述

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

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

圖1 CPM網絡

圖2 平行工序順序對化調整后的網絡

3 理論分析及建模

3.1 理論分析

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

定理1將項目中平行工序A和B調整為順序工序對A→B，造成項目工期延遲量，即DAB為：

DAB=max{EFA-LSB,0}

(1)

(2)

DAB=0

(3)

所以：

(4)

根據CPM法可知[22]：

帶入式(4)可得：

所以：

=EFA-LSB

DAB=max{EFA-LSB,0}

式(1)正確。證畢。

圖3 經過A→B的新增路線

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

根據定理1，我們可以將其拓展，推導出將項目中某2n個平行工序調整為n個順序工序對后，項目工期延遲量的計算方法，如推論1所示：

推論1 將2n個平行工序A1,A2,…,A2n調整為n個順序工序對Ai→Aj，i,j=1,2,…,2n，i≠j造成的項目工期延遲量等于這n個工序對的延遲量DAiAj中的最大值，即maxDAiAj。

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

即：

而若?DAiAj=0，則：

=maxDAiAj

證畢。

3.2 純0-1規劃模型

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

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

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

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

(5)

其中，Ω表示這2n個平行工序中的任意兩個組成的順序工序對的集合，且所有yAiAj=1的工序對中不能有相同的工序，即任一工序只能和另一工序組成一個順序工序對。式(5)表示z≥?DAiAj，AiAj∈Ω，即：

z≥maxDAiAj，AiAj∈Ω

從而可得：

minz=maxDAiAj，AiAj∈Ω(6)

根據推論1，minz表示將2n個平行工序調整為n對順序工序對后，導致項目工期的推遲量，因此模型的目標函數是：

minz

(7)

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

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

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

(8)

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

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

(9)

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

minz

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

yAiAj={0,1}

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

4 實驗分析

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

圖4 將100個平行工序調整為50對最優順序工序對的實驗結果

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

表1 實驗模擬結果

圖5 將200, 300, 400, 500個平行工序調整為100, 150, 200, 250對最優順序工序對的實驗結果

5 結語

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

本文借助CPM網絡解決該平行工序順序優化問題，從路線角度分析了工序時間參數與該調度問題之間的關系。借助這一關系，可以僅用工序的兩個參數量化“平行工序順序化”對項目工期的影響，顯著降低了求解難度。進一步地，建立了該問題的純0-1規劃模型，并通過實驗模擬驗證了該模型的效率。研究結果顯示，本文所揭示的工序時間參數與項目工期之間的關系及規律是簡化和求解平行工序順序優化問題的關鍵。在未來的研究中，我們將以此為基礎，進一步研究該類型項目調度問題的其他子問題，進而推進總問題的有效解決。