c++ - タスクを実行するための時間を含む 2 次元行列の最適解が必要

Question

m 個のプロセッサ (列) と n 個のタスク (行) の 2 次元マトリックスがあります。マトリックスには、プロセッサで各プロセスを実行するのにかかる時間が入力されています。これらの n 個のタスクを m 個のプロセッサで実行する最適な時間を見つける必要があります。

Answer 1

説明されている問題は、並列マシン スケジューリングの問題のカテゴリに属します。
また、各タスクには異なるプロセッサで異なる時間がかかるため、この問題はUniform Machine Scheduling Problemと呼ばれます。

この種の問題は非常に NP 困難であるため、多項式時間アルゴリズムは知られていません。したがって、複雑さが に似ているため、行列が非常に小さい場合を除き、力ずくのアプローチは実際には推奨されませんO( n ^ m )。

そうは言っても、混合整数線形計画法 (MILP) を使用し、Cplex や Gurobi などの最高の線形ソルバーでそれを解くことにより、それほど大きくない行列に対して最適なアプローチがおそらく実行可能です (LP-solve のようなオープン ソース ソルバーはほとんどないと思います)。特定のサイズを超える問題を処理できます)。

この問題に適用可能な MILP モデルの例をここで説明します。

ただし、その複雑さを考えると、この種の問題は通常、ヒューリスティック/メタヒューリスティックを使用して解決されるため、最適なソリューションに確実に到達することはできません。いずれにせよ、優れた貪欲なアルゴリズムに続いて、貪欲なソリューションを改善するための優れたローカル検索を行うと、最適に非常に近づくことができます。

編集 ：

可能性のある強引なアプローチは、TASK-PROCESSOR 割り当てのすべての可能な組み合わせを計算してから、makespan を計算することです。C/C++ での例を次に示します。

Answer 2

最初に、すべての処理を実行するのにかかる合計線形時間を計算します (すべてのタスクの期間を合計します)。それをプロセッサーの数で割りますm。

これが目標平均時間です。この数にできるだけ近くなるように、各プロセッサの期間の組み合わせを見つけたいと考えています。

最も基本的なアプローチは次のとおりです。

avg = <the average from earlier>
list = <all jobs>
FOR i = 0 to m
    WHILE duration(processor[i]) < avg:
        processor[i].add(longest lasting job in `list` that will keep the time less than `avg`

これにより、最後にいくつかのジョブが残り、ジョブがなくなるまで、最も長く持続するジョブが最も短いプロセッサ時間に追加されます。list