基于遺傳算法的項目管理優(yōu)化仿真研究

曾彪, 劉欣

(上海交通大學(xué)安泰經(jīng)濟及管理學(xué)院, 上海 200030)

基于遺傳算法的項目管理優(yōu)化仿真研究

曾彪, 劉欣

(上海交通大學(xué)安泰經(jīng)濟及管理學(xué)院, 上海 200030)

傳統(tǒng)的項目進度一維優(yōu)化擴展至有偏好的二維目標（進度、成本）優(yōu)化, 同時將成本優(yōu)化目標分解為項目成本大小以及資源均衡度從而構(gòu)成三維目標優(yōu)化, 將無資源約束的環(huán)境擴展至資源約束下的復(fù)雜環(huán)境, 將局部搜索優(yōu)化領(lǐng)域擴展至全局范圍內(nèi)的優(yōu)化. 在內(nèi)容上, 先對項目的單目標優(yōu)化管理理論進行詳盡研究并指出其現(xiàn)實的局限性, 同時提出了智能啟化式方法-遺傳算法在資源約束下項目管理優(yōu)化方面的優(yōu)勢. 在此基礎(chǔ)上本文構(gòu)建了基于三維目標偏好的項目管理優(yōu)化仿真模型, 解決了項目管理優(yōu)化理論中最為重要的兩大問題：資源約束下的項目進度優(yōu)化以及資源約束下的三維目標（項目進度、項目成本以及資源均衡度）的優(yōu)化問題. 為了驗證此模型對以上問題的有效性, 本文應(yīng)用Matlab仿真技術(shù)進行仿真模擬并與傳統(tǒng)方法做比較, 從結(jié)果可以看出遺傳算法能夠更好的解決此類問題.

項目管理; 三維目標優(yōu)化; 遺傳算法; 三維偏好

1引言

隨著經(jīng)濟全球化的發(fā)展, 各個行業(yè)的競爭環(huán)境已經(jīng)從相對穩(wěn)定型轉(zhuǎn)變成了動態(tài)多變型. 新技術(shù)的發(fā)展以及動態(tài)的資源供給要求組織在項目范疇內(nèi)逐漸實行矩陣式管理以做到快速決策, 利用有限的資源謀得最優(yōu)績效.但是現(xiàn)有項目管理優(yōu)化理論更多地是將項目假定在沒有任何約束或是較為寬泛的約束下進行, 項目管理優(yōu)化的目標也往往集中在項目的進度方面. 即便增加了項目成本因素也僅涉及成本的大小, 而沒有考慮該項目不同時段對資源需求量的變化對整個組織績效的影響. 同時不同行業(yè), 不同組織以及不同項目對項目管理優(yōu)化目標也存在不同的偏好, 這也增加了優(yōu)化函數(shù)以及優(yōu)化方法的復(fù)雜性, 從而也對傳統(tǒng)的項目管理優(yōu)化理論提出挑戰(zhàn).

如表1所示, 目前項目管理優(yōu)化方法可以分為四大類別：軟邏輯優(yōu)化, 精確算法, 啟發(fā)式算法以及在此基礎(chǔ)上形成的智能啟發(fā)式算法. 應(yīng)用性較為普遍的智能啟發(fā)式算法包括模擬退火算法以及逐漸成為研究熱點的遺傳算法以及混合算法等.

表1 項目管理優(yōu)化方法綜述Table 1 Project schedule optimizing method review

分離弧概念啟發(fā)式方法Bell&Han(1991), Tormos&Lova(2001)將分離弧的概念引入啟發(fā)式算法, 對于特定行業(yè)或是特定項目起到了較為理想的優(yōu)化效果能啟發(fā)式方法模擬退火算法Boctor、Cho 與 Kim、Bouleimen 與Lecocq、Valls 等(2005)將物理退火步驟中系統(tǒng)粒子變動引起的能量與狀態(tài)的變化數(shù)字化, 以項目管理優(yōu)化目標函數(shù)的解來代替遺傳算法[3]S Hartmann, D Briskorn（2010）, Alczraz& Maroto, Sonke Hartmann依據(jù)項目求解目標的適應(yīng)度函數(shù)為判別標準, 將一定數(shù)量的母代種群中適應(yīng)度函數(shù)值較高的個體挑選出來直接遺傳至下一代, 避免其變異、交叉混合遺傳算法Valls, P Wuliang, Quintanilla(2007), 劉士新[4], 王夢光和唐加福(2002)以遺傳算法為基礎(chǔ), 但是在某些特定的優(yōu)化過程中引入退火算法以及其他智能啟發(fā)式算法的優(yōu)化方法. 應(yīng)用范圍較為廣泛.

對于智能啟發(fā)式算法, Lee&Kim[5]提出將蟻群算法與遺傳算法相結(jié)合創(chuàng)造一種新的復(fù)合算法, 作者借用啟發(fā)式算法的優(yōu)先規(guī)則進行算法編碼. Hartmann(1998)[6]提出了以各個工序的列表來表達基因的遺傳算法, 這些列表則是以項目季度為基礎(chǔ). 1999 年 Linet Ozdamar[7]做了一種命題假設(shè), 提出在資源有限供應(yīng)的前提約束條件下求得工期最短的項目進度優(yōu)化算法, 并借以遺傳算法實現(xiàn)最優(yōu)解的求解. Alczraz & Maroto(2001)[8]引入了自適應(yīng)這一自然科學(xué)應(yīng)用領(lǐng)域的機制到啟發(fā)式算法. 2002 年, Sonke Hartmann[9]在Alczra的基礎(chǔ)上完善了自適應(yīng)遺傳理論. Bouleimen & Leeoeq(2003)[10]摒棄了應(yīng)用較為普遍的遺傳算法, 引入模擬退火算法求解資源約束下的項目進度優(yōu)化問題.

在項目管理理論中, 最重要的是項目進度、項目成本以及項目質(zhì)量三要素：而項目質(zhì)量是項目的固有屬性,是項目管理最基礎(chǔ)的目標, 其本身優(yōu)化的空間非常有限. 同時項目的質(zhì)量目標對于每個行業(yè), 每個公司以及每個項目其標準各不相同, 從而無法建立一個應(yīng)用較為廣泛的量化模型, 也無法在此基礎(chǔ)上進行優(yōu)化分析. 鑒于項目質(zhì)量管理優(yōu)化研究價值不大, 同時研究較為復(fù)雜, 因此本文僅鎖定二維的項目管理范疇, 即項目成本以及項目進度范疇, 同時將項目成本分解為成本大小與資源均衡度.

2基于遺傳算法的項目管理優(yōu)化模型

結(jié)合前文所提到的單目標項目管理優(yōu)化理論的研究經(jīng)驗, 本文將傳統(tǒng)的項目進度一維優(yōu)化擴展至有偏好的二維目標（進度、成本）優(yōu)化, 同時將成本優(yōu)化目標分解為項目成本大小以及資源均衡度從而構(gòu)成三維目標優(yōu)化. 進而本文提出了基于三維目標偏好的項目管理優(yōu)化模型. 其中三維目標包括項目成本大小、項目進度（時間）以及項目資源利用的均衡度. 偏好依據(jù)不同行業(yè)、不同公司、不同項目以及不同的項目管理者而不同, 主要依靠專家打分法確定各個維度的具體偏好值. 同時借助啟發(fā)式算法—遺傳算法去計算該模型的解.

約束條件：

其中: a1+a2 =1, a3+a4=1, 且a1, a2, a3, a4不小于零. 假定在t時刻項目工序i開工, 則xit =1, 否則為0. ESN 表示整個項目的歷時工期; N 為項目工序的最后一個; Di 為項目工序i的歷時時間; ESi 為項目工序i最早的開始時間; LSi 為項目工序 i最晚的開始時間; Rik 為項目工序i 對特定資源k單位時間用量; Skt 為整個項目在時間t時可以提供的k資源總量; Bn 為項目工序n的所有緊前工序的集合; M表示總工期內(nèi)資源統(tǒng)計時段數(shù); R’ 表示平均資源使用量; Ri 表示第i天資源使用量,且Ri=∑Ri; Rij表示為第i天j工序資源使用量; C1i表示在第i天保持項目運行的直接費用; C2i表示在第i天保持項目運行的間接費用.

式（1-1）為目標函數(shù), 表示多目標皆為最小化時項目的目標函數(shù). 本文的問題模型以最小化項目工期、資源的綜合利用、最小化項目運營成本為目標. f1(x)代表最小化的項目工期, 是對項目進度優(yōu)化目標的測量. 與前述模型相同, 為了實現(xiàn)項目進度的最優(yōu)化解, 項目可以盡可能增加資源, 增加趕工度, 項目的每個工序都應(yīng)盡可能的實現(xiàn)最早完成時間. f2(x)是表征項目資源平衡利用指數(shù)的目標函數(shù), 我們將資源受限的條件下資源平衡的指標定義為最小化資源利用的方差, 以單位時間資源使用量所計算得到的方差來作為評價遺傳算法子個體優(yōu)劣的標準. 評價函數(shù)的判斷標準是資源利用方差越小的個體適應(yīng)值越大, 表明其均衡利用度越大. 這樣,隨著遺傳進化的進行,算法最終找到方差最小的資源計劃. f3(x)代表項目運行的總成本大小, 包括項目運行過程中所消耗的直接費用成本以及與項目進度成正比的間接費用成本.

另外, 遺傳算法的優(yōu)點是將問題參數(shù)編碼成染色體后進行優(yōu)化, 而不是針對參數(shù)本身, 從而不受函數(shù)約束條件的 限制; 搜索過程從問題的 一個解開是, 而不是單個個體, 具有隱含并行搜索特征, 可大大減少陷入局部最小的可能. 但同時遺傳算法也存在以下缺點: 對于結(jié)構(gòu)復(fù)雜的 RCPSP, 搜索空間大, 搜索時間比較長, 往往會出現(xiàn)早熟早收斂的情況; 對初始種群很敏感, 初始種群的選擇常常直接影響解的質(zhì)量和算法效率.

3結(jié)論

三維目標[11]: 1.最小化項目工期: 資源約束下傳統(tǒng)的項目進度優(yōu)化管理問題的目標, 即追求項目工期最短. 2.項目成本大小: 包括項目的直接成本以及項目的間接成本. 3.項目資源均衡利用率: 各節(jié)點單位時間所需資源總量的均衡利用. 如圖1所示, 借用Matlab仿真技術(shù), 應(yīng)用遺傳算法可以得到項目三維目標優(yōu)化結(jié)果. 項目的總進度與項目總的成本大小之間呈現(xiàn)出凹形的邏輯關(guān)系, 即工期過短或過長都會造成施工成本大幅上升. 這與項目的直接成本與間接成本有關(guān), 工期過低, 項目資源需求量過大, 直接成本過高, 從而導(dǎo)致項目成本大幅上升. 而工期過長, 與間接成本有關(guān)的人員工資, 儲存費用等大幅升高導(dǎo)致項目成本上升. 而項目進度與項目資源均衡利用度基本成反比關(guān)系, 這是因為項目各個工序的資源需求量是各不相同的, 而關(guān)鍵路徑法所得的最佳項目進度是不考慮項目資源約束以及項目資源均衡利用率的, 因此要提高項目的資源綜合利用率就不得不改變項目的關(guān)鍵路徑, 增加緩沖期, 從而也會延長項目結(jié)束時間, 增加項目的工期. 而項目成本同項目資源均衡度之間呈凹型的關(guān)系, 項目資源均衡度過低往往導(dǎo)致項目資源的浪費, 從而意味著增加了項目的直接成本, 而項目資源均衡度過高往往意味著項目總周期的拉長, 同時也意味著項目間接成本的增加[12].

圖1 基于三維目標偏好的項目管理優(yōu)化模型Figure 1 preference of 3D Project schedule optimizing Model

[1] PATTERSON J H, W D Huber. A horizon-varying, zero-one approach to project scheduling [J]. Management Science, 1974, 20(6): 990-998.

[2] BRUCKER P. A branch and bound algorithm for the resource-constrained project scheduling problem[J]. European Journal of Operational Research, 1998, 107(2): 272-288.

[3] 張揚, 基于遺傳算法的多資源約束下工程項目進度計劃優(yōu)化研究 [D]. 華東交通大學(xué), 2009.

[4] 劉士新, 項目優(yōu)化調(diào)度理論與方法[M]. 北京: 機械工業(yè)出版社, 2007.

[5] LEE J K, KIM Y D. Search heuristics for resource constrained project scheduling[J]. Journal of the Operational Research Society, 1996: 678-689.

[6] HARTMANN S. A competitive genetic algorithm for resource‐constrained project scheduling[J]. Naval Research Logistics (NRL), 1998, 45(7): 733-750.

[7] OZDAMAR L. A genetic algorithm approach to a general category project scheduling problem[J]. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 1999, 29(1): 44-59.

[8] ALCARAZ J, C MAROTO. A robust genetic algorithm for resource allocation in project scheduling[J]. Annals of Operations Research, 2001, 102(1-4): 83-109.

[9] HARTMANN S. A self‐adapting genetic algorithm for project scheduling under resource constraints[J]. Naval Research Logistics (NRL), 2002, 49(5): 433-448.

[10 BOULEIMEN K, H LECOCQ. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version[J]. European Journal of Operational Research, 2003, 149(2): 268-281.

[11] LEU S-S, A T Chen, C-H Yang. A GA-based fuzzy optimal model for construction time–cost trade-off[J]. International Journal of Project Management, 2001, 19(1): 47-58.

[12] 陳建華, 林鳴, 馬士華. 基于過程管理的工程項目多目標綜合動態(tài)調(diào)控機理模型[J]. 中國管理科學(xué), 2005. 13(5): 93-99.

The optimization simulation model based on the project’s three-dimensional target preferences

ZENG Biao, LIU Xin
(Antai College of Economics and Management, Shanghai JiaoTong University, Shanghai 200030, P.R.C.)

The paper extends the traditional one-dimensional project schedule optimization to a preference of 2D target (schedule, cost) optimization, and then to a three-dimensional target optimization. First this article shows the theory of dynamic optimizing project schedule in detail and points out the limitations of existing methods. At the same time, it expounds the intelligent and mineralization type method, the basic principle and application of genetic algorithm, and how to use Matlab genetic algorithm of intelligent optimization function. This paper constructs the multidimensional model of optimizing management of project schedule. At last, the model solves the project schedule management problem respectively: no resource constraints project schedule optimization, the resource constraints project schedule optimization and multi-objective optimization (resource, cost, efficiency). Meanwhile, in order to verify the validity of the genetic algorithm to solve above problems, this paper applies universality case for validation. The results show that the genetic algorithm can solve such problem better compared with other traditional methods.

project management; three-dimensional target optimization; genetic algorithm; preference of 3D

TU712

A

1003-4271(2014)03-0474-04

10.3969/j.issn.1003-4271.2014.03.27

2013-12-23

曾彪(1986-), 男, 山東省濟寧市人, 碩士研究生, 研究方向: 技術(shù)經(jīng)濟及管理; 劉欣(1969-), 女, 布依族, 上海市人, 副教授, 研究方向: 項目管理和決策分析.