項目多資源均衡
——投資成本最小的混合整數(shù)線性規(guī)劃

馬國豐，顧凌赟，艾 琪

（同濟大學 經(jīng)濟與管理學院，上海 200092）

資源是影響工程項目進度、質(zhì)量和成本的重要因素。項目進度計劃不僅要考慮項目中各工序的邏輯順序，還需考慮各類資源的均衡使用。資源均衡是在盡可能使進度計劃中描述資源使用的各種動態(tài)曲線（勞動力、材料、機械等）不出現(xiàn)短時期的高峰和低谷，從而避免現(xiàn)場擁擠而增設臨時設施，也減少二次搬運而造成的勞動管理復雜度。尤其是在現(xiàn)代大型復雜項目施工中，涉及各類租賃或采購費用高昂的施工機械等重要資源。在項目計劃中，資源的使用模式比資源的使用峰值更值得關(guān)注。然而，考慮到任何項目都需要建設時間，且資金時間價值的存在［1］，為有效利用并節(jié)約項目投入資金，應在盡可能范圍內(nèi)推遲項目各活動的開工時間，避免過早地投入資金，造成資金積壓；但推遲活動開工時間，則可能導致?lián)尮がF(xiàn)象和材料供應脫節(jié)，影響工程的順利進行。需要考慮資金時間價值因素的均衡優(yōu)化。因此，項目進度計劃需保證資源波動及投入資本兩者的最小化。

目前，對資源均衡問題（Resource Leveling Problem，RLP）的研究主要集中在資源不受限和資源受限兩類，早期研究主要集中在前一類［2］。RLP問題的優(yōu)化方法可分為基于枚舉、整數(shù)規(guī)劃或動態(tài)規(guī)劃的精確算法，基于優(yōu)先規(guī)則的啟發(fā)式算法及智能算法。其中，精確算法中主要歸納為3類：

（1）對活動可行的整數(shù)開始時間進行迭代。Ahuja［3］考慮了資源輪廓變化的平方和，而Younis等［4］則考慮了相對于期望值的資源需求的偏離絕對值。Bandelloni等［5］設計了基于活動整數(shù)時差的動態(tài)規(guī)劃方法。對于有時間約束的問題，Neumann等［6］在上述方法的基礎上，提出了基于分支定界的時間窗。Rieck等［7］則采用快速精確算法，將經(jīng)典資源均衡問題的目標函數(shù)線性化表示，列出了割平面框架。在考慮資源需求實際值與計劃值的偏差的基礎上，Tang等［8］引入了重要性權(quán)重因子進行約束規(guī)劃求解。

（2）對所有可行的次序網(wǎng)絡中的進行迭代。Gather等［9］提出一種基于樹的方法，對所有似穩(wěn)定調(diào)度計劃進行迭代，并采用了避免冗余的方法。為了迭代所有次序網(wǎng)絡的極點，通過固定活動開始時間來生成對應的生成樹。同時引進了“T-最小樹”概念，以避免實施2個代表1個或相同似穩(wěn)定調(diào)度計劃的不同樹。

（3）通過引進二進制變量的混合整數(shù)規(guī)劃方法。這是在Pritsker等［10］和Easa［11］的研究中所啟示。Pritsker等引進了一個將活動分別配置在不同時刻的二進制變量；Easa則是引進了一個描述活動相對于最早開始時間推遲程度的二進制變量。在前人研究的基礎上，El-Sayegh等［12］進行了創(chuàng)新，提出了一個允許活動分裂以控制成本的二進制變量。

綜上，在資源均衡問題研究中，已有的解決方法已較成熟，而具有特殊目標函數(shù)的資源均衡問題將成為當前研究的主流方向。因此，本文考慮項目實施主體的同時也關(guān)注投資主體的投入，構(gòu)建最小化項目投資成本的多資源均衡優(yōu)化模型，對模型中涉及的2個目標函數(shù)分別進行線性化處理，提出一種混合整數(shù)線性規(guī)劃方法進行求解。

1 問題描述

1.1 資源均衡問題

本文研究的資源均衡問題的基本前提：

（1）工程項目由n+2個任務組成，執(zhí)行沒有中斷。用單節(jié)點網(wǎng)絡圖表示，記作N=（V，A），V是頂點的集合，A是弧長的集合。頂點集V=｛1，2，…，n，n+1，n+2｝，其中，任務第1和第n+2個為虛工序，分別表示唯一最早開始和最晚完成的任務。

（2）資源均衡問題只針對有限資源，且單位時間的資源提供量為常數(shù)。

（3）項目中的每個任務都能使用多種資源，但每種任務僅考慮為單執(zhí)行模式。

資源均衡優(yōu)化是指在項目工期固定不變的條件下，合理地調(diào)整項目網(wǎng)絡計劃中的某些任務，使資源的需求量在項目工期范圍內(nèi)趨于均衡的過程。衡量資源使用量是否均衡的指標有多種，如方差［13］、根方差、極差、最大絕對離差和不均衡系數(shù)。本文考慮活動資源使用相對于各資源使用水平的偏差絕對值作為目標函數(shù)，目標函數(shù)定義為

1.2 投資成本問題

由于在工程建設實踐中資金是具有時間價值的，尤其在建設周期較長、費用較大的建筑工程中。故應考慮資金時間價值，將項目現(xiàn)金流量按資本成本進行折現(xiàn)，使不同時點的資金具有可比性，真實地反映出不同時期的現(xiàn)金流出對項目的影響。保證項目總投入最小，即，其中，qi為活動i的資金流入，折現(xiàn)因子e—α=1/（1+r），r為資金的機會成本。

1.3 投資成本最小化的資源均衡優(yōu)化

對建筑工程施工計劃優(yōu)化的目的在于制定一個合理的網(wǎng)絡調(diào)度計劃，使得資源配置均衡，且網(wǎng)絡凈現(xiàn)值最大。綜合考慮資源優(yōu)化及資金時間價值的現(xiàn)實意義，將兩者結(jié)合組成一個多目標規(guī)劃問題。本文采用線性加權(quán)法構(gòu)造一個新的目標函數(shù)，即為F（s）=φ1f（s）+φ2g（s）。其中：

2個權(quán)重系數(shù)φ1、φ2取固定值，分別為資源均衡目標函數(shù)f（s）和投資成本目標函數(shù)g（s）的最大值的倒數(shù)，以此對活動資源使用相對于各資源使用水平的偏差絕對值進行量化處理。

2 混合整數(shù)線性規(guī)劃模型

資源均衡優(yōu)化屬于組合優(yōu)化問題，對于活動數(shù)目較多的問題在理論上稱為NP問題［14-16］。由于目標函數(shù)為非常規(guī)函數(shù)，故本文通過引進二進制變量及相關(guān)約束條件，對目標函數(shù)進行線性化處理，構(gòu)建混合整數(shù)線性規(guī)劃模型。

2.1 活動浮動約束

（1）引進二進制變量表示各活動的浮動程度，配置到可行的開始時間t中，即

2.2 網(wǎng)絡邏輯約束

令活動i的緊后工序集為Qi，j∈Qi，對于活動i及其緊后工序中的每一個活動間存在約束：活動i的浮動時間超出其自由時差的部分不能多與其緊后工序的浮動時間。即xi—FFi≤xj，i∈V，j∈Qi。當xi≤FFi時，約束條件顯然滿足。

2.3 項目資源約束

項目共享K種有限資源，各種資源的單位成本為ck（ck≥0），Rk為各資源的額定資源量，每個工序i對資源k的資源需求量為rik，虛工序的資源需求量為0。令Zkt表示在某一調(diào)度計劃中時刻t對資源k的消耗量，它包含關(guān)鍵活動及非關(guān)鍵活動的資源需求。由于工程實踐中資源供給存在限制，故

其中：Zkt，c為t時刻在執(zhí)行的關(guān)鍵活動對k的資源需求Zkt，c=rik；Zkt，nc為t時刻在執(zhí)行的非關(guān)鍵活動對k的資源需求，由于非關(guān)鍵活動允許時差波動，故

2.4 目標函數(shù)線性化

本文選取計劃資源消耗相對于各資源使用水平偏差的絕對值為衡量指標，即函數(shù)為非線性化，將絕對值消去進行分階段考慮，并引進輔助變量，且滿足

對所有的調(diào)度計劃，（Zkt＞Yk時）或（Yk＞Zkt時）取值為正，另一則為0。因此，資源均衡目標函數(shù)轉(zhuǎn)換為

其中前兩項及αe—αsi0為常數(shù)，則投資成本最小值，轉(zhuǎn)化為

2.5 模型構(gòu)建

考慮資源均衡——投資成本2個目標的RLVC模型。

總目標函數(shù)

該優(yōu)化問題即生成調(diào)度計劃，調(diào)整各活動開始時間Si，即確定推遲時間xi，從而導致目標函數(shù)變化。

3 算例分析

PSPLIB（project scheduling problem library）由Kolisch等［16］采用實驗設計的方法設計，通過設計軟件ProGen來設定項目調(diào)度問題的各種參數(shù)。由軟件可產(chǎn)生符合參數(shù)要求的具有不同目標的調(diào)度問題，包括480個調(diào)度問題，每個問題含30個任務，涉及4種可更新資源。同時，通過對ProGen的擴展，產(chǎn)生一套涉及多種任務模式的調(diào)度問題，從而形成PSPLIB。本文采用PSPLIB標準問題庫中活動多模式j10測試問題集進行驗證分析。運用Matlab進行編程計算。為簡便計算，只選取活動的第1種模式數(shù)據(jù)做參考，如表1所示。

表1 算例基本信息

算例包括12個工序，其中有2個虛工序和10個實工序，施工過程涉及2種可更新資源，資源上限為R1=11，R2=9。假設活動i的資源需求qi與其持續(xù)時間及資源消耗強度呈線性關(guān)系，即目標函數(shù)

以最大資源需求總量為優(yōu)先規(guī)則，計算各活動

最早開始時間

ES=｛0，1，0，0，2，6，9，9，14，14，2，21｝

最晚開始時間

LS=｛0，1，0，0，5，6，9，12，14，18，2，21｝

從而計算活動總時差

TF=｛0，0，0，0，3，0，0，3，0，4，0，0｝

自由時差

FF=｛0，0，0，0，3，0，0，3，0，4，0，0｝

確定關(guān)鍵活動集A（C）=｛1，4，2，11，6，7，9，12｝，非關(guān)鍵活動集A（NC）=｛3，5，8，10｝。以最早開始時間進行調(diào)度的資源輪廓圖，如圖1所示。資源水平Y(jié)1=3.7，Y2=7。

從t=1時刻開始，確定各個時刻關(guān)鍵活動和非關(guān)鍵活動對資源的需求量。確定目標函數(shù)取最小值時，活動的浮動時間為x3=0，x5=0，x8=1，x10=0，最優(yōu)調(diào)度計劃

圖1 資源輪廓圖（最早開始時間）

輸出對應的資源輪廓圖，資源波動偏差為156，如圖2所示。

圖2 綜合優(yōu)化資源輪廓圖（最優(yōu)調(diào)度計劃）

本文考慮投資成本和資源均衡2個目標的優(yōu)化，較僅考慮資源均衡為目標時的投資成本減少了16%，而資源波動保持不變；較僅考慮投資成本目標時的資源波動減少了2.5%，而投資成本則增大了1.3%。

4 結(jié)語

有效利用投資成本的同時保證資源均衡使用，在項目中對實施主體過程管理、投資主體資金投入具有重要作用。本文將雙方關(guān)注點各取一個重要指標，綜合考慮并提出資源受限情況下的項目多資源均衡——投資成本優(yōu)化的混合整數(shù)線性規(guī)劃模型：①對具有開工柔性的非關(guān)鍵活動的資源需求，借助于活動浮動參數(shù)來描述，結(jié)合關(guān)鍵活動的資源消耗，完成資源使用波動目標函數(shù)。②由于資金存在時間價值，為保證可比性，對不同時刻的資金投入折現(xiàn)在項目初始時刻，并運用泰勒展開線性化處理，完成投資成本的目標函數(shù)。③通過線性加權(quán)，將雙目標優(yōu)化統(tǒng)一，在網(wǎng)絡及資源約束下建立模型，運用Matlab軟件實現(xiàn)模型的求解。最后，對PSPLIB標準問題庫進行驗證，結(jié)果表明，較單目標優(yōu)化，綜合優(yōu)化后的調(diào)度計劃既能保證資源波動平穩(wěn)，又能提高資金使用效率，有利于項目利益相關(guān)者間的協(xié)調(diào)，且計算過程可行有效。

另外，本文需要進一步研究的是在原先資源均衡基本前提之外，研究活動多模式、活動可搶斷等情境下的資源均衡，不僅如此，用其他啟發(fā)式或智能算法來解決也可成為該領(lǐng)域的努力方向。