特許
J-GLOBAL ID:200903067679526980
フローショップスケジューリング装置,フローショップスケジューリング方法およびフローショップスケジューリング問題を解くプログラム記録媒体
発明者:
出願人/特許権者:
代理人 (1件):
小笠原 吉義 (外1名)
公報種別:公開公報
出願番号(国際出願番号):特願平11-081008
公開番号(公開出願番号):特開2000-271839
出願日: 1999年03月25日
公開日(公表日): 2000年10月03日
要約:
【要約】【課題】 大規模なフローショップスケジューリング問題の良質な解を高速に求めることができるようにする。【解決手段】 新たな解であるスケジュールが生成(6) される際,そのスケジュールの最長のクリティカルブロックの内部に相当する仕事をワイルドカードに置き換えた枝刈りパターンを生成し(7) ,それらを枝刈りリストとして保持する(8) 。各クリティカルブロックの内部に相当する仕事を外部に移動させることによって新たな解の候補の集合である解の近傍を生成(3) する際に,新たな解の候補が枝刈りリスト中のパターンとマッチするかどうかを調べ(4) ,マッチする場合には候補に含めないようにすることにより,探索の範囲を限定する。
請求項(抜粋):
複数の機械が定められた順序で,定められた時間をかけて複数の仕事を処理する際,処理される仕事の処理順序を工夫することによって,最初の作業開始から最後の作業終了までの時間である総作業時間をなるべく最小にし,その仕事の処理順序を決定するフローショップスケジューリング装置において,新たな解であるスケジュールが生成される際,直前に得られた解と比較して改善がみられた場合にそのスケジュールの最長のクリティカルブロックを計算し,解のスケジュールを表現する仕事名の順列において,このクリティカルブロックの内部に相当する仕事を全てワイルドカードで置き換えたものである枝刈りパターンを生成する手段と,初期解または処理途中で得られた解であるスケジュールについて,クリティカルパスとクリティカルブロックを計算し,各クリティカルブロックの内部に相当する仕事を外部に移動させることによって新たな解の候補の集合である解の近傍を生成する際に,新たな解の候補が,前記生成した枝刈りパターンとマッチするかどうかを調べ,マッチする枝刈りパターンがある場合には候補に含めないようにして探索の範囲を限定する手段とを備えることを特徴とするフローショップスケジューリング装置。
IPC (3件):
B23Q 41/08
, G05B 15/02
, G06F 17/60
FI (3件):
B23Q 41/08 A
, G05B 15/02 Z
, G06F 15/21 R
Fターム (16件):
3C042RH01
, 3C042RJ01
, 5B049AA06
, 5B049BB07
, 5B049CC11
, 5B049CC21
, 5B049EE03
, 5B049EE31
, 5B049EE37
, 5B049GG07
, 5H215AA06
, 5H215BB07
, 5H215BB11
, 5H215CC05
, 5H215CX01
, 5H215GG09
前のページに戻る