基于改進(jìn)匈牙利算法的多技能人員調(diào)度方法*

李廷鵬，錢彥嶺，李　岳

(國(guó)防科技大學(xué) 裝備綜合保障技術(shù)重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙　410073)

?

基于改進(jìn)匈牙利算法的多技能人員調(diào)度方法*

李廷鵬，錢彥嶺，李岳

(國(guó)防科技大學(xué) 裝備綜合保障技術(shù)重點(diǎn)實(shí)驗(yàn)室， 湖南 長(zhǎng)沙410073)

摘要：人員的優(yōu)化配置對(duì)于提高裝備制造效率具有重要意義。針對(duì)經(jīng)典匈牙利算法不能解決具有并聯(lián)環(huán)節(jié)的人員指派問(wèn)題的不足，提出利用虛擬工作代替并聯(lián)環(huán)節(jié)，將問(wèn)題轉(zhuǎn)化為典型的指派問(wèn)題；通過(guò)判斷虛擬工作的可實(shí)現(xiàn)性，迭代搜索得到最優(yōu)解。以某多技能人員任務(wù)指派系統(tǒng)為例，詳細(xì)介紹了該優(yōu)化方法的步驟。優(yōu)化結(jié)果很好地驗(yàn)證了改進(jìn)算法的有效性。

關(guān)鍵詞：匈牙利算法；裝備制造；資源調(diào)度；虛擬工作；多技能

隨著人力成本的增加，使用多技能工人已逐漸成為提高人員利用率的重要途徑。針對(duì)具體任務(wù)，如何優(yōu)化人員配置，更加合理地發(fā)揮各個(gè)人員的特長(zhǎng)是人員調(diào)度問(wèn)題的關(guān)鍵所在。指派問(wèn)題是人員調(diào)度問(wèn)題中的經(jīng)典問(wèn)題——m個(gè)人完成n項(xiàng)工作，且每個(gè)人完成每項(xiàng)工作的效率不一樣，確定任務(wù)指派方案使得完成任務(wù)總的效率最高。

解決指派問(wèn)題的方法主要有兩類：一類是確定性解析算法——匈牙利算法；另一類是啟發(fā)式智能算法，比如遺傳算法[1]、模擬退火算法[2]、蟻群算法[3-4]等。啟發(fā)式算法對(duì)于大規(guī)模的指派問(wèn)題具有速度較快的優(yōu)勢(shì)但不能保證能得到最優(yōu)解，而且算法相對(duì)復(fù)雜，在工程實(shí)際中應(yīng)用并不多。匈牙利算法具有步驟簡(jiǎn)單、能得到最優(yōu)解且無(wú)須驗(yàn)證的特點(diǎn)，被廣泛用于解決中小規(guī)模的指派問(wèn)題[5-6]。

文獻(xiàn)[5-6]在剖析匈牙利算法的基礎(chǔ)上，對(duì)匈牙利算法進(jìn)行了改進(jìn)，提出“加邊補(bǔ)零法”用于解決不完全指派問(wèn)題。文獻(xiàn)[7]給出了匈牙利算法MATLAB實(shí)現(xiàn)的通用程序，并用于解決婚配等典型的指派問(wèn)題。文獻(xiàn)[8]提出了差額法解決非標(biāo)準(zhǔn)型指派問(wèn)題，與傳統(tǒng)算法相比，更加簡(jiǎn)潔、直觀。文獻(xiàn)[9]應(yīng)用匈牙利法解決了不正常航班的應(yīng)急調(diào)度問(wèn)題，取得了較好的效果。文獻(xiàn)[10]利用改進(jìn)的匈牙利算法研究了惡劣環(huán)境下多個(gè)維修活動(dòng)的調(diào)度問(wèn)題。文獻(xiàn)[11]應(yīng)用進(jìn)化匈牙利算法解決無(wú)人機(jī)目標(biāo)分配問(wèn)題。文獻(xiàn)[12]提出將匈牙利算法與拓?fù)浼s束相結(jié)合進(jìn)行高密度條件下的細(xì)胞追蹤研究。文獻(xiàn)[13]為了提高云計(jì)算任務(wù)的分配效率，在標(biāo)準(zhǔn)匈牙利算法的基礎(chǔ)上提出一種快速降階優(yōu)化算法，該算法通過(guò)不斷排除代價(jià)矩陣中已經(jīng)確定的元素，快速降低矩陣的階次，提高了匈牙利算法的計(jì)算效率。文獻(xiàn)[14]將火力分配問(wèn)題轉(zhuǎn)換為指派問(wèn)題，利用匈牙利法對(duì)武器-目標(biāo)動(dòng)態(tài)火力配置進(jìn)行了研究。

雖然匈牙利算法已經(jīng)在實(shí)際中得到了較大的應(yīng)用，并取得了較好的效果。但是傳統(tǒng)的匈牙利算法只能針對(duì)“總代價(jià)為各個(gè)任務(wù)代價(jià)之和”一類問(wèn)題進(jìn)行求解，而在實(shí)際工程中，許多情況并不滿足這個(gè)條件。因此，需要對(duì)算法進(jìn)行改進(jìn)，以便其能更好地解決實(shí)際問(wèn)題。

1經(jīng)典匈牙利算法及應(yīng)用上的不足

1.1經(jīng)典匈牙利算法

經(jīng)典匈牙利算法是Kuhn利用匈牙利數(shù)學(xué)家Koning關(guān)于矩陣中獨(dú)立零元素定理提出的用于解決指派問(wèn)題的優(yōu)化方法[10]。該方法的理論基礎(chǔ)是：在效益矩陣(也稱代價(jià)矩陣)的任意行或列加上或者減去一個(gè)常數(shù)不會(huì)改變最優(yōu)分配方案[15]。其基本思想是通過(guò)每行或每列加減同一個(gè)常數(shù)來(lái)修改效益矩陣，直到效益矩陣不同行不同列至少有一個(gè)零元素，且零元素就對(duì)應(yīng)了一個(gè)總效益最小的最優(yōu)分配方案。

經(jīng)典匈牙利算法的基本步驟如下：

步驟1：建立資源分配問(wèn)題的效益矩陣M0(m×n)。

步驟2：從效益矩陣M0每行減去該行最小的元素，使得每行都有一個(gè)零元素，得到M1。

步驟3：從M1每列減去該列最小的元素，使得每列都有一個(gè)零元素，得到M2。

步驟4：用最少的直線覆蓋M2中的零元素得到M3，如果最少直線的數(shù)量等于m，轉(zhuǎn)入步驟6，否則轉(zhuǎn)入步驟5。

步驟5：矩陣M3中所有未被直線覆蓋的元素減去未被覆蓋元素中最小的元素，同時(shí)在直線相交點(diǎn)加上該最小元素得到M4，令M2=M4，轉(zhuǎn)步驟4。

步驟6：從零元素最少的行或列開(kāi)始指派，直到所有任務(wù)都指派完畢，得到最優(yōu)指派方案P。

上述步驟中，假定的是m=n，即效益矩陣M0是一個(gè)方陣。但在實(shí)際問(wèn)題中，任務(wù)數(shù)與人數(shù)不一定完全相等。針對(duì)任務(wù)數(shù)與人數(shù)不相等的情況，一般的處理方式是增加虛擬人或虛擬任務(wù)，即對(duì)效益矩陣進(jìn)行加零補(bǔ)邊處理，然后再按照上述步驟進(jìn)行任務(wù)指派，具體方法參考文獻(xiàn)[5]。

1.2應(yīng)用中的不足

經(jīng)典匈牙利算法自提出以來(lái)就受到了廣泛的關(guān)注，也解決了不少的工程實(shí)際問(wèn)題。但傳統(tǒng)的匈牙利算法只能針對(duì)總效益為各個(gè)任務(wù)效益之和的情況進(jìn)行任務(wù)指派。假設(shè)效益是用各個(gè)任務(wù)的時(shí)間表示，那么傳統(tǒng)的匈牙利算法只能對(duì)串聯(lián)工作進(jìn)行任務(wù)指派，即總時(shí)間為各個(gè)任務(wù)時(shí)間之和。但在工程實(shí)際中，特別是裝備制造系統(tǒng)中，串并聯(lián)同時(shí)存在是很常見(jiàn)的情況，比如：有4項(xiàng)工作需要完成，工作的先后順序如圖1所示。4個(gè)工人完成各項(xiàng)工作的時(shí)間已知，且每個(gè)工人只能完成一項(xiàng)工作，問(wèn)題是如何安排4個(gè)工人的工作任務(wù)使總時(shí)間最少。

分析該問(wèn)題可以發(fā)現(xiàn)，傳統(tǒng)的匈牙利算法已經(jīng)不能直接拿來(lái)解決此問(wèn)題，因?yàn)楣ぷ?和工作3需要耗費(fèi)較長(zhǎng)的時(shí)間才會(huì)對(duì)總時(shí)間產(chǎn)生影響，即各個(gè)工作加工時(shí)間對(duì)總時(shí)間的貢獻(xiàn)并不處于平等的地位。為了解決此類問(wèn)題(串并聯(lián)并存)，提出了改進(jìn)的匈牙利算法。

2改進(jìn)匈牙利算法

2.1算法改進(jìn)的基本思路

由前面的分析可知，傳統(tǒng)的匈牙利算法之所以不能解決與1.2類似的問(wèn)題，主要是因?yàn)椴⒙?lián)部分的工作總時(shí)間并不是各項(xiàng)工作的時(shí)間之和，而是由其中的最大值決定。所提出的解決思路是將串并聯(lián)系統(tǒng)分成兩個(gè)部分——串聯(lián)部分和并聯(lián)部分(可能有多個(gè))，分別用虛擬工作代替各并聯(lián)部分的所有工作，使得整個(gè)系統(tǒng)變成純串聯(lián)系統(tǒng)。在此基礎(chǔ)上利用傳統(tǒng)的匈牙利算法進(jìn)行任務(wù)指派，然后再判斷指派方案中的虛擬工作能否按照預(yù)定的最小時(shí)間轉(zhuǎn)換為并聯(lián)工作實(shí)現(xiàn)，如果可以則得到了最優(yōu)分配方案并結(jié)束，否則增加虛擬工作對(duì)應(yīng)的時(shí)間，甚至重新分配。

2.2改進(jìn)匈牙利算法詳細(xì)步驟

基于以上思路，針對(duì)串并聯(lián)并存的任務(wù)指派問(wèn)題，改進(jìn)匈牙利算法的流程圖如圖2所示。

圖2　改進(jìn)匈牙利算法流程圖Fig.2　Flow-chart of the improved Hungary algorithm

算法的詳細(xì)步驟如下：

步驟1：將系統(tǒng)分為串聯(lián)部分和并聯(lián)部分(如果有多個(gè)并聯(lián)環(huán)節(jié)則每個(gè)并聯(lián)環(huán)節(jié)獨(dú)立為一部分)，即：

S=C+Bi,i=1,2,…,n

(1)

式中，S代表整個(gè)系統(tǒng)，C代表所有串聯(lián)的工作，Bi代表并聯(lián)環(huán)節(jié)i，n為并聯(lián)環(huán)節(jié)的個(gè)數(shù)。

步驟2：利用虛擬工作Jvi代替并聯(lián)部分i的工作，同時(shí)初始化虛擬工作的各個(gè)人員完成時(shí)間。

(2)

式中，Tvij表示人員j完成虛擬工作i需要的時(shí)間。

虛擬工作Jvi的初始值設(shè)定為各個(gè)人員完成虛擬工作i的理論最小時(shí)間Tij_min。

理論最小時(shí)間Tij_min指的是在人員j參與并聯(lián)環(huán)節(jié)i的某項(xiàng)工作的前提下，并聯(lián)工作可能完成的最小時(shí)間，即：

Tij_min=min(Tij_1,Tij_2,…,Tij_k)

(3)

式中，Tij_p(p=1,2,…,k)表示人員j完成并聯(lián)環(huán)節(jié)i中的第p項(xiàng)工作需要的時(shí)間。

那么，初始虛擬工作為：

(4)

步驟3：利用原系統(tǒng)中的串聯(lián)工作和虛擬工作Jv構(gòu)建新的純串聯(lián)系統(tǒng)。

步驟4：利用傳統(tǒng)的匈牙利算法對(duì)S_new進(jìn)行任務(wù)指派，得到分配方案P。

步驟5：判斷分配方案P中所有虛擬工作Jv是否可實(shí)現(xiàn)，如果可以轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟6。

虛擬工作Jvi可實(shí)現(xiàn)是指可以由方案P中的被指派到虛擬工作Jvi的人員以及空閑人員在虛擬工作規(guī)定的時(shí)間內(nèi)完成并聯(lián)環(huán)節(jié)i的工作。

由于每人只能完成一項(xiàng)工作，因此，虛擬工作的可實(shí)現(xiàn)方案不能相互沖突，否則認(rèn)為Jv不可實(shí)現(xiàn)。

步驟6：如果方案P中虛擬工作Jvi可實(shí)現(xiàn)最小時(shí)間小于虛擬工作i對(duì)應(yīng)的時(shí)間Tviq，即：

Tviq>min(TBi)

(5)

其中TBi表示并聯(lián)環(huán)節(jié)i在方案P中被指派到虛擬工作Jvi的人員參與下的所有可實(shí)現(xiàn)的完成時(shí)間。

那么，Tviq增加一個(gè)單位。即：

Tviq=Tviq+1

(6)

步驟7：如果方案P中虛擬工作Jvi可實(shí)現(xiàn)最小時(shí)間大于虛擬工作對(duì)應(yīng)的時(shí)間Tviq，

Tviq

(7)

則Tviq減少一個(gè)單位，然后轉(zhuǎn)步驟3。即：

Tviq=Tviq-1

(8)

將虛擬工作對(duì)應(yīng)時(shí)間減少稱之為過(guò)優(yōu)回退原則，設(shè)置過(guò)優(yōu)回退原則的目的是為了避免遺漏最優(yōu)解。

步驟8：用可實(shí)現(xiàn)的并聯(lián)工作方案代替分配方案P中的虛擬工作，得到最終的最優(yōu)分配方案P*，優(yōu)化結(jié)束。

3實(shí)例驗(yàn)證

為了更詳細(xì)地介紹所提出的改進(jìn)匈牙利算法的步驟，驗(yàn)證算法的有效性，并給出了一個(gè)多技能人員任務(wù)指派系統(tǒng)的實(shí)例。

3.1問(wèn)題描述

某多技能人員任務(wù)指派系統(tǒng)任務(wù)流程如圖3所示，共有9項(xiàng)工作，其中有兩個(gè)并聯(lián)環(huán)節(jié)，分別記P1(J3，J4，J5)和P2(J7，J8)。該系統(tǒng)總的任務(wù)時(shí)間為Tall：

Tall=T1+T2+max(T3,T4,T5)+T6+max(T7,T8)+T9

(9)

其中Ti(i=1,2,…,9)代表各個(gè)工作需要的時(shí)間。

圖3　某裝備系統(tǒng)制造流程圖Fig.3　Manufacturing flow-chart of the equipment

現(xiàn)有9名工人，并已知每名工人完成各個(gè)工作需要的時(shí)間，見(jiàn)表1。

表1　工人完成各項(xiàng)工作需要的時(shí)間

表中，Ri(i=1,2，…，9)分別代表9名工人，Ji(i=1,2，…，9)分別代表9項(xiàng)工作，時(shí)間單位為min。要求每名工人有且完成一項(xiàng)工作，尋找最優(yōu)的任務(wù)分配方案。

3.2多技能人員任務(wù)調(diào)配

1) 確定并聯(lián)環(huán)節(jié)，同時(shí)計(jì)算并聯(lián)環(huán)節(jié)虛擬工作的各個(gè)人員最小完成時(shí)間。

分析圖3可知，該系統(tǒng)共有兩個(gè)并聯(lián)環(huán)節(jié)，分別是P1(J3，J4，J5)和P2(J7，J8)。利用虛擬工作1(Jv1)和虛擬工作2(Jv2)代替并聯(lián)環(huán)節(jié)，得到新的系統(tǒng)，如圖4所示。

圖4　替換后系統(tǒng)的流程圖Fig.4　Flow-chart of the replaced system

其中，

(10)

其中Tvi_j(i=1,2;j=1,2,…,9)表示工人j完成虛擬工作i需要的時(shí)間。

為了提升算法速度，首先計(jì)算出虛擬工作各個(gè)工人完成的最小虛擬時(shí)間，得到最小時(shí)間虛擬工作Jv1_min和Jv2_min。

(11)

2) 利用最小時(shí)間虛擬工作(Jv1_min，Jv2_min)以及串聯(lián)部分的工作(J1,J2,J6,J9)構(gòu)建效益矩陣M0:

(12)

3) 按照傳統(tǒng)的匈牙利算法得到M0的最優(yōu)分配方案。

由于M0并不是一個(gè)方陣，按照文獻(xiàn)[2]“加零補(bǔ)邊法”的步驟，可以得到M0對(duì)應(yīng)的最優(yōu)分配方案。

(13)

最優(yōu)方案如表2所示,方案對(duì)應(yīng)的時(shí)間為125 min。

表2　M0對(duì)應(yīng)的最優(yōu)分配方案

4) 判斷M0對(duì)應(yīng)的最優(yōu)分配方案中，并聯(lián)環(huán)節(jié)能否實(shí)現(xiàn)。

從表2中可以看到，M0對(duì)應(yīng)的最優(yōu)方案要求R8與R1，R2，R3中的任意兩個(gè)在32 min內(nèi)完成并聯(lián)環(huán)節(jié)P1的工作(J3, J4, J5)。同時(shí)要求R7與R1，R2，R3剩下的那個(gè)在12 min內(nèi)完成并聯(lián)環(huán)節(jié)P2的工作(J7, J8)。

簡(jiǎn)單分析就可以發(fā)現(xiàn)，R8與R1，R2，R3中任意兩個(gè)完成并聯(lián)環(huán)節(jié)P1最小花費(fèi)時(shí)間為43 min。且R7與R1，R2，R3中任意一個(gè)完成并聯(lián)環(huán)節(jié)P2最小花費(fèi)時(shí)間為25 min。因此M0對(duì)應(yīng)的最優(yōu)方案中的虛擬工作不能轉(zhuǎn)化為可實(shí)現(xiàn)的并聯(lián)環(huán)節(jié)，也就是說(shuō)此時(shí)的最優(yōu)方案不可實(shí)現(xiàn)。

根據(jù)改進(jìn)的匈牙利算法的步驟，需要將兩個(gè)虛擬工作對(duì)應(yīng)的時(shí)間(M0的最優(yōu)方案中虛擬工作Jv1和Jv2對(duì)應(yīng)的時(shí)間，即Tv1_8,Tv2_7)提高一個(gè)單位，即Tv1_8：32→33，Tv2_7：12→13，得到新的虛擬工作。

(14)

利用Jv1，Jv2以及J1，J2，J6，J9構(gòu)建效益矩陣M1，返回3)繼續(xù)搜索直到得到可行最優(yōu)解。

3.3優(yōu)化結(jié)果及分析

利用MATLAB 2008a在主頻為3.4 GHz的Window XP平臺(tái)上編程實(shí)現(xiàn)，經(jīng)過(guò)87次迭代，最終得到了最優(yōu)調(diào)配方案見(jiàn)表3，總的時(shí)間為147 min，且此時(shí)迭代的虛擬工作為：

(15)

利用可實(shí)現(xiàn)并聯(lián)環(huán)節(jié)替代表3中的虛擬工作，得到完整最優(yōu)分配方案見(jiàn)表4。

表4　完整最優(yōu)分配方案

為了驗(yàn)證本算法得到的最優(yōu)解是否為全局最優(yōu)，本文在相同的平臺(tái)上通過(guò)MATLAB編程遍歷了所有可能的方案(共362 880個(gè))，找到最優(yōu)的分配方案見(jiàn)表5。

表5　遍歷結(jié)果中的最優(yōu)方案

對(duì)比表4和表5，可以發(fā)現(xiàn)，本文改進(jìn)的算法的確得到了全局最優(yōu)解。

4結(jié)論

針對(duì)傳統(tǒng)的匈牙利算法不能用于解決具有并聯(lián)環(huán)節(jié)的資源調(diào)配問(wèn)題，提出利用等價(jià)虛擬工序代替并聯(lián)環(huán)節(jié)的方式，將問(wèn)題轉(zhuǎn)化為常規(guī)指派問(wèn)題，通過(guò)判斷等價(jià)虛擬工序能否在并聯(lián)環(huán)節(jié)中實(shí)現(xiàn)，逐步提高虛擬工作對(duì)應(yīng)點(diǎn)的時(shí)間，以反復(fù)迭代的方式搜索可實(shí)現(xiàn)方案，同時(shí)為了避免漏掉最優(yōu)解，提出了過(guò)優(yōu)回退原則。最后的實(shí)例驗(yàn)證了該算法的有效性，拓展了匈牙利算法的應(yīng)用范圍。

參考文獻(xiàn)(References)

[1]陶世群， 蒲保興． 基于遺傳算法的多級(jí)目標(biāo)非平衡指派問(wèn)題求解[J]．系統(tǒng)工程理論與實(shí)踐， 2004， 24(8)： 80-86.TAO Shiqun, PU Baoxing. Solving multi-object and unbalanced assignment problem based on genetic algorithm[J].System Engineering-Theory & Practice, 2004, 24(8): 80-86.(in Chinese)

[2]李冰， 徐杰， 杜文． 用模擬退火算法求解有順序約束指派問(wèn)題[J]．系統(tǒng)工程理論方法應(yīng)用，2002，11(4)：330-335.

LI Bing, XU Jie, DU Wen. A simulated annealing algorithm for an assignment problem with precedence relation among the elements[J]. Systems Engineering—Theory Methodology Applications, 2002, 11(4): 330-335. (in Chinese)

[3]殷人昆， 吳陽(yáng)， 張晶煒． 蟻群算法解決指派問(wèn)題的研究和應(yīng)用[J]．計(jì)算機(jī)工程與科學(xué)， 2008， 30(4)： 43-45.

YIN Renkun,WU Yang, ZHANG Jingwei. Research and application of the ant colony algorithm in the assignment problem[J]. Computer Engineering & Science, 2008, 30(4): 43-45. (in Chinese)

[4]梁耀， 覃征， 楊利英， 等． 指派問(wèn)題的變異蟻群算法求解[J]．微電子學(xué)與計(jì)算機(jī)， 2005， 22(6)： 80-83.

LIANG Yao, QIN Zheng,YANG Liying, et al. Mutated ant colony algorithm for assignment problem[J]. Microelectronics & Computer, 2005, 22(6): 80-83. (in Chinese)

[5]陳元明．匈牙利算法的注記[J]．麗水學(xué)院學(xué)報(bào)， 2011， 33(5)： 78-81.

CHEN Yuanming. A note on Hungary algorithm [J]. Journal of Lishui University, 2011, 33(5): 78-81. (in Chinese)

[6]杜金玲， 周杰． 關(guān)于幾種不平衡指派問(wèn)題的修正匈牙利解法[J]．價(jià)值工程， 2010， 2010(13)： 120-122.

DU Jinling, ZHOU Jie. Fixed Hungary algorithm to unbalanced assignment problems [J]. Value Engineering, 2010, 2010(3): 120-122. (in Chinese)

[7]常庭懋， 韓中庚．用“匈牙利算法”求解一類最優(yōu)化問(wèn)題[J]．信息工程大學(xué)學(xué)報(bào)， 2004， 5(1)： 60-62.CHANG Tingmao, HAN Zhonggeng. Solution to a class optimization problem by utilizing the “hungary calculate way” [J]. Journal of Information Engineering University, 2004, 5(1): 60-62. (in Chinese)

[8]馬曉娜．“人少任務(wù)多”型指派問(wèn)題的一種新算法術(shù)[J]．重慶工商大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2014， 31(12)： 68-71.

MA Xiaona. A new algorithm for assignment problems with“tasks more than the number of persons” [J]. Journal of Chongqing Technology and Business(Natural Sciences Edition), 2014， 31(12)： 68-71. (in Chinese)

[9]趙萬(wàn)林．不正常航班應(yīng)急調(diào)度的模型與算法[D]．天津:中國(guó)民航大學(xué)， 2014.

ZHAO Wanlin. Model and algorithm for the irregular flight emergency scheduling[D]. Tianjin:Civil Aviation University of China, 2014. (in Chinese)

[10]仇勇．惡化環(huán)境下帶多個(gè)維修活動(dòng)的調(diào)度算法研究[D]．杭州:浙江工商大學(xué)， 2013.

QIU Yong. Study on scheduling algorithm with deteriorating jobs and multiple maintenance activity [D]. Hangzhou:Zhejiang Gongshang University, 2013. (in Chinese)

[11]谷穩(wěn)．基于進(jìn)化匈牙利算法的目標(biāo)分配問(wèn)題研究及應(yīng)用[D]．西安:西安電子科技大學(xué)， 2013.

GU Wen. A study and application of target allocation based on evolution Hungary algorithm [D]. Xi′an:XiDian University, 2013. (in Chinese)

[12]董莎莎．基于拓?fù)浼s束和匈牙利算法的高密度細(xì)胞追蹤方法[D]．哈爾濱:哈爾濱工程大學(xué)， 2011.

DONG Shasha. The method of high density cells′tracking based on Topological constraint combined with Hungarian algorithm [D]. Harbin: Harbin Engineering University, 2011. (in Chinese)

[13]何富江, 任金霞． 快速降階匈牙利算法的云計(jì)算任務(wù)分配模型[J]．江西理工大學(xué)學(xué)報(bào)， 2014， 35(3)： 63-67.

HE Fujiang,REN Jinxia. Task assignment model in cloud computing based on Hungary algorithm of faster reduced order[J]. Journal of Jiangxi University of Science and Technology, 2014, 35(3): 63-67. (in Chinese)

[14]李建立．武器-目標(biāo)動(dòng)態(tài)火力分配及戰(zhàn)效評(píng)估的研究[D]．南昌:南昌航空大學(xué)， 2014.

LI Jianli.Research on weapon-target dynamic assignment and effectiveness evaluation[D]. Nanchang :Nanchang Hangkong University, 2014. (in Chinese)

[15]宋雨晴．指派問(wèn)題的改進(jìn)算法[J]．科技視界， 2012(14)： 106-108.

SONG Yuqing. The improved algorithm for assignment problem [J].Science & Technology Vision, 2012(14)： 106-108. (in Chinese)

doi:10.11887/j.cn.201602024

*收稿日期：2015-05-06

基金項(xiàng)目：部委級(jí)重點(diǎn)預(yù)研基金資助項(xiàng)目(9140C710301150C71001)

作者簡(jiǎn)介：李廷鵬(1987—)，男，重慶人，博士研究生，E-mail:tovey1987@126.com; 李岳(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail:liyue@nudt.edu.cn

中圖分類號(hào)：TN95

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-2486(2016)02-144-06

Multi-skilled labor allocating method based on improved Hungary algorithm

LI Tingpeng, QIAN Yanling, LI Yue

(Science and Technology on Integrated Logistics Support Laboratory, National University of Defense Technology, Changsha 410073, China)

Abstract：The optimal allocation of labor is of great significance to improve the efficiency of equipment manufacturing. For the shortcoming of traditional Hungary algorithm could not solve the resource scheduling problem with parallel links, an improved Hungary algorithm was proposed. The improved algorithm converted the problem into a typical assignment problem by replacing parallel link jobs with virtual jobs, and optimized it with classical Hungary algorithm and determined the realizability of the virtual jobs based on the results. Finally, the optimal scheme was obtained through iterative searching. In addition, an example of multi-skilled labor allocation system is introduced to verify the effectiveness of the proposed algorithm.

Key words：Hungary algorithm; equipment manufacturing; resource scheduling; virtual jobs; multi-skill

http://journal.nudt.edu.cn