我一直在考虑调度和负载平衡算法，我想出了一个我认为很有趣的问题。
有N个笼子和M个动物园管理员。每个笼子都有一个大小S和一些动物A。必须清洁笼子的频率计算为 A/S 的某个函数（动物较多的较小笼子变脏得更快）。清洁笼子的难度计算为A和S的其他函数，其细节并不重要（笼子的大小贡献了大部分难度，动物的数量贡献了一点）。每三天清洁一次，任何需要清洁的笼子都会被清洁（"清洁日"）。动物园管理员是完全相同且可互换的。动物园管理员每个清洁日需要做类似数量的工作，并且不必比其他任何动物园管理员做更多的工作。笼子清洁所需的时间不是问题的一部分（假设时间大致反映在难度上，并且一天中总是有足够的时间让动物园管理员完成他们分配的任务）。
调度算法必须告诉每个动物园管理员在每个清洁日要清洁哪些笼子，以便
- 每个笼子都以理想的频率或尽可能接近地清洁，
- 为每个清洁次数分配最少且大致相等的清洁次数每个清洁日的动物园管理员，
- 并确保所有动物园管理员的工作量尽可能相等（即在一段时间内，每个动物园管理员工作量的总难度尽可能接近相等，笼子以大约 1/M 的概率分布在动物园管理员之间）。
我想知道这种优化问题的近似算法会是什么样子。它与NP硬调度/资源利用问题的几个不同的经典示例相似;也许它可以简化为一个这样的问题，我只是错过了它。如果我们去掉任务元素的频率/周期性，它类似于经典的多处理器调度或有限箱打包问题。
鉴于目标是平衡动物园管理员的努力，处理此类任务的标准方法或多或少是在线贪婪。
在这种情况下，这相当于：
记录每个动物园管理员到目前为止所付出的努力，最初为零。 在每个清洁日，统计所需的清洁工作，并使用第一次、最适合或随机适合的方式分配工作，以倾向于平衡工作量的方式。 即为了最合适，将他最大的工作分配给迄今为止分配的工作中最落后的守门员。重复此操作，直到分配了所有任务。