algorithm - 周期性任务的最佳公平负载平衡/多处理器调度

Question

我一直在思考调度和负载均衡算法，我想出了一个我觉得很有趣的问题。

有N个笼子和M个动物园管理员。每个笼子的大小为 S，动物的数量为 A。笼子必须清洁的频率是根据 A/S 的某个函数计算的(笼子越小，动物越多，脏得越快)。清洁笼子的难度被计算为 A 和 S 的一些其他函数，其细节并不重要(笼子的大小贡献了大部分难度，动物的数量贡献了一点)。每三天清洁一次需要清洁的笼子(“清洁日”)。 Zookeeper 完全相同并且可以互换。动物园管理员每个清洁日需要做的工作量相似，而且不必比其他动物园管理员做更多的工作。清洁笼子所花费的时间不是问题的一部分(假设时间大致反射(reflect)了难度，并且一天中总是有足够的时间让动物园管理员完成分配给他们的任务)。

调度算法必须告诉每个动物园管理员在每个清洁日清洁哪些笼子，这样

• 每个笼子都以理想的频率或尽可能接近的频率清洁，
• 每次分配最少且大致相等的清洁次数每个清洁日的动物园管理员，
• 并确保所有动物园管理员的工作量尽可能均等(即，在一段时间内，每个动物园管理员的工作量的总难度尽可能接近相等，笼子以大约 1/M 的概率分布在动物园管理员之间)。

我想知道这种优化问题的近似算法是什么样的。它与几个不同的 NP-hard 调度/资源利用问题的经典示例相似；也许它可以归结为这样一个问题，而我只是想念它。如果我们去掉任务元素的频率/周期性，它类似于经典的multiprocessor scheduling。或有限 bin packing问题。

Answer 1

鉴于目标是平衡 zookeeper 的努力，处理此类任务的或多或少的标准方法是在线贪婪。

在这种情况下，这相当于:

记录每个动物园管理员到目前为止所付出的努力，最初为零。在每个清洁日，汇总所需的清洁工作，并使用首次匹配、最佳匹配或随机匹配来分配工作，使工作总和趋于均等。 IE。为了最合适，将他最大的工作分配给迄今为止分配的工作中最落后的守门员。重复直到分配完所有任务。