基于網(wǎng)絡(luò)計劃的施工項目調(diào)度優(yōu)化問題研究

柯 玲

(寧夏大學(xué)新華學(xué)院，寧夏 銀川 750000)

0 引言

工程項目進(jìn)度管理最重要的是設(shè)計一個合理的進(jìn)度計劃，進(jìn)度計劃需要按照項目施工的目的設(shè)計目標(biāo)函數(shù)。目前國內(nèi)外對項目調(diào)度問題的理論模型、算法設(shè)計以及實驗驗證等方面都取得了很大的進(jìn)展。在國內(nèi)研究文獻(xiàn)中，張立輝研究了資源受限條件下的重復(fù)性項目調(diào)度問題，考慮到重復(fù)性項目中的工序存在工作連續(xù)性約束，對串行進(jìn)度生成方案進(jìn)行了改進(jìn)，在此基礎(chǔ)上設(shè)計了一種求解模型的遺傳算法[1]；熊鷹提出了資源受限施工項目凈現(xiàn)值最大化問題。設(shè)計了一種求解模型的蟻群算法[2]。

工程活動的完成需要考慮各種類型資源如何利用，工期的優(yōu)化，利潤的最大。如何利用有限的資源進(jìn)行資源優(yōu)化和工程調(diào)度，這是在具體施工中普遍關(guān)心的問題。本文主要圍繞以下兩方面問題進(jìn)行研究與分析。

1 資源受限工程調(diào)度問題的分類

近年來，關(guān)于資源受限工程調(diào)度問題的分類的方法有很多分類模型。本文根據(jù)項目調(diào)度的目標(biāo)函數(shù)不同，可以分為：（1）項目工期最小化；（2）資源均衡問題；（3）最大化項目凈現(xiàn)值。

1.1 項目工期最小化

在一般項目施工之前都會制定合理的施工網(wǎng)絡(luò)計劃，部分施工項目在施工過程目的是在最短的工期內(nèi)完成項目施工。縮短工期可能會帶給項目很多壓力，消耗更多的資源。這就需要確定合理的施工方案，使得施工項目的工期時間與成本的支出達(dá)到最優(yōu)化。這類問題的模型如下：

問題描述：整個項目包含j(j=1,2,…，J)個子項目，每個項目施工結(jié)束需要的資源為k種，每種資源的需求量為qjk，每個子項目的施工時間為dj，第k種資源的需求量為Qk(k=1,2,…，K)，子項目j的施工開始時間為STj，At為這件在（t-1，t）這個時間段內(nèi)要施工的項目集合。i∈pj,i=1,2,…,J，其中i為子項目j的準(zhǔn)備活動。

目標(biāo)函數(shù)為：

s.t.子項目的間的關(guān)系

有些項目工期問題還需要考慮其他方面的因此，比如費用，網(wǎng)絡(luò)計劃中的關(guān)鍵施工路線等。

1.2 資源均衡問題

施工的資源均衡問題也是網(wǎng)絡(luò)計劃中的重要組成部分。部分施工項目對資源利用有要求,在施工過程中希望資源利用可以保持平衡。這類問題的數(shù)學(xué)模型如下：

問題描述：假設(shè)施工項目由M個子項目（a1,a2,…,aM）組成，子項目aj，j=1,2,…,M需要施工時間為為非負(fù)整數(shù)；施工項目需要的總資源數(shù)為K，子項目aj需要的施工資源k(k=1,2,…,K)的總量為rrk(aj)。

目標(biāo)函數(shù)的建立：這類問題的目標(biāo)是資源需求量最小，根據(jù)時間的施工時間及資源需求量I最小建立數(shù)學(xué)模型。

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

注：ck是第k中資源的價格，rrk(t)是在t時間資源k的需求量，計算公式如下：

注：rrkt(aj)是t時間段子項目aj對資源k的需求量，子項目開工時間的約束條件如下。

1.3 最大化項目凈現(xiàn)值

利潤最大化，就是在資金總量不變的情況下，通過統(tǒng)籌安排，對各種項目方案所需的資金進(jìn)行合理分配，以期達(dá)到投資的最大收益[3]。這類問題強調(diào)的是利益最大化，對工期最小化和資源均衡問題都沒有最優(yōu)化的要求。這這類問題的模型如下：

問題描述：假設(shè)施工項目的總預(yù)算A，總預(yù)算A的投資分為I種資源，投資時間段分為n期，每期投入量為bi1,…,bij(i=1,…,n,j=1,…,m)每年施工項目的投資總額為a1,…,am投資手段為B1,…,Bm每年獲得效益為C1,…,Cm，考慮時間對資金的影響，假設(shè)收益率為q其中，x1,x2,…,xn為各子項目的資金分配值，則目標(biāo)函數(shù)使凈現(xiàn)值NPV最大。

對于約束方程，假設(shè)每期的投資是固定的，則有約束方程為：

2 資源受限工程調(diào)度問題的求解

2.1 最優(yōu)化方法

根據(jù)上述對資源受限工程調(diào)度問題的分類，在資源受限工程調(diào)度問題如果分別是以工程工期，資源消耗最小，凈現(xiàn)值最大為目標(biāo)函數(shù)的最優(yōu)化方法中，分支界定法由于計算效果和效率上的特點被人們廣泛采用。分支界定法是數(shù)學(xué)模型中對于整數(shù)線性規(guī)劃的一種求解方法。分支定界算法是資源受限工程調(diào)度問題最優(yōu)化的方法。在這類問題的求解過程需要建立枚舉樹。對于線性規(guī)劃問題的求解方法有以下幾種方法：

（1）分支界定法—可求純或混合整數(shù)線性規(guī)劃。

（2）割平面法—可求純或混個整數(shù)線性規(guī)劃。

（3）隱枚舉法—求解“0-1”整數(shù)規(guī)劃。

①過濾隱枚舉法；

②分支隱枚舉法。

（4）匈牙利法—解決指派問題。

（5）蒙特卡洛法—求解各種類型規(guī)劃。

用最優(yōu)化方法解決實際的工程調(diào)度問題一般的步驟是：一、分析問題、整理數(shù)據(jù)、二、建立模型、列出目標(biāo)函數(shù)，以及對目標(biāo)函數(shù)的約束條件。三、解出問題，檢驗最優(yōu)解。四、應(yīng)用最優(yōu)解。

最優(yōu)化的核心內(nèi)容是數(shù)學(xué)模型的建立，下面介紹一下數(shù)學(xué)模型建立的一般過程。

設(shè)變量：在工程項目施工的網(wǎng)絡(luò)計劃中，不管施工項目的目標(biāo)函數(shù)是什么，都需要假設(shè)出建立目標(biāo)函數(shù)需要的各種數(shù)學(xué)變量。

給出約束條件：不管是目標(biāo)函數(shù)是最小工期，資源均衡的優(yōu)化還是凈現(xiàn)值最大化都是有約束條件的，比如資源均衡問題要考慮施工項目的開始時間和結(jié)束時間的約束，工期最小優(yōu)化考慮資源總需求量的約束。

建立目標(biāo)函數(shù)：用最優(yōu)化方法求解問題核心的部分就是建立合適的目標(biāo)函數(shù)，目標(biāo)函數(shù)最基本的類型就是最大和最小的目標(biāo)函數(shù)。

2.2 現(xiàn)代算法

現(xiàn)代優(yōu)化算法是20世紀(jì)80年代初興起的啟發(fā)式算法。這些算法包括禁忌搜索（Ta-bu Search）、模擬退火（Simulated Annealing）、遺傳算法（Genetic Algorthms）、人工神經(jīng)網(wǎng)絡(luò)（Neural Networks）。他們主要用于解決大量的實際問題。目前這些算法理論和實際應(yīng)用方面得到了較大的發(fā)展。無論這些算法是怎樣產(chǎn)生的，它們都有一個共同的目標(biāo)—就NP-hard組合優(yōu)化問題的全局最優(yōu)解。雖然有這些目標(biāo)，但是NP-hard理論限制它們只能以啟發(fā)式的算法去求解實際問題。

啟發(fā)式算法包括的算法很多，例如求解復(fù)雜優(yōu)化問題的蟻群算法（Ant Colony Algo-rithms）。有些啟發(fā)式算法是根據(jù)實際問題而產(chǎn)生的；另外一些算法是集成算法，這些算法是諸多啟發(fā)式算法的合成。

用算法求解資源受限項目調(diào)度問題一般包括五個過程：

選取編碼程序與方式，這一過程主要是要確定解碼規(guī)則。

確定算法的初始化方式。

確定算法的迭代方法。

確定整個算法帶入數(shù)據(jù)的適應(yīng)區(qū)間。

確定整個算法的終止條件。

近年來，隨著科技的發(fā)展，對于各類施工項目問題的智能優(yōu)化算法不斷發(fā)展和成熟，目前各種資料都有關(guān)于智能優(yōu)化算法求解施工項目調(diào)度優(yōu)化問題。比如郭研等學(xué)者給出了資源均衡問題的微粒群算法。

3 結(jié)語

本文對網(wǎng)絡(luò)計劃的施工項目調(diào)度優(yōu)化問題的研究主要是圍繞兩個方面：一是對資源受限工程調(diào)度問題按照目標(biāo)函數(shù)不同分類并建立相應(yīng)的數(shù)學(xué)模型，二是對求解項目調(diào)度優(yōu)化問題方法的總結(jié)梳理。施工項目調(diào)度優(yōu)化問題是一類比較復(fù)雜的優(yōu)化問題，在今后的工作中就是對求解的算法做進(jìn)一步的研究。