多技能項目調度問題研究綜述

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

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

1 引 言

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

多技能使資源的分配更加靈活,這不僅能豐富項目計劃的多樣性,還能在項目面臨不確定風險時,為管理者提供更為靈活多變的應對措施.如Hegazy 等[1]研究了單技能項目和多技能項目的調度問題,結果表明項目管理者在調度時考慮多技能策略能有效地減少工期降低成本. Arashpour 等[2]則指出,多技能員工有助于降低項目周期、提高項目產出、提升資源均衡水平,并鼓勵企業對員工進行適當的跨技能培訓.此外,陳蓉等[3]在研究人員隨機離職的多技能項目調度問題時提出,當項目實施過程中出現人員離職時,可根據技能特征選擇與離職員工相近的員工補缺,以降低這類不確定事件的影響.

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

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

圖1 2000 年～2020 年MSPSP 相關文獻數量Fig.1 Quantity of literatures on MSPSP in 2000～2020

2 基于MSPSP 建模的研究綜述

2.1 問題描述與基礎數學模型

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

表1 MSPSP 相關參數匯總Table 1 Summary of the parameters in MSPSP

續表1Table 1 Continues

MSPSP 需要解決的是, 在一定的環境下, 如何對活動排程并為之分配資源, 以滿足預設的目標.所以,MSPSP 的主要決策內容為:活動的開始時間、活動所使用的資源以及資源在對應活動中所執行的技能.根據現有文獻,模型中決策變量的構建可分為兩類. 第一類為含有時間索引的決策變量,其最常用變量形式為

由式(1)或式(2)可以確定項目活動的排程,由式(3)可以推導出相應的資源分配方案.據此,含有時間索引的MSPSP 數學模型(I)如下

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

第二類決策變量在構建時不以時間為索引,而是引入了活動的時序關系,最常見的變量形式為

Si表示活動i的開始時間,

由決策變量(12)可以確定項目活動的排程,由決策變量(14)可以得出項目的資源分配方案.由此可歸納出含有時序關系的MSPSP 數學模型(II)如下

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

2.2 目標函數

項目工期是MSPSP研究中最常見的目標,一般是指在確定性環境下所生成的調度計劃的工期,其典型的數學表達為

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

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

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

成本類目標具有鮮明的項目特征,不同的項目其成本構成會存在較大差異.如在研發項目中,研發人員的工資、獎金、分紅以及培訓費用等資源使用成本是研究的重點. 而在一些具有嚴格交付期的大型工程項目中,更受關注的則是和工期有關的懲罰性和獎勵性成本等.

資源類目標在多技能項目調度問題研究中,有顯著區別于一般項目的特點. 在項目計劃階段,多技能資源的指派方案更多,這使得資源均衡問題變得更復雜,但同時也使其具備了更大的優化空間. 在項目實施階段,當發生計劃外的不確定事件時,常常會進行反應性的資源重調度,而資源的多技能特征也使得這種反應性調度更加靈活. MSPSP 的變量形式及目標見表2.

表2 MSPSP 的變量形式及目標Table 2 Models and objectives in MSPSP

2.3 約束條件

在現實中,不同的項目具有不同的內部特征,也面臨著不同的外部環境. 項目間的這些差異在數學模型中表現為不同的約束條件,并由此產生了許多MSPSP 的變體.以下將從項目環境、活動以及資源–技能三個角度,介紹多技能項目在現實中所面臨的不同狀況,以及在構建模型時所對應的約束條件.

1)項目環境類約束

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

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

現代項目面臨著愈發復雜的內外環境,因此不確定環境下的魯棒項目調度研究也成為近些年來的研究熱點[95]. 然而多數研究還停留在一般單技能項目的層面,而很少有對多技能項目魯棒調度的研究.此外,很多現實的多技能項目,如研發項目等,都是以項目組合的形式實施進度管理的,而學術界對于多技能項目組合調度問題的關注還不足.

2)活動類約束

在最基本的MSPSP 中, 活動工序服從結束–開始(finish-start, FS)的約束類型, 也即緊前活動結束之后,后續活動才可開工. 而在現實項目中,活動工序之間的約束類型往往更加復雜,即廣義優先關系(generalized precedence relations)[69],如SS(start-start),SF(start-finish)和FF(finish-finish)等.

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

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

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

3)資源–技能類約束

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

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

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

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

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

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

3 基于MSPSP 求解的研究綜述

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

3.1 精確算法

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

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

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

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

3.2 啟發式算法

啟發式算法是一種針對具體問題開發的, 貼合問題特征的求解策略,它不保證給出問題的最優解, 但是能在可接受的時間及空間內給出可行解. 除了精確求解法以外, 大多數的項目調度求解方法都是一個不斷為活動安排時間、分配資源的迭代過程,因此涉及兩個問題:如何迭代,以及每次迭代內如何操作,關于MSPSP 的啟發式算法也大多是圍繞這兩點設計的.

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

可以看出,并行調度隨時間迭代,在每次迭代內不斷選擇滿足約束的活動加入當前開始活動集,串行調度隨活動迭代,在每次迭代內選擇活動并按最早可開始時間為之排程. PSGS 和SSGS 之中并不存在一個普適的最優的方法,學者們根據所設計的算法采用了不同的計劃生成機制,如文獻[32,33]采用的是PSGS,而文獻[78]則選擇SSGS.

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

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

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

3.3 元啟發式算法

相對于啟發式算法而言,元啟發式算法不依賴于具體問題,而是借助于一系列通用求解策略對問題進行求解,因此在MSPSP 的現有研究成果中,元啟發式算法的應用最為廣泛.

盡管目前有很多求解MSPSP 的元啟發式算法,但其最根本的思路大多遵循著算法1 和算法2 的調度過程,即通過迭代,逐步完成對活動的調度和資源的指派. 基于規則的啟發式算法是通過經驗或推理設計一定的規則賦予活動和資源優先權,元啟發式算法則是以隨機的方式產生初始解,而后根據目標值的反饋,經過進化不斷優化解的質量. 因此,元啟發式算法隨機性更大,但同時也具有更廣的搜索空間,而且一個有效的進化機制能保證解不斷向最優解收斂,這是基于規則的啟發式算法所不及的.

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

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

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

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

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

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

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

3.4 算例庫

在檢驗算法的優劣時,一個合理的數據庫至關重要.MSPSP 與傳統的單技能RCPSP 有共同點也有不同點,相較于傳統RCPCP,MSPSP 增加了有關技能的參數,所以RCPSP 研究中所使用的標準算例庫無法被直接應用于MSPSP 研究之中. 因此,有些學者在研究過程中通過修改RCPSP 標準算例庫以適應MSPSP,有些學者則構造了全新的MSPSP 算例庫.

算法有效性及穩健性的檢驗, 需要用到各種規模各種類型的項目算例, 因此項目算例庫的多樣化程度越高, 越具有使用價值. 一般來說, 主要從以下四個指標衡量MSPSP 算例的類型: 活動數量(number of activities, N)、網絡復雜度(network complexity, NC)、資源強度(resource strength, RS)和技能因素(skill factor,SF).

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

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

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

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

4 結束語

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