基于改進匈牙利算法的多技能人員調度方法*

李廷鵬，錢彥嶺，李　岳

(國防科技大學 裝備綜合保障技術重點實驗室， 湖南 長沙　410073)

?

基于改進匈牙利算法的多技能人員調度方法*

李廷鵬，錢彥嶺，李岳

(國防科技大學 裝備綜合保障技術重點實驗室， 湖南 長沙410073)

摘要：人員的優化配置對于提高裝備制造效率具有重要意義。針對經典匈牙利算法不能解決具有并聯環節的人員指派問題的不足，提出利用虛擬工作代替并聯環節，將問題轉化為典型的指派問題；通過判斷虛擬工作的可實現性，迭代搜索得到最優解。以某多技能人員任務指派系統為例，詳細介紹了該優化方法的步驟。優化結果很好地驗證了改進算法的有效性。

關鍵詞：匈牙利算法；裝備制造；資源調度；虛擬工作；多技能

隨著人力成本的增加，使用多技能工人已逐漸成為提高人員利用率的重要途徑。針對具體任務，如何優化人員配置，更加合理地發揮各個人員的特長是人員調度問題的關鍵所在。指派問題是人員調度問題中的經典問題——m個人完成n項工作，且每個人完成每項工作的效率不一樣，確定任務指派方案使得完成任務總的效率最高。

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