我一直在考虑调度和负载平衡算法，我想出了一个我认为很有趣的问题。
有 N 个笼子和 M 个饲养员。每个笼子的大小为 S，动物数量为 A。笼子必须清洁的频率被计算为 A / S 的某个函数（具有更多动物的较小笼子会更快变脏）。清洁笼子的难度被计算为 A 和 S 的一些其他函数，其中的细节并不重要（笼子的大小贡献了大部分的难度，动物的数量贡献了一点点）。每三天一次，清洁任何需要清洁的笼子（“清洁日”）。Zookeepers 是完全一样的并且可以互换。动物园管理员在每个清洁日都需要做类似的工作量，并且不必比任何其他动物园管理员做更多的工作。清理笼子所需的时间不是问题的一部分（假设时间大致反映在难度上，
调度算法必须告诉每个动物园管理员在每个清洁日要清洁哪些笼子，这样
- 每个笼子都以理想的频率或尽可能接近的频率进行清洁，
- 为每个动物园管理员每个清洁日分配最少且大致相等的清洁次数，
- 并确保所有 zookeepers 的工作量尽可能相等（即，在一段时间内，每个 zookeeper 工作量的总难度尽可能接近相等，笼子以大约 1/M 的概率分布在 zookeepers 中）。
我想知道这种优化问题的近似算法是什么样的。它与 NP-hard 调度/资源利用问题的几个不同经典示例相似；也许它可以简化为一个这样的问题，而我只是想念它。如果我们去掉任务的频率/周期元素，它类似于经典的多处理器调度或有限装箱问题。