私は現在、イベントのスケジューリングを処理するシステムのモジュールに取り組んでいます。各イベント オブジェクトには、開始と終了のタイムスタンプと、必要なリソースの配列があります。各リソースで使用できる数には制限があり、同時に発生できるイベントの数にも制限があります。最終的には、部屋、プロジェクター、椅子などの数が限られている会議室の予約型システムに似ています。
現時点では、現在のイベントをループしてリソース使用率と同時イベント数を計算していますが、これが数千のイベントに実行されると、非効率的な方法のように思えます。
誰でもより効率的な方法を提案できますか?
これは、いわゆるNP 完全問題です。サンプルサイズが大きくなるにつれて、「数学的に最適な」解を見つけることは非常に高価になる可能性があります。「現実世界」のソリューションに費やす時間は、要件によって異なります。いくつかのヒューリスティックを使用して、最適ではないソリューションを見つけることができます。
1 つのヒューリスティック:
モジュールを何らかのメトリックで並べ替えることができます。それらを降順でプールに追加するよりも。最も高価なモジュールから始めます。同じスロットに収まるすべてのモジュールを追加します。その後、残りのモジュール用に新しいスロットを開きます。などなど。