特許

J-GLOBAL ID：200903082288225135

ジョブショップスケジューリング方法

発明者： 山田 武士 ,  中野 良平 ,  ブルース イー.ローゼン
出願人/特許権者： 日本電信電話株式会社
代理人 (1件)： 三好 秀和 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平6-246093
公開番号（公開出願番号）：特開平8-110920
出願日： 1994年10月12日
公開日（公表日）： 1996年04月30日
要約：

【要約】【目的】 総作業時間を最小とする大規模なジョブショップスケジューリング問題の準最適解を高速に求めるジョブショップスケジューリング方法を提供する。【構成】 入力部1に問題データが入力され、初期解生成部2がランダムな解を生成し、最長経路計算部3が解スケジュールに対して最長経路を計算し、メモリ8に格納される。ブロック近傍生成部4が解スケジュールに対しブロック近傍を生成し、遷移選択部5がブロック近傍から1つの要素を選び、スケジュールを生成する。遷移受理部6が解スケジュールの評価値から新スケジュールの評価値を引いた値ΔEから受理確率を計算する。受理確率に基づいて新スケジュールが選択され、新スケジュールで置き換える。パラメータ更新部7が温度パラメータTをT:=γTと変更し、Tf が成り立つ場合は、終了条件を満足するためにメモリ上の解を出力し処理を終了させる。

請求項（抜粋）：

複数の機械上で所定の順序で所定の加工時間をかけて処理されるべき複数の仕事が与えられたとき、その総作業時間を最小にする作業のスケジュールを求める問題に対して、ある解から該解の近傍に属する他の解への確率的な遷移を繰り返すことによって解の品質を次第に改善するアニーリング法を用いるジョブショップスケジューリング方法において、現在の状態での解であるスケジュール上の最長経路と、該最長経路上の同一機械上の作業列であるクリティカルブロックを計算し、該クリティカルブロック内の作業を該クリティカルブロックの先頭あるいは最後に移動させる遷移を全て列挙することによって近傍を生成し、該近傍中からランダムに遷移を選択し、この選択された遷移を採用し、対応する解のスケジュールを生成し、該解により全ての作業が処理された場合、該解の評価値の、現在の状態での解の評価値からの差を計算し、該差が負である場合は無条件に新たに生成された解を現在の状態とし、正である場合はその差の大きさに応じた確率を計算し、該確率に応じて新たに生成された解を現在の状態とするかどうかを決定することを特徴とするジョブショップスケジューリング方法。