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

馬國豐，顧凌赟，艾 琪

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

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

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

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

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

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

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

1 問題描述

1.1 資源均衡問題

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

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

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

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

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

1.2 投資成本問題

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

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

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

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

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

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

2.1 活動浮動約束

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

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

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

2.3 項(xiàng)目資源約束

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

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

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

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

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

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

2.5 模型構(gòu)建

考慮資源均衡——投資成本2個目標(biāo)的RLVC模型。

總目標(biāo)函數(shù)

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

3 算例分析

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

表1 算例基本信息

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

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

最早開始時間

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｝

從而計(jì)算活動總時差

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｝。以最早開始時間進(jìn)行調(diào)度的資源輪廓圖，如圖1所示。資源水平Y(jié)1=3.7，Y2=7。

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

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

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

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

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

4 結(jié)語

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

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