论文标题
瓶颈分配问题中的利用结构
Exploiting Structure in the Bottleneck Assignment Problem
论文作者
论文摘要
当存在一组必须分配给一组代理的任务时，就会出现分配问题。瓶颈分配问题（BAP）的目的是最大程度地减少对代理商的任务分配最昂贵的分配。在某些条件下，可以利用BAP的结构，以使任务的子组分别分别以较低的复杂性分别分配，然后合并以形成组合分配。特别是，我们讨论从两个单独的BAPS合并分配，并使用子问题的解决方案来绑定合并问题的解决方案。我们还为子问题解决方案在合并问题上产生精确解决方案的情况提供了条件。然后，我们引入了一种特定的算法来解决利用这种见解的BAP。这些方法在数值案例研究中得到了证明。
An assignment problem arises when there exists a set of tasks that must be allocated to a set of agents. The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment. In particular, we discuss merging the assignments from two separate BAPs and use the solution of the subproblems to bound the solution of the combined problem. We also provide conditions for cases where the solution of the subproblems produces an exact solution to the BAP over the combined problem. We then introduce a particular algorithm for solving the BAP that takes advantage of this insight. The methods are demonstrated in a numerical case study.
