王瑩瑩，吳立云

(河南理工大學(xué) 能源科學(xué)與工程學(xué)院，河南 焦作 454000)

許多企業(yè)在日常生產(chǎn)及研發(fā)過程中經(jīng)常多個項目并行開展，這使得企業(yè)管理難度加大。合理進(jìn)行多項目管理和人力資源分配，不僅能提高生產(chǎn)效率、降低勞動成本，還能提升員工的滿意度和公平性。因此，如何在多項目中合理安排各項目調(diào)度及分配人力資源對增強(qiáng)企業(yè)的競爭力至關(guān)重要。

在多項目環(huán)境中，Wu等[1]研究了考慮學(xué)習(xí)效果的項目進(jìn)度和人員分配的決策問題。Fang等[2]研究了多項目進(jìn)度優(yōu)化管理問題，基于列生成法和啟發(fā)式方法，采用免疫遺傳算法進(jìn)行求解。肖菁等[3]在多項目并行的調(diào)度問題研究中考慮了各項目之間存在的優(yōu)先級別對調(diào)度過程的影響。

員工技能和熟練度是人力資源管理中需要考慮的重要特性。Heimerl等[4]、Myszkowski等[5]和Yannibelli等[6]將員工技能分為單技能、多技能和全技能，研究了不同技能的工作效率對作業(yè)時間的影響。Barz等[7]在決策模型中對具有不同技能水平員工的分配問題展開了研究。陳蓉等[8]研究新產(chǎn)品研發(fā)項目的多技能人力資源調(diào)度問題時，在模型中考慮了多技能工離職的情況。劉振元等[9]研究了多技能資源時間窗約束下的可中斷項目調(diào)度問題。

目前項目調(diào)度的優(yōu)化目標(biāo)主要為追求工期、成本、資源等方面的最優(yōu)解。Myszkowski等[5]、Hanne等[10]、Chen等[11]和陳俊杰等[12]以最小化項目的總工期和總成本為目標(biāo)函數(shù)。Yannibelli等[6]考慮了為項目分配人力資源的有效水平的最大化和工期最小化2個具有相互沖突的優(yōu)化目標(biāo)。伊雅麗[13]考慮了人力成本以及項目的延期懲罰成本。傳統(tǒng)的項目調(diào)度優(yōu)化研究主要集中于提高資源配置效率和降低成本，很少考慮因不均衡的任務(wù)分配會造成工作量差異引起多能工的不滿情緒，而影響到員工的工作效率，進(jìn)而影響項目的完成。廉潔等[14]研究了生產(chǎn)系統(tǒng)中以多能工工作量均衡為目標(biāo)的多能工分配問題。廖婷婷[15]對軟件開發(fā)項目的資源分配進(jìn)行優(yōu)化，提高了員工工作量分配的均衡水平。

人力資源是一種具有多技能性、異質(zhì)效率性等特點的動態(tài)資源。現(xiàn)有相關(guān)研究成果缺乏對多項目和多技能的全面考慮，未能體現(xiàn)多能工技能差異以及工作量均衡對項目進(jìn)度的影響。因此，本文提出的以多項目總工期最短和多能工間工作量均衡為目標(biāo)的多項目多技能人力資源調(diào)度問題，具有重要的理論意義和現(xiàn)實意義。

1 問題描述

假設(shè)共有J個項目并行開展，I個多能工可供分配。項目j有Nj項任務(wù)，項目j中的任務(wù)k需要具備技能的多能工來完成。其中，任務(wù)1和任務(wù)Nj為虛擬任務(wù)，分別表示項目的開始和結(jié)束，不消耗時間和人力資源。每個多能工i的技能集合為其技能熟練度水平集合為(pi1,pi2,···,pis)。技能熟練度系數(shù)rik的倒數(shù)(1/rik)作為作業(yè)時間系數(shù)wik，wik＜1表示多能工i完成任務(wù)k的時間少于標(biāo)準(zhǔn)作業(yè)時間。一項任務(wù)的實際工作時間是該任務(wù)的標(biāo)準(zhǔn)作業(yè)時間tjk和負(fù)責(zé)該任務(wù)的多能工Yijk的工作時間系數(shù)wik的乘積。

圖1描述了本文研究的問題。圖中包含3個項目、9位多能工，不同的項目包含不同的任務(wù)且任務(wù)需要的技能也不同，而9名多能工都具備多種技能，現(xiàn)將9名多能工分配至項目的任務(wù)中。以項目1為例，項目1的任務(wù)列表為(W2,W3,W4,W5,W7,W8)，任務(wù)需要的技能分別為(k3,k1,k2,k4,k3,k1)，僅多能工-項目分配方案就有35 280種。圖中將多能工1、3、8分配至項目1，分別負(fù)責(zé)的任務(wù)為I1:(W3,W8)、I3:(W4,W5)、I8:(W2,W7)。

圖1 多項目的多能工分配示例Figure 1 Example of multi-skilled assignment for multi-project

因此，本問題包含以下關(guān)鍵決策，以達(dá)到多項目總工期最短和多能工工作量最均衡。1) 給每個項目分配哪些多能工；2) 給已分配至項目中的多能工分配哪些任務(wù)；3) 項目中每個任務(wù)的開始時間及結(jié)束時間。

1.1 基本假設(shè)

1) 每個多能工同一時間只能使用一項技能；

2) 任務(wù)一旦開始，不允許搶占、不能中斷；

3) 多能工一旦被分配到某個項目中，只能做這個項目；

4) 一個任務(wù)只能由一個多能工來完成；

5) 多能工的技能熟練水平是固定的，不考慮學(xué)習(xí)和遺忘。

1.2 符號定義

多能工的總數(shù)；Nj表示項目j的任務(wù)總數(shù)(1≤k≤Nj)；

1)變量參數(shù)。J表示項目總數(shù)(1≤j≤J)；I表示tjk表示項目j的任務(wù)k的標(biāo)準(zhǔn)工作時間系數(shù)；rik表示多能工i對任務(wù)k技能熟練度水平；wik表示多能工i進(jìn)行任務(wù)k時的工作時間系數(shù)wik=1/rik；Qk表示任務(wù)k的緊前任務(wù)集合；m為Qk的任意緊前任務(wù)；sjk表示項目j中任務(wù)k的開始工作時間；fjk表示項目j中任務(wù)k的工作結(jié)束時間。

2) 變量定義。

2 數(shù)學(xué)模型

第1個目標(biāo)函數(shù)(式(1))表示多項目總工期T最小，其中，表示項目j中Nj個任務(wù)的工作結(jié)束時間；第2個目標(biāo)函數(shù)(式(2))表示所有多能工工作量的方差B最小，即多能工間工作量最均衡；式(3)保證一個多能工僅能分配到一個項目中；式(4)表示多能工必須具備分配的任務(wù)所需技能；式(5)避免項目間的多能工調(diào)度；式(6)表示每項任務(wù)必須被完成且只被完成一次；式(7)約束了任務(wù)的開始時間不得早于其緊前任務(wù)的結(jié)束時間；式(8)定義了項目中每個任務(wù)的結(jié)束時間等于開始時間與工作時間之和。

3 算法設(shè)計

本文研究的問題屬于NP-hard問題，因此選取第2代非支配排序遺傳算法(non-dominated sorting genetic algorithm II,NSGA-II)作為求解算法，并在

NSGA-II的基礎(chǔ)上，根據(jù)問題的特點開發(fā)了適用于本文模型的算法。

3.1 編碼規(guī)則

本文參考Vila Goncalves Filho等[16]的編碼方式，將編碼結(jié)構(gòu)設(shè)計為便于交叉操作的雙層染色體編碼結(jié)構(gòu)。第1層染色體包含I個基因位，I為多能工數(shù)，每個基因位的值為多能工編號，第1層染色體可分為J段，J為項目數(shù)，每段表示一個項目，項目之間用“|”分隔，每1段的值表示項目-多能工分配結(jié)果。第2層染色體的基因位為所有項目的任務(wù)數(shù)總和，每個基因位的值為多能工編號，表示任務(wù)-多能工分配結(jié)果。第2層染色體的基因值的分配范圍由第1層基因值決定。圖2為染色體編碼結(jié)構(gòu)示例。

圖2 染色體編碼結(jié)構(gòu)示例Figure 2 Example of chromosome coding structure

3.2 創(chuàng)建初始種群

為保證生成的每個染色體都滿足約束條件，本文根據(jù)模型特點，提出了一種啟發(fā)式規(guī)則來生成染色體。

第1階段，將多能工分配至各項目。首先給每個項目分配若干位多能工，保證項目正常運(yùn)轉(zhuǎn)，然后將剩余未分配的多能工根據(jù)多技能水平隨機(jī)分配到各項目中，如圖3所示。

圖3 多能工項目分配Figure 3 Allocation of multi-workers for projeccts

第2階段，給項目中的多能工分配任務(wù)。首先給每個多能工分配1項任務(wù)，使每一位多能工至少負(fù)責(zé)一項任務(wù)；然后將剩余未分配的任務(wù)隨機(jī)分配至具備任務(wù)所需技能的多能工，如圖4所示。

圖4 任務(wù)分配Figure 4 Allocation of multi-workers for tasks

所有分配過程都必須考慮多能工是否具備相關(guān)技能。

3.3 適應(yīng)度值計算

在非支配排序之前根據(jù)數(shù)學(xué)模型中的目標(biāo)函數(shù)計算染色體的適應(yīng)度。目標(biāo)函數(shù)(式(1))的求解過程可視為求解資源約束項目調(diào)度問題RCPSP (resourceconstrained project scheduling problem)，項目由一系列相互關(guān)聯(lián)的任務(wù)組成，調(diào)度決策需要同時滿足項目任務(wù)之間的時序約束和資源約束，以使項目調(diào)度目標(biāo)最優(yōu)。選取蟻群算法去搜尋當(dāng)前分配方案下的最短工期。本文蟻群算法的啟發(fā)項矩陣中的值為多能工在該任務(wù)工作時長的倒數(shù)?(ijk)=信息素矩陣初始化所采用的策略為品質(zhì)因子與任務(wù)數(shù)的比值ρ=Q/activity_num，其中，Q為品質(zhì)因子，初始化時Q=1，表示螞蟻在走完一條路徑后留下的信息素總量，為總?cè)蝿?wù)數(shù)。狀態(tài)轉(zhuǎn)移策略采取輪盤賭策略。決定下一個任務(wù)選取的概率為activity_num η=其中，α 是信息素重要程度因子，β是啟發(fā)函數(shù)重要程度因子。信息素的局部更新式為其中，r ho=0.2，表示信息素的揮發(fā)速度。精英螞蟻策略計算公式為

由于本算法中產(chǎn)生的所有染色體均符合約束條件，不存在不可行解的情況，所以不用對染色體進(jìn)行懲罰，適應(yīng)度函數(shù)即為目標(biāo)函數(shù)的映射。根據(jù)式(1)，通過上述的蟻群算法可計算得出每個項目的最短工期，求出每個染色體的適應(yīng)度值eval1和eval2。

3.4 遺傳操作

采用Deb等[17]提出的非支配排序方法對種群中的個體進(jìn)行分層，并計算同一層染色體間的擁擠距離；采用錦標(biāo)賽選擇法選出父代個體；使用基于項目的兩點雜交法對父代個體進(jìn)行雜交，如圖5所示。

圖5 雜交算子操作示例Figure 5 Example of hybrid operator operation

為保證雜交出的子代染色體中項目信息的完整性，采用交換項目信息來進(jìn)行雜交，但雜交產(chǎn)生的子代染色體仍會出現(xiàn)信息冗余或缺失。

為解決雜交后子代個體的染色體信息不完整問題，本文提出一個子代個體調(diào)整流程，具體步驟如下。

1) 刪除冗余基因。若子代染色體中有基因重復(fù)，則保留“新”基因，刪除“舊”基因，即刪除非雜交區(qū)域的重復(fù)基因[18]。刪除員工-項目的基因時，同時刪除員工負(fù)責(zé)的活動信息。

2) 填補(bǔ)第1層空白信息。刪除冗余基因后，判斷每個項目中的員工是否能夠保證項目順利運(yùn)行，若不能順利運(yùn)行，給該項目分配員工，以最少的員工保證項目運(yùn)行。若每個項目都能運(yùn)行，仍有部分員工未分配，則將該員工隨機(jī)分配到其能工作的項目中。

3) 填補(bǔ)第2層空白信息。根據(jù)填補(bǔ)完成的第1層基因信息將員工隨機(jī)分配到各活動中，分配之前需判斷員工是否具有該活動所需技能。

本文的變異操作先應(yīng)用于染色體的第1層基因，染色體的第2層基因隨第1層的基因變異信息而發(fā)生變異。變異操作根據(jù)變異概率隨機(jī)選取染色體的基因位，然后將基因位對應(yīng)的多能工信息從當(dāng)前項目轉(zhuǎn)移至其他項目。變異后的染色體需進(jìn)行調(diào)整，調(diào)整流程如圖6所示。最后使用精英策略規(guī)則從父代種群和子代種群中挑選出最好的N個染色體進(jìn)行下一代遺傳操作。

圖6 子代個體調(diào)整流程圖Figure 6 Flow chart of offspring individual adjustment

4 算例研究

4.1 數(shù)值算例

某研發(fā)企業(yè)有3個項目需同時進(jìn)行，共需要6種技能來完成項目。每個項目所包含的任務(wù)、任務(wù)所需技能、標(biāo)準(zhǔn)工時、任務(wù)間時序約束分別如表1、圖7～9所示?，F(xiàn)有14位多能工，每位多能工具備不同的技能，且對所掌握技能也有不同的作業(yè)時間系數(shù)，如表2所示。

表2 多能工作業(yè)時間系數(shù)Table 2 Time coefficient of multi-tasking work

圖7 項目1網(wǎng)絡(luò)計劃圖Figure 7 Network plan of project 1

表1 項目信息Table 1 Project information

4.2 參數(shù)設(shè)置及實驗結(jié)果

算法采用Python編程，環(huán)境為Python3.7，編譯器為Spyder，運(yùn)行環(huán)境為2.5 GHz主頻的CPU,Intel Core i5處理器。遺傳算法參數(shù)值如表3所示。為保證解的質(zhì)量，算例運(yùn)算10次，選取最好的結(jié)果。表4列出了算例的非支配解集。表5以解1為例給出了各個項目的具體分配方案，其中，項目下任務(wù)編號順序表示任務(wù)優(yōu)先級，碰到人力資源約束或任務(wù)時序約束時，優(yōu)先級高的任務(wù)優(yōu)先分配和使用人力資源。

表3 遺傳算法參數(shù)Table 3 Parameters of the genetic algorithm

表4 非支配解集Table 4 Non-dominated solution set

表5 解1中的項目調(diào)度方案Table 5 Project scheduling scheme in solution 1

算例中初始種群所有個體及末代種群中帕累托前沿個體的比較如圖10所示。圖11為遺傳算法進(jìn)化過程中每一代種群中最優(yōu)解的均值變化情況。圖12為不同迭代次數(shù)得到的帕累托最優(yōu)解集間的關(guān)系。

圖10 初始種群和末代種群適應(yīng)度對比Figure 10 Comparison of adaptability between initial and last population

圖11 雙目標(biāo)隨迭代次數(shù)的變化趨勢Figure 11 Trend of doublel targets with the number of iterations

圖12 不同迭代次數(shù)的收斂結(jié)果Figure 12 Convergence results of different iteration times

為進(jìn)一步驗證NSGA-II算法的穩(wěn)定性，將算法運(yùn)行10次，產(chǎn)生10個帕累托解集，如表6所示。采用解集覆蓋度C[19]來比較帕累托解集之間的相互支配關(guān)系，解集相互覆蓋度的定義如式(9)所示，其中，a′?a′′表示a′支配a′′。

表6 10次運(yùn)行解集覆蓋度比較結(jié)果Table 6 Comparison results of solution set coverage for 10 runs

圖8 項目2網(wǎng)絡(luò)計劃圖Figure 8 Network plan of project 2

圖9 項目3網(wǎng)絡(luò)計劃圖Figure 9 Network plan of project 3

式中，X1、X2為2個不同的帕累托解集；C(X1,X2)為X1中的解能支配或等于X2解的比例，C(X1,X2)∈[0,1]；C(X1,X2)=1表示X2中的所有解都能在X1中找到支配解或等于該解的解；C(X1,X2)=0則表示X2中的任何解都不會被X1中的解所支配，即X1的解中所有解的質(zhì)量都不會比X2中的任何一個解差。這可以直觀地比較出每一次計算所得解集的優(yōu)劣性，即驗證算法的穩(wěn)定性。

4.3 結(jié)果分析

本文提出的算法能得到一系列帕累托解。在圖10和表4中，無法根據(jù)2個目標(biāo)選出最優(yōu)解，因為它們都是非劣解。決策人員可以根據(jù)自己的訴求來選擇滿足自己需求的解決方案。若他們認(rèn)為員工工作量均衡比項目總工期更重要，可選擇非支配解5；若認(rèn)為項目總工期更重要，可選擇非支配解1。

從圖10可以看出帕累托最優(yōu)解集的適應(yīng)度明顯高于初始種群的適應(yīng)度，這也充分證明本算法的有效性。從圖11可以看出，種群在進(jìn)化過程中2個目標(biāo)值的均值均呈下降趨勢，這說明在求解的過程中最優(yōu)解的質(zhì)量在不斷提高，且解集在迭代60次左右就穩(wěn)定下來。為了驗證迭代100次就能得到很好的解集，本文分別迭代了20次、100次、500次，比較其解集的支配關(guān)系。從圖12可以看出，迭代20次求得帕累托最優(yōu)解的質(zhì)量不如迭代100次的結(jié)果，而迭代500次得到的帕累托最優(yōu)解集雖然比迭代100次的情況多了2個非支配解，但迭代500次并沒有得到更高質(zhì)量的解，這充分說明本文算法具有較好的收斂速度，在迭代100次時解的質(zhì)量就很穩(wěn)定。

從表6可以看出，算法運(yùn)行10次得到的10個非支配解集質(zhì)量很穩(wěn)定。例如，C(1,2)=0表示第2次運(yùn)行生成的解集不被第1次運(yùn)行生成的解集所支配；C(4,3)=0.15則表示第3次生成的解中15%被第4次運(yùn)行生成的解集所支配。而10次運(yùn)行出來的解集僅有C(4,3)不為0，由此說明本文提出的NSGAII算法性能穩(wěn)定。

5 結(jié)論

為解決多項目并行環(huán)境下多技能人力資源多目標(biāo)調(diào)度問題，本文提出了基于NSGA-Ⅱ和蟻群算法的多目標(biāo)優(yōu)化方法，得出如下結(jié)論。

1) 綜合考慮多能工的多技能及其技能熟練水平對任務(wù)作業(yè)時間的影響，建立了以多項目總工期最短和多能工間工作量均衡為目標(biāo)的多目標(biāo)整數(shù)非線性規(guī)劃模型。

2) 提出了系列啟發(fā)式規(guī)則生成初始種群，避免不可行解的產(chǎn)生，提高了算法效率。采用蟻群算法搜尋當(dāng)前分配方案下的最短工期。在進(jìn)行雜交和變異操作時，為了避免陷入局部最優(yōu)，采取“保新刪舊”策略進(jìn)行基因調(diào)節(jié)。

3) 通過數(shù)值算例證明了所提出的多目標(biāo)優(yōu)化方法能夠在可接受時間內(nèi)得到有效、穩(wěn)定的人力資源調(diào)度方案集(pareto解集)供調(diào)度人員決策。

本文研究多能工的技能熟練度水平是固定的，沒有考慮學(xué)習(xí)和遺忘。在未來的研究中，可考慮技能熟練度隨著經(jīng)驗累積或遺忘而變化的異質(zhì)性多能工分配問題。