(この質問をmath.stackexchange.comにも投稿しました。これは、どこに属すべきかわからないためです。)
次の入力を持つシステムがあります。
- 完了する作業項目のセット。これらは可変サイズです。特定の順序で完了する必要はありません。
- 過去に作業項目が完了するまでにかかった時間に関する履歴データ。ただし、過去の実績は将来の成功を保証するものではありません。つまり、作業項目を実際に実行すると、以前よりも時間がかかったり短くなったりすることがあります。
- これまで見たことがなく、履歴データがない作業項目が存在する可能性があります。
- ワークアイテムには、さらに「パラレル」または「シリアル」という「分類」があります。
- 作業項目をピックアップして作業できる「エージェント」のセット。エージェントの数は固定されており、事前にわかっています。エージェントは、一度に 1 つの作業項目しか処理できません。
- エージェントが作業項目を実行する「サーバー」のセット。サーバーにはさまざまな機能があります。具体的には、異なる数のエージェントを同時に処理できます。
ルール:
- サーバーが「シリアル」ワークアイテムの実行に使用されている場合、他のワークアイテムの実行に同時に使用することはできません。
- サーバーが「シリアル」ワークアイテムの実行に使用されていない場合、サーバーは可能な限り多くのエージェントを同時に処理し、すべて「パラレル」ワークアイテムを実行できます。
- 特定のサーバーに対して実行する必要がある作業項目がいくつかあります (ただし、どのエージェントでも実行できます)。それが重要な場合、これらの作業項目は「並列」です。(今のところ、このルールを無視する方が簡単かもしれません!)
要件：
上記の入力とルールを考慮して、一連の作業項目を「できるだけ早く」実行する必要があります。作業項目が完了するまでにどれくらいの時間がかかるかを知ることはできないため、事前に完全な解決策を導き出すことを期待することはできません (おそらく)。各作業項目を 1 つずつ実行する!
歴史的に、私は非常に単純なラウンド ロビン アルゴリズムを使用し、最も長く実行されている作業項目がより早くスケジュールされるように、履歴期間の降順で単純に作業項目を並べ替え、できればサイクルの終わりにすべてを保持できるようにしました。エージェントとサーバーには、短期間の作業項目が適度にロードされています。これにより、使用率グラフは非常に良好な「正方形」の形状になり、サイクルの終わりに長時間の作業項目が長く続くことはありません。
ただし、この歴史的なアルゴリズムでは、エージェントとサーバーの数を事前に構成し、作業項目を「プール」に事前に割り当て、プールをサーバーに割り当てるなど、多くの恐ろしいことを行う必要がありました。再構成することなく、動的な数のエージェントとサーバーをサポートする必要があります。(サーバーの数はサイクル中に固定されることに注意してください。つまり、数はサイクル間でのみ変化しますが、エージェントの数はサイクルの途中で増減する可能性があります。)
すべての作業項目が完了すると、各作業項目が次のサイクルにフィードするのにかかった時間を記録し、最初からやり直します!