多技能項(xiàng)目調(diào)度問題研究綜述

胡振濤, 崔南方, 胡雪君, 張 艷

(1. 華中科技大學(xué)管理學(xué)院,湖北武漢 430074;2. 湖南大學(xué)工商管理學(xué)院,湖南長沙 410082;3. 東莞理工學(xué)院經(jīng)濟(jì)與管理學(xué)院,廣東東莞 523808)

1 引 言

多技能項(xiàng)目調(diào)度問題(multi-skilled project scheduling problem,MSPSP)中的資源可同時(shí)具備多種技能,以芯片研發(fā)項(xiàng)目中的研發(fā)人員為例,掌握模擬IC 設(shè)計(jì)技能的員工,也往往會(huì)了解一些模擬版圖實(shí)現(xiàn)的技能,這種多技能資源的存在對(duì)項(xiàng)目的計(jì)劃制定者而言,既是機(jī)遇也是挑戰(zhàn).

多技能使資源的分配更加靈活,這不僅能豐富項(xiàng)目計(jì)劃的多樣性,還能在項(xiàng)目面臨不確定風(fēng)險(xiǎn)時(shí),為管理者提供更為靈活多變的應(yīng)對(duì)措施.如Hegazy 等[1]研究了單技能項(xiàng)目和多技能項(xiàng)目的調(diào)度問題,結(jié)果表明項(xiàng)目管理者在調(diào)度時(shí)考慮多技能策略能有效地減少工期降低成本. Arashpour 等[2]則指出,多技能員工有助于降低項(xiàng)目周期、提高項(xiàng)目產(chǎn)出、提升資源均衡水平,并鼓勵(lì)企業(yè)對(duì)員工進(jìn)行適當(dāng)?shù)目缂寄芘嘤?xùn).此外,陳蓉等[3]在研究人員隨機(jī)離職的多技能項(xiàng)目調(diào)度問題時(shí)提出,當(dāng)項(xiàng)目實(shí)施過程中出現(xiàn)人員離職時(shí),可根據(jù)技能特征選擇與離職員工相近的員工補(bǔ)缺,以降低這類不確定事件的影響.

然而, 多技能資源的出現(xiàn)也為項(xiàng)目調(diào)度帶來了更大的挑戰(zhàn).在單技能項(xiàng)目調(diào)度中, 由于活動(dòng)所需資源的類型明確,資源技能單一,項(xiàng)目的調(diào)度計(jì)劃一旦確定,資源分配方案便隨之確定,并不涉及復(fù)雜的資源指派問題.而在MSPSP 中,資源的多技能屬性使得不同種類的資源之間存在相互替代的可能性,活動(dòng)所需要的技能可由不同的資源執(zhí)行. 因此, 即便已經(jīng)生成了項(xiàng)目的調(diào)度計(jì)劃, 依舊需要解決資源的指派問題. 所以MSPSP 是調(diào)度問題與指派問題的組合,求解更加復(fù)雜,屬于NP-hard 問題[4].

近年來,越來越多的學(xué)者開始研究MSPSP,而目前尚缺乏對(duì)這些成果的系統(tǒng)梳理. 本文以“柔性+項(xiàng)目調(diào)度”、“多技能+項(xiàng)目調(diào)度”和“flexible+project scheduling”,“multi-skill+project scheduling”為關(guān)鍵詞,分別在知網(wǎng)、萬方、維普等中文數(shù)據(jù)庫,Elsevier ScienceDirect,Web of Science,SpringerLink,EBSCO 等英文數(shù)據(jù)庫檢索了相關(guān)文獻(xiàn),以2000 年～2020 年為限,經(jīng)過相關(guān)性及創(chuàng)新性篩選后,按文獻(xiàn)公開年份統(tǒng)計(jì)結(jié)果見圖1.可以看出,學(xué)術(shù)界對(duì)MSPSP 的關(guān)注度在逐漸提升. 因此,有必要對(duì)MSPSP 的國內(nèi)外相關(guān)研究成果進(jìn)行歸納整理,為本領(lǐng)域的后續(xù)研究提供支持.

圖1 2000 年～2020 年MSPSP 相關(guān)文獻(xiàn)數(shù)量Fig.1 Quantity of literatures on MSPSP in 2000～2020

2 基于MSPSP 建模的研究綜述

2.1 問題描述與基礎(chǔ)數(shù)學(xué)模型

基礎(chǔ)MSPSP 主要包含如下要素: 活動(dòng)參數(shù)、資源參數(shù)、技能參數(shù)及其它相關(guān)參數(shù). 其中項(xiàng)目網(wǎng)絡(luò)采用節(jié)點(diǎn)式表示, 共包含n個(gè)活動(dòng)節(jié)點(diǎn), 起始節(jié)點(diǎn)1 和終止節(jié)點(diǎn)n代表虛活動(dòng); 活動(dòng)之間存在工序約束;以G={V,E}表示項(xiàng)目網(wǎng)絡(luò),其中V={1,2,...,n}表示活動(dòng)集合,E為有向弧,表示活動(dòng)的工序約束;活動(dòng)i的工期為di,對(duì)技能l的需求表為TFil;資源具備多技能,每個(gè)資源都至少具備一種項(xiàng)目所需求的技能,R={1,2,...,K}表示資源集合,資源總量為K;F={1,2,...,L}表示技能集合,技能種類為L. 相關(guān)符號(hào)匯總于表1.

表1 MSPSP 相關(guān)參數(shù)匯總Table 1 Summary of the parameters in MSPSP

續(xù)表1Table 1 Continues

MSPSP 需要解決的是, 在一定的環(huán)境下, 如何對(duì)活動(dòng)排程并為之分配資源, 以滿足預(yù)設(shè)的目標(biāo).所以,MSPSP 的主要決策內(nèi)容為:活動(dòng)的開始時(shí)間、活動(dòng)所使用的資源以及資源在對(duì)應(yīng)活動(dòng)中所執(zhí)行的技能.根據(jù)現(xiàn)有文獻(xiàn),模型中決策變量的構(gòu)建可分為兩類. 第一類為含有時(shí)間索引的決策變量,其最常用變量形式為

由式(1)或式(2)可以確定項(xiàng)目活動(dòng)的排程,由式(3)可以推導(dǎo)出相應(yīng)的資源分配方案.據(jù)此,含有時(shí)間索引的MSPSP 數(shù)學(xué)模型(I)如下

其中式(4)表示目標(biāo)函數(shù); 式(5)表示各活動(dòng)的執(zhí)行時(shí)間必須得到滿足; 式(6)表示活動(dòng)工序約束不可違背;式(7)表示資源只可執(zhí)行其所掌握的技能;式(8)表示資源在某一時(shí)刻最多只能執(zhí)行一種技能,且最多只能分配給一個(gè)活動(dòng);式(9)表示各活動(dòng)的技能需求必須得到滿足,且不會(huì)被分配到過多的資源;式(10)表示活動(dòng)在執(zhí)行過程中不可被中斷;式(11)表示決策變量的可行域.

第二類決策變量在構(gòu)建時(shí)不以時(shí)間為索引,而是引入了活動(dòng)的時(shí)序關(guān)系,最常見的變量形式為

Si表示活動(dòng)i的開始時(shí)間,

由決策變量(12)可以確定項(xiàng)目活動(dòng)的排程,由決策變量(14)可以得出項(xiàng)目的資源分配方案.由此可歸納出含有時(shí)序關(guān)系的MSPSP 數(shù)學(xué)模型(II)如下

其中式(15)表示目標(biāo)函數(shù); 式(16)表示活動(dòng)的工序約束不可違背; 式(17)表示資源只可執(zhí)行其所掌握的技能;式(18)表示各活動(dòng)的技能需求必須得到滿足,且不會(huì)被分配到過多的資源;式(19)表示資源在一個(gè)活動(dòng)中最多只能執(zhí)行一種技能;式(20)表示兩個(gè)活動(dòng)不可互為前序;式(21)表示并行的活動(dòng)不可使用同一資源;式(22)表示決策變量的可行域.

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

項(xiàng)目工期是MSPSP研究中最常見的目標(biāo),一般是指在確定性環(huán)境下所生成的調(diào)度計(jì)劃的工期,其典型的數(shù)學(xué)表達(dá)為

項(xiàng)目成本是項(xiàng)目管理者關(guān)注的另一個(gè)重點(diǎn). 在MSPSP 研究中,考慮的成本主要有三類: 和多技能資源有關(guān)的成本CR[57,79],和工期有關(guān)的成本CT[65],以及固定成本CF[91]. MSPSP 中最小化項(xiàng)目成本可總結(jié)為

此外, 還有以資源均衡[42]、項(xiàng)目凈現(xiàn)值[84]、調(diào)度計(jì)劃魯棒性[53]等為單目標(biāo), 以“項(xiàng)目工期+項(xiàng)目成本”[8]、“項(xiàng)目工期+工作時(shí)間均衡”[92]等為多目標(biāo)的MSPSP 研究,整理相關(guān)文獻(xiàn)可知,MSPSP 的目標(biāo)可分為三類: 時(shí)間類目標(biāo)、成本類目標(biāo)和資源類目標(biāo).

時(shí)間類目標(biāo)的研究背景可分為確定性環(huán)境和不確定環(huán)境兩種. 確定性環(huán)境假設(shè)項(xiàng)目的內(nèi)容、項(xiàng)目的活動(dòng)時(shí)間、資源的狀態(tài)等都是確知且不變的,如何在工序約束、資源約束及時(shí)間約束之下,得到一個(gè)項(xiàng)目周期最短的調(diào)度計(jì)劃是這類問題研究的重點(diǎn). 而不確定環(huán)境,則假設(shè)項(xiàng)目中存在不確定因素,且這些因素會(huì)干擾調(diào)度計(jì)劃的實(shí)施,如何在計(jì)劃制定期便考慮這些不確定因素,以保護(hù)項(xiàng)目如期進(jìn)行是這類問題研究的核心,其最常見的目標(biāo)形式為最大化按時(shí)完工率、最小化項(xiàng)目期望工期等[94].

成本類目標(biāo)具有鮮明的項(xiàng)目特征,不同的項(xiàng)目其成本構(gòu)成會(huì)存在較大差異.如在研發(fā)項(xiàng)目中,研發(fā)人員的工資、獎(jiǎng)金、分紅以及培訓(xùn)費(fèi)用等資源使用成本是研究的重點(diǎn). 而在一些具有嚴(yán)格交付期的大型工程項(xiàng)目中,更受關(guān)注的則是和工期有關(guān)的懲罰性和獎(jiǎng)勵(lì)性成本等.

資源類目標(biāo)在多技能項(xiàng)目調(diào)度問題研究中,有顯著區(qū)別于一般項(xiàng)目的特點(diǎn). 在項(xiàng)目計(jì)劃階段,多技能資源的指派方案更多,這使得資源均衡問題變得更復(fù)雜,但同時(shí)也使其具備了更大的優(yōu)化空間. 在項(xiàng)目實(shí)施階段,當(dāng)發(fā)生計(jì)劃外的不確定事件時(shí),常常會(huì)進(jìn)行反應(yīng)性的資源重調(diào)度,而資源的多技能特征也使得這種反應(yīng)性調(diào)度更加靈活. MSPSP 的變量形式及目標(biāo)見表2.

表2 MSPSP 的變量形式及目標(biāo)Table 2 Models and objectives in MSPSP

2.3 約束條件

在現(xiàn)實(shí)中,不同的項(xiàng)目具有不同的內(nèi)部特征,也面臨著不同的外部環(huán)境. 項(xiàng)目間的這些差異在數(shù)學(xué)模型中表現(xiàn)為不同的約束條件,并由此產(chǎn)生了許多MSPSP 的變體.以下將從項(xiàng)目環(huán)境、活動(dòng)以及資源–技能三個(gè)角度,介紹多技能項(xiàng)目在現(xiàn)實(shí)中所面臨的不同狀況,以及在構(gòu)建模型時(shí)所對(duì)應(yīng)的約束條件.

1)項(xiàng)目環(huán)境類約束

在MSPSP 研究中, 因自然環(huán)境、社會(huì)環(huán)境及項(xiàng)目內(nèi)部環(huán)境變化而導(dǎo)致的模型中某些預(yù)設(shè)參數(shù)出現(xiàn)變化的情況,被稱為不確定環(huán)境的MSPSP.項(xiàng)目不確定性的來源主要有兩個(gè),活動(dòng)和資源. 其中最常見的是活動(dòng)時(shí)間不確定[53],也即模型中di不再是常數(shù),而是一個(gè)隨機(jī)量. 此外還有活動(dòng)需求的不確定[34],即模型中的TFil為隨機(jī)量;活動(dòng)存在不確定[52],即在項(xiàng)目網(wǎng)絡(luò)中活動(dòng)數(shù)量有增加或減少的可能;以及活動(dòng)實(shí)現(xiàn)不確定[55],即活動(dòng)完工后存在返工的可能.資源的不確定情況可分為兩類,第一類為資源狀態(tài)不確定[3],如員工離職、設(shè)備故障等導(dǎo)致某些資源處于不可用狀態(tài);第二類為資源效率不確定,如資源的技能水平存在波動(dòng)等.

此外,在實(shí)際中項(xiàng)目的執(zhí)行或多或少地會(huì)與其它項(xiàng)目產(chǎn)生聯(lián)系,因此部分學(xué)者考慮了多項(xiàng)目環(huán)境(multiproject)下的MSPSP.多項(xiàng)目調(diào)度的研究可分為普通多項(xiàng)目調(diào)度和項(xiàng)目組合(project portfolio)調(diào)度,普通多項(xiàng)目調(diào)度假設(shè)各項(xiàng)目有互相獨(dú)立的項(xiàng)目管理者,項(xiàng)目間利益獨(dú)立、信息獨(dú)立,唯一的聯(lián)系是共享有限的全局資源. 而項(xiàng)目組合調(diào)度則假設(shè)各子項(xiàng)目不僅共享資源還具有共同的戰(zhàn)略目標(biāo),并且子項(xiàng)目與子項(xiàng)目之間還可能存在工序約束.

現(xiàn)代項(xiàng)目面臨著愈發(fā)復(fù)雜的內(nèi)外環(huán)境,因此不確定環(huán)境下的魯棒項(xiàng)目調(diào)度研究也成為近些年來的研究熱點(diǎn)[95]. 然而多數(shù)研究還停留在一般單技能項(xiàng)目的層面,而很少有對(duì)多技能項(xiàng)目魯棒調(diào)度的研究.此外,很多現(xiàn)實(shí)的多技能項(xiàng)目,如研發(fā)項(xiàng)目等,都是以項(xiàng)目組合的形式實(shí)施進(jìn)度管理的,而學(xué)術(shù)界對(duì)于多技能項(xiàng)目組合調(diào)度問題的關(guān)注還不足.

2)活動(dòng)類約束

在最基本的MSPSP 中, 活動(dòng)工序服從結(jié)束–開始(finish-start, FS)的約束類型, 也即緊前活動(dòng)結(jié)束之后,后續(xù)活動(dòng)才可開工. 而在現(xiàn)實(shí)項(xiàng)目中,活動(dòng)工序之間的約束類型往往更加復(fù)雜,即廣義優(yōu)先關(guān)系(generalized precedence relations)[69],如SS(start-start),SF(start-finish)和FF(finish-finish)等.

多模式(multi-mode)指的是活動(dòng)的執(zhí)行可從多種模式中選擇[65],不再是消耗固定量的資源、花費(fèi)固定量的時(shí)間,一般情況下,可通過增加資源數(shù)量來減少活動(dòng)的工期,也可通過延長活動(dòng)工期來減少資源的投入.表現(xiàn)在模型中,活動(dòng)對(duì)技能的需求量TFil及活動(dòng)工期di都不再是定值,且TFil與di具有相關(guān)性

實(shí)際上,多模式項(xiàng)目調(diào)度問題更一般化的情況是離散時(shí)間/資源平衡問題(discrete time/resource trade-off problem,DTRTP),它假設(shè)各活動(dòng)有固定量的工作內(nèi)容(work content/workload),當(dāng)投入資源與花費(fèi)時(shí)間的乘積等于工作內(nèi)容時(shí)活動(dòng)才可完工[47].

活動(dòng)可中斷(preemptive)也被部分學(xué)者稱為任務(wù)可拆分[6],區(qū)別于傳統(tǒng)項(xiàng)目調(diào)度問題中活動(dòng)一旦開始必須持續(xù)到完工的要求,可中斷約束允許活動(dòng)在執(zhí)行過程中暫停,并在之后任意時(shí)刻開始. 在研究MSPSP 時(shí),若加入活動(dòng)可中斷約束,會(huì)引出很多與中斷–再開始這一過程有關(guān)的問題,如活動(dòng)中斷–再開始的過程是否消耗額外的資源與時(shí)間[15],活動(dòng)重新開始時(shí)會(huì)否產(chǎn)生額外成本[37],活動(dòng)中斷再重新開始時(shí)是否可更改原本的資源分配方案[6]等. 此外,還有關(guān)于活動(dòng)可中斷更加一般性的假設(shè): 如項(xiàng)目中僅有部分活動(dòng)可中斷,且在中斷以后,相應(yīng)活動(dòng)所使用的資源并非全部都可被釋放[70]等.

3)資源–技能類約束

項(xiàng)目所涉及的資源一般可分為可更新資源和不可更新資源兩種,MSPSP 中的多技能資源多是指可更新資源,且一般情況下,資源的總量為定值,資源之間相互獨(dú)立. 而文獻(xiàn)[20,21]則提出了關(guān)鍵資源的概念,雖然研究的是單技能項(xiàng)目調(diào)度問題,但是其有關(guān)關(guān)鍵資源(principal resource)、附屬資源(dependent resource)和獨(dú)立資源(independent resource)的闡述,能為MSPSP 的研究提供較有價(jià)值的參考.

技能水平(skill level)約束是MSPSP 研究中最常見的一種技能類約束, 在傳統(tǒng)MSPSP 中資源對(duì)技能的熟練度是二元的, 資源對(duì)技能或是完全掌握或是完全不掌握[32], 即RFkl ∈{0,1}. 而在考慮技能水平的MSPSP 中,資源對(duì)技能的熟練水平是多元的[50],不同資源對(duì)同一技能的熟練程度存在差異,技能水平有高有低. 引入索引參數(shù)g ∈{1,2,...,G}表示資源對(duì)技能的掌握水平,以及二元參數(shù)

其中當(dāng)g ＜g′, RFklg′= 1時(shí),有RFklg= 1,即當(dāng)資源具備高等級(jí)技能時(shí),也必然能具備該技能的低等級(jí)技能[72].

資源技能水平的差異給項(xiàng)目帶來的影響是多方面的,學(xué)者們從不同視角對(duì)這一問題進(jìn)行了研究,其中最常見的假設(shè)是,活動(dòng)會(huì)對(duì)資源的技能水平有要求[72];活動(dòng)工期的長短會(huì)受資源技能水平的影響[67]等. 此外,也有部分學(xué)者假設(shè)資源的技能水平會(huì)影響項(xiàng)目產(chǎn)品的質(zhì)量[49]、項(xiàng)目的完工率、返工率[58]以及活動(dòng)對(duì)資源的需求量[50]等.

在多技能人力資源項(xiàng)目的研究中,員工技能存在學(xué)習(xí)效應(yīng)的現(xiàn)象也引起了學(xué)者的關(guān)注,學(xué)習(xí)效應(yīng)指的是員工的技能熟練度會(huì)隨技能的使用而逐漸提高[39]. 與之相應(yīng)的,還有遺忘效應(yīng):頻繁使用技能會(huì)提升技能熟練度,而長時(shí)間閑置技能則會(huì)降低技能水平[76]. 表3 列出MSPSPc 的約束條件.

表3 MSPSP 的約束條件Table 3 Constraints in MSPSP

3 基于MSPSP 求解的研究綜述

MSPSP 屬于NP-hard 問題,具有較高的求解難度,目前關(guān)于MSPSP 的求解方法可分為三種: 精確求解法、啟發(fā)式算法和元啟發(fā)式算法.

3.1 精確算法

在前文所介紹的兩種MSPSP 模型中,以時(shí)間為索引所構(gòu)建的是0-1 規(guī)劃模型,其決策變量均為二元變量,活動(dòng)的開始時(shí)間Si被限定為整數(shù),但是該模型是非線性的,雖然在求解小規(guī)模問題時(shí)便于使用窮舉法等精確方法,但在大規(guī)模算例中求解則較為困難.如文獻(xiàn)[42]以多技能資源均衡為目標(biāo),構(gòu)建了以時(shí)間為索引的0-1 規(guī)劃模型,利用LINGO 求解,但所求解的算例是僅包含5 個(gè)活動(dòng)的項(xiàng)目.

引入活動(dòng)時(shí)序關(guān)系后, 則可以將Si擴(kuò)展為全體實(shí)數(shù), 且該問題可被描述為混合整數(shù)線性規(guī)劃模型(mixed integer linear programming,MILP),便于使用分支定界法進(jìn)行精確求解. 如文獻(xiàn)[4]建立了MILP,通過啟發(fā)式算法求得解的下界后,根據(jù)活動(dòng)的最早–最晚開始時(shí)間縮小了決策變量Si的取值范圍,并基于活動(dòng)時(shí)序關(guān)系構(gòu)造了若干約束,進(jìn)一步壓縮了解空間. 盡管如此,現(xiàn)有的求解器如CPLEX 和LINGO 等,在求解MSPSP 時(shí)依舊只能處理小規(guī)模的項(xiàng)目案例,如文獻(xiàn)[20]使用的案例僅包含20 個(gè)活動(dòng).

分支定界法是在精確求解MSPSP 的主要方法,而提高其求解效率的關(guān)鍵在于下界的計(jì)算,一個(gè)緊的下界能大大降低搜索空間,提高求解效率.目前MSPSP 研究領(lǐng)域求解下界的方法有兩種,第一種最直觀最常見的方法可稱為“直接法”,也即是對(duì)模型中的某些約束進(jìn)行松弛甚至直接刪除,如文獻(xiàn)[4]刪除了所有資源約束,直接以關(guān)鍵路徑的長度作為下界,文獻(xiàn)[20]則放寬了資源約束,假設(shè)每個(gè)活動(dòng)都能以最短工期進(jìn)行,這種下界計(jì)算方式盡管簡單,但是給出的往往是一個(gè)過于寬松的下界,緊密性較差,難以顯著降低搜索節(jié)點(diǎn)的數(shù)量.

第二種是“突破法”[78],即先預(yù)設(shè)一個(gè)較寬松的下界,在證明該下界無可行解后,逐漸提升下界,直至出現(xiàn)可行解,固定下界的值.相較于直接法,突破法能有效提升下界的緊密性,但其難點(diǎn)也是重點(diǎn),在于如何證明一個(gè)給定的下界無可行解存在,尤其由于MSPSP 中的復(fù)雜性,一旦開發(fā)出高效的證明方式,突破法獲得的下界很可能遠(yuǎn)優(yōu)于關(guān)鍵路徑長度,有效減小搜索空間. 如文獻(xiàn)[16]提出了基于“活動(dòng)相容集”的下界突破證明方法,能有效求解包含32 個(gè)活動(dòng)的項(xiàng)目算例.

3.2 啟發(fā)式算法

啟發(fā)式算法是一種針對(duì)具體問題開發(fā)的, 貼合問題特征的求解策略,它不保證給出問題的最優(yōu)解, 但是能在可接受的時(shí)間及空間內(nèi)給出可行解. 除了精確求解法以外, 大多數(shù)的項(xiàng)目調(diào)度求解方法都是一個(gè)不斷為活動(dòng)安排時(shí)間、分配資源的迭代過程,因此涉及兩個(gè)問題:如何迭代,以及每次迭代內(nèi)如何操作,關(guān)于MSPSP 的啟發(fā)式算法也大多是圍繞這兩點(diǎn)設(shè)計(jì)的.

調(diào)度計(jì)劃生成機(jī)制解決的便是如何迭代的問題, 常用的有并行調(diào)度(parallel scheduling generation scheme,PSGS)和串行調(diào)度(serial scheduling generation scheme,SSGS)兩種. 算法1 和算法2 展示了兩種調(diào)度計(jì)劃生成機(jī)制的偽代碼.

可以看出,并行調(diào)度隨時(shí)間迭代,在每次迭代內(nèi)不斷選擇滿足約束的活動(dòng)加入當(dāng)前開始活動(dòng)集,串行調(diào)度隨活動(dòng)迭代,在每次迭代內(nèi)選擇活動(dòng)并按最早可開始時(shí)間為之排程. PSGS 和SSGS 之中并不存在一個(gè)普適的最優(yōu)的方法,學(xué)者們根據(jù)所設(shè)計(jì)的算法采用了不同的計(jì)劃生成機(jī)制,如文獻(xiàn)[32,33]采用的是PSGS,而文獻(xiàn)[78]則選擇SSGS.

活動(dòng)相容性判斷在很多MSPSP 啟發(fā)式算法中是很重要的一步[4],它是指根據(jù)工序約束和資源約束判斷當(dāng)前可同時(shí)開始的活動(dòng)集合.在傳統(tǒng)的單技能資源受限項(xiàng)目調(diào)度中,若干活動(dòng)能否相容,除了判斷工序約束外,只需對(duì)資源的供應(yīng)和需求數(shù)量做簡單對(duì)比即可.但在多技能項(xiàng)目中,由于資源具備多技能,即便資源數(shù)量是確定的,其技能分配也是可變的,簡單的數(shù)量對(duì)比并不足以作為判斷的依據(jù). 而最大程度上使相容的活動(dòng)同時(shí)開始,不僅能提高資源的利用率,還能縮短項(xiàng)目工期.如文獻(xiàn)[32]的最小費(fèi)用最大流法,文獻(xiàn)[33]的二分圖最大匹配法,都是用來求解固定資源數(shù)量下的最大相容活動(dòng)集的. 對(duì)SGSS 而言,由于其每次迭代僅考慮單獨(dú)一個(gè)活動(dòng),并不存在活動(dòng)相容性判斷的問題.這降低了問題的求解難度,但同時(shí)也會(huì)使一些原本可以并行的活動(dòng),由于資源技能的分配不合理而無法并行,導(dǎo)致項(xiàng)目工期變長,這也是更多MSPSP 啟發(fā)式算法選擇PSGS 而不是SGSS 的原因.

在確定了調(diào)度計(jì)劃生成機(jī)制以后,需要決定每次迭代內(nèi)如何操作,即圖2 中的決策(Ⅰ)和決策(Ⅱ),它們分別代表活動(dòng)調(diào)度以及資源指派問題.現(xiàn)有文獻(xiàn)中,最常見的決策方式是通過一定的規(guī)則賦予活動(dòng)和資源優(yōu)先權(quán),而后根據(jù)各自的優(yōu)先權(quán),按照一定的調(diào)度計(jì)劃生成機(jī)制對(duì)項(xiàng)目實(shí)施調(diào)度,這類調(diào)度算法被稱為基于優(yōu)先規(guī)則的啟發(fā)式算法. 如文獻(xiàn)[32]考慮了活動(dòng)的最遲開始時(shí)間及后續(xù)活動(dòng)時(shí)間等因素以賦予活動(dòng)權(quán)值,考慮了資源稀缺度技能需求度等因素以賦予資源權(quán)值,文獻(xiàn)[33]則更進(jìn)一步,在調(diào)度過程中根據(jù)資源的供給及活動(dòng)的需求,動(dòng)態(tài)調(diào)整資源的權(quán)值.

基于優(yōu)先規(guī)則的啟發(fā)式算法具有規(guī)則易理解、易設(shè)計(jì)、求解速度快等優(yōu)點(diǎn),尤其對(duì)于規(guī)模較大的復(fù)雜項(xiàng)目而言,往往能在很短的時(shí)間內(nèi)求得滿意解,這是精確求解法和其它元啟發(fā)式算法難以企及的. 然而由于相關(guān)規(guī)則的設(shè)計(jì)具有很強(qiáng)的目標(biāo)針對(duì)性,這使其難以被應(yīng)用于求解多目標(biāo)問題.如活動(dòng)規(guī)則中的“具有最多后續(xù)的活動(dòng)優(yōu)先開始”這一規(guī)則,顯然是針對(duì)優(yōu)化項(xiàng)目工期這一目標(biāo)設(shè)計(jì)的,在求解以資源、成本為目標(biāo)的問題時(shí),就很難起到作用. 此外,規(guī)則的制定還應(yīng)考慮項(xiàng)目特征,即便對(duì)于同一類型的項(xiàng)目,由于活動(dòng)數(shù)量、網(wǎng)絡(luò)復(fù)雜度、資源需求強(qiáng)度等的不同,其最優(yōu)的規(guī)則也往往是不同的,這無疑對(duì)項(xiàng)目計(jì)劃的制定者提出了較高的知識(shí)及經(jīng)驗(yàn)要求.

3.3 元啟發(fā)式算法

相對(duì)于啟發(fā)式算法而言,元啟發(fā)式算法不依賴于具體問題,而是借助于一系列通用求解策略對(duì)問題進(jìn)行求解,因此在MSPSP 的現(xiàn)有研究成果中,元啟發(fā)式算法的應(yīng)用最為廣泛.

盡管目前有很多求解MSPSP 的元啟發(fā)式算法,但其最根本的思路大多遵循著算法1 和算法2 的調(diào)度過程,即通過迭代,逐步完成對(duì)活動(dòng)的調(diào)度和資源的指派. 基于規(guī)則的啟發(fā)式算法是通過經(jīng)驗(yàn)或推理設(shè)計(jì)一定的規(guī)則賦予活動(dòng)和資源優(yōu)先權(quán),元啟發(fā)式算法則是以隨機(jī)的方式產(chǎn)生初始解,而后根據(jù)目標(biāo)值的反饋,經(jīng)過進(jìn)化不斷優(yōu)化解的質(zhì)量. 因此,元啟發(fā)式算法隨機(jī)性更大,但同時(shí)也具有更廣的搜索空間,而且一個(gè)有效的進(jìn)化機(jī)制能保證解不斷向最優(yōu)解收斂,這是基于規(guī)則的啟發(fā)式算法所不及的.

編解碼和進(jìn)化策略是元啟發(fā)式算法優(yōu)化求解過程的兩個(gè)核心內(nèi)容.在MSPSP 的元啟發(fā)式算法中,編碼包含活動(dòng)編碼和資源編碼,分別對(duì)應(yīng)算法1 和算法2 中的決策(Ⅰ)和決策(Ⅱ). 最常見的活動(dòng)編碼方式有兩類,第一類為按活動(dòng)順序編碼[23],其個(gè)體基因位上的數(shù)值是活動(dòng)的編號(hào),在個(gè)體上位置越靠前的活動(dòng)優(yōu)先權(quán)越高,見圖2(a),這類編碼方式的優(yōu)點(diǎn)是活動(dòng)優(yōu)先級(jí)明確,基因信息在傳遞過程中不會(huì)失真,缺點(diǎn)是在進(jìn)行交叉變異等進(jìn)化操作時(shí),可能會(huì)產(chǎn)生大量需要修正的不可行解;第二類是按活動(dòng)權(quán)值編碼[25],其個(gè)體基因位上的數(shù)值指的是對(duì)應(yīng)活動(dòng)的權(quán)值,權(quán)值越大的活動(dòng)優(yōu)先權(quán)越高,見圖2(b),這類編碼方式的優(yōu)點(diǎn)是不會(huì)產(chǎn)生不可行解,但是在進(jìn)化時(shí),由于不同權(quán)值在不同序列內(nèi)的排序可能不同,從而導(dǎo)致基因交換后信息失真.

圖2 MSPSP 元啟發(fā)式算法常用編碼方式Fig.3 Common solution representations in meta-heuristic algorithms for MSPSP

除此之外,也有文獻(xiàn)采用了活動(dòng)時(shí)間編碼的方式,也即每個(gè)基因位上的數(shù)值代表對(duì)應(yīng)活動(dòng)的開始時(shí)間.盡管這類編碼在解碼時(shí)可直接生成調(diào)度計(jì)劃,不需要通過調(diào)度計(jì)劃生成機(jī)制處理編碼信息,但是它在進(jìn)化時(shí)也可能會(huì)生成大量的不可行解,且相對(duì)于按活動(dòng)順序編碼,它更不易修正,因此只有針對(duì)特定的算例時(shí),才有部分學(xué)者采用了這種編碼方式[84].

部分元啟發(fā)式算法中僅考慮活動(dòng),而不含資源信息,資源的指派是通過其它方式求解的,這種算法可理解為用元啟發(fā)式求解決策(Ⅰ),而用啟發(fā)式求解決策(Ⅱ). 在同時(shí)包含活動(dòng)和資源信息的元啟發(fā)式算法中,資源的編碼方式也有兩類,第一類是一維賦值型編碼[25],即在活動(dòng)編碼后端繼續(xù)設(shè)置等于資源數(shù)量的基因位,每個(gè)基因位上的數(shù)值代表對(duì)應(yīng)資源的優(yōu)先權(quán),從而為決策(Ⅱ)的進(jìn)行提供依據(jù),見圖2(c). 因此,該類編碼個(gè)體結(jié)構(gòu)簡單易于進(jìn)化操作,但由于其活動(dòng)信息和資源信息是相互獨(dú)立的,這就導(dǎo)致在進(jìn)化過程會(huì)各自獨(dú)立變化,不能改善活動(dòng)與資源之間的匹配關(guān)系;第二類是二維賦值型編碼[73],即在活動(dòng)編碼的下方繼續(xù)編碼,為對(duì)應(yīng)活動(dòng)賦予資源,從而使編碼由一維轉(zhuǎn)變?yōu)槎S,見圖2(d),這類編碼能保證優(yōu)秀的活動(dòng)-資源匹配信息得到遺傳,但是在進(jìn)化過程可能會(huì)導(dǎo)致不可行解的產(chǎn)生,且編碼復(fù)雜度會(huì)隨著項(xiàng)目規(guī)模的增大而快速上升,算法運(yùn)行時(shí)間也隨之增加.

解碼是將個(gè)體信息轉(zhuǎn)譯成具體調(diào)度計(jì)劃的過程,解碼過程可以說是調(diào)度計(jì)劃的生成過程,由于大多數(shù)元啟發(fā)式算法中個(gè)體所包含的信息僅僅是活動(dòng)及資源的優(yōu)先權(quán),因此在解碼時(shí)仍需要選擇調(diào)度計(jì)劃生成機(jī)制.對(duì)于按照活動(dòng)順序編碼的算法而言,最適合的是SGSS,因?yàn)閭€(gè)體中的活動(dòng)序列已經(jīng)決定了迭代的次序,不需要額外的數(shù)據(jù)處理. 無論是哪種調(diào)度計(jì)劃生成機(jī)制,兩種編碼方式下的個(gè)體經(jīng)過處理后都可應(yīng)用,更進(jìn)一步地,文獻(xiàn)[25]直接將其納入個(gè)體的編碼,在解碼的過程中,只需讀取個(gè)體中該基因位上的信息,采取相應(yīng)的調(diào)度計(jì)劃生成機(jī)制即可.這樣的處理方式增大了算法的搜索空間,但是在面對(duì)具有不同特征的算例時(shí),也能挑選出最適合的調(diào)度計(jì)劃生成機(jī)制,規(guī)避了用單一調(diào)度計(jì)劃生成機(jī)制處理所有項(xiàng)目算例的缺陷.

一般的基于規(guī)則的啟發(fā)式算法難以應(yīng)對(duì)多目標(biāo)問題,因此在面對(duì)多目標(biāo)MSPSP 時(shí),更多的是采用元啟發(fā)式算法. 在多目標(biāo)求解算法中,如何根據(jù)個(gè)體目標(biāo)值判別解的優(yōu)劣是保證進(jìn)化的關(guān)鍵,其中最常見的個(gè)體優(yōu)劣判別方法是非支配排序技術(shù), 它基于Pareto 最優(yōu)理論,設(shè)計(jì)了擁擠度等指標(biāo),通過多目標(biāo)值的對(duì)比及個(gè)體在解空間內(nèi)的位置對(duì)個(gè)體排序,從而為進(jìn)化提供依據(jù). 如非支配排序遺傳算法(non-dominated sorting genetic algorithms,NSGA-Ⅱ)等,具體文獻(xiàn)見表4.

表4 MSPSP 的求解算法Table 4 Algorithms for MSPSP

3.4 算例庫

在檢驗(yàn)算法的優(yōu)劣時(shí),一個(gè)合理的數(shù)據(jù)庫至關(guān)重要.MSPSP 與傳統(tǒng)的單技能RCPSP 有共同點(diǎn)也有不同點(diǎn),相較于傳統(tǒng)RCPCP,MSPSP 增加了有關(guān)技能的參數(shù),所以RCPSP 研究中所使用的標(biāo)準(zhǔn)算例庫無法被直接應(yīng)用于MSPSP 研究之中. 因此,有些學(xué)者在研究過程中通過修改RCPSP 標(biāo)準(zhǔn)算例庫以適應(yīng)MSPSP,有些學(xué)者則構(gòu)造了全新的MSPSP 算例庫.

算法有效性及穩(wěn)健性的檢驗(yàn), 需要用到各種規(guī)模各種類型的項(xiàng)目算例, 因此項(xiàng)目算例庫的多樣化程度越高, 越具有使用價(jià)值. 一般來說, 主要從以下四個(gè)指標(biāo)衡量MSPSP 算例的類型: 活動(dòng)數(shù)量(number of activities, N)、網(wǎng)絡(luò)復(fù)雜度(network complexity, NC)、資源強(qiáng)度(resource strength, RS)和技能因素(skill factor,SF).

文獻(xiàn)[93]構(gòu)造的項(xiàng)目調(diào)度算例庫(project scheduling problem library,PSPLIB1http://www.om–db.wi.tum.de/psplib/main.html)是項(xiàng)目調(diào)度領(lǐng)域最常用的一個(gè)算例庫. 該算例庫經(jīng)過不斷更新,目前不僅包含普通的RCPSP 算例,還含有多模式RCPSP 算例,項(xiàng)目規(guī)模從小到大依次包含30,60,90 和120 個(gè)活動(dòng),且每個(gè)規(guī)模下包含480 個(gè)算例.

然而PSPLIB 中的資源均為單技能資源,它無法被直接用于MSPSP 研究.因此學(xué)者們對(duì)其做了修改,大多是在保持項(xiàng)目網(wǎng)絡(luò)不變的前提下,對(duì)資源的技能、活動(dòng)的需求等方面進(jìn)行調(diào)整. 如文獻(xiàn)[36]提出了一種基于PSPLIB 的多技能項(xiàng)目算例生成機(jī)制,構(gòu)造了PSPMSWC 算例庫,依據(jù)項(xiàng)目網(wǎng)絡(luò)中活動(dòng)數(shù)量分為四個(gè)子集: J30,J60,J90 和J120,每個(gè)子集包含360 個(gè)活動(dòng),共1 440 個(gè)項(xiàng)目算例.

也有學(xué)者根據(jù)MSPSP 的特點(diǎn),構(gòu)造全新的算例庫,如文獻(xiàn)[87]構(gòu)造了專門應(yīng)用于MSPSP 的iMOPSE 算例庫2http://imopse.ii.pwr.edu.pl/index.html,依據(jù)項(xiàng)目網(wǎng)絡(luò)中活動(dòng)數(shù)量分為四個(gè)子集: J10,J15,J100 和J200,分別含有3 個(gè),3 個(gè),18 個(gè)和18 個(gè)算例,共42 個(gè)算例. 此外還有學(xué)者通過RanGen 軟件3https://www.projectmanagement.ugent.be/生成算例,或者自行設(shè)計(jì)算例,或者直接選取現(xiàn)實(shí)項(xiàng)目案例進(jìn)行研究,各文獻(xiàn)所采用的算例庫具體見表5.

表5 MSPSP 的算例庫Table 5 Case library for MSPSP

4 結(jié)束語

為給多技能項(xiàng)目調(diào)度的研究提供參考,本文從問題建模和問題求解兩個(gè)方面分析了MSPSP 的現(xiàn)有研究成果.在模型的目標(biāo)函數(shù)方面,目前的研究集中于優(yōu)化項(xiàng)目的工期、成本、資源均衡等,而項(xiàng)目管理者所重視的目標(biāo)中仍有部分鮮有學(xué)者關(guān)注,如項(xiàng)目凈現(xiàn)值問題.除此之外,實(shí)際項(xiàng)目中管理者的目標(biāo)往往更加復(fù)雜,同時(shí)考慮多個(gè)目標(biāo)的調(diào)度方法更能符合現(xiàn)實(shí)需求. 在模型的約束條件方面,學(xué)者們將多技能與多項(xiàng)目、多模式、活動(dòng)可中斷、技能可變等方面結(jié)合,形成了較為豐富的理論成果.然而,實(shí)際項(xiàng)目往往具有鮮明的行業(yè)特征,所涉及的多技能資源也具有不同的特性,此外,不確定環(huán)境下多技能項(xiàng)目、項(xiàng)目組合中的多技能項(xiàng)目等也各具特點(diǎn),所以多技能項(xiàng)目調(diào)度的研究,可更多地結(jié)合行業(yè)特點(diǎn)及項(xiàng)目環(huán)境,根據(jù)實(shí)際構(gòu)建模型. 在問題求解方面,學(xué)者們開發(fā)了大量的元啟發(fā)式算法,而對(duì)啟發(fā)式算法的研究則相對(duì)較少. 但在實(shí)踐中,一些基于規(guī)則的啟發(fā)式算法往往更便于應(yīng)用,也能給予項(xiàng)目管理者更多啟示. 因此,如何開發(fā)出求解速度快、求解質(zhì)量高的啟發(fā)式方法也是未來的一個(gè)研究方向.最后,在研究所采用的算例庫方面,目前所使用的大規(guī)模算例庫大多是對(duì)PSPLIB 修改得來的,很難有統(tǒng)一的對(duì)比基準(zhǔn)(benchmark),開發(fā)一個(gè)算例數(shù)量多的包含對(duì)比基準(zhǔn)的大規(guī)模算例庫也是MSPSP 研究的一個(gè)重點(diǎn).