ｍ個のジョブをｎ台のCPUに分担する

質問

情報処理技術者試験の勉強会の時の、並列処理の話題だったんですが、誰も明快な答が出せなくて、ここに質問する事にしました。
どなたか知恵を貸して頂ければ、幸いです。
＜問題＞
ｍ個のジョブがあり、その処理時間はＴ０～Ｔｍである。
これをｎ台のＣＰＵで処理したときに、最短の時間で終わるようにスケジューリングしたい。
どういう手順で決めれば良いか？
ナップザック問題に近いように思えたんですが、ナップザク（ＣＰＵ）は一つではないし、最大で決まるのでもないので、それ以上知恵が出ませんでした。
＜例＞
例えば、ＣＰＵの台数ｎ＝４、ジョブの数ｍ＝１０で、Ｔ０～Ｔｍが、１，２，３，４，５，６，７，８，９，１０[s]であれば、
ＣＰＵ１に、１，３、１０：合計１５
ＣＰＵ２に、２，４，９：合計１４
ＣＰＵ３に、５，８：合計１３
ＣＰＵ４に、６，７：合計１３
１３～１５のばらつきはありますが、最長１５のこの組み合わせが全体としては最短の処理時間になります。
また、答はこの組み合わせ以外にもあります。

ナップザックであれば、重さの異なるｍ個の荷物があって、それらをｎ個のナップザックに、出来るだけ同じ重さになるように振り分ける問題と言い換えた方が分かりやすいかもしれませんね。

回答No.4

chirubou

えーと、No.2 さんのご指摘のようにこの問題が「NP困難」である、ということは、総当たりで全ての組み合わせを試してみる以外に最適解は得る方法はない、ということです。

実際、スケジューリングの世界では、NP 困難な場合、総当たり方式は現実的ではないため、適当な折り合いを付けて、言い換えればより簡単な「適当」なアルゴリズムを実装し、それで得られた解を準最適な解（と思って）それで良し、としています。

学術的（？）には、スケジューリングの準最適アルゴリズムをどう評価するかはすごく悩ましいのです。適当な分散をもったジョブの集合を作ってシミュレーションし、「××に比べて良い結果が得られた」なんて論文を書いたりしますが、そうすると「実際の運用ではそんなキレイな分散ではジョブが投入されないので、そんな結果は実用的ではない」なんて言われてしまいます。じゃあ、ということでどこからか持って来た実際のジョブの投入パターンを使ってシミュレーションすると、今度は「そのジョブ投入パターンはどの程度一般性があるのか」なんて文句が出て「じゃあどうすればいいんだぁー！」と叫びたくなってしまいます。つまりは何をやっても突っ込みどころ満載な訳です。これは元々が準最適という「ごまかし」なので避けようがないのです。えっと、これは思いっきり蛇足でした。

ということで、本当に最適な解を見つけるには全ての組み合わせをやってみるしかないですね。

お礼

私も、Webをあさってみましたが、おっしゃる通りのようですね。
ジョブの数がｍ個なら、総当りするとｍ！回計算することになります。
結果が出るのは確かですが、本来のジョブの実行時間より余計にかかる場合も有り得ますね。(笑)
ただ、この問題の場合は、
ＣＰＵ１に、１，３，１０：合計１５
と、
ＣＰＵ１に、３，１，１０：合計１５
は同じなので除外すれば、組み合わせの数は劇的に少なくなるはず。
というアプローチもありますね。
または、No1さんの方法で作っておいて、入れ替えて行く方法が現実的なような気がします。
いずれにしても、意外に難しい問題でした。

回答No.3

chirubou

No.2 さんのおっしゃる通り NP 困難のようですね。失礼しました。

メイクスパン問題という名前は知らなかったのですが、ジョブショップスケジューリング問題として良く知られた話でした。

お礼

ありがとうございます。
質問文の例題が単純過ぎたかもしれません。
9,9,6,6,5,5,4,4,4,2の場合
ソートして降順に、各ＣＰＵへ割り当てて行くと、次のようになり、最大15[s]となります。
CPU_1 9,4→計13
CPU_2 9,4→計13
CPU_3 6,5,2→計13
CPU_4 6,5,4→計15

でも、CPU_3の2番目のジョブ5と、CPU_4の1番目のジョブ6を入れ替えると、
最大14[s]であり、これが最適解ですね。
CPU_1 9,4→計13
CPU_2 9,4→計13
CPU_3 6,6,2→計14
CPU_4 5,5,4→計14

「ジョブショップスケジューリング問題」をキーワードに、Web検索したら、意外に難しい問題だと分かってきました。
スケジューリング学会なんて団体もあるんですね。

とりあえず、No1．のご回答の方法で並べたものを元にして、入れ替える方法で考えてみます。
入れ替えの方法は難しそうですから、お知恵を貸していただければ幸いです。

回答No.2

Tacosan

これは「メイクスパン最小化問題」という問題で, 詳細は確認していませんが NP-困難のようです＞#1.
とはいえ, この問題に関していえば「全てのプロセッサの処理能力が同じ」ということで問題が簡単になって, PTAS が存在するとか.
簡単にいくと, 「時間のかかるジョブから順に, 『そのジョブの終了時間が最も速い』プロセッサに割り当てる」アルゴリズムで 4/3 近似になるみたい.

参考URL：

http://www.nada.kth.se/~viggo/wwwcompendium/node181.html

お礼

＞「時間のかかるジョブから順に, 『そのジョブの終了時間が最も速い』プロセッサに割り当てる」
これが現実問題としては、最適な方法かもしれませんね。
なぜなら、ジョブの処理時間はあらかじめ予想できる場合はほとんどありませんから。

回答No.1

chirubou

もしジョブが並列処理で複数のCPUを使用するというのであれば、ナップザック問題と等価ですが、今回のジョブはCPUをひとつしか使わないので、NP困難ではないようです。

正解かどうかは分かりませんが、私ならこうします。

まずジョブを処理時間でソートしておきます。処理時間が長い方から順にnジョブをそれぞれ CPU_0 から CPU_n-1 に順番に割り当てます。次に CPU_n-1から CPU_0 の順で残ったジョブを降順ソートの順番で割り当てます。

さらにジョブが残ったら今度は CPU の並びを割り当てられたジョブのトータルの長さで昇順ソートしてから、上の操作を繰り返せば良いのではないでしょうか。

これが最短か？証明できるか／正しいかは分かりません。