JPH03166644A

JPH03166644A - 計画作成装置

Info

Publication number: JPH03166644A
Application number: JP1307182A
Authority: JP
Inventors: Fumihiro Kimura; 木村　文宏; Yasuhiro Inooka; 猪岡　保裕
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1989-11-27
Filing date: 1989-11-27
Publication date: 1991-07-18

Abstract

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

Description

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

〔従来の技術〕

ジぢブショップ問題やプロジェクト計画問題を解くため
に．分技限定法が用いられる場合が多い。

分技限定法は探索法の１つである。探索法では探索木を
構戒し，探索木の各節点で，既に割り当てた作業の部分
計画に対して未割り当て作業の１つを割り当てて，新し
い節点を作成していく。

分技限定法では．分技操作と限定操作とを繰り返すこと
によって解を取得する．分技操作とは，どの節点から分
技するかを決め．該節点に対して，未割り当て作業のう
ちどれを割り当てるべきかを判断し．新しい節点を作戊
する操作である。限定操作とは，評価値の悪い節点から
の分校操作を禁止する操作である。

本発明は分岐操作に特徴があるので，分技操作のみにつ
いて説明する。

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

（＋）　　展開すべき節点がもつ部分計画と各仕事の先
行関係とに基づき，未割り当て作業を割り当て可能作業
と割り当て不可作業とに分類した作業分類表を作成する
。

（２）部分計画と各仕事の工程間の先行関係とに基づき
，各未割り当て作業が他の未割り当て作業に阻害される
ことな《順調に処理されたと仮定した時に，各工程で処
理が行われる開始時刻と完了時刻とを示す作業時刻表を
作成する。

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

（４）競合作業集合に基づき．要素数の最も少ない競合
作業集合を１つ選択する．上記操作を簡単な例で説明する。次に割り当てる作業の
条件として，Ｊｉ適解を保障した「遅れあり」計画とす
る．「遅れあり」計画とは，ある工程がどの作業も処理
をしていなくて処理可能な状態のとき９割り当て可能作
業があったとしてもわざと該工程に遊び時間を発生させ
て他の作業を先に処理することが許される計画である。

本条件では．以下のステップで競合作業集合表が作成さ
れる． ■　作業時刻表に基づき，各工程毎に割り当て可能作業
の中で最小な完了時刻を求める。

■　各工程毎に，上記最小完了時刻よりも小さな開始時
刻をもつ未割り当て作業を抽出する。

■　各工程で．上記抽出した未割り当て作業の中に，割
り当て不可作業が含まれないものを選ぶ．第５図は．ジ
ョブションプ問題の例である。図中の数値は処理時間を
示す。各仕事の先行関係はすぺて「工程３」の前に「工
程２」の処理が必要であり９　「工程２」の前に「工程
１」の処理が必要である。数値が空（資）の工程はスキ
ップされる。

第２図は第５図図示の問題において，目的を総所要時間
最小化とした場合の最適解を示す。

具体例として，作業がまだ割り当てられていない節点か
らの分技操作を説明する。

（１）　　作業分類表は，第６図図示のものとなる。

（２）作業時刻表は第７図図示のものとなる．左の数値
が開始時刻を，右の数値が完了時刻を示す。

（３）最小な完了時刻は，「工程１」では「２」「工程
２」では「２」である。「工程３」には割り当て可能作
業がないので選ばれない．最小な完了時刻よりも小さな
開始時刻をもつ作業を抽出すると，「王程１」ではａｌ
とｂ１とＣＩ「工程２」ではｄ２とｅ２である。「工程
ｌ」と「工程２」とも割り当て不可作業を含まない。

よって．競合作業集合表は第８図図示のものとなる。

（４）第８図で，「王程１」の競合作業集合の要素数は
「３」であり，「工程２Ｊのそれは「２」であるので，
「工程２」の競合作業集合が選択される。

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

従来においては，探索の効率を上げるために探索木の横
幅を成長させないで．探索木の深さを成長させることと
していた。それは，なるべく探索木を狭めたまま．部分
計画を成長させ．その後に，探索木を広げた方が．下界
の成長が見込め，効率よく探索ができるからである。こ
のために，競合作業集合表の中から要素数が最小なもの
を選１尺してきた。

しかしながら．探索木の横幅が広がったとしても，下界
が成長ずる節点が多ければ．そこで探索木の成長が停止
することが多く，このために結果的には効率的な探索が
可能となることがある．っまり，下界が成長しない節点
の数が問題である。

下界が成長しない節点からはさらにその下に探索木が成
長ずるからである。

上記観点から考えると．従来技術のように，時的な探索
木の横の広がりに着目するよりも，新節点作ｔ２後さら
に探索木が或長ずるか否かに着目した方が効率よい探索
が可能となる。

本発明は．探索を効率的に行うために，下界が成長しな
い節点数に着目して分技操作を行うようにすることを目
的としている。

〔課題を解決するための手段］本発明は，以下の機能部を有する。

（１）　　各節点がもつ部分計画と各仕事の先行関係と
に基づき，未割り当て作業を割り当て可能作業と割り当
て不可作業とに分類した作業分類表を作成する作業管理
部，（２）部分計画と各仕事の工程間の先行関係とに基づき
，各未割り当て作業が他の未割り当て作業に阻害される
ことなく順調に処理されたと仮定した時に．各工程で処
理が行われる開始時刻と完了時刻とを示す作業時刻表を
作成する作業時刻管理部，（３）各節点の下界を求め，該下界を与える仕事の割り
当て可能作業や工程を示すか，あるいは．各仕事の割り
当て可能作業や各工程についてそれぞれの下界と該節点
の下界との差を示す下界理由表を作成する下界理由規定
部，（４）作業時刻表と次に割り当てる作業の条件とに基づ
き，各工程毎に．次に割り当てる作業を割り当て可能作
業の中から抽出し，ｎ合作業集合表を作成する競合作業
抽出部（５）下界理由表に基づき，各競合作業集合について，
下界が成長しない要素数を求め．該要素数が最も少ない
競合作業集合を１つ選択する競合作業決定部。

〔作　用〕

本発明では，新節点を作成し，下界を評価する段階で２
下記（１）〜（３）の処理を行う。また，分枝すベき節
点カマ与えられたとき，下記（４）と（５）の処理にて
分技操作に必要な次に割り当てるべき作業を選択する。

（１）作業管理部が．未割り当て作業を割り当て可能作
業と割り当て不可作業とに分類した作業分類表を作成す
る．（２）作業時刻管理部が，部分計画と各仕事の工程間の
先行関係とに基づき，各未割り当て作業が他の未割り当
て作業に阻害されることなく順調に処理されたと仮定し
た時に，各工程で処理が行われる開始時刻と完了時刻と
を示す作業時刻表を作成する．（３）下界理由規定部が，各節点の下界を求め．該下界
を与える仕事の割り当て可能作業や工程を示すか，ある
いは．各仕事の割り当て可能作業や各工程についてそれ
ぞれの下界と該節点の下界との差を示す下界理由表を作
成する。

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

（５）競合作業決定部が．下界理由表に基づき，各競合
作業集合について，下界が戊長しない要素数を求め，該
要素数が最も少ない競合作業集合を１つ選択する。

〔実施例〕

第１図は，本発明の一実施例ブロック構戒を示す。

図中１は，分技操作を担う分技操作部であり，図中２は
，限定操作を担う限定操作部である。

分技操作部１は，展開すべき節点を選択する展開節点選
択部１１，次に割り当てる作業を選択する作業選択部１
２　，新しい節点を作成し下界を評価する新節点作成部
１３とからなる。

作業選択部１２には，作業時刻表と次に割り当てる作業の条件とに基づき，各
工程毎に，次に割り当てる作業を割り当て可能作業の中
から抽出し，競合作業集合表を作成する競合作業抽出部
２１と，下界理由表に基づき，各競合作業集合について５下界が
成長しない要素数を求め５該要素数が最も少ない競合作
業集合をｌつ選択する競合作業決定部２２とが含まれる
。

また．新節点作成部１３には部分計画を成長させ，新節点を作る節点展開部３１と各節点がもつ部分計画と各仕事の先行関係とに基づき．
未割り当て作業を割り当て可能作業と割り当て不可作業
とに分類した作業分類表を作成する作業管理部３２と，部分計画と各仕事の工程間の先行関係とに基づき，各未
割り当て作業が他の未割り当て作業に阻害されることな
く順調に処理されたと仮定した時に．各工程で処理が行
われる開始時刻と完了時刻とを示す作業時刻表を作成す
る作業時刻管理部３３と，新節点の下界を評価し．該下界を与える仕事の割り当て
可能作業や工程を示すか，あるいは．各仕事の割り当て
可能作業や各工程についてそれぞれの下界と該節点の下
界との差を示す下界理由表を作成する下界理由規定部３
４とが含まれる。

具体例として．第５図図示のジョブショップ問題を取り
上げる。さらに，次に割り当てる作業の条件も同じく，
最適解を保障した「遅れあり」計画とする。目的も同じ
く総所要時間最小化とする。

最初に全体の処理の流れを説明し，後ほど詳細を説明す
る。全体の流れは以下である．■　次に割り当てる作業
を，　　ｒｏｏｉとする．■　新節点作成部ｌ３で９次
に割り当てる作業の１つを選沢し．新節点を作成し．下
界を評価する。ただし，次に割り当てる作業がなければ
■にいく。

■　限定操作部２で．新節点をさらに作成するか判断す
る。新節点の作成が必要ならぱ■へいく。

不要ならば終える。

■　展開節点選択部ｌ１にて．展開すべき節点を選択す
る。

■　作業選択部１２にて，次に割り当てる作業を選択す
る。そして■へいく。

では．詳細を説明する．最初は，作業選択部１２で，次
に割り当てる作業を，　ｒｏｏｔとする．次に．新節点
作成部ｌ３が働く。ただし．次に割り当てる作業がなけ
れば．展開節点選択部Ｕに処理が移行する。

まず，節点展開部３ｌにて，次に割り当てる作業の１つ
を選択し，新しい節点を作成ずる。選ばれた作業を割り
当て作業とする。そして．割り当て作業を次に割り当て
る作業から取り除く。

次に，作業管理部３２が働く，割り当て作業がｒｏｏｔ
であれば．部分計画はないものとする。

ｒｏｏｔでなければ，展開節点選択部ｌ１で選ばれた節
点の部分計画に．割り当て作業を追加し部分計画を或長
させる．部分計画ができると，作業の先行関係から９未
割り当て作業を割り当て可能作業と割り当て不可作業と
に分類し．作業分類表を作成する。結果は第６図図示の
ものとなる。分頚は以下によって実行される。各仕事に
ついて，■　先行関係から作業を順に並べた作業順リス
トを作成する。

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

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

例えば，仕事ａでは，作業順リストとして，（ａｌ，ａ
２，ａ３）を作成する。部分計画にある作業はなく，先
頭の作業ａ１を割り当て可能作業とする。残りの作業ａ
２とａ３とが割り当て不可作業である。

次に．作業時刻管理部３３が働く。部分計画と各仕事の
工程間の先行関係とに基づき，各未割り当て作業が他の
未割り当て作業に阻害されることなく順調に処理された
と仮定した時に，各工程で処理が行われる開始時刻と完
了時刻とを示す作業時刻表を作成する。結果は第７図図
示のものとなる。作成は以下によって実行される。各仕
事について ■　対象作業を割り当て可能作業とする。

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

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

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

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

例えば，仕事ａでは．割り当て可能作業ａｌの前作業が
な＜ＴＩ−０となる。また，「工程１」の進捗時刻Ｔ２
は０である。よって，開始時刻Ｔ３は０であり．完了時
刻Ｔ４は処理時間「２」をたして「２」である。次の作
業ａ２では，ＴＩ＝２，Ｔ２＝０であるので，開始時刻
は「４」．完了時刻は「６」である。

次に，下界理由規定部３４が働く。ここでは，節点の下
界を評価し，下界を与えた理由を示す下界理由表を作成
する。

一般に下界評価は２種類ある．１つは，仕事基準の下界
評価である。これは，各仕事について，部分計算と工程
間の先行関係とに基づき，未割り当て作業が他の未割り
当て作業に阻害されることなく順調に処理されたと仮定
した時に，全工程での処理を終える時刻である。これは
．作業時刻表から，各仕事の完了時刻の最大値で取得で
きる。

初期の仕事基準の下界を第９図に示す。例えば仕事ａで
は，作業時刻表の完了時刻２，　　６．　　１１の最大
値ｌ１　となる。

他のｌつは，工程基準の下界評価である。各工程の下界
は以下の３つの合計で得られる。

■　作業時刻表を利用して得られる最小な開始時刻，こ
れを工程の開始時刻とする。

■　未割り当て作業の当該工程での処理時間の合計． ■　未割り当て作業が，当該工程の後．他の未割り当て
作業に阻害されることなく最終工程を終えるまでの処理
時間の最小値。

初期の工程基準の下界を第ｌＯ図に示す。例えば，「工
程１」では．工程の開始時刻は「０」，処理時間の合計
はｒｌＯＪ　，終了までの最小加工時間は仕事Ｃの「１
」であるので．下界は合計「１１」となる。

節点の下界は，仕事基準．工程基準両者の個々の下界の
最大値であり．　　ｒｌｌＪとなる。

次に．下界理由表の作成について述べる。下界理由表は
，節点の下界を与える仕事の割り当て可能作業や工程を
示すか，あるいは．各仕事の割り当て可能作業や各工程
についてそれぞれの下界と該節点の下界との差を示す。

前者の場合．仕事基準の理由は．該仕事の割り当て可能
作業の開始時刻をＳ，該仕事の未割り当て作業の処理時
間の合計をＴとすると，（Ｓ＋Ｔ）が該節点の下界と同
じ割り当て可能作業を選ぶ。作業ａ１は，開始時刻が「
０」，処理時間合計がｒｌｌＪなので選ばれる。作業ｂ
ｉは，開始時刻が「Ｏ」，処理時間合計が「４」なので
選ばれない．工程基準の理由は，第１０図図示の工程基
準の下界から．節点の下界である「１１」と同じ下界を
もつ工程を選ぶ。「工程１」と「工程３」とが得られる
。これらより，第１１図図示の下界理由表の例を作成す
る。仕事基準の理由を第９図の下界から選ばないのは，
下界に作業が処理されるまでの待機時間が含まれるから
である．工程の進捗時刻が前作業の完了時刻よりも大き
いと，作業がそこで待機する。

後者の場合，仕事基準の理由は，割り当て可能作業の開
始時刻をＳ．未割り当て作業の処理時間の合計をＴとす
ると，節点の下界と（Ｓ＋Ｔ）との差を求める。作業ａ
ｌは，開始時刻が「０」処理時間合計がｒ１１Ｊなので
．差はｒＱ，である．作業ｂ１は，開始時刻が「０」．
処理時間合計が「４」なので，差は「７」である。工程
基準の理由は，第１０図の工程基準の下界と節点の下界
との差を求める。「工程ｌ」の下界は「ｌ１」であるの
で，差は「０」である．これらより，第１２図図示の他
の下界理由表の例を作成する．仕事基準の理由は第９図
図示の下界から選ばないのは．第１１図作成のときと同
しである。

こうして節点が作成されると．新しい節点をさらに作成
する必要があるかを限定操作部２が判断する。新節点の
展開が不要ならば処理を終える。

必要ならば．また新節点作成部１３に処理が移行する。

新節点の作成が必要で，次に割り当てる作業がないと，
展開すべき節点を選択するために．展開節点選択部１１
が働く。選択方法はいろいろある。

ここでは．最適解を効率よく求めることを狙いとしてい
るので，下界最優先の戦略を採用する。つまり，下界が
最良な節点から選択する。もし，複数あるならば，部分
計画が最大な節点を選択する。

当然最初は，節点が１つしかなく５最初に作成された節
点が選択される。

展開すべき節点が決まると，次に割り当てる作業を決め
るために，作業選択部ｌ２が働く．まず，競合作業抽出
部２ｌが働く。作業時刻表と次に割り当てる作業の条件
とに基づき，各工程毎に．次に割り当てる作業を割り当
て可能作業の中から抽出し，競合作業集合表を作成する
。次に割り当てる作業の条件が．最適解を保障した「遅
れあり」計画であるので．以下によって実行される。各
工程について， ■　割り当て可能作業を対象とし，最小な完了時刻をＴ
ｍとする。

割り当て可能作業がなければ，競合作業集合とはなりえ
ず，処理を終える。

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

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

結果は．第８図図示のものとなる。例えば．ｒ工程２」
では．割り当て可能作業はｄ２とｅ２とであり．最小完
了時刻ＴＩ１ば「２」となる。未割り当て作業ａ２，ｃ
２，ｄ２．ｅ２のうち開始時刻がＴｍより小さいｄ２と
ｅ２とが抽出される。

抽出されたｄ２とｅ２とはともに割り当て可能作業であ
るので．１１１合作業集合とする。これに対して，「工
程３ｊでは，割り当て可能作業がないので，ｆｉ合作業
集合となりえない。

次に，競合作業決定部２２が働く。下界理由表に基づき
，各競合作業集合について，下界が成長しない要素数を
求め，該要素数が最小な競合作業集合を１つ選択する。

まず，各競合作業集合について下界が成長しない要素数
を求める。仕事基準の理由と工程基準の理由から独立に
．各競合作業集合の各作業について，下界が成長ずるか
否かを判断し，両者から下界が成長しないと判断された
作業の数が下界が成長しない要素数である。下界が成長
しない要素数が求まれば．該要素数が最小な較合作業集
合を１つ選択することは容易である。

では，第１１図図示の下界理由表を利用した場合，下界
が成長しない要素数の取得方法を以下に述べる。結果を
第１３図図示の下界或長見込み表の例に示す。

仕事基準の理由の作業は，待機されることなく作業が処
理されないと，下界が成長ずることを意味する。競合作
業集合に含まれる作業のうち，仕事基準の理由にある作
業の数をＮとする。Ｎが複数ならば，どの作業を選んで
も，下界は必ず成長ずる。Ｎがｒ１，であれば，Ｎを与
えた作業以外は下界が成長ずる．該作業のみ下界が成長
しない。

Ｎが「０」ならば，全作業で下界が成長しない。

例えば，「工程ｌ」では．作業ａ１が節点の下界を与え
ているのでａ１は下界が成長しなく．他のｂｌと０１と
は下界が成長ずる。

工程基準の理由にある工程は．作業の処理を休むことな
く続けないと下界が成長ずることを意味する。作業の開
始時刻が，工程の開始時刻よりも大きいと下界が成長す
る。工程基準の理由にない工程では．全作業で下界が成
長しない．例えば．「工程ｌ」では，工程基準の理由の
工程であるが，どの作業も待機することなく処理される
ので，すべて下界が成長しない。

それでは．第１２図図示の下界理由表を利用した場合，
下界が成長しない要素数の取得方法を以下に述べる．結
果を第１４図図示の他の下界成長見込みを表す図に示す
．仕事基準では，作業が待機する時間が下界との差を越え
ると，下界が或長ずることを意味する。

競合作業集合の各作業について，該作業の処理時間をＰ
，他の作業のうち最小な下界との差をＤとすると，Ｐが
Ｄを越えるとＤを与えた作業の下界が成長ずる。例えば
．「工程ｌ」の競合作業集合を判断する。作業ａ１では
．処理時間Ｐは「２」，他の作業ｂｌとｃｌの下界との
差の最小値Ｄはｒ７，であるので，下界は成長しない。

作業ｂ１では，処理時間Ｐは「２」，他の作業ａｌと０
１の下界との差の最小値Ｄは「０」であるので，下界は
威長ずる。

工程基準の理由は，作業が待機する時間が工程の下界と
の差を越えると．下界が成長することを意味する．競合
作業の各作業について，該作業の開始時刻をＳ，工程の
開始時刻をＭ，該工程の下界との差をＣとすると，Ｓと
Ｍとの差がＣを越えると下界が成長ずる。例えば．「工
程１」の競合作業集合を判断する。「工程１ノの下界と
の差Ｃは「０」，工程の開始時刻は「０」である．作業
ａ１の開始時刻Ｓは「０」であるので，下界は或長しな
い．第１３図あるいは第１４図から，下界が成長しない要素
数は，「工程１」ではｒｌＪ，ｒ工程２」では「２」で
ある．よって．本要素数が最小な「工程１」の競合作業
集合が選択される。

こうして，次に割り当てる作業が決まると，また，新節
点作成部ｌ３に処理が移行する。

以上説明したように，本発明では「工程ｌ」の作業ａｌ
，ｂｌ，ｃｌが選沢されて．新しい節点が作成される。

それに対して，従来技術では「工程２」の作業ｄ２，ｅ
２が選択される。

第３図は，第５図図示の例題に対する本発明の探索空間
を示す。図中の記号は割り当てた作業を示し５括弧内の
数値は下界を示す。ｒｏｏ　ｔは何も割り当てられてい
ない状態を示す．図の見方は以下である．節点から下に
延びる罫線の先の節点の記号が割り当てられた作業を示
す．例えば，ｒｏｏ　ｔからａ１への関係は，何も割り
当てられていない状態の下で，作業ａ１を割り当てたこ
とを示す。また，ａｌからｂ１の関係は，作業ａｌが割
り当てられた状態の下でｂ１を割り当てたことを示す．
全部で１６個の節点がある。また９第４図は従来技術に
よる探索空間を示す。図中の記号，括弧内の数値の意味
は第３図図示の場合と同じである。全部で１９個の節点
がある．本発明では，探索空間で比較して，３節点分小
さいことがわかる．以上の説明では，下界評価を仕事基準と工程基準との両
面から求めたが．どちらか一方から求めてもさしつかえ
ない。この場合．下界理由表も下界を求めるときの基準
からのみで作成することとなる．そして．下界が成長し
ない要素数を求める段階では，下界を求めるときの基準
からのみ判断することとなる。

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

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

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

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

「遅れなしｊ計画では，競合作業集合のどの作業も同じ
開始時刻をもつので，工程基準から下界が成長しない要
素数を求めることは無意味である。

よって，下界評価は．仕事基準と工程基準の両面から行
ったとしても．下界理由表の作成と下界が成長しない要
素数を求める段階では，仕事基準からのみ処理を行う，その他にも，次に割り当てる作業の条件はある。

例えば，「遅れありｊ計画と「遅れなし」計画の中間と
して．ある工程がどの作業も処理をしていなくて処理可
能な状態のとき，割り当て可能作業があったとしたら，
ある一定時間までは，わざと該工程に遊び時間を発生さ
せて他の作業を先に処理することが許される計画とする
こともできる。

この場合は．ｆｉ合作業集合の作成方法が異なるのみで
．本発明を適用できる。また．最適解を保障しない戦略
を採用しても同じである。

〔発明の効果〕

本発明によれば．探索木がさらに展開されるか否かを判
断し．下界が成長しない要素数が少ないところから探索
木を成長させるようにする。このために下界が成長ずる
節点では，技刈りが行えることが多く，探索の効率が向
上することを期待できる。

【図面の簡単な説明】

第１図は計画作成装置のブロック構或．第２図は第５図
の最適スケジュールを示すガントチャート．第３図は本
発明による探索木，第４図は従来技術による探索木．第
５図はジゴブショップ問題の例，第６図は作業分類表の
例．第７図は作業時刻表の例，第８図は競合作業集合表
の例、第９図は仕事基準の下界，第１０図は工程基準の
下界．第１１図は下界理由表の例，第１２図は他の下界
理由表，第１３図は下界威長見込み表の例，第１４図は
他の下界成長見込み表．図中．２１は競合作業抽出部，２２は執合作業決定部，
３２は作業管理部，３３は作業時刻管理部，３４は下界
理由規定部を表す。

Claims

【特許請求の範囲】　仕事と工程、そして各仕事の各工程における作業が与
えられ、さらに、各仕事における工程間の先行関係が与
えられたとき、探索木を構成し、展開可能な探索木の１
つの節点を選択する操作と、選択された節点から次に割
り当てる作業を選択して新しい節点を作成する操作とを
繰り返すことによって、最終的に計画を立てる計画作成
装置において、節点がもつ部分計画と各仕事の先行関係とに基づき、未
割り当て作業を割り当て可能作業と割り当て不可作業と
に分類した作業分類表を作成する作業管理部と、部分計画と各仕事の工程間の先行関係とに基づき、各未
割り当て作業が他の未割り当て作業に阻害されることな
く順調に処理されたと仮定した時に、各工程で処理が行
われる開始時刻と完了時刻とを示す作業時刻表を作成す
る作業時刻管理部と、節点の下界を求め、該下界を与え
る仕事の割り当て可能作業や工程を示すか、あるいは、
各仕事の割り当て可能作業や各工程についてそれぞれの
下界と該節点の下界との差を示す下界理由表を作成する
下界理由規定部と、作業時刻表と次に割り当てる作業の条件とに基づき、各
工程毎に、次に割り当てる作業を割り当て可能作業の中
から抽出し、競合作業集合表を作成する競合作業抽出部
と。下界理由表に基づき、各競合作業集合について。下界が成長しない要素数を求め、該要素数が最も少ない
競合作業集合を１つ選択する競合作業決定部とを備えることを特徴とする計画作成装置。