JPH03228175A

JPH03228175A - 計画作成装置

Info

Publication number: JPH03228175A
Application number: JP2023858A
Authority: JP
Inventors: Fumihiro Kimura; 木村　文宏; Yasuhiro Inooka; 猪岡　保裕
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1990-02-02
Filing date: 1990-02-02
Publication date: 1991-10-09

Abstract

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

Description

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

〔従来の技術〕

計画作成装置では、ジョブショップ問題やプロジェクト
計画問題を解くために、分枝限定法が用いられる場合が
多い。分枝限定法は探索法の１つである。

探索法では探索木を構成し、探索木の各節点で、既に割
り当てた作業の部分計画に対して末剤り当て作業の１つ
を割り当てて新しい節点を作成していく。この時、分枝
限定法は、分枝操作と限定操作を繰返すことによって解
を取得する。分枝操作とは、どの節点から分枝するかを
決め、該節点に対して、末剤り当て作業のうちどれを割
り当てるへきかを判断し、新しい節点を作成する操作で
ある。限定操作とは、評価値の悪い節点からの分枝操作
を禁止する操作である。本発明は分枝操作に係わるので
、以下では分枝操作について説明する。

従来、展開すべき節点が与えられたとき次に割り当てる
作業を選択する場合、効率的に探索を行う手法としては
、先に本出願人が提案した特願平１−２５２７６１号が
ある。そこでは以下のステップにて次に割り当てる作業
を選択している。

（１）展開すべき節点がもつ部分計画と各仕事の先行関
係に基づき、末剤り当て作業を割り当て可能作業と割り
当て不可作業とに分類した作業分類表を作成する６（２）部分計画と各仕事の工程間の先行関係に基づき、
各末剤り当て作業が他の作業に阻害されることなく順調
に処理されたと仮定した時に、各工程で処理が行われる
開始時刻と完了時刻を示す作業時刻表を作成する。

（３）作業時刻表と次に割り当てる作業の条件に基づき
、各工程毎に次に割り当てる作業を、作業分類表の割り
当て可能作業の中から抽出し競合作業集合表を作成する
。

（４）競合作業集合表に基づき、要素数の最も少ない競
合作業集合を１つ選択する。

上記操作を簡単な例で説明する。次に割り当てる作業の
条件として、最適解を保障した「遅れあり」計画とする
。［遅れありＪ計画とは、ある工程がどの作業も処理し
ていなくて処理可能な状態のとき、割り当て可能作業が
あったとしても、わざと該工程に遊び時＋！ｆｆを発生
させて他の作業を先に処理することが許される計画であ
る。

第２図は、ジョブショップ問題の例である０表中の矢印
は作業の先行関係を示す。また、カッコ内の数値は処理
時間を示している。本問題の目的を総所要時間最小化と
した場合の最適解を第３図に示す。

ここでは、具体例として、第４図のように作業ａ４．ｂ
ｌ、ｂ２．ｃ２が割り当てられた節点から分枝操作を示
す、上記（１）の操作により第５図の作業分類表が得ら
れる。また、（２）の操作により第６図の作業時間表が
得られる。第６図の数値中、左の数値が開始時刻、右の
数値が完了時刻を示す、（３）の操作による競合作業集
合表は第８図のようになる。第８図中、競合作業の下線
は割り当て不可作業を示す。本例の場合、工程１、工程
３、工程４への割り当てが可能である。（４）の操作で
は、第８図により各工程の競合作業集合の要素数は同じ
であるので、他の要因により競合作業集合を選択する。

例えば、工程に順序を付けて選択する。

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

複数の競合作業集合がある場合、どの競合作成集合を選
択するかによって、探索の効率が異なる。

効率よく探索を行うためには、下界の成長を促す競合作
業集合を選択することである。このために、先の特願平
１−２５２７６１号では、競合作業集合表の中から要素
数が最小なものを選択するようにしている。しかし、こ
れの問題点は、新しく作業を割り当てた節点の下界が成
長し、バックトラックが必要であったとしても、なんら
バックトラックの情報を反映しないで、それ以降の探索
を続けていることである。

従って２本発明の目的は、展開すべき節点が与えられた
とき次に割り当てる作業を選択する場合、バックトラッ
クの情報を利用してさらに効率よい探索を行う計画作成
装置を提供することにある。

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

上記目的を達成するために、本発明は、仕事と工程、各
仕事の各工程における作業、及び各仕事における工程間
の先行関係が与えられたとき、探索木を構成し、展開可
能な探索木の１つの節点を選択する操作と１選択された
節点から次に割り当てる作業を選択して新しい節点を作
成する操作とを繰返すことによって、最終的に計画を立
てる計画作成装置において、展開すべき節点に手順を割
り当てて新しく作成されたすべての節点の下界を評価し
、展開すべき節点の下界との比較からバックトラックが
必要か否かを判断し、新しく割り当ててた作業が処理さ
れる工程によりバックトラック表を維持管理する下界評
価部と、節点がもつ部分計画と各仕事の先行関係に基づ
き、未割り当て作業を割り当て可能作業と割り当て不可
作業とに分類した作業分類表を作成する作業管理部と、
部分計画と各仕事の工程間の先行関係に基づき、各未割
り当て作業が他の未割り当て作業に阻害されることなく
順調に処理されたと仮定した時に、各工程で処理が行わ
れる開始時刻と完了時刻を示す作業時刻表を作成する作
業時刻管理部と、作業時刻表と次に割り当てる作業の条
件に基づき、各工程毎に次に割り当てる作業を、作業分
類表の割り当て可能作業の中から抽出し、競合集合表を
作成する競合作業作成部と、競合作業集合表からバック
トラック表を利用して競合作業集合を決定する競合作業
決定部とを備えることを特徴とする。

〔作　用〕

ある節点の展開でバックトラックが必要になったのであ
れば、該節点とよく似た部分計画をもつ節点の展開でも
同じ理由によりバックトラックが必要になる可能性は高
い、そこで１本発明では、バックトラックが起きたとき
の割り当てられた作業が処理される工程を判断し、該工
程をバックトラック表に追加または削除することなどに
よりバックトラック表を維持管理する。そして、このバ
ックトラック表を利用して競合作業集合を選択する。こ
れによって、バックトラックが発生した工程を以降の探
索に反映することができ、効率よい探索が可能になる。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明による計画作成装置の一実施例のブロッ
ク図である。計画作成装置は、分枝操作を担う分枝操作
部１と、限定操作を担う限定操作部２に大別される。以
下では分枝操作部１について説明する。

分枝操作部１は、新しい節点を作成し下界を評価する新
節点作成部１１、展開すべき節点を選択する展開節点選
択部１２、次に割り当てる作業を選択する作業選択部１
３とからなる。新節点作成部１１には、競合作業集合３
２０の手順を元の展開すべき節点の部分計画に割り当て
、新節点を作る節点展開部２１と、各節点がもつ部分計
画と各仕事の先行関係に基づき、未割り当て作業を割り
当て可能作業と割り当て不可作業とに分類した作業分類
表２２０を作成する作業管理部２２と、部分計画と各仕
事の工程間の先行関係に基づき、各未割り当て作業が他
の未割り当て作業に阻害されることなく順調に処理され
たと仮定した時に、各工程で処理が行われる開始時刻と
完了時刻を示す作業時刻表２３０を作成する作業時刻管
理部２３と、新節点の下界を評価し、元の展開すべき節
点の下界との比較から、バックトラックが必要か否かを
判断し、新しく割り当てた作業が処理される工程からバ
ックトラック表２４０を維持管理する下界評価部２４と
が含まれる。また１作業選択部１３には、作成時刻表２
３０と次に割り当てる作業の条件に基づき、各工程毎に
次の割り当てる作業を、作業分類表２２０の割り当て可
能作業の中から抽出し、競合作業集合表３１０を作成す
る競合作業作成部３１と、競合作業集合表３１０から、
バックトラック表２４０を利用して、競合作業集合３２
０を決定する競合作業決定部３２とが含まれる。

具体的として、ここでも第２図のジョブショップ問題を
取り上げる。さらに、次に割当てる作業の条件も同じく
、最適解を保障した「遅れあり」計画とする。目的も同
じく総所要時間最小化とする。また、展開す入き節点の
選び方として、最良優先戦略を採用する。最良優先戦略
では、第１に下界が最小な節点を優先は、第２にすでに
割り当てた作業の数が最大な節点を優先する。さらにこ
こでは、バックトラック表２４０には、バックトラック
が発生した工程名を格納することとする。

全体の処理の流れは以下の通りである。

■　節点展開部２１が、作業が何も割り当てられていな
い節点であるｒｏｏｔを作成する。

■　作業管理部２２が１節点ｒｏｏｔの作業分類表２２
０を作成する。

■　作業時刻管理部２３が、節点ｒｏｏｔの作業時刻表
２３０を作成する。

■　下界評価部２４が、節点ｒｏｏｔの下界を評価し、
バックトラック表２４０を初期化する。

■　限定操作部２で、新節点をさらに作成するか判断す
る。不要ならば終える。

■　新節点を作成する必要がある場合、展開節点選択部
１２にて、展開すべき節点を選択する。

■　競合作業作成部３１にて、競合作業集合表３１０を
作成する。

■　競合作業決定部３２にて、次に割り当てる作業を決
定する。

■　節点展開部２１が、展開すべき節点の部分計画に作
業を割り当て新節点を作成する。

［相］　作業管理部２２が、新節点の作業分類表２２０
を作成する。

■　作業時刻管理部２３が、新節点の作業時刻表２３０
を作成する。

＠　下界評価部２４が新節点の下界を評価し、バックト
ラック表２４０を維持管理する。

■　■に戻る。

次に、第２図の例について詳述する。説明は、第４図の
部分計画をもつ節点を展開すべき節点として選択した段
階から行う。この段階でバックトラック表２４０は無デ
ータと仮定する。

第４図の部分計画における作業分類表２２０は、第５図
のように与えられる。この作業分類表は、作業管理部２
２によって、次のようにして作成されたものである。即
ち、作業管理部２２では、部分計画と各仕事の先行関係
に基づき、未割り当て作業を割り当て可能作業と割り当
て不可作業とに分類した作業分類表２２０を作成する０
分類は以下によって実行される。各仕事について、■　
先行関係から作業を順に並べた作業順リストを作成する
。

■　作業順リストから部分計画にある作業を取り除く。

■　作業順リストの先頭の作業を割り当て可能作業とし
、作業順リストの先頭以外の作業を割り当て不可能作業
とする。

例えば、仕事ａでは、作業順リストとして、（ａ４．ａ
３．ａ２）を作成する。第４図の部分計画にある作業ａ
４を取り除き、先頭の作業ａ３を割り当て可能作業とす
る。残りの作業ａ２を割り当て不可作業とする。

第４図の部分計画における作業時刻表２３０は、第６図
のように与えられる。この作業時刻表は、作業時刻管理
部２３によって、次のように作成されたものである。即
ち、作業時刻管理部２３では、部分計画と各仕事の工程
間の先行関係に基づき、各未割り当て作業が他の未割り
当て作業に阻害されることなく順調に処理されたと仮定
した時に、各工程で処理が行われる開始時刻と完了時刻
を示す作業時刻表２３０を作成する。これは以下によっ
て実行される。各仕事について、 ■　対象関係を割り当て可能作業とする。

■　対象作業の前作業の完了時刻Ｔ１を部分計画から取
得する。ただし、前作業がなければ、Ｔ１は■の進捗時
刻とする。

■　対象作業が処理される工程の部分計画から、すでに
割り当てられた作業の完了時刻の最大値Ｔ２を取得する
。本時刻を工程の進捗時刻とする。

■　Ｔ１とＴ２の最大値Ｔ３が開始時刻であり、Ｔ３＋
対象作業の処理時間が完了時刻Ｔ４である。

■　先行関係から対象作業を次作業とし、また、Ｔ　１
　＝Ｔ４として■から繰返す。

例えば、第４図の場合、仕事ａでは、割り当て可能作業
ａ３の前作業ａ４の完了時刻からＴ１＝Ｔ　５となる。

また、工程３の進捗時刻′１゛２はＯである。よって、
開始時刻Ｔ３は５であり、完了時刻゛■゛４は処理時間
５をたして１０である。次の作業ａ２では、Ｔｌ＝１０
、Ｔ　２　＝　５であるので、開始時刻は１０、完了時
刻は１４である。

第４図の部分計画における下界の評価は、下界評価部２
４によって、次のようにして与えられる。

ここでは、下界の評価に２種類を採用する。

１つは、仕事基準の下界である。これは、各仕事につい
て、部分計画と工程間の先行関係に基づき、未割り当て
作業が他の未割り当て作業に阻害されることなく順調に
処理されたと仮定した時に、全工程での処理を終える時
刻である。これは、作業時刻表２３０から、各仕事の完
了時刻の最大値で取得できる。第６図の例では１８とな
る。

他の１つは、工程基準の下界である。これは、各工程の
下界の最大値である。各工程の下界は以下の３つの合計
で得られる。

■　作業時刻表を利用して得られる最小な開始時刻 ■　未割り当て作業の当該工程での処理時間の合計 ■　未割り当て作業が、当該工程の後、他の未割り当て
作業に阻害されることなく最終工程を終えるまでの処理
時間の最小値第４図の部分計画の工程基準の下界は第７図のようにな
る。例えば、工程１では、最小開始時刻は３、処理時間
の合計は１６、終了までの最小加工時間はＯで、これら
より、工程１の下界は合計１９となる。

節点の下界は、仕事基準、工程基準両者の個々の下界の
最大値であり、１９となる。

いま、第４図の部分計画に対して、第５図の作業分類表
、第６図の作業時刻表、及び第７図の工程基準の下界等
はすでに与えられているとする。

さて、展開すべき節点が与えられると、次に割り当てて
る作業を決めるために、作業選択部１３が動作する。

まず、競合作業作成部３１が働く。競合作業作成部３１
では、作業時刻表２３０と次に割り当てる作業の条件に
基づき、各工程毎に９次に割り当てる作業を、作業分類
表２２０の割り当て可能作業の中から抽出し、競合作業
集合表３１０を作成する。ここでは、次に割り当てる作
業の条件が、最適解を保障した「遅れあり」計画である
ので、以下のように実行される。各工程について、■　
未割り当て作業を対象とし、最小な完了時刻をＴｍとす
る。

■　上記Ｔｍよりも小さな開始時刻をもつ未割り当て作
業を抽出する。

■　上記抽出した未割り当て作業がすべて割り当て可能
作成の場合、競合作業集合表に追加する。

結果の競合作業集合表３１０は第８図のようになる。例
えば、工程１では、最小完了時刻Ｔｍは第６図により７
となる。Ｔｍより小さい開始時刻をもつｄｌとｆｌが抽
出される。第５図よりｄｌとｆｌはともに割り当て可能
作業であるので、競合作業集合となる。これに対して、
工程２では、最小開始時刻Ｔｍは１２であり、Ｔｍより
小さい開始時刻をもつａ２と０２が抽出される。しかし
、第５図よりａ２もｅ２も割り当て不可能作業であるの
で、競合作成集合となりえない、こうして、作程１．工
程３、工程４への割り当てを行う競合作業集合表３１０
が作成される。

次に、競合作成決定部３２が働く、競合作成決定部３２
では、競合作業集合表３１０のうち、バックトラック表
２４０にある工程への競合作業集合を優先的に選択する
０本段階では、バックトラック表２４０は無データであ
るので、第８図より工程１、工程３、工程４の競合作業
集合を対象とし、他の要因、例えば要素数が最小な競合
作業集合を選択する０本例では、それでも同じであるの
で、さらに他の要因、例えば、工程に付けられた順序か
ら選択する。ここでは、工程３の競合作業集合（ａ３．
ｃ３）を選択したとする。

こうして、次に割り当てる作業が決まると、新節点作成
部１１が動作する。まず、節点展開部２１が働き、作業
ａ３を割り当てた部分計画をもつ節点を新規に作成する
。次に、作業管理部２２が働き、第４図の部分計画の場
合と同じようにして作業分類表２２０を作成する。さら
に、作業時刻管理部２３が働き１作業時刻表２３０を作
成する。

そして、下界評価部２４が働き、下界を評価する。

第９図に、作業ａ３を割り当てた部分計画の工程基準の
下界を示す。新節点の下界は２０である。

選択された競合作業集合にある他の作業Ｃ３についても
１作業ａ３と同じ処理がなされる。第１０図に、作業ｃ
３を割り当てた部分計画の工程基準の下界を示す。第１
０図より本節点の下界は２２である。

ところで、下界評価部２４では、個々の節点の下界を評
価するとともに、新規節点の下界が元の展開すべき節点
の下界と比べて成長したか判断し、バックトラック表２
４０の管理を行っている。本例では、元の展開すべき節
点の下界は第７図にわかるように１９であり、新規節点
の下界は第９図、第１０図より２０と２２であり、とも
に成長している。展開すべき節点の選択方法が最良優先
戦略であるので、すべての新規節点の下界が成長したと
きには、バックトラックをせざるをえない、そこで、本
例では割り当てた作業が処理される工程３をバックトラ
ック表２４０に追加する。よって、バックトラック表２
４０は工程３となる。もしも、作業ａ３か０３を割り当
てたどちらかの節点の下界が１９であったとしたら、バ
ックトラックの必要がないので、工程３をバックトラッ
ク表２４０から取り除く。

こうして、新節点が作成され、バックトラック表２４０
が管理されると、展開節点選択部１２が動作する。ここ
では、第１１図に示す部分計画をもつ節点が選択された
とする。

本節点には、作業管理部２２の働きにより、第１２図に
示す作業分類表２２０が作成される。また、作業時刻管
理部２３の働きにより、第１３図に示す作業時刻表２３
０が作成される。さらに、下界評価部２４の働きにより
、第１３図と第１４図かられかるように、下界として１
９が与えられる。

展開すべき節点が与えられると、次に割り当てる作業を
決めるために、作業選択部１３が再び動作する。

まず、競合作業作成部３１が働き、第１５図に示す競合
作業集合表３１０を作成する。第１５図より、工程１、
工程３．工程４への割り当てが可能である。

次に、競合作業決定部３２が働き、競合作業集合表３１
０のうち、バックトラック表２４０にある工程への競合
作業集合を優先的に選択する。本段階では、バックトラ
ック表２４０は工程３である。よって、工程３の競合作
業集合（ａ　３．　ｃ　３゜ｄ３）を選択する６本例で
は、これで決定する。

もしも、複数の競合作業集合が残れば、他の要因。

例えば要素数が最小な競合作業発会を選択する。

こうして、次に割り当てる作業が決まると、新節点作成
部１１が再び動作する。まず、節点展開部２１が、作業
ａ３を割り当てた部分計画をもつ節点を新規に作成する
。本節点の下界は、第１６図かられかるように２０とな
り、元の展開すべき節点の下界１９から成長している。

選択された競合作業集合にある他の作業Ｃ３とｄ３につ
いても、作業ａ３と同じ処理がなされる０本節点の下界
はそれぞれ、第１７図と第１８図からｂかるように２２
と２２であり、元の展開すべき節点の下界から成長して
いる。よって、工程３の競合作業集合を選択した結果、
バックトラックが必要なことが判明する。

先の特願平１−２５２７６１号の方法では、要素数が最
小な競合作業集合を選択するので、第１５図より工程４
の競合作業集合が選択される。しかし、工程４の競合作
業集合にある作業ｅ４を割り当てても、第１９図から分
かるように、下界は１９で成長しない。このように、工
程４の競合作業集合を先に選択すると、下界が成長しな
いので、効率よく探索が行えない。

第２図の例題に対する本発明の探索空間を第２０図に示
す。図中、上段の記号は割り当てた作業を示し、下段の
数値は下界を示す。ｒｏｏｔは何も割り当てられていな
い状態を示す。該探索木の見方は以下の如くである。節
点から下に延びる罫線の先の節点の記号が割り当てられ
た作業を示す。

例えば、ｒｏｏｔから０２への関係は、何も割り当てら
れていない状態に１作業ｃ２を割り当てたことを示す、
また、ｃ２から８４の関係は、作業ｃ２が割り当てられ
た状態に作業ａ４を割り当てたことを示す。第２０図で
は、全部で６９個の節点がある。一方、従来技術による
探索空間を第２１図に示す。図の見方は第２０図と同じ
である。

第２１図では、全部で７６個の節点がある。第２０図、
第２１図より、探索空間で比較して、本発明では７節点
分小さいことがわかる。

以上の説明では、次に割り当てる作業の条件を、最適解
を保障した「遅れあり」計画とした。しかし、最適解を
保障した「遅れないｊ計画としてもよい。「遅れない」
計画とは、ある工程がどの作業も処理していなくて処理
可能な状態のとき、割り当て可能作業があったとしたら
、わざと該工程に遊び時間を発生させて他の作業を先に
処理することが許されない計画である。本条件を満足さ
せるためには、以下のステップで競合作業集合表が作成
される。

■　作業時刻表に基づき、各工程毎に未割り当て作業の
中で最小な開始時刻を求める。

■　各工程毎に、上記最小開始時刻以下の開始時刻をも
つ未割り当て作業を抽出する。

■　各工程で、上記抽出した未割り当て作業の中に１割
り当て不可能作業が含まれないものを選ぶ。

また、以上の説明では、バックトラックが発生すれば、
工程名をバックトラック表に追加し、発生しなければ、
削除していた。しかし、バックトラックが発生した回数
をカウントしていく方法も考えられる。この場合は、競
合作業集合を選択する段階で、バックトラックが一番多
く発生した工程を優先して選択することになる。

〔発明の効果〕

以上説明したように、本発明によれば、バックトラック
が発生した工程を、以降の探索に反映しているので、展
開すべき節点が与えられたとき、次に割り当てる作業を
選択する場合、効率よい探索が行える効果がある。しか
も、バックトラックの情報を工程名等で管理するという
単純な方法で、効率よく探索できる。

【図面の簡単な説明】

第１図は本発明による計画作成装置の一実施例のブロッ
ク図、第２図はジョブショップ問題の一例を示す図、第
３図は第２図の最適スケジュールの一例を示す図、第４
図は部分計画の一例を示す図、第５図は第４図における
作業分類表を示す図。第６図は第４図における作業時刻表を示す図、第７図は
第４図における工程基準の下界を示す図、第８図は第４
図における競合作業集合表を示す図、第９図は第４図に
作業ａ３を割り当てた部分計画の工程基準の下界を示す
図、第１０図は第４図に作業ｃ３を割り当てた部分計画
の工程基準の下界を示す図、第１１図は別の部分計画を
示す図、第１２図は第１１図における作業分類表を示す
図、第１３図は第１１図における作業時刻表を示す図、
第１４図は第１１図における工程基準の下界を示す図、
第１５図は第１１図における競合作業集合表を示す図、
第１６図は第１１図に作業ａ３を割り当てた部分計画の
工程基準の下界を示す図、第１７図は第１１図に作業ｃ
３を割り当てた部分計画の工程基準の下界を示す図、第
１８図は第１１図に作業ｄ３を割り当てた部分計画の工
程基準の下界を示す図、第１９図は第１１図に作業ｅ３
を割り当てた部分計画の工程基準の下界を示す図、第２
０図は本発明による探索木を示す図、第２１図は従来技
術による探索木を示す図である。２２・・・作業管理部、　２３・・・作業時刻管理部、
２４・・・下界評価部、　３１・・・競合作業作成部、
３２・・・競合作業決定部、　２２０・・・作業分類表
、２３０・・作業時刻表。２４０・・・バックトラック表、３１０・・・競合作業集合表、第 ■ 図第２図シ゛ヨ７ショ′バ１外ｉ廿の６門３図第２区−６靜６ヌＹシ工−ルリ１利０４０第８図′４化にお牛Ｓｔ、Ｚ町１１讐ζ 第１４図ＩｌＩ　ｎ　Ｉｒａｒｒｌｌ蓼４−第１６　図
　讐１１６１む撓−り泥部勺１のＬ荘１闇第　１８　図　）【１ｊρ〕１でイ？−巣Ｊ５４刺り３
才Ｆｒ画ｑ深革；鼾下庫（

Claims

【特許請求の範囲】

（１）仕事と工程、各仕事の各工程における作業、及び
各仕事における工程間の先行関係が与えられたとき、探
索木を構成し、展開可能な探索木の１つの節点を選択す
る操作と、選択された節点から次に割り当てる作業を選
択して新しい節点を作成する操作とを繰返すことによっ
て、最終的に計画を立てる計画作成装置において、展開
すべき節点に手順を割り当てて新しく作成されたすべて
の節点の下界を評価し、展開すべき節点の下界との比較
からバックトラックが必要か否かを判断し、新しく割り
当ててた作業が処理される工程によりバックトラック表
を維持管理する下界評価部と、節点がもつ部分計画と各仕事の先行関係に基づき、未割
り当て作業を割り当て可能作業と割り当て不可作業とに
分類した作業分類表を作成する作業管理部と、部分計画と各仕事の工程間の先行関係に基づき、各未割
り当て作業が他の未割り当て作業に阻害されることなく
順調に処理されたと仮定した時に、各工程で処理が行わ
れる開始時刻と完了時刻を示す作業時刻表を作成する作
業時刻管理部と、作業時刻表と次に割り当てる作業の条件に基づき、各工
程毎に次に割り当てる作業を作業分類表の割り当て可能
作業の中から抽出し、競合作業集合表を作成する競合作
業作成部と、競合作業集合表からバックトラック表を利用して競合作
業集合を決定する競合作業決定部と、を備えることを特
徴とする計画作成装置。