-
从上世纪50年代初提出以来，指派问题的研究已有751十多年的历史，科学家们开发了大量的求指派问题的算法。其中最多求解的一个问题即任务分配问题。最早的算法是在1955年，库恩（ ）在一篇题为 的文章中提出了一个算法，用来构造二部图的最大权完美匹配问题。在这篇文章中，他解释了两个匈牙利数学家König和Egervary对指派问题的贡献，他们提出了：在价值系统矩阵 中，如果位于不同行不同列的0元素（称为独立0元素）的最多个数与价值系数矩阵 的文数相同，则只要令对应于这些独立0元素位置的 =0，此解就是最优解。因此他把这个算法叫做匈牙利算法。除此之外，以下性质也在匈牙利算法迭代求解的过程中被反复利用，即价值系数矩阵 的任一行（列）的全部元素上同时加或减去一个常数，指派问题的最优解（即最优匹配矩阵）不变。1957年，Munkres给出了匈牙利算法的一个不同的版本，并证明其算法复杂度为 。之后，Dinic等人提出了匈牙利算法的一个算法复杂性为 的版本，这是求解任务分配问题的第一个复杂性为 的算法。1976年，Lawer在给出了匈牙利算法的一种标记版本，这是目前最流行的版本。2005年，库恩的论文被评为Naval Research Logistics 50年来的最佳论文。Naval Research Logistics召开学术会议，回顾和总结了50年来和任务分配问题相关的研究结果，以纪念他对该领域的贡献。22713
- 上一篇：C#美容中心业务管理系统的设计与实现
- 下一篇：国内外植物提取物的制备技术研究现状
此后，研究人员提出了各种求解任务分配问题的算法。首先是拍卖算法的提出，Bertsekas提出的拍卖算法，在很多问题中都有应用。2003年，Lim等人提出了一种类似于拍卖法的竞标算法，该算法可以直接求解非平衡的任务分配问题，而不需要添加虚拟人工或虚拟任务。对于工人人数和任务数相差较大的情况下，这种算法具有较大的优势。1983年，Hung提出了一种单纯形方法，用于求解任务分配问题。尽管单纯形法对于一般的线性规划问题是非多项式算法，但是，这种用于求解任务分配问题的单纯形算法的时间复杂度为 。之后，Balinski提出了一种签名算法，这种方法基于对偶理论，类似于对偶单纯形，但并不是严格意义上的对偶单纯形，该算法复杂度也为 。论文网
自20世纪90年代至今，提出的求解任务分配问题的新算法除了上面提到的竞标算法，Goldberg等人提出了一种cost scaling算法，该算法基于网络流理论中的伪流方法和逼近的思想来得到最优解。Ji等人于1997年提出了一种算法。这种方法基于 的增广矩阵迭代，其迭代求解过程与对偶单纯形方法类似，其时间复杂度也为 。除此之外，Ramakrishnan等人还提出了一种用于求解指派问题的内点法。
尽管指派问题有超过751十年的研究历史，但到目前人们还没有发现如何应用此算法运用到大规模的实际应用中。因此改进指派问题的算法仍是一个十分重要的研究课题。