柯 玲

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

0 引言

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

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

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

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

1.1 項(xiàng)目工期最小化

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

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

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

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

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

1.2 資源均衡問題

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

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

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

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

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

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

1.3 最大化項(xiàng)目?jī)衄F(xiàn)值

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

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

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

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

2.1 最優(yōu)化方法

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

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

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

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

①過濾隱枚舉法；

②分支隱枚舉法。

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

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

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

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

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

給出約束條件：不管是目標(biāo)函數(shù)是最小工期，資源均衡的優(yōu)化還是凈現(xiàn)值最大化都是有約束條件的，比如資源均衡問題要考慮施工項(xiàng)目的開始時(shí)間和結(jié)束時(shí)間的約束，工期最小優(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）。他們主要用于解決大量的實(shí)際問題。目前這些算法理論和實(shí)際應(yīng)用方面得到了較大的發(fā)展。無(wú)論這些算法是怎樣產(chǎn)生的，它們都有一個(gè)共同的目標(biāo)—就NP-hard組合優(yōu)化問題的全局最優(yōu)解。雖然有這些目標(biāo)，但是NP-hard理論限制它們只能以啟發(fā)式的算法去求解實(shí)際問題。

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

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

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

確定算法的初始化方式。

確定算法的迭代方法。

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

確定整個(gè)算法的終止條件。

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

3 結(jié)語(yǔ)

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