ジョンソンのアルゴリズム

アルゴリズムの実装例としてジョンソンのアルゴリズムを取り上げる。

ジョンソンのアルゴリズムとは、 ある種のスケジューリングを行なう時のアルゴリズムである。 作業（ジョブ）は全部で N 種類ある。また、N 個の作業はすべて、２つの機械 X と Y によって、 X -> Y の順で加工されるものとする。 それぞれの作業の所要時間は異なる。 このとき、作業の最短時間はどのようになるかを求めるのがジョンソンのアルゴリズムである。

アルゴリズムは以下の通りである。 まず作業に対する機械の所要時間を表として表し、以下を繰り返す。

1. 表において、最も所要時間の短い作業の要素（作業の種類と機械）を探す。
2. その要素の機械が X ならばその作業を最初に位置付け、Y ならば最後に位置付ける。
3. 上記要素の作業の行を製品表から削除し、行がなくなれば終了、行があれば1.へ戻る。

製品表は下の欄に入れること。 １行にそれぞれ機械X,Yに要する時間を入力する。区切りはスペースで表す。

「計算」ボタンをクリックすると、解の欄に最短時間を実現する作業の順序を表示する。 ただし、作業の種類は、左の欄の最上段から順に0,1,2, ... と番号をふったものである。 １行に入っている数字が２個所でない場合、解の欄に"???"と表示される。

ここまで来れば、あとは所要時間を求めるだけとなる。これは次のように考える。 機械 Y が k 番め（k = 1...N ）の作業を開始できる時刻を S_Y(k)とする。この時刻は、

• 機械 X が k番めの作業を終了した時刻 S_X(k)
• 機械 Y が k - 1 番めの作業を終了した時刻T_S(k-1)

の遅いほう（早くないほう）になる。 機械 X が k 番めの作業を開始できる時刻は機械 X の k - 1 番目の作業が終了した時刻だから、 S_Y(k-1)と S_Y(k)のあいだには次の関係が成り立つ。

S_Y(k) = max(S_X(k) , S_X(k-1) + T_Y(k-1))

ここで T_Y(k-1)は、機械 Y の k - 1 番目の作業に要する時間を表す。

例 : 次のように入力する。

5 4
3 2
6 5
3 5
1 10

順序の欄には 4->3->2->0->1 と表示される。また、所要時間は 27 と計算される。

まりんきょ学問所 ＞ JavaScript 手習い ＞ ジョンソンのアルゴリズム