基于匈牙利法的企业员工任务分配问题研究

2011-10-18郑烨王明杰樊娟

统计与决策 2011年5期

关键词：指派匈牙利矩阵

郑烨，王明杰，樊娟

（湖南大学政治与公共管理学院，长沙410082）

基于匈牙利法的企业员工任务分配问题研究

郑烨，王明杰，樊娟

（湖南大学政治与公共管理学院，长沙410082）

现代企业的发展，必须依托科学高效的管理模式，各项资源配置的合理优化，以达到提高劳动生产率，降低生产成本和获取高额利润的目标。因此立足于现代企业管理的宗旨，通过借鉴匈牙利法，结合人员任务分配实例进行分析研究，最终得出人员与岗位配置的最优化解，从而为企业的人事决策提供参考。

员工任务分配；匈牙利法；指派；最优化解

管理工作中，企业经常会遇到这样的决策问题：N个人，M项任务，由于每个人的特点和能力不同，因此完成不同任务所花费的成本Cij和效率也各不同，若指定每项任务有其中的一个人完成，应如何分配任务，使得企业花费的成本最低，同时也能激发个人的工作动力，做到“因岗设职，动态适应”的原则。这类工作最优匹配的问题在运筹学中被称为指派问题（Assignment Problem），而匈牙利法被作为解决分配问题的有效算法，在企业管理决策中常常为管理者们提供了有效人事决策方案。

1 指派问题的数学模型和“匈牙利法”概述

1 .1指派问题

指派问题（Assignment Problem）是指在满足特定指派要求条件下，使指派方案总体效果最佳。如：有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在若干教室里上课等[1]。通常在企业人力资源管理工作中，由于每个人的能力特长不同，因而完成任务的时间和绩效也就不尽相同。因此，指派问题就是要利用各种定量分析的方法，科学最优化地分配任务，使完成某项任务所花费的总成本最低或总收益最大。现假设有N个员工，M项任务，由于现实中，M和N的数量可能不同，因此指派问题可以分为以下三种情况考虑：

(1)当M=N的时候，即任务的数量等于人的数量，此时每人一项任务。

(2)当M>N时,即任务的数量多于人的数量。这时可以通过虚设(M-N)个人构成一个M×M的效率矩阵,并且这个(MN)人在执行M项任务时的效率应该是成本最高的。

(3)当M

通过虚设任务或人,使得指派问题要求最小化，即：时间、成本及资源耗费等为最小，现假设Xij=1，表示由第i个人去做第j项工作，否则Xij=0，于是得出指派模型为：

目标函数表示完成全部n项工作所消耗的总资源最少，Cij表示指派第i个人去完成第j项任务时所消耗的资源,有Cij(i=1,2,3,…,n；j=1，2，3，…，n)组成的方阵,称为系数矩阵,简记为C。

约束条件（1）说明第j项任务只能由一个人去完成，约束条件（2）说明第i人只能完成一项任务[2]。

Xij=0或1，其中

1 .2匈牙利法

1955年库恩(W．W．Kuhn)提出了指派问题的解法，该方法是以匈牙利数学家考尼格(Konig)提出的一个关于矩阵中O元素的定理为基础，因此得名匈牙利法[3]。其基本步骤是：(1)简化效率矩阵，在行列中构建0元素；(2)试进行一个完全分配方案，对矩阵中的0元素作分配标记；(3)画盖0线，作覆盖所有0元素的最少数的直线集合；(4)增加0元素，重复前述步骤。参阅各种文献资料，当前国内学者在指派问题中的匈牙利算法问题的研究主要集中在以下两个层面：

（1）匈牙利法的应用领域。国内学者韩志伟，谢骏（2008）等将匈牙利法应用到舰船维修保障资源分配问题中，提出匈牙利法的主要依据是，在效率矩阵的任何行或列中，加上或减去同一常数，并不改变最优分配。利用此性质，可使原来的效率矩阵转变为含有很多新元素的效率矩阵，找出在其中的位于不同行、不同列的N个独立的元素，将其取值为1，其他元素取值为0，得到原分配问题的最优解[4]。此外，石岩涛（2006）通过运用匈牙利法对一个航班时刻表中的机组人员在异地的停留时间进行分析调研后，进而提出了科学合理的人员分配方案[5]。与此同时，匈牙利法在实际管理工作中的应用也是较为广泛的，刘晓红，徐扬（2003）提出了基于模糊关系的工作分配算法，通过建立员工个体能力矩阵和建立工作满意程度的模糊集，将匈牙利法应用到工作分配方案的求解中[6]。陈玉兰（2006）介绍了匈牙利法在解决分配工作、汽车运输以及人员选拔问题中的应用，通过举例论证，将匈牙利法的应用过程和步骤清楚地进行了论证说明[7]。

（2）匈牙利法的不足和改进。熊燕华（2009）总结了匈牙利法的特点，并对现有的改进研究进行了探讨，提出了匈牙利法应用的处理技巧，经验证得出改进方法是有效的[8]。顾大全，左莉（2003）等通过全面分析匈牙利算法，找到了存在的问题及原因，对该算法进行了改进，同时提出了程序设计的关键技术，将匈牙利算法变为解决分配问题的最有效算法[9]。

综合上述学者的研究，笔者认为匈牙利法在指派问题中的应用是非常广泛有效的，尤其是在管理工作中的应用，目前很多企业在员工工作配置决策中，以及在其他资源分配问题上，匈牙利法都是比较常用的一种决策工具。鉴于此，笔者通过利用匈牙利算法对企业员工任务分配问题进行研究，从而得出科学的结论。

2 “匈牙利法”应用的实证分析

在企业的劳动组织过程中，为了提高人力资源配置的有效性，通常可以采用运筹学的定量分析方法，在解决员工任务的指派问题时，企业所普遍采用的就是匈牙利法，目的是为了实现员工与任务配置的科学化、合理化。基于上文中的指派模型，并结合实际案例，匈牙利法的应用可以推广到以下方面[10]。

2.1 求解最小化问题

在应用匈牙利法时，求解最小化问题，一般包括：工作时间最小化、生产成本最小化及企业费用最小化等。在求解最小化问题的过程中，必须充分考虑到以下三种情况：

（1）当员工数目与任务数目相等。例：假定某企业有甲、乙、丙、丁、戊五名员工，需要在一定的生产条件下完成A、B、C、D、E五项任务，每个员工完成每项工作所需要耗费的工时，如表1所示，员工与任务之间应该怎样进行配置，才能保证完成工作任务所用的时间最短。

表1 各员工完成任务的时间汇总表（单位：小时）

解：①以各个员工完成各项任务的时间构造效率矩阵一

②对矩阵一进行行约减，即每一行数据减去本行数据中的最小数，得到矩阵二

a、找出未被“盖0”线覆盖的数中的最小值λ=1，b、将未被“盖0”线覆盖住的数字减去λ，c、将“盖0”线交叉点的数加上λ，因此得到矩阵五

目等于矩阵的维度，以此类推，得到最终的矩阵六

根据矩阵七可以得出结论，完成此项任务的最优分配方案是：甲负责任务A，乙负责任务D，丙负责任务B,丁负责任务C，戊负责任务E。此时工作完成的时间最短，最短时间是：10+8+7+5+10=40小时。

（2）当员工数目多于任务数目时。根据上文中指派模型的内容，当员工数目多于任务的数量时，可以通过增加虚任务，使得员工和任务二者达到匹配，增加的虚任务的工作时间和利润都为“0”，此时企业的成本最小。例：A公司目前有赵、钱、孙、李、王五名员工，需要在既定的工作条件下完成甲、乙、丙、丁，四项工作，每个员工的工时如表2所示，求解保证工作时间最短的任务分配法。

表2 A公司员工完成任务的工时表（1）（单位：小时）

分析：此案例中，由五个员工负责四项任务，则必有一名员工没有任务，此时企业可以通过增设虚任务E，各员工完成任务E的时间均为0，因此该做法又回归到第一种情况，可以采用匈牙利法进行计算。表2进行变形后得到表3，即增设一项虚任务之后的情况。

表3 A公司员工完成任务的工时表（2）（单位：小时）

根据表3内容，可以构建效率矩阵C，然后用上文中同样的方法进行计算，最后得出的结果是：赵做丙工作，钱做甲工作，孙做乙工作，王做丁工作，此时李没有分配到任务，经计算得出最短的工作时间为：6+6+7+15=34小时。

（3）当员工数目少于任务数目时。当员工数目少于任务数目的情况下，就必须考虑让一个员工承担两个或多个任务。例：B公司安排2名员工去完成3项任务，每个员工完成任务的时间如表4所示，求解工作时间最短的任务分配方案。

分析：由于两名员工要负责完成三项任务，因此必须有一名员工承担两项工作，在此，增设甲1和乙1两个人，以及虚任务D来分别表示他们完成此项任务的情况，从而表4可以变形得到表5所示：

表4 B公司员工完成任务的工时表（1）（单位：小时）

表5 B公司员工完成任务的工时表（2）（单位：小时）

利用匈牙利法进行计算，最后得出的任务分配方案是：甲做B项任务，乙做A、C项任务。此时的最短工作时间为：12+6+5=23小时。

2.2 求解最大化问题

如果所要求的是最大化问题如maxF,那么可以将其转化为最小化问题进行求解。一般方法是:取e是一个很大的正数,一般可以取：

e=maxcij(i=1,2,…，n;j=1,2,…，n)令：bij=e-cij(i,j=1,2,…，n)

例：某外贸公司目前有5名员工完成5项任务，每个员工完成各项任务所获得利润如表6所示，如何进行任务分配以保证该公司获得最大的利润额。

表6 某外贸公司员工完成任务的收益汇总表（单位：万元）

分析：根据上表中的数据可以得出，表中最大数据为19，用19分别减去表中的各个数据，则数据表可以转化为表7所示，此时可以利用匈牙利法进行求解。

表7 某外贸公司员工完成任务的收益转换表（单位：万元）

通过表中的数据，构造效率矩阵，然后按照上文中介绍的匈牙利法求解最小化问题的解法步骤进行计算，最终得出保证该公司获利最大的任务分配方案是：甲做D工作，乙做B工作，丙做E工作，丁做A工作，戊做C工作，此时该外贸公司可以获得最大利润额为：17+19+12+9+7=64万元。

综上所述，匈牙利法的应用方面主要集中在求解最小化问题和求解最大化问题，无论是求解最小化问题还是求解最大化问题，匈牙利法的使用都是为了给企业带大最大的效益，或耗费最低成本。因此，人力资源管理作为现代企业长期发展的核心和根本保障，指派问题的匈牙利法在企业部门中的应用，为企业的人员配置等工作提供了科学有效的决策建议。

3 “匈牙利法”在企业人力资源管理中的优劣分析

匈牙利法自推广以来，迄今为止已经成为企业人事决策的重要辅助工具，匈牙利法的最大特点就是能够科学的对人员和工作进行合理的配对，即通常所说的“人事匹配”。利用匈牙利法进行合理的劳动分工，发挥出员工的最大潜能，既可以帮助企业创造出最大的利润，实现最初制定的战略目标，同时也可以避免企业内外部各项资源的闲置浪费，发挥各项资源的边际效用[12]。然而，任何一种技术手段和工具本身都具有现实制约性，存在某些不足，因此，匈牙利法在现代企业人力资源管理中的应用也体现出积极和消极两方面的作用。

3.1 积极作用

根据上文中，匈牙利法在现实应用的实证研究，其积极作用主要可以概括为以下几个方面：

（1）为人员配置提供科学决策。人力资源作为推动现代企业前进的内驱力，先进科学的管理模式可以帮助企业在短期内获得巨大收益。匈牙利法的应用，一方面解决了企业中经常关注的人员分配问题，促进了生产力的发展和员工工作积极性的提高，另一方面合理的“能岗配置”，促进了企业内部部门之间以及其他一系列管理活动顺畅有序的进行，为企业利润的增长，战略的制定，绩效的考评，薪酬的设置等人力资源管理的重要环节提供了科学可行的决策方法和手段。

（2）操作简单，应用性强。在当今国际化的市场竞争中，企业成本和利润成为衡量其经营绩效的重要参考指标，企业经营的目标都是以最小化的成本换回最大化的利润回报。随着现代科技的飞速发展，企业必须适应时代的潮流，不断进行技术创新和产品研发，在此过程中，科学合理的决策方案将成为影响企业发展的重要因素。匈牙利法不仅可以为企业人事决策提供可靠的政策建议，同时可以预测和估算出企业未来一段时期的成本和收益总量，而且操作方便，应用性强，受到了现代企业管理者的青睐。

（3）应用的领域较广泛。随着匈牙利法的普遍推广，其应用领域已经从现代企业部门拓宽到了公共事业单位及交通运输行业等等，包括像很多的竞技体育类项目，学校课程安排，以及交通线路的优化改良等方面都合理巧妙地利用了匈牙利法的优势和特点，为各行各业的管理决策活动，提供了科学保证。因此，匈牙利法的应用可以促进社会生产力的发展，充分发挥资源优化配置的功能，从而节省了大量不必要资源的投入和消耗，节约了成本，提高了利润。

3.2 消极影响

匈牙利法的应用，尽管给人们的日常管理工作带来了较大的便利，但是与此同时，其本身也存在着一定的缺陷，具体表现为：

（1）计算过程较繁琐。经过国内外学者的研究发现，匈牙利法普遍存在的一个较大的问题就是运算量较大，运算过程较繁琐。一般情况下，匈牙利法的计算过程都要经过很多步骤，如果中间稍有差错，就可能导致最终结果的失灵。尽管其应用简单易懂，但是繁琐的计算量，使得国内学者长期以来不断探索如何优化和改进这种方法，以提高其应用效率。

（2）无法处理一些特殊数据。尽管目前匈牙利法处理了很多与指派问题相关的分配问题、调度问题，大多数情况下，由于假定的效率矩阵的维度不多，数据较少，因而很难找出应用中的问题。然而，当处理一些较复杂的问题以及一些特殊的数据时，匈牙利算法不收敛从而导致了无法找出最终的最优解，矩阵的维度越高，不收敛的情况就越容易发生。因此，目前很多学者对于匈牙利法的应用进行不断地修正完善，为了尽量避免各种计算偏差和失误的发生。

4结束语

随着现代科技的发展和生产力水平的提升，现代企业人力资源管理中应该采用定量分析的方法对企业中的员工进行岗位的配置和调整，以实现动态适应的原则。匈牙利法在企业员工任务分配中的应用，有助于解决企业人力资源管理中经常出现的用人主观和随意等问题，同时对企业战略目标的实现、人员培训和开发、绩效考评、薪酬调整及职业生涯规划等一系列管理活动都起到了重要的影响意义。因此，在科学高效地利用匈牙利法的基础上，也必须善于发现其本身存在的缺陷和问题，不断优化改进，以保证企业各项管理工作的客观高效。

[1]严文利.求解指派问题的新方法[J]．南京审计学院学报，2009，（6）.

[2]袁迁，刘舒燕.关于匈牙利法的优化[J].武汉理工大学学报，2007，(3).

[3]张联朋.对指派问题匈牙利解法的两点改进[J]．西安航空技术高等专科学校学报，2007,(1).

[4]谢骏，韩志伟等.匈牙利法在舰船维修保障资源分配中的应用[J]．中国修船，2008，（2）.

[5]石岩涛.一个世纪指派问题的研究[J]．运筹与管理，2006，（4）.

[6]刘晓红，徐扬等.基于模糊关系的人力资源管理工作分配算法[J]．软科学，2003，（4）.

[7]陈玉兰.指派模型在管理工作中的应用[J]．吉林财税高等专科学校学报，2006，（4）.

[8]熊燕华.对国内求解指派问题的匈牙利法改进的评述[J]．中国制造业信息化，2009,(10).

[9]顾大全，左莉等.匈牙利法存在的问题及改进方法[J]．微机发展，2003，（4）.

[10]王琼华,王刚.指派问题数学建模的匈牙利解法[J]．昆明冶金高等专科学校学报,2006,(5).

[11]黄龙生，徐光辉.有资格限制的指派问题的求解方法[J]．运筹与管理，2005，（1）.

[12]吴志明.招聘与选拔实务手册[M]．北京：机械工业出版社，2006.