主机中任务的分配

Question

我有一组主机和一组任务。
每个主机都有cpu、mem和任务容量，每个任务都有cpu、mem要求。
每个主机都属于一个延迟类，并且可以与具有特定延迟值的其他主机通信。
每个任务可能需要与另一个任务进行通信，延迟等于或小于某个值。
下一张图片显示了我的问题输入示例。 其中，任务t1需要与任务t2、t3和t4通信，延迟分别等于或小于3、3和5，主机h1属于延迟类3，与h2、h3和h4通信，延迟分别为2、5和3。
我在想用匈牙利/蒙克雷斯算法来解决这个问题，但是我怎样才能正确地设置一个成本函数呢？ 有没有更好的分配算法来解决这个问题？
谢谢。在

Answer 1

有一个用于Munkres的Python包：http://software.clapper.org/munkres/。您可以参考它们的实现：https://github.com/bmc/munkres/blob/master/munkres.py

Answer 2

你应该知道，这个问题是QAP（二次分配问题）的一个例子，这是NP完全的，这意味着：至少在多项式时间内，不存在解决它的最佳算法。更多详细信息here

虽然有几种方法需要处理，但我尝试了一些简单的方法，比如遗传算法（GA）和蚁群算法（ACO），但都取得了很好的效果。我向你推荐。在