周期任务的最优公平负载均衡/多处理器调度

Question

我一直在考虑调度和负载平衡算法，我想出了一个我认为很有趣的问题。

有N个笼子和M个动物园饲养员。每个笼子有一个尺寸S和一些动物A。必须清洗笼子的频率计算为A/S的某个函数(动物越多的小笼子越脏越快)。清洗笼子的难度被计算为A和S的其他函数，其细节并不重要(笼子的大小决定了大部分困难，而动物的数量贡献很少)。每三天一次，任何需要清洗的笼子都会被清洗(“清洁日”)。动物园管理员是完全相同和可互换的。动物园管理员每一天都需要做同样数量的工作，而且不必比任何其他动物园管理员做更多的工作。笼子清理所需的时间并不是问题的一部分(假定时间大致反映在困难之中，而且一天中总是有足够的时间让动物园管理员完成指定的任务)。

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

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

我想知道这样一个优化问题的近似算法会是什么样子。它类似于NP硬调度/资源利用问题的几个不同的经典例子；也许它可以归结为这样的一个问题，而我只是忽略了它。如果去掉任务元素的频率/周期性，则类似于经典的多处理机调度或有限垃圾箱包装问题。

Answer 1

考虑到目标是平衡动物园管理员的努力，或多或少的标准方式来处理这类任务，这是在线贪婪的。

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

保存每个动物园管理员到目前为止花费的努力的记录，最初为零。在每个清洁的日子，总结所需的清洁工作，并使用第一适合，最适合，或随机拟合分配工作的方式，往往是相等的工作量总和。也就是说，为了达到最佳状态，将最大的任务分配给门将，这远远落后于迄今为止分配的工作。重复，直到所有任务都被分配。