特許
J-GLOBAL ID：200903080515246834
ジョブショップスケジューリング装置
発明者：
出願人/特許権者：
代理人 (1件)：
三好 秀和 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平6-073445
公開番号（公開出願番号）：特開平7-282144
出願日： 1994年04月12日
公開日（公表日）： 1995年10月27日
要約：
【要約】【目的】 複雑な制約を持ち総作業時間を最小とするような大規模なジョブショップスケジューリング問題の準最適解を、組み合せ爆発を起こすことなく高速に求めることができるジョブショップスケジューリング装置を提供する。【構成】 入力部1から問題データおよびパラメータが入力されると、初期個体集団生成部2がP個のランダムな個体を生成し、生成された初期個体集団はメモリ7に格納される。交叉処理部5がメモリ7上の個体集団から高い評価値に応じて2つの個体を選択し、このペアをスケジュール計算部4に入力として与え、スケジュール計算部4から出力として新しい個体を受け取る。個体集団更新部6が評価値をもとに個体集団の更新を行い、その結果新しい個体集団を得て、メモリ7に格納する。個体集団更新部6による個体集団の更新の結果、終了条件を満たしているか否かをチェックし、満たしていたならば、メモリ7上の個体集団を出力して全ての処理を終了する。
請求項（抜粋）：
複数の機械上で所定の順序で所定の加工時間をかけて処理されるべき複数の作業から構成される仕事が複数個与えられたとき、全仕事の作業時間の総和が最小に近くなるように作業の処理順序を決定するジョブショップスケジューリング装置において、各仕事に関して、作業を実施する機械と作業終了時刻の組を作業順に並べたリストを内部状態に持つ個体を解として表現し、各仕事中の各作業の処理順序である技術的順序、該作業を処理する機械、該機械上での該作業の加工時間を予め与え、前記技術的順序が最も早い作業の集合cを求め、集合c中の作業に対して、作業の完了時刻の初期値として該作業の加工時間を設定し、最も完了時刻が早い作業を求め、該作業と同一機械上で処理され、かつ加工時間帯が重複する作業の集合をコンフリクト集合として求め、該集合中の任意の作業aを選んでスケジュール化し、集合cから作業aを取り除き、代わりにもしあれば該作業の技術的順序が次の作業bを加え、作業bを処理する機械上でスケジュール済みの最後の作業の完了時刻と、作業aの完了時刻tの大きい方に、作業bの加工時間を加えたものを作業bの完了時刻とし、もし集合c中で作業aと同一の機械上で処理される作業の完了時刻が完了時刻tと該作業の加工時間との和t’より早い場合は該作業完了時刻をt’に変更し、未スケジュールの作業がなくなるまで上記の処理を繰り返すという Giffler & Thompson によるアクティブスケジュール生成法により有限数の初期個体集団を作成する初期個体集団生成部と、0から1の間の値を有する突然変異率を予め定め、個体の総作業時間を評価値として定め、該評価値の高いものから前記初期個体集団の中から2つの個体X,Yを選択し、一方の個体Xに対して、作業の完了時間が総作業時間に一致する作業に至る経路である最長経路上にある作業を特定する第1のステップと、前記コンフリクト集合を求め、0から1の間の乱数を発生させ、該乱数値が前記突然変異率より小さい場合は、該コンフリクト集合の中から任意の1個を選択して、次の処理対象とし、それ以外の場合は、個体Xの最長経路上にある作業の個数が該コンフリクト集合中の作業数の半数以上を占めたら、個体Yを選択し、半数に達しなかったら個体Xを選択し、該コンフリクト集合中の作業の中で、選択した個体中での処理順序が最も早い作業を次の処理対象とする第2のステップとを備え、第1のステップを実行後、第2のステップをスケジュール化が完了するまで繰り返し、完成した該スケジュールを内部状態に持つ新規個体を最終解の候補として作成する交叉処理部と、前記新規個体の評価値を測定し、前記初期個体集団中の最低の評価値を持つ個体の評価値と比較し、前者の評価値が後者の評価値より優れていれば、後者と前者を入れ替えて前記初期個体集団を更新する個体集団更新部と、予め定めた繰り返し回数に達するか前記初期個体集団中の個体が全て同一の個体になったという終了条件を予め定め、該終了条件が満足されない場合は、前記スケジュール計算部と前記個体集団更新部の処理を繰り返す制御部とを有することを特徴とするジョブショップスケジューリング装置。
IPC (2件)：
FI (2件)：
G06F 15/21 R
, G05B 15/02 S
