主机中任务的分配/分配

Question

我有一组主机和一组任务。

每个主机都有cpu、内存和任务能力，每个任务都有cpu、内存要求。

每个主机属于等待时间类，并且可以与具有特定等待时间值的其他主机通信。

每个任务可能需要以等于或小于特定值的等待时间与另一个任务通信。

我的问题输入示例如下图所示。

其中任务t1需要分别以等于或小于3、3和5的时延与任务t2、t3和t4通信，而主机h1属于时延等级3，并且分别以时延2、5和3与h2、h3和h4通信。

我正在考虑使用匈牙利/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的。