主机中任务的分配/分配

Question

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

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，效果很好。我会为你推荐GA。