论文标题
任务分配问题的时间触发尺寸减少算法
A Time-Triggered Dimension Reduction Algorithm for the Task Assignment Problem
论文作者
论文摘要
任务分配问题是组合优化的基础，旨在将一个或多个任务分配给许多代理商，同时最大程度地减少总成本或最大化整体分配收益。已知该问题在计算上很难，因为它通常被称为混合整理编程问题。在本文中，我们考虑了一种新型的时间触发的降低算法（TTDRA）。我们提出了凸式化方法，以使一般非凸位分配问题的约束和成本函数均匀。计算速度通过我们的时间触发的尺寸缩减方案加速，其中触发条件是基于最佳公差和成本函数的凸度设计的。最佳和计算效率通过基准示例的数值模拟得到验证。
The task assignment problem is fundamental in combinatorial optimisation, aiming at allocating one or more tasks to a number of agents while minimizing the total cost or maximizing the overall assignment benefit. This problem is known to be computationally hard since it is usually formulated as a mixed-integer programming problem. In this paper, we consider a novel time-triggered dimension reduction algorithm (TTDRA). We propose convexification approaches to convexify both the constraints and the cost function for the general non-convex assignment problem. The computational speed is accelerated via our time-triggered dimension reduction scheme, where the triggering condition is designed based on the optimality tolerance and the convexity of the cost function. Optimality and computational efficiency are verified via numerical simulations on benchmark examples.
