根据剩余空间将作业分配给主机的算法

Question

输入:

• 作业实例列表，其中 (job_i, size_of_job_i) where 我 = 1..n
• 这样的主机列表 (host_j, remaining_space_host_j) 其中 j = 1..m

想要

• 相应地将工作分配给主机。

输出

• (host_j, job_i) 其中 j=1..m 且 i = 1..n

仅供引用，当作业分配给主机时，主机的剩余空间将会减少。 例如job1 = (job_1, 1TB)分配给host1 = (host_1, 100TB)后，host1变为(host_1, 90TB)。

目前使用贪心算法，贪心算法的工作方式是先找到一个最大的剩余主机，然后给它们分配任务。

这个算法的问题是作业没有分布在所有主机上。 这意味着一些有足够剩余空间的主机没有工作，而一些主机分配了太多的工作。

我很确定有一些著名的算法。 我搜索了关键词“资源分配算法”，但找不到适合我的。可能我选错了关键字。

有人知道或推荐一个好的简单算法吗？

Answer 1

背包问题或许能帮到你。看一看。

它是关于具有权重变量的项目。问题是，如果背包的极限是 X(1,2,3...)，最佳组合是什么。