私は割り当て問題の変種のように見える問題に取り組んでいます。サーバーに割り当てる必要があるタスクがあります。サーバーにかかるコストの合計を最小限に抑える必要があります。次の条件が成り立ちます。
- 各タスクには単位サイズがあります。
タスクを複数のサーバーに分割することはできません。タスクは、厳密に 1 つのサーバーによって処理される必要があります。
サーバーには、割り当てられるタスクの最大数に制限があります。
タスク割り当てのコスト関数は階段関数です。サーバーには最小コスト「a」が発生します。サーバーが処理するタスクごとに、コストは 1 ずつ増加します。特定のサーバーに割り当てられたタスクの数がその容量の半分を超えると、そのサーバーのコストは正の数 'd' に等しくなります。
- タスクにはプリファレンスがあります。つまり、特定のタスクをいくつかのサーバーのうちの 1 つに割り当てることができます。
これは NP 困難な問題であると感じていますが、マッピングする NP 完全問題を見つけることができないようです。Bin Packing、Assignment problem、Multiple Knapsacks、bipartite graph matching を試しましたが、これらの問題のどれも、私の問題のすべての重要な特徴を持っていません。それに対応する問題を教えてください。
よろしくお願いします
サキブ