分配算法

Question

我需要分配N实体(每个有可能的父母以及可能的儿童)的M计算的节点，同时满足以下优化条件：

1. 儿童的一个实体希望被分配到同一计算的节点(以最大限度地提高数据的地区之间的兄弟姐妹)
2. 分配的实体都应当为即使可能(即没有超出单个节点)。

我在找一些建议的启发式的方法来解决这个问题。

我读过 http://en.wikipedia.org/wiki/Assignment%5Fproblem.

谢谢。

Answer 1

我不确定是否1是一个很难的要求。如果是这样，作为第一步，应该集团实体 连接部件.如果没有，则应指定什么样的折衷1和2之间的，例如作为一个成本的功能。

把这件上计算的节点是 binpacking问题, 如果限制每个节点，以N/M实体。一个很好的近似是下列算法：

1. 排序的部件通过的实体数量，在降低了
2. 把它们放到节点，只要每个节点仍能力可用
3. 当做有2,你可能已经组成，没有被放置。将这些节点上，它具有最小的负荷为止。

Answer 2

嗯，很明显，你必须预测有多少儿童(或者简单地总载荷)中的每一个过程将在平均水平。比你可以使用的经典分配的算法，他们通常很简单。

最重要的问题当然是决定什么你要尽量减少。通常我们要最大限度地减少迟到(多少"落后于时间表"我们得到的)，但不总是...

编辑：如果你知道所有的孩子/父母和儿童的过程中必须在同一台机器，可以考虑一个过程和它的所有儿童以同样的进程的开始。然后你就可以用非常简单的算法，以尽量减少任何你想要尽量减少。

编辑#2:阅读有关 工作调度 得到一个更好的主意