スケジューリングと負荷分散のアルゴリズムについて考えていて、面白いと思う問題を思いつきました。
N 個のケージと M 個の飼育係がいます。各ケージのサイズは S で、動物の数は A です。ケージを掃除する必要がある頻度は、A / S の関数として計算されます (動物が多く、ケージが小さいほど汚れが早くなります)。ケージの掃除の難しさは、A と S の他の関数として計算されますが、その詳細は重要ではありません (ケージのサイズが難しさのほとんどに寄与し、動物の数が少し寄与します)。3 日に 1 回、清掃が予定されているケージを清掃します (「清掃日」)。Zookeepers は完全に同一であり、交換可能です。飼育係は、清掃の日に同じ量の作業を行う必要があり、他の飼育係よりも多くの作業を行う必要はありません。ケージを掃除するのにかかる時間は問題の一部ではありません (時間は難易度によって大まかに反映されると想定されますが、
スケジューリング アルゴリズムは、次のように、清掃日にどのケージを清掃するかを各飼育係に通知する必要があります。
- 各ケージは理想的な頻度で、または可能な限り近い頻度で洗浄されます。
- 清掃日ごとに飼育係ごとに最小限の、ほぼ同数の清掃を割り当てること、
- すべての飼育係にできる限り均等な作業負荷を保証する (つまり、一定期間にわたって、各飼育係の作業負荷の総計の困難は可能な限り等しくなり、ケージは飼育係間でおよそ 1/M の確率で分散される)。
このような最適化問題の近似アルゴリズムはどのようになるのだろうかと思っています。これは、NP 困難なスケジューリング/リソース使用の問題のいくつかの異なる古典的な例に似ています。多分それはそのような問題の1つに還元可能であり、私はそれを見逃しています。タスクの頻度/周期性要素を取り除くと、従来のマルチプロセッサ スケジューリングまたは有限ビン パッキングの問題に似ています。