任務(wù)可拆分的多模式多項(xiàng)目調(diào)度模型與算法

王偉鑫，王 旭，葛顯龍

（1．重慶大學(xué) 機(jī)械工程學(xué)院，重慶 400030；2．重慶交通大學(xué) 管理學(xué)院，重慶 400074）

0 引言

任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題是針對(duì)項(xiàng)目的相關(guān)活動(dòng)、項(xiàng)目的多種執(zhí)行模式，考慮項(xiàng)目調(diào)度的整體效用最大化，研究子項(xiàng)目、活動(dòng)之間的高效調(diào)度和資源的有效利用問(wèn)題，以達(dá)到工期最小化［1］、成本最小化［2］、資源平衡［3］、時(shí)間—成本均衡［4］以及現(xiàn)金流均衡［5］等目標(biāo)。多模式資源受限項(xiàng)目調(diào)度問(wèn)題是著名的NP問(wèn)題，具有復(fù)雜性和動(dòng)態(tài)性的特征。因此，本文打破了傳統(tǒng)的項(xiàng)目調(diào)度執(zhí)行模式（即每個(gè)活動(dòng)一旦開(kāi)始就不能中途停止，要一直執(zhí)行到活動(dòng)結(jié)束），提出采用非搶占式的操作模式，任務(wù)優(yōu)先級(jí)較高的任務(wù)可以搶占優(yōu)先級(jí)較低任務(wù)的資源，并允許任務(wù)在任何時(shí)候被搶占資源且重新開(kāi)始，沒(méi)有任何額外成本。力求在任務(wù)可拆分的模式下，提高多模式多項(xiàng)目調(diào)度的資源利用率，改善工期并降低項(xiàng)目成本。

彭武良［6］在考慮資源約束、活動(dòng)多模式和活動(dòng)模式工期不確定的情況下，建立了多模式關(guān)鍵鏈項(xiàng)目調(diào)度模型并對(duì)模型進(jìn)行求解；Parviz［7］研究了多模式的項(xiàng)目調(diào)度問(wèn)題并建立了多模式資源受限的離散時(shí)間—成本—資源優(yōu)化模型；吳兵［8］分析了柔性資源受限的多模式項(xiàng)目調(diào)度問(wèn)題并建立了混合整數(shù)規(guī)劃模型；Stefan［9］提出采用項(xiàng)目調(diào)度的方法分析車(chē)間工作流的多模式生產(chǎn)調(diào)度問(wèn)題；Jarboui［10］采用粒子群優(yōu)化算法求解多模式資源受限項(xiàng)目調(diào)度問(wèn)題；Vincent［11］分析了項(xiàng)目調(diào)度執(zhí)行過(guò)程中存在多種執(zhí)行模式對(duì)項(xiàng)目整體的影響。對(duì)于多模式項(xiàng)目調(diào)度問(wèn)題，每種模式代表一組資源需求量和相應(yīng)的工期，不同的資源組合對(duì)應(yīng)不同的任務(wù)工期，從而在現(xiàn)有條件下獲得更高效的調(diào)度方案。

Tyson［12］研究了任務(wù)可拆分的項(xiàng)目調(diào)度問(wèn)題，認(rèn)為任務(wù)分解有利于充分利用資源并優(yōu)化調(diào)度方案；Buddhakulsomsiri［13］研究了任務(wù)可拆分調(diào)度模式對(duì)項(xiàng)目工期的影響，發(fā)現(xiàn)在資源受限條件下，任務(wù)拆分對(duì)縮短項(xiàng)目工期有良好的效果；Debels［14］提出雙種群遺傳算法（Double－Population Genetic Algorithm，DPGA）以解決搶占式執(zhí)行模式的資源受限項(xiàng)目調(diào)度問(wèn)題；Buddhakulsomsiri［15］研究發(fā)現(xiàn)，在存在資源閑置和臨時(shí)資源不可用的情況下，非搶占式調(diào)度模式能有效縮短項(xiàng)目工期。可見(jiàn)，非搶占式操作模式能有效縮短項(xiàng)目工期，提高資源利用率。

基于上述分析，為了提高資源利用率并使多項(xiàng)目調(diào)度的整體效用最大化，本文提出了任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題。構(gòu)建并剖析了以工期—成本—質(zhì)量—資源均衡為優(yōu)化目標(biāo)的任務(wù)可拆分的多模式多項(xiàng)目調(diào)度模型，利用正態(tài)云模型中云滴的隨機(jī)性與穩(wěn)定性的特征，改進(jìn)遺傳算法中交叉算子與變異算子的設(shè)置方式。最后，通過(guò)算例驗(yàn)證了模型和算法的有效性。

1 基于多屬性效用函數(shù)的多項(xiàng)目調(diào)度模型

在工程領(lǐng)域，多項(xiàng)目調(diào)度的目標(biāo)集中在工期、成本、質(zhì)量和資源均衡等方面。但工期、成本、質(zhì)量和資源均衡四個(gè)屬性不具備同類(lèi)可比性，針對(duì)該問(wèn)題，采用多屬性效用函數(shù)法建立此研究的問(wèn)題模型。

1．1 效用函數(shù)相關(guān)定義

多屬性效用函數(shù)利用試驗(yàn)心理學(xué)原理，將具有不同量綱的目標(biāo)函數(shù)轉(zhuǎn)化為單一的目標(biāo)函數(shù)。把多項(xiàng)目調(diào)度的策略映射為不同的效用值，從而找到使多項(xiàng)目整體效用最大化的任務(wù)調(diào)度方案。為了更準(zhǔn)確地描述本文研究的問(wèn)題，需明確如下定義。

定義1 屬性。屬性是影響調(diào)度決策的一個(gè)或一組變量。分為成本型屬性（即數(shù)值越低越好）和效益型屬性（即數(shù)值越高越好），

在工期、成本、質(zhì)量和資源均衡四個(gè)屬性中，工期和成本屬性是成本型屬性；質(zhì)量和資源均衡是效益型屬性。對(duì)上述屬性進(jìn)行規(guī)范化處理，可以得到矩陣R＝（rij）m×4。

定義2 效用。在多項(xiàng)目調(diào)度中，效用通常表示為客戶(hù)對(duì)項(xiàng)目承包商整體服務(wù)質(zhì)量的滿(mǎn)意程度。

定義3 效用函數(shù)。效用的量化表示形式，本文的效用函數(shù)為調(diào)度的效用函數(shù)，記為U（rij），rij為第i個(gè)項(xiàng)目的第j個(gè)要素的屬性。

1．2 問(wèn)題描述

活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題包含N個(gè)項(xiàng)目，各個(gè)項(xiàng)目之間并行執(zhí)行，不存在緊前緊后關(guān)系。第i個(gè)項(xiàng)目中有Ji個(gè)活動(dòng)，活動(dòng)s0為虛擬開(kāi)始活動(dòng)，活動(dòng)e0為虛擬結(jié)束活動(dòng)，虛擬活動(dòng)表示多項(xiàng)目的啟動(dòng)和結(jié)束，都不占用時(shí)間和資源?？偣灿衚種可更新資源和p種不可更新資源。

各個(gè)符號(hào)的含義如下：

Eij表示計(jì)劃結(jié)束時(shí)間；

Sij表示計(jì)劃開(kāi)始時(shí)間；

Aij表示第i個(gè)項(xiàng)目中的第j個(gè)活動(dòng)；tij表示計(jì)劃工期；

Pij表示活動(dòng)Aij的緊前活動(dòng)集合；

Uij表示Aij的緊后活動(dòng)集合；

rijk表示活動(dòng)Aij對(duì)第k種資源的需求量；

Rρk（k＝1，2，…，p）表示第k種可更新資源的可用量；

Rνp（p＝1，2，…，p）表示第p種不可更新資源總量；

riρjk表示項(xiàng)目i的活動(dòng)j單位工期可更新資源的需求量；

rνijp表示項(xiàng)目i的活動(dòng)j所需的不可更新資源總量；

qij表示項(xiàng)目i的活動(dòng)j執(zhí)行時(shí)的質(zhì)量指數(shù)；

對(duì)工期、成本、質(zhì)量和資源均衡四個(gè)屬性進(jìn)行目標(biāo)優(yōu)化。記工期為T(mén)，成本為C，質(zhì)量為Q，資源均衡為L(zhǎng)。根據(jù)多屬性效用函數(shù)的分解定理，活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化問(wèn)題可用加式分解方程表示：

式中：u（T），u（C），u（Q）和u（L）分別表示工期、成本、質(zhì)量和資源均衡的單變量效用函數(shù)；ωT，ωC，ωQ和ωL分別表示各單變量效用函數(shù)的權(quán)重系數(shù)。效用函數(shù)的優(yōu)化目標(biāo)是求解最大值，解空間是凸集，則效用函數(shù)均為凹函數(shù)，故采用效用函數(shù)的二次函數(shù)形式。項(xiàng)目總工期D的工期效用值為1，則

多項(xiàng)目調(diào)度中的成本由可更新資源和不可更新資源的成本構(gòu)成。其效用函數(shù)值為1。則

多項(xiàng)目調(diào)度中的質(zhì)量效用值為1時(shí)，則有

多項(xiàng)目調(diào)度中的資源均衡效用值為1時(shí)，則有

1．3 活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度優(yōu)化目標(biāo)

活動(dòng)可拆分的多項(xiàng)目調(diào)度計(jì)劃編制和控制極為復(fù)雜，工期是客戶(hù)和承包商關(guān)注的焦點(diǎn)。因此，活動(dòng)可拆分的多項(xiàng)目調(diào)度的優(yōu)化目標(biāo)之一是總的工期最短，即

在活動(dòng)可拆分的多項(xiàng)目調(diào)度的執(zhí)行過(guò)程中，多項(xiàng)目調(diào)度的總成本由可更新資源成本和不可更新資源成本構(gòu)成。令cp表示不可更新資源p的單位工期的單價(jià)，ck表示可更新資源k的單位工期的單價(jià)，則活動(dòng)可拆分的多項(xiàng)目調(diào)度的成本目標(biāo)函數(shù)為：

為了對(duì)活動(dòng)可拆分的多項(xiàng)目調(diào)度進(jìn)行更系統(tǒng)深入的研究，需要對(duì)項(xiàng)目的質(zhì)量屬性進(jìn)行量化，在此，每個(gè)活動(dòng)中引入中間變量，用來(lái)表示已獲得質(zhì)量?jī)r(jià)值EQVij，

式中：EVij表示項(xiàng)目i中活動(dòng)j的掙值，qij表示項(xiàng)目i的活動(dòng)j執(zhí)行時(shí)的質(zhì)量指數(shù)，用于衡量一個(gè)活動(dòng)的實(shí)際質(zhì)量水平，其計(jì)算方法如下：

因此，多項(xiàng)目調(diào)度計(jì)劃的總質(zhì)量水平可用所有活動(dòng)質(zhì)量水平的加權(quán)平均值表示，即

在對(duì)活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題的研究中，分析了資源均衡的量化問(wèn)題。目前的研究對(duì)資源均衡的研究集中在資源需求量不均衡系數(shù)、資源需求量極差和資源需求量方差三方面。三種方法均為目標(biāo)值越小其資源均衡效果越好。本文采用需求量方差為活動(dòng)可拆分的多項(xiàng)目調(diào)度資源均衡的目標(biāo)。令rijk（T）為在［t－1，t］時(shí)間段對(duì)第k種資源的需求量為多項(xiàng)目工期T內(nèi)對(duì)第k種資源的平均需求量。資源均衡的計(jì)算公式如下：

1．4 建立優(yōu)化模型

在考慮管理者和承包商最關(guān)注的工期、成本、質(zhì)量和項(xiàng)目整體的資源均衡四個(gè)重要屬性的基礎(chǔ)上，利用多屬性效用函數(shù)對(duì)活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題進(jìn)行均衡優(yōu)化，并構(gòu)建其多屬性均衡優(yōu)化模型。已有研究都假設(shè)每個(gè)活動(dòng)一旦開(kāi)始就不能中途停止，要一直執(zhí)行到活動(dòng)結(jié)束。本文提出采用非搶占式的操作模式，即任務(wù)優(yōu)先級(jí)較高的任務(wù)可以搶占優(yōu)先級(jí)較低任務(wù)的資源，并允許任務(wù)在任何時(shí)候被搶占資源且重新開(kāi)始，沒(méi)有任何額外成本。采用非搶占式執(zhí)行模式制定的任務(wù)可拆分的多模式多項(xiàng)目調(diào)度計(jì)劃，能更高效地利用資源并縮短項(xiàng)目工期，使多項(xiàng)目調(diào)度整體效用最佳。活動(dòng)i在執(zhí)行模式mi下都分配一個(gè)開(kāi)始時(shí)間Eiv。其模型如下：

其中：式（12）是目標(biāo)函數(shù)，表示活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化問(wèn)題的效用最大；式（13）表示活動(dòng)j的最早開(kāi)始時(shí)間不能比其緊前活動(dòng)i的持續(xù)時(shí)間?。皇剑?4）表示緊后活動(dòng)的開(kāi)始時(shí)間至少比緊前活動(dòng)的開(kāi)始時(shí)間大一個(gè)單位時(shí)間；式（15）強(qiáng)制項(xiàng)目開(kāi)始時(shí)間為零，式（16）表示活動(dòng)的開(kāi)始時(shí)間為非負(fù)整數(shù)；式（17）和式（18）分別表示對(duì)不可更新資源和可更新資源的限制；式（19）表示活動(dòng)在確定執(zhí)行模式之后，對(duì)不可更新資源的需求量不能超過(guò)各階段給定的資源需求量Wiρjk；式（20）表示對(duì)可更新資源的需求量不能超過(guò)各階段給定的資源需求量Wνijρ；式（21）表示每個(gè)活動(dòng)j只有一種執(zhí)行模式；式（22）表示活動(dòng)j的總工期等于在m 執(zhí)行模式下活動(dòng)的持續(xù)時(shí)間；式（23）和式（24）分別表示活動(dòng)j的開(kāi)始時(shí)間和結(jié)束時(shí)間。

2 設(shè)計(jì)云遺傳算法

2．1 活動(dòng)表示法

常用的活動(dòng)列表表示法（Activity－List representation，AL）和隨機(jī)鍵表示法（Random Key representation，RK）。在AL方法中，活動(dòng)的位置決定各活動(dòng)之間的相對(duì)優(yōu)先級(jí)，而在RK方法中，活動(dòng)調(diào)度的序列是基于每個(gè)活動(dòng)的優(yōu)先級(jí)值。本文采用RK表示法，每個(gè)個(gè)體由一個(gè)向量λ代表優(yōu)先級(jí)值，μ代表模式列表。向量λ的每個(gè)優(yōu)先級(jí)值都基于其值對(duì)應(yīng)一個(gè)活動(dòng)，活動(dòng)的調(diào)度計(jì)劃按照序列進(jìn)行編制。向量λ的各個(gè)種群元素也對(duì)應(yīng)一組執(zhí)行模式列表μ。模式列表μ分配一種模式mi給每個(gè)活動(dòng)i（i∈｛1，…，N｝），并且決定相對(duì)于不可再生資源，調(diào)度方案是否可行。

ERR（μ）表示額外資源需求，ERR（μ）＝0表示解決方案可行；如果ERR（μ）＞0，則解決方案不可行。

允許活動(dòng)的非搶占式執(zhí)行模式，原活動(dòng)網(wǎng)絡(luò)需轉(zhuǎn)換成新的網(wǎng)絡(luò)。一個(gè)活動(dòng)i用模式列表μ分配一種執(zhí)行模式mi，其持續(xù)時(shí)間dimi已知。將每個(gè)活動(dòng)分解成di個(gè)子活動(dòng)并形成新的結(jié)構(gòu)網(wǎng)絡(luò)。向量λ決定新項(xiàng)目網(wǎng)絡(luò)所有子活動(dòng)的調(diào)度序列，并決定子活動(dòng)的開(kāi)始時(shí)間。

2．2 云遺傳算法

標(biāo)準(zhǔn)遺傳算法（Static Genetic Algorithm，SGA）采用固定概率進(jìn)行交叉、變異操作，存在收斂速度慢或陷入局部收斂現(xiàn)象等缺陷，影響了算法的求解效果。同時(shí)，本文中的算例比較復(fù)雜，對(duì)算法要求較高，標(biāo)準(zhǔn)遺傳算法顯然難以勝任，為此，在傳統(tǒng)遺傳算法的基礎(chǔ)上引入云模型理論，提出了云遺傳算法（Cloud Genetic Algorithm，CGA）。利用云模型云滴的隨機(jī)性和穩(wěn)定傾向性的特征，設(shè)計(jì)遺傳算法中的交叉和變異概率，在算法的初期設(shè)置較大的交叉和變異概率以快速產(chǎn)生優(yōu)秀個(gè)體，在算法后期設(shè)置較小的交叉和變異概率，適應(yīng)度高的優(yōu)秀個(gè)體以較小的概率參與交叉變異以保護(hù)優(yōu)秀個(gè)體不被破壞，從而加速算法的全局收斂。通過(guò)云發(fā)生器產(chǎn)生交叉和變異概率，利用正態(tài)云模型的控制參數(shù)，在種群適應(yīng)度發(fā)生變化時(shí)進(jìn)行自適應(yīng)調(diào)整，提高了算法在搜索精度和搜索范圍上的準(zhǔn)確性。云遺傳算法設(shè)計(jì)了交叉概率Pc和變異概率Pm，能根據(jù)適應(yīng)度進(jìn)行動(dòng)態(tài)調(diào)整。交叉概率Pc和變異概率Pm隨自身適應(yīng)度呈現(xiàn)線性變化。適應(yīng)度越高的個(gè)體其交叉變異概率越小；反之，適應(yīng)度越低的個(gè)體其交叉變異概率越大。

交叉概率Pc和變異概率Pm的自適應(yīng)生成公式如下：

（1）Pc的生成算法（2）Pm 的生成算法

其中：k1，…，k4為［0，1］的常數(shù)，取k1＝k3＝1，k2＝k4＝0．5。由此可知，Pc和Pm的初始值較大，但隨著種群的不斷進(jìn)化而逐漸減小。

熵En、期望Ex和超熵He是云模型的重要控制參數(shù)，熵En反映了云模型的陡峭程度；期望Ex反映了云模型的水平位置；超熵He反映了它與云滴的離散程度，云滴均在期望值上下波動(dòng)，其波動(dòng)程度受He控制。超熵He過(guò)大時(shí)云模型的穩(wěn)定性下降，當(dāng)超熵He過(guò)小時(shí)云模型的隨機(jī)性有所下降。在確保最大適應(yīng)度周?chē)膬?yōu)秀個(gè)體維持正態(tài)云模型穩(wěn)定傾向性的同時(shí)，提高適應(yīng)度較低的個(gè)體的搜索能力，從而生成更大解空間內(nèi)的新個(gè)體，有效改善了算法的隨機(jī)性。CGA的具體步驟如下：

（1）編碼設(shè)計(jì)本文選用多組編碼的染色體結(jié)構(gòu)，染色體的基因?qū)?yīng)活動(dòng)的編號(hào)，基因值對(duì)應(yīng)一個(gè)優(yōu)先權(quán)列表。自然編碼表示任務(wù)優(yōu)先權(quán)，優(yōu)先權(quán)為1～m之間的自然數(shù)，優(yōu)先權(quán)的數(shù)值越大，優(yōu)先權(quán)越大。為保證染色體的有效性，活動(dòng)的優(yōu)先權(quán)必須與基因建立一一對(duì)應(yīng)的關(guān)系，以滿(mǎn)足解空間分布的均勻性和搜索的全局性要求。染色體結(jié)構(gòu)如圖1所示。

（2）初始種群隨機(jī)產(chǎn)生優(yōu)先權(quán)的全排列Wu（T），染色體所確定的各個(gè)任務(wù)的優(yōu)先權(quán)是生成調(diào)度計(jì)劃的重要依據(jù)。

（3）適應(yīng)度函數(shù)適應(yīng)度函數(shù)是評(píng)價(jià)染色體優(yōu)劣的依據(jù)，為此，設(shè)計(jì)的適應(yīng)度函數(shù)為fit（T），fit（T）＝1/u（T）。其中u（T）表示個(gè)體的目標(biāo)值。適應(yīng)度函數(shù)值越小，個(gè)體越優(yōu)。

（4）交叉算子由云模型X發(fā)生器生成種群的交叉概率Pc，計(jì)算交叉算子的確定度u，Ex，En和He，由X云發(fā)生器生成一對(duì)個(gè)體，采用雙交叉點(diǎn)操作，選擇一個(gè)基因交叉點(diǎn)，將選中的基因編碼置于子代染色體首位，在刪除父代染色體相同基因編碼的基礎(chǔ)上，按原編碼順序復(fù)制到子代上，如果生成違反約束條件的子代染色體，則對(duì)插入點(diǎn)的位置進(jìn)行調(diào)整。交叉操作如圖2所示。

（5）變異算子由云模型X發(fā)生器生成種群的變異概率Pm，Ex取原個(gè)體，計(jì)算En和He，利用云發(fā)生器生成一個(gè)新個(gè)體，當(dāng)在（0，1）產(chǎn)生的隨機(jī)數(shù)temp＞u時(shí)，隨機(jī)選擇染色體中的兩個(gè)基因并對(duì)換兩者的基因碼，生成新的染色體，變異操作如圖3所示。

（6）重復(fù)步驟（2）～步驟（5），當(dāng)Maxgen＝50或滿(mǎn)足條件時(shí)停止操作，輸出結(jié)果。

3 仿真試驗(yàn)

3．1 算例分析

以3個(gè)并行項(xiàng)目組成的多項(xiàng)目調(diào)度問(wèn)題為例，建立活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度優(yōu)化模型，并利用云遺傳算法進(jìn)行試驗(yàn)仿真。多項(xiàng)目調(diào)度中各個(gè)活動(dòng)的相關(guān)信息如表1所示，共包含28個(gè)活動(dòng)及虛擬開(kāi)始活動(dòng)和虛擬結(jié)束活動(dòng)，多項(xiàng)目調(diào)度中共包含7種資源，其中有4種可更新資源和3種不可更新資源。多項(xiàng)目的各個(gè)活動(dòng)之間的緊前緊后關(guān)系如圖1所示。單位工期的間接成本c＝4，六種資源單價(jià)分別為c1p＝c2p＝c3p＝c4p＝3，ck1＝ck2＝2。

工期T，成本C，質(zhì)量Q和資源均衡L的效用函數(shù)為u（T），u（C），u（Q）和u（L），根據(jù)變量上下限可以求得各參數(shù)的具體數(shù)值：。對(duì)于各個(gè)參數(shù)的權(quán)重設(shè)置，目前采用較多的方法是專(zhuān)家打分法或根據(jù)其在企業(yè)實(shí)際執(zhí)行中的需要進(jìn)行設(shè)置。各個(gè)參數(shù)的權(quán)重系數(shù)分別為αT＝0．4，αC＝0．2，αQ＝0．1，αL＝0．3。因此，活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的多屬性效用函數(shù)為：

表1所示為活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的相關(guān)信息，包含28個(gè)活動(dòng)，每個(gè)活動(dòng)有兩種執(zhí)行模式，活動(dòng)的執(zhí)行模式、所用資源的種類(lèi)和質(zhì)量指數(shù)如表2所示。用云遺傳算法求解該問(wèn)題，得出可更新資源的用量是29，不可更新資源的用量是20。子項(xiàng)目1的工期是8d，子項(xiàng)目2的工期是12d，子項(xiàng)目3的工期是10d。活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示，調(diào)度方案如圖5所示。

由Mpple12．0實(shí)現(xiàn)云遺傳算法編程，對(duì)建立的模型進(jìn)行求解。設(shè)種群規(guī)模Popsize＝50，為滿(mǎn)足種群多樣性的要求，進(jìn)化代數(shù)Maxgen＝50，最終求得最優(yōu)解的效用值為u（T，C，Q，L）＝0．892，多項(xiàng)目調(diào)度的整體工期為12d，C＝4 719，Q＝0．973 6，L＝0．910 4，最優(yōu)解信息如表2所示。

由圖4可知，在活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題中，利用多屬性效用函數(shù)建立活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化模型，根據(jù)工期、成本、質(zhì)量和資源均衡四個(gè)屬性建立均衡優(yōu)化目標(biāo)，優(yōu)化的結(jié)果能幫助管理者和經(jīng)營(yíng)者有效控制和監(jiān)管多項(xiàng)目的進(jìn)度。根據(jù)算例的結(jié)果，管理者和經(jīng)營(yíng)者能在有效縮短工期并高效利用資源的前提下，使多項(xiàng)目調(diào)度的整體效用最大化。管理者和經(jīng)營(yíng)者根據(jù)項(xiàng)目各個(gè)階段關(guān)注點(diǎn)的不同，作出使多項(xiàng)目調(diào)度整體效用最大的多屬性均衡優(yōu)化決策。

表1 項(xiàng)目模式列表及資源使用信息

表2 最優(yōu)解信息

3．2 算法對(duì)比分析

為檢驗(yàn)云遺傳算法的性能，本文分別采用標(biāo)準(zhǔn)遺傳算法、禁忌搜索算法和云自適應(yīng)遺傳算法對(duì)上述算例進(jìn)行算例分析，采用各算法的計(jì)算結(jié)果收斂情況如圖6所示。

由圖6可見(jiàn)，雖然禁忌搜索算法的收斂速度最快，但是容易產(chǎn)生局部最優(yōu)解，而云遺傳算法的收斂速度比禁忌搜索算法略慢，但其收斂下降速度最快，因此，其全局收斂能力在三者中最強(qiáng)。為了進(jìn)一步檢驗(yàn)算法的有效性，將上述算例計(jì)算20次，對(duì)其最優(yōu)值、最劣值和平均值三個(gè)指標(biāo)進(jìn)行統(tǒng)計(jì)，計(jì)算結(jié)果如表3所示。

分析表3的數(shù)據(jù)發(fā)現(xiàn)，云遺傳算法的搜索成功率最大，禁忌搜索算法的搜索成功率最小。最劣值和平均值都是云遺傳算法的結(jié)果最小，從而反映出云遺傳算法的全局搜索能力最強(qiáng)。

3．3 標(biāo)準(zhǔn)化測(cè)試分析

下面從項(xiàng)目調(diào)度問(wèn)題網(wǎng)站http：//129．187．106．231/psplib/上下載關(guān)于有項(xiàng)目調(diào)度問(wèn)題的標(biāo)準(zhǔn)算例，因?yàn)楸疚囊孕в米畲蠡癁槟繕?biāo)函數(shù)研究多項(xiàng)目調(diào)度，它在題庫(kù)中沒(méi)有標(biāo)準(zhǔn)算例，所以以項(xiàng)目工期最短建立標(biāo)準(zhǔn)化測(cè)試的目標(biāo)函數(shù)。分別采用標(biāo)準(zhǔn)遺傳算法、禁忌搜索算法和云遺傳算法進(jìn)行求解，并對(duì)每個(gè)算例隨機(jī)運(yùn)行20次，統(tǒng)計(jì)平均誤差和最優(yōu)解所占的比例。如表4所示，分析算法的求解效率和穩(wěn)定性。

對(duì)于任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題，三種算法均能計(jì)算出比較好的解，但是任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題中的活動(dòng)數(shù)量較多，基于云遺傳算法中動(dòng)態(tài)改變的交叉變異率，使得算法的初期能夠較快地產(chǎn)生優(yōu)秀個(gè)體，算法的后期保護(hù)最優(yōu)個(gè)體，全局搜索能力強(qiáng)。由此可知，云遺傳算法能在保證收斂的同時(shí)提高全局搜索能力。

試驗(yàn)表明：本文設(shè)計(jì)的云遺傳算法在全局搜索和快速收斂方面優(yōu)于其他智能算法，能夠保證任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題對(duì)求解算法的要求。

表3 仿真結(jié)果對(duì)比分析

表4 測(cè)試數(shù)據(jù)統(tǒng)計(jì)結(jié)果

4 結(jié)束語(yǔ)

本文研究了活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度的多屬性均衡優(yōu)化問(wèn)題，以活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度整體效用最大化為目標(biāo)，采用多屬性效用函數(shù)建立以工期—成本—質(zhì)量—資源均衡為優(yōu)化目標(biāo)的活動(dòng)可拆分的多模式多項(xiàng)目調(diào)度模型并進(jìn)行優(yōu)化。

本文設(shè)計(jì)了云遺傳算法求解任務(wù)可拆分的多模式多項(xiàng)目調(diào)度問(wèn)題，利用云模型云滴的隨機(jī)性和穩(wěn)定傾向性特征，設(shè)計(jì)遺傳算法中的交叉和變異概率，在算法的初期設(shè)置較大的交叉和變異概率以快速產(chǎn)生優(yōu)秀個(gè)體，在算法的后期設(shè)置較小的交叉和變異概率以防止優(yōu)秀基因被破壞，并設(shè)置最大保留機(jī)制的交叉算子以避免優(yōu)秀基因被破壞。通過(guò)算例驗(yàn)證了模型和算法的實(shí)用性和有效性。結(jié)合算例對(duì)設(shè)計(jì)的算法進(jìn)行了實(shí)驗(yàn)計(jì)算，結(jié)果表明，云遺傳算法在求解效率、收斂速度和穩(wěn)定性方面優(yōu)于其他智能算法。

模型的主要缺陷是同時(shí)考慮多個(gè)屬性的效用函數(shù)，但各個(gè)目標(biāo)權(quán)重的確定會(huì)受到主觀因素的影響，在后續(xù)的研究中筆者將進(jìn)行進(jìn)一步的研究。

［1］ DEMEULEMEESTER E，HERROELEN W．A branch－and

bound procedure for the multiple resource－constrained project scheduling problem［J］．Management Science，1992，38（12）：

1803－1818．

［2］ REN Shike，HE Zhengwen，XU Yu．Study on bank credit limit based max－NPV project scheduling problems［J］．Journal of Industrial Engineering and Engineering Management，2009，23（2）：85－90（in Chinese）．［任世科，何正文，徐 渝．基于銀行授信額度的Max－NPV項(xiàng)目調(diào)度問(wèn)題研究［J］．管理工程學(xué)報(bào)，2009，23（2）：85－90．］

［3］ VANHOUCKE M，DEBELS D．The impact of various activity assumptions on the lead time and resource utilization of resource－constrained projects［J］．Computers and Industrial Engineering，2008，54（1）：140－154．

［4］ ZHANG Jingwen，XU Yu，HE Zhengwen，et al．A review on the time/cost trade－offs problem in project scheduling［J］．Journal of Industrial Engineering and Engineering Management，2007，21（1）：92－97（in Chinese）．［張靜文，徐 渝，何正文，等．項(xiàng)目調(diào)度中的時(shí)間－費(fèi)用權(quán)衡問(wèn)題研究綜述［J］．管理工程學(xué)報(bào)，2007，21（1）：92－97．］

［5］ HE Zhengwen，LIU Renjing，XU Yu．Multi－mode project scheduling problems with cash flow balanced objectives［J］．Journal of Industrial Engineering and Engineering Management，2011，25（2）：124－130（in Chinese）．［何正文，劉人境，徐

渝．基于現(xiàn)金流均衡目標(biāo)的多模式項(xiàng)目調(diào)度問(wèn)題研究［J］．管理工程學(xué)報(bào)，2011，25（2）：124－130．］

［6］ PENG Wuliang，JIN Minli，JI Guotao．A critical chain project scheduling problem with multi－mode and its heuristic ［J］．Computer Integrated Manufacturing Systmems，2012，18（1）：93－101（in Chinese）．［彭武良，金敏力，紀(jì)國(guó)燾．多模式關(guān)鍵鏈項(xiàng)目調(diào)度問(wèn)題及其啟發(fā)式求解［J］．計(jì)算機(jī)集成制造系統(tǒng)，2012，18（1）：93－101．］

［7］ PARVIZ G，EHSAN E．Multi－mode resource－constrained dis

crete time－cost－resource optimization in project scheduling u－sing non－dominated sorting genetic algorithm［J］．Automation in Construction，2013，30（3）：216－227．

［8］ WU Bing，LIU Jiyin，LUO Ronggui．Modeling of the flexible resource–constrained multi－mode project scheduling problem［J］．Journal of Wuhan University of Technology，2008，30（11）：176－179（in Chinese）．［吳 兵，劉繼印，羅榮桂．柔性資源受限的多模式項(xiàng)目調(diào)度問(wèn)題的建模［J］．武漢理工大學(xué)學(xué)報(bào)，2008，30（11）：176－179．］

［9］ STEFAN V，ANDREAS W．Hybrid flow shop scheduling as a multi－mode multi－project scheduling problem with batching requirements：a real－world application［J］．International Journal of Production Economics，2007，105（2）：445－458．

［10］ JARBOUI B，DAMAK N，SIARRY P，et al．A combinatorial particle swarm optimization for solving multi－mode resource－constrained project scheduling problems［J］．Applied Mathematics and Computation，2008，195（1）：299－308．

［11］ VINCENT V P，MARIO V．A genetic algorithm for the pre

emptive and non－preemptive multi－mode resource－constrained project scheduling problem［J］．European Journal of Opera－tional Research，2010，201（2）：409－418．

［12］ TYSON R B，ALI A Y．Resource－constrained multi－project scheduling：priority rule performance revisited［J］．International Journal of Production Economics，2010，126（2）：212－228．

［13］ BUDDHAKULSOMSIRI J，DAVID S K．Priority rule－based heuristic for multi－mode resource－constrained project scheduling problems with resources vacations and activity splitting［J］．European Journal of Operational Research，2007，178（2）：374－390．

［14］ DEBELS D，VANHOUCKE M．A bi－population based genetic algorithm for the resource－constrained project scheduling problem［J］．Lecture Notes in Computer Science，2005，3483：378－387．

［15］ BUDDHAKULSOMSIRI J，KIM D．Properties of multi－mode resource－constrained project scheduling problems with resource vacations and activity splitting［J］．European Journal of Operational Research，2006，175（1）：279－295．