【作者】 鄢超波； 赵千川；

【Author】 Yan Chaobo 1,Zhao Qianchuan 1 1.Dept.of Automation,Tsinghua University,Beijing 100080,P.R.China

【机构】 清华大学自动化系；

【摘要】 任务分配问题是一个被广泛研究的问题,在运筹学理论和工程应用中都有很高的价值。匈牙利算法是任务分配问题的一种有效的求解方法。尽管任务分配问题得到了广泛的研究,但是已有文献缺乏对各种算法的求解效率进行全面的对比。本文首先概述任务分配问题及其基本性质,然后综述任务分配问题的研究历程,并在现有的算法分类的基础上完善了分类,最后对比两种较新的算法和匈牙利算法所能求解实际工程问题中任务分配问题的规模和求解效率,说明在求解平衡的任务分配问题时,匈牙利算法的性能比这两种新算法的性能要好;在求解非平衡的任务分配问题时,竞标算法具有很大的优势。更多还原

【Abstract】 Assignment Problem(AP) was well studied in the past 50 years,and is of great value in operations research and engineering.The Hungarian Method is one of the effective algorithms for the assignment problem.Although the assignment problem is well studied and a variety of algorithms are proposed,the efficiencies of the algorithms are never completely compared in the literature.In this paper,we summarize the properties of the assignment problem,and then survey its research history,add two new algorithms to existing classification,and compare the performances of these two algorithms with that of the Hungarian Method.The computational results show that the Hungarian Method can solve larger balanced assignment problems in engineering and is more efficient than the two algorithms involved,and the bidding algorithm is superior to solve unbalanced assignment problems.更多还原