JPH03172964A - 計画作成装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ジョブショップ問題やプロジェクト計画問題
のように、仕事と工程とそして各仕事の各工程における
作業とが与えられ１　さらに、各仕事における工程間の
先行関係が与えられたとき分枝操作と限定操作を繰り返
すことによって前記作業を順次割り付け、最終的に計画
を立てるようにする計画作成装置に関する。

〔従来の技術〕

ジョブショップ問題やプロジェクト計画問題を解くため
に１分枝限定法を用いる場合が多い。分技限定法は探索
法の１つである。探索法では、探索木を構成し、探索木
の各節点で、既に割り当てた作業の部分計画に対して未
割り当て作業の１つを割り当てて、新しい節点を作成し
てい（。

分枝限定法では１分枝操作と限定操作とを繰り返すこと
によって解を取得する０分枝操作とはどの節点から分枝
するかを決め、該節点に対して未割り当て作業のうちど
れを割り当てるべきかを判断し、新しい節点を作成する
操作である。限定操作とは、評価値の悪い節点からの分
枝操作を禁止する操作である０分枝限定法では、以下の
操作で計画を作成する。

■　作業が何も割り当てられていない節点を作成する。

■　新節点の下界を評価する。

■　さらに新しい節点を作成するか判断する。新節点の
作成が不要ならば処理を終える。

■　展開すべき節点を選択する。

■　展開すべき節点に対して０次に割り当てる作業を選
択する。

■　次に割り当てる作業について、新節点を作成し、■
へいく。

従来、探索を効率よく行う手法として、特願平１−２５
２７６１号がある。同特許願では、■の次に割り当てる
作業の選択に特徴がある０次に割り当てる作業の選択の
ステップは以下である。

■　展開すべき節点に対して３作業を割り当てることが
できる工程を調べ、該工程への割り当て可能作業を示す
競合作業集合表を作成する。

■　競合作業集合のうち１割り当て可能作業の数が少な
い工程の競合作業集合を次の割り当てる作業とする。

上記操作を例で説明する。第６図は、ジョブショップ問
題の例である０表中の数値は処理時間を示す、各仕事の
先行関係は、すべて工程３の前に工程２の処理が必要で
あり、工程２の前に工程ｌの処理が必要である。数値が
空欄の工程はスキップされる０本問題を「遅れあり」計
画とし、目的を「総所要時間最小化」とした場合の最適
解の１つを第３図に示す、「遅れあり」計画とは、ある
工程が作業を処理できる状態にあり、かつ、ある作業が
該工程で処理可能な状態であったとしても。

わざと該工程に待機時間を作り他の作業を先に処理する
ことが許される計画である。

具体例で、「遅れあり」計画における競合作業集合表の
作成方法を示す。展開すべき節点として。

作業ｅｌ、ｄｉ、ｃｌが割り当てられて、第３図図示の
部分計画をもつ節点とする。

■　節点の未割り当て作業を１割り当て可能作業と割り
当て不可作業とに分類する。結果は第７図図示のものと
なる。

■　各未割り当て作業について、他の未割り当て作業に
阻害されないとして２作業の開始時刻と完了時刻とを求
める。結果は第８図図示のものとなる。表中ハイフォン
は１割り当て済み作業を示す。

■　各工程について１割り当て可能作業の完了時刻の最
小値を取得する。第９図に示すように例えば、工程Ｉで
はＩ９となる。

■　各工程について、上記最小な完了時刻よりも小さな
開始時刻をもつ未割り当て作業を抽出する。第９図に示
すように例えば、工程１では。

ａｌとｂｌとになる。

■　上記抽出された未割り当て作業に１割り当て不可作
業を含まないならば、Ｕ合作業集合とする。第９図に示
すように２例えば、工程３では。

割り当て不可作業ｄ３を含むので、工程３に作業を割り
当てることはできない。

特願平１−２５２７６１号を利用した場合の第６図図示
の例題に対する探索木を第４図に示す。図中。

上段左の記号は割り当てた作業を示す。ただし。

ｒｏｏｔは何も割り当てられていない状態を示す。

図中、上段の右の括弧内の数値は総所要時間の下界を示
す、下段の左の値は節点の識別番号である。

下段の右の値は展蘭すべき節点として選択した順序を示
す０図の見方は以下である０節点から下に延びる罫線の
先の節点の記号が割り当てられた作業を示す０例えば、
　　ｒｏｏｔからｅｌへの関係は。

何も割り当てられていない状態の下で１作業ｅ１を割り
当てたことを示す。探索に当たって、以下の２点を戦略
として採用している。

■　下界は、仕事基準と工程基準との両者から評価する
。

■　展開すべき節点の選択では、最良な下界をもつ節点
とする。本節点が複数あれば５割り当て済み作業の数が
多い節点とする。

〔発明が解決しようとする課題〕

従来技術では、下界が成長しないで探索木が大きく広が
り、探索木の深い段階で作業を割り当てると、全節点で
の下界が成長する場合に問題がある。第４図では、最初
の節点ｌの下界は３１であるので、総所要時間３１の計
画の可能性があるとの立場から探索を行う。そして、破
線で示す上部の探索を終えると下界の鰻小値は３２であ
るので。

総所要時間３２の計画の可能性を探って、最適解を得る
。

このように、探索木の深い段階で、全節点の下界が成長
すると、探索木が大きく広がっているので、早く解を得
ることができない。

本発明は１探索木の深い段階で全節点の下界が成長する
ような問題に対しても、早く解を得るべく探索すること
を目的とする。

〔課題を解決するための手段〕

探索木の深い段階で全節点の下界が成長するような問題
に対しては、各仕事の作業間の先行関係をまったく逆に
した対称問題を作成し、対称問題で探索を行えば、下界
が探索木の浅い段階で成長するので、早く解を得ること
ができる。

第５図は、実際に行った第６図図示の対称問題に対する
探索木を示す。図の見方は第４図と同じである。第５図
の探索木は第４図のそれと比べて格段に小さいことがわ
かる。第５図の探索木が小さい原因は、探索木の浅い段
階で下界が成長しているからである。

しかしながら、与えられた元の問題の下界が。

必ず探索木の深い段階で成長するとは限らない。

探索木のどの深さで下界が成長するかはわからない、そ
こで１本発明では１元の問題に対する探索と、対称問題
に対する探索とをほぼ均等に行う。

両者の探索はほぼ均等に行うことで、下界の成長がどの
ようであったとしても、どちらか一方の探索木は、探索
の早い段階で下界が成長する。よって、探索木の爆発的
な広がりの危険が防がれる。

本発明は１元の問題に対する探索と、対称問題に対する
探索とをほぼ均等に行うために、以下の機能をもつ。

■　元の問題に対して、各仕事における工程間の先行関
係をまったく逆にした対称問題を作成する対称問題作成
部。

■　元の問題に対して、探索木を構成し計画を立てる元
問題探索部。

■　対称問題に対して、探索木を構成し計画を立てる対
称問題探索部。

■　元問題の探索木の成長と対称問題の探索木の成長と
が一方に偏らないように１両者の探索木の成長を制御す
る探索木成長管理部。

〔作　用〕

まず対称問題探索木が働き１元の問題に対して。

各仕事における工程間の先行関係をまったく逆にした対
称問題を作成する。

次に、探索木成長管理部が働く２元問題の探索木の成長
と対称問題の探索木の成長が一方に偏らないように５両
者の探索木の成長を制御する。すなわち１元問題探索部
あるいは対称問題探索部に対して、ある一定サイクルの
探索を行うように交互に指示する。すると、指示された
元問題探索部あるいは対称問題探索部は、ある一定サイ
クルの探索を行い、探索が終了したか否かの返答を探索
木成長管理部へ送る。

探索木成長管理部は、探索が終了していなければ、前回
指示した探索部とは逆の探索部に対して探索を指示する
。こうして探索を行う。

〔実施例〕

第１図は２本発明のブロック構成を示す。

図中１は２元の問題に対して、各仕事における工程間の
先行関係をまったく逆にした対称問題を作成する対称問
題作成部。

図中２は２元の問題に対し°Ｃ１探索木を構成し計画を
立てる元問題探索部 図中３は、対称問題に対して、探索木を措成し計画を立
てる対称問題探索部。

図中４は２元問題の探索木の成長と対称問題の探索木の
成長が一方に偏らないように２両者の探索木の成長を制
御する探索木成長管理部。

図中５は１元問題探索部２あるいは対称問題探索部３の
指示を受けて、実際に探索を行う探索共通部である。

探索共通部５には、新節点を作成しその部分計画を成長
させる新節点作成部１３　、新節点の下界を評価する下
界評価部１４　、展開すべき節点を選択する展開節点選
択部１１　、展開すべき節点に対して次に割り当てる作
業を選択する次割当て作業選択部１２がある。

例題として、第６図図示のジ目ブショップ問題を取り上
げる。

まず、対称問題作成部１が働く。元の問題に対して、各
仕事における工程間の先行関係をまったく逆にした対称
問題を作成する。本処理は１元の問題を与えるデータ構
造に依存する。ここでは問題のデータ構造として、各仕
事の定義が以下のリストからなるとする。

（仕事名　各作業の処理時間と工程を示すリスト各作業
の先行関係） 例えば、第６図図示の仕事ａは以下のデータ構造とする
。

（ａ（（ａｔ　　３　　工程１）（ａ２３　　工程２）
（ａ３２　工程３））（ａｌ　　ａ２　　ａ３））この
ようなデータ構造では、リストの３番目の要素である（
ａｌ　　ａ２　　ａ３）の順序を逆にするだけでよい。

次に、探索木成長管理部４が働き８元問題探索部２と対
称問題探索部３との両者に対して、探索の準備を指示す
る。

探索の準備を指示された元問題探索部２と対称問題探索
部３とは、それぞれ、以下の処理を行う。

■　何も作業が割り当てられていない節点を作成しその
下界を評価する。

■　展開すべき節点のリストを上記節点とする。

本例では、第４図、第５図でわかるように、下界３１を
もつ節点ｌが作成され１節点１が展開すべき節点のリス
トとなる。

次に探索木成長管理部４が働く１元問題の探索木の成長
と対称問題の探索木の成長とが一方に偏らないように１
両者の探索木の成長を制御ｎする。

すなわち１元問題探索部２あるいは対称問題探索部３に
対して、ある一定サイクルの探索を行うように交互に指
示する。ここでは８元問題探索部２への指示から始める
ものとする。

探索を指示された元問題探索部２が働く。ある一定サイ
クルの探索を行う、一定サイクルの探索をここでは、以
下とする。

■　展開すべき節点を選択する。

■　該節点に対して次に割り当てる作業を選択する。

■　次に割り当てる各作業について、新節点を作成しそ
の下界を評価する。

■　探索木と展開すべき節点のリストを維持管理する。

上記一定サイクルの探索のうち１元問題探索部２では、
■の探索木と展開すべき節点とのリストを維持管理する
。■から■の処理は、探索共通部５に対して展開すべき
節点のリストを渡して処理を依願する０本例では、最初
、展開すべき節点のリストは節点１である。

依願された探索共通部５は、一定サイクルの探索で示し
た■から■の処理を行う。

■　展開節点選択部１１が働き、展開すべき節点のリス
トから展開すべき節点として節点ｌを選ぶ。

■　次割当て作業選択部１２が働き、該節点に対して次
に割り当てる作業として、ａｌ、ｂｌ。

ｃｌ、ｄｉ、ｅｌを選ぶ。

■　新節点作成部１３と下界評価部１４とが働く。

次に割り当てる各作業について、新節点を作成しその下
界を評価する。例えば、第４図に示すように、ａｌを割
り当てると下界３３の新油点３が作成され、ｂｌを割り
当てると下界３５の新油点４が作成される。

そして、以下の情報を元問題探索部２に返す。

■　選ばれた展開すべき節点、ここでは節点ｌ。

■　新油点とその下界２節点２の３１　、節点３の３３
など。

元問題探索部２では、探索木と展開すべき節点のリスト
を維持管理し、探索を終了するかを判断し判断結果を探
索木成長管理部４に返す、探索木の管理は、順次新節点
を格納することである。展開すべき節点のリストは以下
で管理する。

■　選ばれた展開すべき節点を、展開すべき節点のリス
トから除く、ここでは２節点ｌを除き空になる。

■　新油点に全作業が割り当てられていなければ。

展開すべき節点のリストに追加する。ここでは節点２か
ら節点６が追加される。

■　新油点に全作業が割り当てられているものがあれば
、今までに求めた計画のうち最良な下界を求める。全最
適解を求めるのであれば、該下界よりも大きな下界をも
つ節点を展開すべき節点のリストから除く、最適解の１
つを求めるのであれば、該下界以上の下界をもつ節点を
展開すべき節点のリストから除く、ここでは、全作業が
割り当てられている新油点はない。

探索終了の判断は、展開すべき節点のリストが空であれ
ば、探索終了となる。ここでは、展開すべき節点のリス
トに節点２から節点６があるので。

探索続行との返事を探索木成長管理部４に返す。

探索木成長管理部４では、探索続行との返事から、今度
は対称問題探索部３に対して探索を指示する。

対称問題探索部３では９元問題探索部２と同じ処理を行
う、違いは、管理している探索木と展開すべき節点のリ
ストである０元問題探索部２のときと同じく、展開すべ
き節点のリストを節点ｌとして、探索を探索共通部５に
依頼する。

探索共通部５は、依頼に応じて探索を行い、以下を返答
する。

■　選ばれた展開すべき節点、ここでは節点ｌ。

■　新油点とその下界、ここでは第５図に示すように節
点２の３３１節点３の３１など。

対称問題探索部３では３元問題探索部２と同じく、探索
木と展開すべき節点のリストを維持管理し、探索を終了
するかを判断し判断結果を探索木成長管理部４に返す。

展開すべき節点のリストは節点２から節点５となり、探
索続行との返事を探索木成長管理部４に返す。

探索木成長管理部４では、探索続行との返事から、今度
はまた９元問題探索部２に対して探索を指示する。こう
、したことを繰り返し、１３回目の対称問題探索部３へ
の探索指示が行われたとする。

対称問題探索部３が、探索共通部５に探索を依頼すると
、その返答は第５図でわかるように、以下となる。

■　選ばれた展開すべき節点１節点２２゜■　新油点と
その下界１節点２４の３２゜節点２４には、全作業が割
り当てられている。

最適解の１つを求める場合、該下界の３２以上の下界を
もつ節点を展開すべき節点のリストから除く、すると、
展開すべき節点のリストは空となる。

よって、探索終了との返事を探索木成長管理部４に返す
。

これにより、探索は終了する。

１３回目までの探索で作成された節点の数は。

元の問題の探索木では、第４図の太線より上にある節点
であり、　　３０個の節点がある。対称問題の探索木で
は、第５図の太線より上にある節点であり、２４個の節
点がある０合計５４節点である。

もしも８本問題を元の問題からのみ解くとすると。

第４図から３５サイクルの探索が必要であり６３個の節
点ができる０本発明と従来技術との探索効率を比較する
。探索のサイクルからみると１３の２倍は３５より小さ
い０作成された節点からみても、５４個は６３個よりも
小さい、よって１本発明の探索が優れる。

以上の説明では、「遅れあり」計画とした。しかし、「
遅れなし」計画であっても、探索共通部５で次に割り当
てる作業を選ぶ処理が異なるたけである。他の処理は同
じであり、効果は同じように期待できる。「遅れなし」
計画とは、ある工程が作業を処理できる状態にあり、か
つ、ある作業が該工程で処理可能な状態であったとした
ら　わざと該工程に待機時間を作ることが許されない計
画である。

今回は、探索の実行を探索共通部５で行った。

しかし２元問題探索部２と対称問題探索部３がそれぞれ
個別の探索機能を持っても、同し効果が期待できる。

ここで扱ったジョブショップ問題はｒＮＰＪ完全問題と
言われ、探索木の深い段階はど、探索木が爆発的に広が
っている。探索木の深い段階で全節点の下界が成長する
ような最悪ケースの場合でも、対称問題の探索から早く
解を求めることができる。

〔発明の効果〕

本発明によれば９元の問題に対する探索と、仕事の先行
関係を逆にした対称問題に対する探索とをほぼ均等に行
う。両者の探索をほぼ均等に行うことで、下界の成長が
どのようであったとしてもどちらか一方の探索木は、下
界が早く成長する。

よって、探索木の爆発的な広がりの危険が防がれる。

本発明では、最悪ケースにおける解の取得時間が大幅に
向上する。従来、実用時間内で解けないような問題であ
っても、解くことができる。この効果は大きい。

【図面の簡単な説明】

第１図は計画作成装置のブロック構成、第２図は第６図
の問題に対する最適解の一例、第３図は部分計画の例、
第４図は元の問題に対する探索木。 第５図は対称問題に対する探索木、第６図はジョブショ
ップ問題の例、第７図は作業の分類例、第８図は作業時
刻の例、第９図は競合作業集合表の例を示す。 図中、■は対称問題作成部、２は元問題探索部。 ３は対称問題探索部、４は探索木成長管理部を表す。

Claims (1)

1. 【特許請求の範囲】 仕事と工程とそして各仕事の各工程における作業とが与
   えられ、さらに、各仕事における工程間の先行関係が与
   えられたとき、 探索木を構成し、展開可能な探索木の１つの節点を選択
   する操作と、選択された節点から次に割り当てる作業を
   選択して新しい節点を作成する操作とを繰り返すことに
   よって、 最終的に計画を立てる計画作成装置において、元の問題
   に対して、各仕事における工程間の先行関係をまったく
   逆にした対称問題を作成する対称問題作成部と、 元の問題に対して、探索木を構成し計画を立てる元問題
   探索部と、 対称問題に対して、探索木を構成し計画を立てる対称問
   題探索部と、 元問題の探索木の成長と対称問題の探索木の成長が一方
   に偏らないように、両者の探索木の成長を制御する探索
   木成長管理部 とを備える ことを特徴とする計画作成装置。