國防科學技術大學排名范文(通用2篇)

時間：2020-12-19 思想宣傳點擊：

《大學》是一篇論述儒家修身齊家治國平天下思想的散文，原是《小戴禮記》第四十二篇，相傳為春秋戰國時期曾子所作，實為秦漢時儒家作品，是一部中國古代討論教育理論的重要著作。經北宋程顥、程頤竭力尊崇，南宋朱熹又作《大學章句》，最終和《中庸》《論語》《，以下是為大家整理的關于國防科學技術大學排名2篇 , 供大家參考選擇。

國防科學技術大學排名2篇

第1篇: 國防科學技術大學排名

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

李廷鵬，錢彥嶺，李岳

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

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

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

中圖分類號：TN95 文獻標志碼：A　　　文章編號：

Mulit-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 shortage of traditional Hungary algorithm that can"t solve the resource scheduling problem which contains parallel jobs, an improved Hungary algorithm is proposed in this paper. The improved algorithm converts the problem to a typical assignment problem by replacing parallel link jobs with virtual job. And then, optimizing it with classical Hungary algorithm and determining the realizability of the virtual job based on the results. Finally, the optimal scheme will be got through iterative searching. In addition, an example of mulit-skilled labor allocation system is introduced to verify the effectiveness of the proposed algorithm.

Keywords: Hungary algorithm, Equipment manufacturing, Resource Scheduling, Virtual job，Multi-Skill

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

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

文獻[5, 6]在剖析匈牙利算法的基礎上，對匈牙利算法進行了改進，提出“加邊補零法”用于解決不完全指派問題。文獻[7]給出了匈牙利算法MATLAB實現的通用程序，并用于解決婚配等典型的指派問題。文獻[8]提出了差額法解決非標準型指派問題，與傳統算法相比，更加簡潔、直觀。文獻[9]應用匈牙利法解決了不正常航班的應急調度問題，取得了較好的效果。文獻[10]利用改進的匈牙利算法研究了惡劣環境下多個維修活動的調度問題。文獻[11]應用進化匈牙利算法解決無人機目標分配問題。文獻[12]提出將匈牙利算法與拓撲約束相結合進行高密度條件下的細胞追蹤研究。文獻[13]為了提高云計算任務的分配效率，在標準匈牙利算法的基礎上提出一種快速降階優化算法，該算法通過不斷排除代價矩陣中已經確定的元素，快速降低矩陣的階次，提高了匈牙利算法的計算效率。文獻[14]將火力分配問題轉換為指派問題，利用匈牙利法對武器-目標動態火力配置進行了研究。

雖然匈牙利算法已經在實際中得到了較大的應用，并取得了較好的效果。但是傳統的匈牙利算法只能針對“總代價為各個任務代價之和”一類問題進行求解，而在實際工程中，許多情況并不滿足這個條件。因此，需要對算法進行改進，以便其能更好的解決實際問題。

1經典匈牙利算法及應用上的不足1.1經典匈牙利算法

經典匈牙利算法是W.W.Kuhn利用匈牙利數學家D.Koning關于矩陣中獨立零元素定理提出的用于解決指派問題的優化方法[10]。該方法的理論基礎是：在效益矩陣（也稱代價矩陣）的任意行或列加上或者減去一個常數不會改變最優分配方案[15]。其基本思想是通過每行或每列加減同一個常數來修改效益矩陣，直到效益矩陣不同行不同列至少有一個零元素，且零元素就對應了一個總效益最小的最優分配方案。

經典匈牙利算法的基本步驟如下：

步驟1，建立資源分配問題的效益矩陣M0（m×n）。

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

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

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

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

步驟6，從零元素最少的行或列開始指派，直到所有任務都指派完畢，得到最優指派方案P。

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

1.2應用中的不足

經典匈牙利算法自提出以來就受到了廣泛的關注，也解決了不少的工程實際問題。但傳統的匈牙利算法只能針對總效益為各個任務效益之和的情況進行任務指派。假設效益是用各個任務的時間表示，那么傳統的匈牙利算法只能對串聯工作進行任務指派，即總時間為各個任務時間之和。但在工程實際中，特別是裝備制造系統中，串并聯同時存在是很常見的情況，比如：

問題1：有4項工作需要完成，工作的先后順序如圖1所示。4個工人完成各項工作的時間已知，且每個工人只能完成一項工作，問題是如何安排4個工人的工作任務使總時間最少。

圖1串并聯任務示例

Fig. 1 Example of Serial-Parallel sytem

分析該問題可以發現，傳統的匈牙利算法已經不能直接拿來解決此問題，因為工作2和工作3較大的時間才會對總時間產生影響，即各個工作加工時間對總時間的貢獻并不處于平等的地位。為了能夠解決此類問題（串并聯并存），本文提出了改進的匈牙利算法。

2改進匈牙利算法2.1算法改進的基本思路

由前面的分析可知，傳統的匈牙利算法之所以不能解決類似問題1的問題，主要是因為并聯部分的工作總時間并不是各項工作的時間之和，而是由其中的最大值決定。本文提出的解決思路是將串并聯系統分成兩個部分——串聯部分和并聯部分（可能有多個），分別用虛擬工作代替各并聯部分的所有工作，使得整個系統變成純串聯系統。在此基礎上利用傳統的匈牙利算法進行任務指派，然后再判斷指派方案中的虛擬工作是否能夠按照預定的最小時間轉換為并聯工作實現，如果可以則得到了最優分配方案并結束，否則增加虛擬工作對應的時間，重新分配。

2.2改進匈牙利算法詳細步驟

基于以上思路，針對串并聯并存的任務指派問題，改進匈牙利算法的流程圖如圖2。

圖2改進匈牙利算法流程圖

Fig.2 flow-chart of the improved Hungary algorithm

算法的詳細步驟如下：

步驟1，將系統分為串聯部分和并聯部分（如果有多個并聯環節則每個并聯環節獨立為一部分），即：

(1)

式中，S代表整個系統，C代表所有串聯的工作，Bi代表并聯環節i，n為并聯環節的個數。

步驟2，利用虛擬工作Jvi代替并聯部分i的工作，同時初始化虛擬工作的各個人員完成時間。

(2)

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

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

理論最小時間Tij_min指的是在人員j參與并聯環節i的某項工作的前提下，并聯工作可能完成的最小時間，即：

(3)

式中，Tij_p (p=1,2,…,k)表示人員j完成并聯環節i中的第p項工作需要的時間。

那么，初始虛擬工作為：

(4)

步驟3，利用原系統中的串聯工作和虛擬工作Jv構建新的純串聯系統。

步驟4，利用傳統的匈牙利算法對S_new進行任務指派，得到分配方案P。

步驟5，判斷分配方案P中所有虛擬工作Jv是否可實現，如果可以轉步驟8，否則轉步驟6。

虛擬工作Jvi可實現是指可以由方案P中的被指派到虛擬工作Jvi的人員以及空閑人員在虛擬工作規定的時間內完成并聯環節i的工作。

由于每人只能完成一項工作，因此，虛擬工作的可實現方案不能相互沖突，否則認為Jv不可實現。

步驟6，如果方案P中虛擬工作Jvi可實現最小時間小于虛擬工作i對應的時間Tviq，即：

(5)

其中TBi表示并聯環節i在方案P中被指派到虛擬工作Jvi的人員參與下的所有可實現的完成時間。

那么，Tviq增加一個單位。即：

(6)

步驟7，如果方案P中虛擬工作Jvi可實現最小時間大于虛擬工作對應的時間Tviq，

(7)

則Tviq減少一個單位，然后轉步驟3。即：

(8)

本文將虛擬工作對應時間減少稱之為過優回退原則，設置過優回退原則的目的是為了避免遺漏最優解。

步驟8，用可實現的并聯工作方案代替分配方案P中的虛擬工作，得到最終的最優分配方案P*，優化結束。

3實例驗證

為了更詳細的介紹本文提出的改進匈牙利算法的步驟，并驗證算法的有效性，本文給出了一個多技能人員任務指派系統的實例。

3.1問題描述

某多技能人員任務指派系統任務流程如圖3所示，共有9項工作，其中有兩個并聯環節，分別記P1(J3、J4、J5)和P2(J7，J8)。該系統總的任務時間為Tall：

(9)

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

圖3某裝備系統制造流程圖

Fig. 3 the manufacturing flow-chart of the equipment

現有9名工人，并已知每名工人完成各個工作需要的時間，如表1。

表1工人完成各項工作需要的時間

Tab.1 the finish time of each worker

表中，Ri(i=1,2……9)分別代表9名工人，Ji(i=1,2……9)分別代表9項工作，時間單位為分鐘。要求每名工人有且完成一項工作，尋找最優的任務分配方案。

3.2基于改進匈牙利算法的任務分配

（1）確定并聯環節，同時計算并聯環節虛擬工作的各個人員最小完成時間。

分析圖3可知，該系統共有兩個并聯環節，分別是P1(J3、J4、J5)和P2(J7、J8)。利用虛擬工作1(Jv1)和虛擬工作2(Jv2)代替并聯環節，得到新的系統，如圖4.

圖4 替換后系統的流程圖

Fig.4 the flow-chart of the replaced system

其中，

(10)

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

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

(11)

（2）利用最小時間虛擬工作（Jv1_min，Jv2_min）以及串聯部分的工作（J1,J2,J6,J9,）構建效益矩陣M0:

(12)

（3）按照傳統的匈牙利算法得到M0的最優分配方案。

由于M0并不是一個方陣，按照文獻[2]“加零補邊”法的步驟，可以得到M0對應的最優分配方案。

(13)

最優方案如表2所示,方案對應的時間為125分鐘。

表2 M0對應的最優分配方案

Tab. 2 the optimal assignment plan of M0

（4）判斷M0對應的最優分配方案中，并聯環節能否實現。

從表2中可以看到，M0對應的最優方案要求R8與R1，R2，R3中的兩個在32分鐘完成并聯環節P1的工作（J3, J4, J5）。同時要求R7與R1，R2，R3剩下的那個在12分鐘內完成并聯環節P2的工作（J7, J8）。

簡單分析就可以發現，R8與R1，R2，R3中任意兩個完成并聯環節P1最小花費時間為43分鐘。且R7與R1，R2，R3中任意一個完成并聯環節P2最小花費時間為25分鐘。因此M0對應的最優方案中的虛擬工作不能轉化為可實現的并聯環節，也就是說此時的最優方案不可實現。

根據改進的匈牙利算法的步驟，需要將兩個虛擬工作對應的時間（M0的最優方案中虛擬工作Jv1和Jv2對應的時間，即Tv1_8,Tv2_7）提高一個單位，即Tv1_8：32→33，Tv2_7：12→13，得到新的虛擬工作。

(14)

利用Jv1，Jv2以及J1，J2，J6，J9構建效益矩陣M1，返回（3）繼續搜索直到得到可行最優解。

3.3優化結果及分析

利用MATLAB 2008a在主頻為3.4GHz的window Xp平臺上編程實現，經過87次迭代，最終得到了最優調配方案如表3，總的時間為147分鐘，且此時迭代的虛擬工作為：

(15)

表3最終的最優配置方案

Tab.3 the final optimal assignment plan

利用可實現并聯環節替代表3中的虛擬工作，得到完整最優分配方案如表4。

表4完整最優分配方案

Tab. 4 the complete optimal assignment plan

為了驗證本算法得到的最優解是否為全局最優，本文在相同的平臺上通過MATLAB編程遍歷了所有可能的方案（共362880個），找到最優的分配方案如表5。

表5遍歷結果中的最優方案

Tab.5 the optimal assignments of all possible plans

對比表4和表5，可以發現，本文改進的算法的確得到了全局最優解。

4結論

針對傳統的匈牙利算法不能用于解決具有并聯環節的資源調配問題，本文提出利用等價虛擬工序代替并聯環節的方式，將問題轉化為常規指派問題，通過判斷等價虛擬工序是否能在并聯環節中實現，逐步提高虛擬工作對應點的時間，以反復迭代的方式搜索可實現方案，同時為了避免漏掉最優解，提出了過優回退原則。最后的實例驗證了該算法的有效性，拓展了匈牙利算法的應用范圍。

參考文獻（References）

[1] 陶世群，蒲保興．基于遺傳算法的多級目標非平衡指派問題求解[J]．系統工程理論與實踐，2004，2004(8)：80.

TAO ShiQun, PU Baoxing. Solving Multi-object and Unbalanced Assignment Problem Based on Genetic Algorithm[J].System Engineering-Theory &Practice. 2004, 2004(8): 80-85.(in Chinese)

[2] 李冰，徐杰，杜文．用模擬退火算法求解有順序約束指派問題[J]．系統工程理論方法應用，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]. Systemss Engineering-Theory Methodology Applications, 2002, 11(4):330-335. (in Chinese)

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

YIN Renkun,WU Yang, ZHANG Jing wei. Research and Application of the Ant Colony Algorithm in the Assignment Problem[J]. Computer Engineering &Science, 2008, 30(4): 43-45. (in Chinese)

[4] 梁耀，覃征，楊利英，黃茹．指派問題的變異蟻群算法求解[J]．微電子學與計算機，2005，22(6)：80-83

LIANG Ya, QIN zheng,YANG Li-ying,HUANG Ru. Mutated Ant Colony Algorithm for Assignment Problem[J]. Microelectronics &Computer, 2005 ,22 (6): 80-83. (in Chinese)

[5] 陳元明．匈牙利算法的注記[J]．麗水學院學報，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] 杜金玲，周杰．關于幾種不平衡指派問題的修正匈牙利解法[J]．價值工程，2010，2010(13)：120-122.

Du Jinlin, Zhou Jie. Fixed Hungaryaigorithm to Unbalanced Assignment Problems [J]. Value Engineering, 2010, 2010(3):120-122. (in Chinese)

[7] 常庭懋，韓中庚．用“匈牙利算法”求解一類最優化問題[J]．信息工程大學學報，2004，5(1)：60-63

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-63. (in Chinese)

[8] 馬曉娜．“人少任務多"型指派問題的一種新算法術[J]．重慶工商大學學報(自然科學版)，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 Technol Business UniV．(Nat Sei Ed), 2014，31(12)：68-71. (in Chinese)

[9] 趙萬林．不正常航班應急調度的模型與算法[D]．中國民航大學，2014.

Zhao Wan-lin. Model and algorithm for the irregular flight emergency scheduling[D]. Civil Aviation University of China, 2014. (in Chinese)

[10] 仇勇．惡劣環境下帶多個維修活動的調度算法研究[D]．浙江工商大學，2013.

Qiu Yong. Study on Scheduling Algorithm with Deteriorating jobs and multiple maintenance Acticity [D]. Zhejiang Gongshang University, 2013. (in Chinese)

[11] 谷穩．基于進化匈牙利算法的目標分配問題研究及應用[D]．西安電子科技大學，2013.

Gu Wen. A Study and Application of Target Allocation based on Evolution Hungary Algorithm [D]. XiDian University, 2013. (in Chinese)

[12] 董莎莎．基于拓撲約束和匈牙利算法的高密度細胞追蹤方法[D]．哈爾濱工程大學，2011.

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

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

Ren Jinxia, He Fujiang. 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] 李建立．武器一目標動態火力分配及戰效評估的研究[D]．南昌航空大學，2014.

Li JianLi, Research on Weapon—Target Dynamic Assignment and Effectiveness Evaluation [D]. Nanchang Hangkong University, 2014. (in Chinese)

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

Song Yuqing. The Imprroved Algorithm for Assignment Problem [J].Science＆Technology Vision, 2012，2012(14)：106-108. (in Chinese)

第2篇: 國防科學技術大學排名

國防科學技術大學2012年博士研究生招生簡章

發布時間 : 2011-07-05

? 點擊下載??2012年博士招生簡章

?????????????????? 2012年博士報名登記表

??? 請認真參讀2012年博士研究生報名通知，按照要求進行網上報名。

一、培養目標

按照“理想信念堅定、軍事素質優良、科技底蘊厚實、創新能力突出、身心素質過硬”人才培養目標總要求，培養軍政素質優良，掌握本門學科堅實寬廣的基礎理論和系統深入的專門知識，具有獨立從事科學研究工作的能力，能夠立足學科前沿、開展創新研究，并具備適應軍隊建設和信息化條件下聯合作戰的需要，鍛煉成長為高層次參謀、指揮和管理人才的基本能力和素質的高級研究人才。

博士研究生畢業后主要分配到全軍各單位從事指揮管理、技術保障和教學科研工作。報考我校的考生，都要做好到一線部隊、到艱苦地區建功立業的思想準備。

二、學習年限

一般為3-4年。

三、報考條件

1、思想政治基礎好，品德良好，遵紀守法，有為國防和軍隊現代化建設服務的意愿。

2、報名對象：

（1）國家承認學歷的軍隊院校應屆碩士畢業生；

（2）已獲碩士學位的軍隊在職干部。

3、身體要求符合《中國人民解放軍軍隊院校招收學員體格檢查標準》，主要有：

（1）身高：男生不低于1.62米，女生不低于1.60米；

（2）兩眼無色盲、色弱；

（3）乙肝表面抗原陰性，肝功能正常。