Pat

J-GLOBAL ID：200903097175583989

ジョブショップスケジューリング問題解決方式

Inventor： 山田 武士
Applicant, Patent owner： 日本電信電話株式会社
Agent (1)： 鈴木 誠
Gazette classification：公開公報
Application number (International application number)：1992029220
Publication number (International publication number)：1993225203
Application date： Feb. 17, 1992
Publication date： Sep. 03, 1993
Summary：

【要約】【目的】 ジョブショップスケジューリング問題へ遺伝アルゴリズムの適用を可能にして、大規模な問題の良質な解を高速に求める。【構成】 問題データ、遺伝アルゴリズムのパラメータを入力部1から入力する。問題の解を遺伝アルゴリズムで用いられる個体で表現し、各個体の評価を、各個体の成分の最大値(総作業時間)で表わす。まず、初期個体群生成部2で初期個体群を構成するランダムスケジュールを生成する。個体群を淘汰処理部5で淘汰し、終了条件を満足しない場合、交叉処理部4が個体群を二個体ずつペアにしてスケジュール計算部3へ与え、該スケジュール計算部3から新しい個体とその評価値を得る。この処理を個体群の全ての個体のペアに対して繰り返し、淘汰処理部5の処理に戻る。各部の動作の制御は制御部7が司どる。

Claim (excerpt)：

複数の機械上で、定められた順序で、定められた時間をかけて処理される複数の仕事が与えられた時、その総作業時間を最小にする問題の準最適解を自動的に求める方式であって、解を各機械上での各仕事の処理である作業の終了時刻のリストを内部状態に持つ個体で表現して、ランダムに初期個体群を生成する手段と、初期個体群あるいは処理途中の個体群の各個体を二つずつペアにして選び、それを元に部分スケジュールを生成し、該部分スケジュールに対して次にスケジュールすべき作業の候補の集合を決定し、この候補の集合から先に選ばれた二個体の情報に基づいて次にスケジュールすべき作業を決定する操作を、スケジュールが完了するまで続けて、新たな二つの個体を出力する手段と、前記初期個体群あるいは出力された個体群を評価値に基づいて淘汰して準最適解を得る手段とを有することを特徴とするジョブショップスケジューリング問題解決方式。

IPC (2)：

G06F 15/21 ,  G06F 15/20