主机中任务的分配/分派
我有一组主机和一组任务。
每台主机都有CPU、内存和任务处理能力，而每个任务也有CPU和内存的需求。
每台主机属于一个延迟类别，并且可以与其他主机进行通信，但会有一定的延迟值。
每个任务可能需要与另一个任务进行通信，延迟必须等于或小于某个特定值。
下面的图片展示了我的问题输入示例。
在这个例子中，任务t1需要与任务t2、t3和t4进行通信，延迟分别不能超过3、3和5，而主机h1属于延迟类别3，并且与h2、h3和h4的通信延迟分别是2、5和3。
我在考虑用匈牙利算法（Hungarian/munkres算法）来解决这个问题，但我该如何正确设置成本函数呢？有没有更好的分配算法可以解决这个问题？
谢谢。
2 个回答
1
你应该知道，这个问题属于QAP（二次分配问题），而且这是一个NP完全的问题。简单来说，就是没有一个最好的算法能在多项式时间内解决它。想了解更多细节，可以点击这里。
不过，有几种方法可以处理这个问题。我尝试过一些简单的人工智能方法，比如遗传算法（GA）和蚁群算法（ACO），效果都不错。我推荐你使用遗传算法。
1
有一个Python的库叫做Munkres，你可以在这里找到它：http://software.clapper.org/munkres/。你也可以查看他们的实现代码：https://github.com/bmc/munkres/blob/master/munkres.py