これは、人気のある El Goog 問題のバリエーションです。
次のスケジューリングの問題を考えてみましょう。n 個のジョブがあり、i = 1..n です。スーパーコンピュータ1台、PC台数無制限。各ジョブは、最初にスーパーコンピューターで前処理され、次に PC で処理される必要があります。スーパーコンピュータ上のジョブ i の所要時間は si, i = 1..n です。PC の場合は pi、i = 1..n です。PC は並行して作業できますが、スーパーコンピューターは一度に 1 つのジョブしか処理できません。スーパーコンピュータがジョブを処理するスケジュールSが作成されます。スケジュール S の完了時刻 Ti(S) は、PC 上でジョブが終了する時刻によって与えられます。Maxi[Ti(s)] を最小化するスケジュールを見つけたい(読み方: 最高終了時間を最小化するスケジュールを見つける必要がある). 次の貪欲なアルゴリズムが提案されています。このアルゴリズムの複雑さは O(nlogn) です。このアルゴリズムが最適解を生成することを証明するか、そうでないことを示す反例を提供してください。
私の解決策 (これが正しいかどうかはわかりません): ジョブの順序は重要ではないと思います。最高終了時間は変わりません。ジョブのリストに対する PC での処理時間の例を考えてみましょう: <5、7、17、8、10>。これにより、終了時間が <5、12、29、37、47> となります。アルゴリズムに従って、リストを <17, 10, 8, 7, 5> としてソートし、終了時間は <17, 27, 35, 42, 47> になります。したがって、技術的には、貪欲なアルゴリズムは最適な順序付けを行いますが、それには nlogn の時間がかかりますが、ジョブのリストを単純に反復しても同じ結果が得られます。
貪欲なアルゴリズムの方がうまく機能する、または私のアプローチに欠陥があると考える人がいる場合は、ご意見をお待ちしております。ありがとう！
更新：答えがあると思います。スーパーコンピュータにかかる時間は関係ありません。ここで重要なのは、PC が並行して実行されることです。pi = <5, 7, 17, 8, 10> の最初の例から、si = <8, 5, 1, 12, 9> を追加しましょう。デフォルトのソートされていない順序では、処理時間は <13, 20, (8 + 5 + 1 + 17 = )31, 34, 45> になります。したがって、45 は完了の時間です。パイが減少するソート順を想定します。出力は次のとおりです。<18、20、30、34、40>。[ソートされた入力: pi = <17, 10, 8, 7, 5>, si = <1, 9, 12, 5, 8>].
おそらくすべてをクリアする例を次に示します: si = <17, 10>, pi = <10, 17>. ソートされていない場合 (si の降順でソートされていることもあります) の出力は、<27, 44> になります。pi に基づいてソートすると、入力は si = <10, 17>、pi = <17, 10> になります。出力は <27, 37> です。PC は並行して実行されるため、最短のジョブを最後に送信する必要があります。