JSPの問題構造と計算時間の解析

スケジューリング問題は,限られた資源とこなさなければならない複数の仕事が存在する際に,どの仕事をどの資源にどの順序で割り当てた場合に最も効率的なスケジュールとなるかを求める問題です.この問題は工場における生産スケジュールや荷物の配送スケジュール,果ては毎日の料理の作成スケジュールなど身近に多数存在しています.
そのスケジューリング問題の代表的なモデルとして,ジョブショップスケジューリング問題(Job-shop Scheduling Problem,JSP)があります.
JSP は種類の仕事に対して種類の機械により処理する場合に,全体の処理時間(makespan)を最小化するための処理スケジュールを求める問題です.各仕事を処理する機械の順序(技術的順序)とその時の処理時間はあらかじめ問題条件として与えられています.
下図はJSPの仕事の数が3,機械の数が3の問題例と,それに対する全体の処理時間が14となるスケジュール例です.
 
 
 
JSPの探索では,主に機械上での処理順序を並べ替えながら,全体の処理時間が小さくなるスケジュールを探索していきます.下図はある探索法においてJSPを探索した経過です.初期の状態から徐々に空白が少なくなり,全体として左に詰められて行きます.
 

 
この研究では,JSPの問題構造に着目し,その特性からより良い探索法につながることを目指しています.JSPの問題構造として,事前に与えられるのは仕事の数や機械の数です.この仕事の数と機械の数の比率によってJSPの問題を分類し,探索に用いるパラメータの調整に繋がる傾向が観測できました.