特許

J-GLOBAL ID：200903016127437580

ジョブショップスケジューリング装置

発明者： 山田 武士
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 三好 秀和 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平8-086788
公開番号（公開出願番号）：特開平9-282359
出願日： 1996年04月09日
公開日（公表日）： 1997年10月31日
要約：

【要約】【課題】 複雑な制約を持ち、総作業時間を最小にするような大規模なジョブショップスケジューリング問題の準最適解を遺伝的アルゴリズムを用いて組み合わせ爆発を起こすことなく高速に求めることができるジョブショップスケジューリング装置を提供する。【解決手段】 遺伝的アルゴリズム中の個体集団から選択された2個体(両親)に基づき新しい個体を生成する交叉手続きにおいて一方の親のクリティカルブロック近傍から評価値の優れた個体を確率的に選択し、しかもその選択は他方の親と共通な性質を多く持つ個体ほど選ばれやすくなるようにバイアスをかけることによって、局所近傍探索と従来の交叉処理の利点をあわせ持つ新たな交叉である局所探索交叉と呼ぶ交叉手続きをもつ新しい遺伝的アルゴリズムを用いている。

請求項（抜粋）：

複数の機械上で、定められた順序で、定められた時間をかけて処理される複数の仕事が与えられた時、全仕事の作業時間の総和が最小に近くなるように作業の処理順序を決定するジョブショップスケジューリング装置において、各機械毎に、各機械上で処理される仕事の処理順序を表す順列である仕事名のリストによって解を表現し、有限個のランダムな解の集合である初期個体集団を生成する初期個体集団生成部と、初期個体集団あるいは処理途中の個体集団より評価値の良い個体ほど選ばれやすくなるようにバイアスをかけてランダムに2個体を選択する2個体選択部と、一方のスケジュールに対してスケジュール上の作業の部分列である最長経路を計算し、最長経路を同一機械で連続して処理される作業の集まりであるクリティカルブロック毎に分割し、各クリティカルブロック上の各作業を当該クリティカルブロックの先頭あるいは最後に移動させることによって新たに得られるスケジュール全体からなる集合であるクリティカルブロック近傍を計算し、クリティカルブロック近傍の各要素を他方の個体までの距離の短さでソートし、距離が短い個体の順位が高くなるように要素間に順位を付け、順位の高い要素が選ばれやすくなるようにバイアスをかけてランダムに要素を1つ選択し、その要素に対応するスケジュールを生成し、評価値を計算し、もしその評価値が元のスケジュールの評価値より良い場合は無条件にそのスケジュールを選択し、そうでない場合は評価値のよさに応じて確率的にそのスケジュールを選択し、そのスケジュールが選択された場合は元のスケジュールをそのスケジュールで置き換え、クリティカルブロック近傍を新たに計算し、再び他方の個体までの距離の短さでソートし、選択されなかった場合は対応する近傍の要素の順位を下げ、再び順位の高い要素が選ばれやすくなるようにバイアスをかけてランダムに要素を1つ選択するという操作を所定回数だけ繰り返し、この過程で得られた最も評価値の高い個体を最終的に出力する局所探索交叉計算部と、上記局所探索交叉計算部で生成された解が初期個体集団あるいは処理途中の個体集団中最低の評価値をもつ解よりも優れている場合は、後者を前者で置き換えることによって個体集団を更新する個体集団更新部と、予め定めた繰り返し回数に達するか、上記初期個体集団あるいは処理途中の個体集団中の全個体全て同一の個体になったという終了条件を定め、その終了条件が満足されない場合は、上記最長経路計算部から個体集団更新部までの各処理部の処理を繰り返す制御部とを有することを特徴とするジョブショップスケジューリング装置。