JSSP シミュレータ 解説
- JSSP シミュレータとは
GA を用いてスケジューリング問題（Job shop scheduling problem, JSSP）を解くことができます。概観は以下のとおりです。
スケジュリング問題（JSP）について
- ある決まった数のタスクを定められた順番で処理してゆく「仕事」（以下Job）がいくつか用意されています。
- Jobに応じてタスクの順番が決まっています。またひとつのタスクにかかる時間も定義されています。
- ひとつのタスクはひとつの機械で処理されます。
- 各Jobに定められたタスクの順番を守りながら、対応する機械にタスクを割り当ててゆき、 いくつかのJob を最短の時間で終わらせるように機械の稼動スケジュールを立てるのがJSPです。 ひとつのJobにおける機械の数や、Jobの数が多くなると探索空間が広くなり、最適な解を見つけるのは困難になります。
JSSPシミュレータの仕様
- JSPとしてJob数50,機械数50までを扱えます。
- 問題の設定は問題を記述したファイルを読みこむことで行います。
- 解の探索にはGAを用います。個体数の上限は2000、世代数の上限はlong intの大きさです。 遺伝的操作として、交叉、突然変異、エリート保存を行います。
- 染色体はJob番号の並びによって表現されます。Jobによって処理する機械の番号が分かっているので、 Job番号を染色体の頭から読み込んでいけば、そのJob番号の出現回数によって次に処理する機械番号を知ることができます。 読み込んだ順に、制約を満たすように機械にスケジュールを配置してゆくことで全体のスケジュールが一意に決まります。
- 適合度の値は、全Jobの完了時間にしてあります。
- 親の選択にはルーレット、トーナメント、ランダムが選択できます。
- 交叉は2点交叉を行います。上述の染色体の表現方法では、各Job番号が決まった数（機械数）だけ出現しなければならないので、 交叉点間で同じJob番号が存在するときは、位置を保存して相手の子に移し、あとは自分の子の染色体の空いたところに移します。
- 突然変異は同一個体内で、遺伝子（＝Job番号）の位置を入れ替えるようにします。
- 結果は最も早い世代に出た最良成績の個体について表示しています。