JPH06223084A - 制約条件修正支援装置 - Google Patents

Abstract

(57)【要約】 【目的】 修正案を評価する制約条件修正支援装置を提
供する。 【構成】 データ入力部１によってスケジューリング対
象に関する対象データと、スケジューリングの内容を制
約する制約条件と、前記対象データ及び前記制約条件に
基づくスケジューリング結果をユーザが修正した結果修
正例とを入力する。修正規則ファイル６が、制約条件修
正の内容を一般的に規定する修正規則を保存する。修正
案生成部３が、前記対象データ、前記結果修正例及び前
記修正規則に基づいて前記制約条件の修正案を生成す
る。修正案評価部４が、前記修正案の妥当性を所定の評
価基準に基づいて評価する。修正案提示部５が、前記修
正案を出力する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、スケジューリング型知
識ベースシステムにおける制約条件の修正を支援する制
約条件修正支援装置の改良に関するものである。

【０００２】

【従来の技術】従来から、加工計画などのスケジューリ
ングを自動的に行うシステムとして、スケジューリング
型知識ベースシステム（以下、「システム」という。）
が用いられている。このシステムは、図１２（概念図）
に示すように、スケジューリング内容を制約する制約条
件を知識ベースＢに格納しておき、スケジューリング対
象に関するデータ（本明細書において「対象データ」と
いう。）が入力されると、推論エンジンＥが、その対象
データと前記制約条件とに基づいて、加工計画などのス
ケジューリング結果を自動的に生成・出力するものであ
る。

【０００３】なお、このようなシステムにおける対象デ
ータは、スケジューリング対象である各ジョブの諸元を
表すもので、制約条件は、対象データに含まれる各ジョ
ブ間に必要な間隔や実行順序などの関係を定義するもの
である。また、このようなシステムでは、前記のような
関係の記述に用いるため、各ジョブは属性とその属性値
からなる「クラス」と呼ばれるデータセットによって定
義される。

【０００４】前記のように生成されたスケジューリング
結果は、一般に、各生産設備などのリソース上に、処理
すべき各ジョブを時間ごとに割り付けたものとして表現
される。図１３は、このようなスケジューリング結果の
一例である。そして、ユーザによるスケジューリング結
果の修正は、このようにリソース上に割り付けられたジ
ョブの割付け位置を移動したり、ジョブを削除したり、
また、スケジューリング結果上に割り付けられていない
新たなジョブを追加することによって実現される。な
お、ユーザによって修正されたスケジューリング結果
を、本明細書において「結果修正例」という。図１４
は、図１３に示したジョブｊ２を移動したことによる結
果修正例の一例である。

【０００５】このようにユーザ自身が判断して行った修
正は本来的に正しいものと考えられるので、システムが
行った判断結果よりも優先されるべきである。したがっ
て、システムによるスケジューリング結果をユーザが修
正した場合は、次回からその結果修正例のようなスケジ
ューリング結果がシステムから出力されるように、その
システムの有する制約条件自体を修正する必要がある。

【０００６】このため、スケジューリング型知識ベース
システムは、制約条件修正支援装置を接続したり、組み
込んだりして用いられる。ここで、制約条件修正支援装
置とは、結果修正例に合わせた制約条件の具体的修正内
容を示す修正案をユーザに提案する装置である。なお、
制約条件修正支援装置におけるこのような修正案の生成
は、制約条件の修正内容を一般的に規定する修正規則に
したがって行われる。

【０００７】ところで、この制約条件修正支援装置にお
ける制約条件の修正は、（１）誤っている（修正すべき
である）可能性があるために修正の候補となる制約条件
（本明細書において「候補条件」という。）を知識ベー
スの中から発見し、（２）発見した制約条件を修正す
る、という２段階によって行われる。

【０００８】上記２段階のうち、候補条件の発見は、結
果修正例を知識ベース中の制約条件に照合し、結果修正
例に矛盾する制約条件を特定することによって行うこと
ができる。例えば、ある加工計画を作成するシステムに
おいて、知識ベースに次のような制約条件Ａが格納され
ているものとする。 制約条件Ａ：「治具がａ又はｂであるジョブと、治具が
ｃ又はｄであるジョブは、同時に処理してはならな
い。」

【０００９】ここで、ａ，ｂ，ｃ，ｄは治具の種類であ
り、上記の制約条件Ａは、ａとｃ、ａとｄ、ｂとｃ、ｂ
とｄという組み合わせで治具を同時に使用できないこと
を意味している。このような使用が不都合な場合として
は、この組み合わせで各治具を使用すると治具の消費電
力の合計が加工設備の電気容量の上限を越えるなどの場
合が考えられる。

【００１０】このような制約条件Ａを有するシステム
に、図１５に示すようなデータが入力され、図１３に示
すようなスケジューリング結果が出力されたとする。こ
のスケジューリング結果では、制約条件Ａにしたがっ
て、治具ａを用いるジョブｊ１と治具ｃを用いるジョブ
ｊ２の同時処理が回避されている。このようなスケジュ
ーリング結果に対して、ユーザが図１４に示すような修
正を行い、ジョブｊ１とジョブｊ２の同時処理をいとわ
なかった場合、ジョブｊ１とジョブｊ２の同時処理を排
除する前記制約条件Ａが、この結果修正例に矛盾する候
補条件となる。

【００１１】このように発見された候補条件を修正する
修正規則としては複数のものが考えられる。例えば、修
正規則の一つとして、まず、候補条件中のジョブのクラ
スがとっている属性値のうち、候補条件と矛盾するジョ
ブのペアのいずれかがとる属性値を削除するという修正
規則が考えられる。また、このような各修正規則による
具体的修正案としても、通常、複数のものが考えられ
る。

【００１２】例えば、前記のスケジューリングの実例で
は、制約条件Ａを、ジョブｊ１とジョブｊ２の同時処理
と矛盾しないように修正する必要があり、前記修正規則
による修正案として、次の２つが考えられる。

【００１３】（１）まず、ジョブｊ１は、図１５によれ
ば治具ａを使用するので、制約条件Ａから「治具にａを
使用する」という条件を削除し、次のように修正すれば
よい。「治具にｂを使用するジョブと、治具にｃ又はｄ
を使用するジョブは同時に処理してはならない。」 （２）また、ジョブｊ２は図１５によれば治具ｂを使用
するので、制約条件ａから「治具にｂを使用する」とい
う条件を削除し、次のように修正してもよい。「治具に
ａ又はｂを使用するジョブと、治具にｄを使用するジョ
ブは同時に処理してはならない。」 また、修正規則として、候補条件のジョブのクラスに、
候補条件と矛盾するジョブのペアのいずれかが該当しな
い属性とその属性値を追加し、いわば一般的加重条件を
設けるという修正規則も考えられる。この修正規則を前
記の実例に適用した場合は、次の２つの修正案が考えら
れる。

【００１４】（１）まず、ジョブｊ１は、図１５によれ
ば図面Ｋを使用するので、制約条件Ａにおいてジョブｊ
１に対応する「治具にａ又はｂを使用するジョブ」とい
う条件に、「図面にＫを使用しない」という条件を加
え、次のように修正すればよい。「治具にａ又はｂを使
用し、かつ図面にＫを使用しないジョブと、治具にｃ又
はｄを使用するジョブは同時に処理してはならない。」 （２）また、ジョブｊ２は図１５によれば図面Ｆを使用
するので、制約条件Ａにおいてジョブｊ２に対応する
「治具にｃ又はｄを使用するジョブ」という条件に、
「図面にＦを使用しない」という条件を加え、次のよう
に修正してもよい。「治具にａ又はｂを使用するジョブ
と、治具にｃ又はｄを使用し、かつ図面にＦを使用しな
いジョブは同時に処理してはならない。」 以上のように、候補条件の修正においては、修正規則の
種類数×問題となりうる属性数だけ修正案を挙げること
ができる。特に、修正対象とする属性が複数である修正
規則が採用される場合は、修正案の数は一層増加するこ
ととなる。

【００１５】

【発明が解決しようとする課題】ところで、従来の制約
条件修正支援装置は、候補条件がある場合、上記のよう
に、ユーザに対して修正案を提案することはできるが、
提案した修正案の内容的妥当性を評価する手段を備えて
いなかった。このため、提案された修正案の妥当性の評
価はすべてユーザが行わなければならず、制約条件の修
正におけるユーザの負担が大きかった。

【００１６】特に、従来の制約条件修正支援装置では、
修正案を評価する手段を備えていなかった結果、全候補
条件・可能な全ての修正規則・問題となる全ての属性と
いう組み合わせによって得られた修正案が、良否を問わ
ずに全て提案されていた。このため、ユーザが妥当性を
判断すべき修正案が多数にのぼり、制約条件の修正にお
けるユーザの負担は一層増大せざるを得なかった。

【００１７】また、制約条件の修正では具体的なケース
に応じて最適な修正規則が異なるのに対して、従来の制
約条件修正支援装置では装置の有する修正規則が固定さ
れており、ユーザがこれを変更することができなかっ
た。このため、従来では、装置の有する全ての修正規則
がどのようなケースにも一律に適用され、最適な修正規
則の適用が困難であった。

【００１８】本発明は、上記のような従来技術の問題点
を解決するために提案されたもので、その目的は、修正
案を評価する制約条件修正支援装置を提供することにあ
る。

【００１９】

【課題を解決するための手段】上記の目的を達するた
め、請求項１の発明は、スケジューリング対象に関する
対象データと、スケジューリングの内容を制約する制約
条件と、前記対象データ及び前記制約条件に基づくスケ
ジューリング結果をユーザが修正した結果修正例と、を
入力する入力手段と、制約条件修正の内容を一般的に規
定する修正規則を保存する修正規則保存手段と、前記対
象データ、前記結果修正例及び前記修正規則に基づいて
前記制約条件の修正案を生成する修正案生成手段と、前
記修正案を出力する出力手段とを備えた制約条件修正支
援装置において、前記修正案の妥当性を所定の評価基準
に基づいて評価する修正案評価手段を備えたことを特徴
とする。

【００２０】また、請求項２の発明は、請求項１記載の
制約条件修正支援装置において、前記修正規則を変更す
るための修正規則変更手段を備えたことを特徴とする。

【００２１】また、請求項３の発明は、請求項１記載の
制約条件修正支援装置において、前記評価基準を変更す
るための評価基準変更手段を備えたことを特徴とする。

【００２２】

【作用】上記のような構成を有する本発明は、次のよう
な作用を有する。すなわち、請求項１の発明では、修正
案評価手段が修正案の妥当性を所定の評価基準に基づい
て評価するので、修正案の妥当性の評価に係るユーザの
負担が軽減される。

【００２３】また、請求項２の発明では、ユーザは、修
正規則選択手段によって修正規則を選択できるので、ケ
ースごとに最適な修正規則を適用することができる。

【００２４】また、請求項３の発明は、ユーザは、評価
基準変更手段によって評価基準を変更できるので、ケー
スごとに最適な評価基準を用いることができる。

【００２５】

【実施例】以下、本発明の一実施例である制約条件修正
支援装置（以下、「本装置」という。）について、図面
に従って具体的に説明する。なお、本装置はコンピュー
タ上に実現されるもので、本装置の各機能は、プログラ
ムの形式で表現された所定の手順でコンピュータを動作
させることによって実現されている。したがって、以
下、本装置の各機能を有する仮想的回路ブロックを想定
して本装置を説明する。

【００２６】（１）実施例の構成…図１ まず、図１は、本装置の構成図である。本装置は、図１
２に示したようなスケジューリング型知識ベースシステ
ムに接続して用いられる。そして、本装置は、システム
から前記のような対象データ、制約条件及び結果修正例
からなるデータ（本明細書において「入力データ」とい
う。）を入力するためのデータ入力部１（前記入力手段
に相当するもの）と、前記入力データに基づいて修正の
対象となる候補条件を検出する候補条件検出部２とを有
している。また、本装置は、前記入力データ、及び、制
約条件の修正内容を一般的に規定する所定の修正規則に
基づいて前記候補条件の修正案を生成する修正案生成部
３（前記修正案生成手段に相当するもの）を有してい
る。また、本装置は、生成された修正案の妥当性を所定
の評価基準に基づいて評価する修正案評価部４（前記修
正案評価手段に相当するもの）と、修正案をユーザに提
示する修正案提示部５（前記出力手段に相当するもの）
とを有している。

【００２７】また、本装置は、前記修正規則を格納する
修正規則ファイル６（前記修正規則保存手段に相当する
もの）と、修正案生成の基礎とする修正規則を選択する
ための修正規則選択部７（前記修正規則変更手段に相当
するもの）を有している。また、本装置は、前記評価基
準を格納する評価基準ファイル８と、修正案の評価の基
準とする評価基準を選択するための評価基準選択部９
（前記評価基準変更手段に相当するもの）を有してい
る。なお、本装置には、必要なＩ／Ｏ制御回路１０、表
示装置１１及びキーボード１２が接続されている。

【００２８】［制約条件］ここで、本実施例においてシ
ステムから本装置に入力される制約条件の一般的フォー
マットは、次のようなリスト形式によるものである。

【数１】

【００２９】このフォーマットにおいてカギ括弧
（［〜］）内の文字はパラメタを意味する。ここでは、
知識ベースには、次のような制約条件Ａが格納されてい
るとする。 制約条件Ａ：「治具がａ又はｂであるジョブと、治具が
ｃ又はｄであるジョブは、同時に処理してはならな
い。」

【００３０】この制約条件Ａは、上記のフォーマットに
したがって、次のようなリスト形式で入力される。

【数２】

【００３１】すなわち、「ＣＯＮＳＴ＿ＣＬＡＳＳ」は
制約条件の種類であり、上記制約条件Ａの場合は、[con
straint]にnooverlap （同時に処理してはならない）が
入る。「ＴＥＲＭ」は、この制約条件がジョブのクラス
[jobname1]とジョブのクラス[jobname2]の関係であるこ
とを表す。ＣＯＮＤは[jobname1]と[jobname2]との関係
を表現する[logical form]（論理式）の列であり、各[l
ogical form]は次の書式によって記述される。

【００３２】

【数３】（[eval] [attr-value] [value-list]） これは、関数[attr-value]の値と[value-list]が[eval]
の関係にあることを示している。ここで[eval]には肯定
を意味する"=="と否定を意味する"!="があり、また、[a
ttr-value]は[jobs]及び[attr]の２つの引数を取る関数
である。ここで、引数[jobs]は[jobname1]もしくは[job
name2]を表し、引数[attr]は[jobs]の属性を表す。ま
た、関数の戻り値は[jobs]の[attr]の属性値である。[v
alue-list]は文字・数値などのリストであり、このリス
トの各要素は記号“，”（カンマ）で区切られる。

【００３３】［修正規則］また、本実施例の修正規則フ
ァイル６には、次の４種類の修正規則が格納されてい
る。なお、以下の説明では、あるスケジューリング結果
においてある制約条件を満たすジョブのペアを「正の実
例」、あるスケジューリング結果においてある制約条件
と矛盾するジョブのペアを「負の実例」と称する。ま
た、正の実例及び負の実例を「実例」と総称する。

【００３４】まず、第１の修正規則Ｓ１は、候補条件の
ジョブのクラス[jobs]を表現する[logical form]の一つ
について、負の実例に対応する属性値を一つ削除すると
いう規則である。

【００３５】また、第２の修正規則Ｓ２は、候補条件を
表現する[logical form]に、次のような[logical form]
を追加するという規則である。なお、ここで追加される
[logical form]は、[eval]に"!="、[attr-value]に[job
s]の[attr]、[value-list]に、負の実例のうち[jobs]に
対応する方のジョブの[attr]の属性値を当てはめたもの
である。この修正規則Ｓ２は、制約条件に、負の実例が
除外されるような一般的加重要件を追加する意義を有す
る。なお、この場合における[attr]は、ジョブの属性
（例えば、処理時間、機会、治具、図面、入材時刻、納
期）中から、ユーザが候補条件の修正に用いることを意
図する属性を自由に選択することができ、このような属
性の選択は複数行うこともできる。

【００３６】第３の修正規則Ｓ３は、候補条件を表現す
る[logical form]に、第２の修正規則Ｓ２と同様の[log
ical form]を追加するものであるが、ここでは、[attr]
を、装置が乱数などを用いて非決定的に決定する点で第
２の修正規則と異なっている。なお、この第３の修正規
則においても、選択する属性の数はユーザが自由に決定
することができる。

【００３７】第４の修正規則Ｓ４は、候補条件を、適用
範囲が重複しない複数の制約条件に分解し、分解された
各条件から負の実例に当てはまる制約条件を削除し、残
余を修正案にするという規則である。

【００３８】［評価基準］また、本実施例における評価
基準ファイル８は、２種類の評価基準を格納している。
これらの評価基準は、修正前の候補条件に対する正の実
例の集合をT-InsA、修正前の候補条件に対する負の実例
の集合をF-InsA、修正案に対する正の実例の集合をT-In
sB、修正案に対する負の実例の集合をF-InsB、T-InsAと
T-InsBの共通部分の集合をT-InsI、集合ｓの要素数をＮ
（ｓ）、２つの集合α，βの共通部分をα＆β、と表記
する場合、次のように表現することができる。

【００３９】まず、第１の評価基準Ｈ１は、

【数４】N(T-InsI)/N(T-InsA) ≧Ｘ が成立するものを妥当と認めるというものである。この
評価基準は、条件修正前の正の実例が条件修正によって
減少しない修正案ほど妥当性が高いことを意味してい
る。

【００４０】また、第２の評価基準Ｈ２は、

【数５】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ≧Ｘ が成立するものを妥当と認めるというものである。この
評価基準は、条件修正前の正の実例が条件修正によって
減少しない修正案ほど妥当性は高いが、その中でも、条
件修正前の負の実例のうち条件修正によって正の実例と
なるものが多いものは妥当性が低下することを意味して
いる。なお、ここで評価値Ｘは０から１の範囲内でユー
ザが選択する数値である。

【００４１】また、第３の評価基準Ｈ３は、

【数６】 ｛1-N(F-InsB)/N(F-InsA)}*{N(T-InsI)/N(T-InsA)}≧Ｘ が成立するものを妥当と認めるというものである。この
評価基準は、条件修正前の正の実例が条件修正によって
減少しない修正案ほど妥当性は高いが、その中でも、条
件修正後の負の実例の数が条件修正前の負の実例の数よ
りあまり減少していないものは、妥当性が低下すること
を意味している。なお、ここで評価値Ｘは０から１の範
囲内でユーザが選択する数値である。

【００４２】（２）実施例の作用及び効果…図２〜図１
５ 上記のような構成を有する本実施例における制約条件の
修正は次のように行われる。まず、ユーザは、知識ベー
スに制約条件を格納しているスケジューリング型知識ベ
ースシステムに対象データを入力してスケジューリング
結果を出力させる。次に、ユーザは、このスケジューリ
ング結果に必要な修正を施して結果修正例とし、この結
果修正例をシステム内に保存させておく。ここでは、知
識ベースＢに前記制約条件Ａを格納しているスケジュー
リング型知識ベースシステムに（図１２）、図１５に示
すような対象データを入力し、図１３に示すスケジュー
リング結果が出力されたものとする。そして、ユーザ
は、このスケジューリング結果に必要な修正を施して図
１４に示す結果修正例とし、この結果修正例をシステム
内に保存させておいたものとする。

【００４３】ここで、図２は本装置における修正案の提
案の手順を示すフローチャートである。すなわち、この
図に示すように、本装置が起動されると、データ入力部
１がシステムから対象データ、制約条件及び結果修正例
を読み込む（ステップ１）。

【００４４】次に、修正規則選択部７が、修正規則ファ
イル６に格納されている修正規則を表示装置に表示し、
ユーザに修正規則の選択を要求する。ここで、図３は表
示装置１１における修正規則の表示の一例である。ユー
ザが修正規則を選択し、その番号をキーボードから入力
すると（ステップ２）、選択された修正規則に関する対
象データの属性が表示装置１１に表示されるので、ユー
ザは、修正の基礎とする属性を選択してキーボード１２
から入力する（図４）。

【００４５】次に、評価基準選択部９が、評価基準ファ
イル８に格納されている評価基準を表示装置１１に表示
し、ユーザに評価基準の選択を要求する。ここで、図５
は表示装置１１における評価基準の表示の一例である。
ユーザが評価基準を選択し、その番号をキーボード１２
から入力すると（ステップ３、図６）、選択された評価
基準における評価値（変数）Ｘの値の入力を要求される
ので（図７）、ユーザは、評価の基準とする評価値Ｘの
値をキーボード１２から入力する（図８）。

【００４６】次に、候補条件検出部２が、前記入力デー
タに含まれる対象データと、制約条件と、結果修正例と
を照合することによって、結果修正例と矛盾する制約条
件を候補条件として検出する（ステップ４）。なお、こ
の検出は、各制約条件について次のような具体的手順に
よって行われる。

【００４７】まず、制約条件の各ジョブに当てはまる実
例を結果修正例から検索する。例えば、前記の制約条件
Ａについては、Job1、Job2（Job1≠Job2）に当てはまる
実例はジョブｊ１とジョブｊ２、ジョブｊ１とジョブｊ
３、ジョブｊ１とジョブｊ４である。なお、対象データ
を制約条件に当てはめた実例を図９に示す。

【００４８】次に、このような実例を正の実例と負の実
例に峻別する。例えば、制約条件Ａと図１４の結果修正
例との関係では、負の実例はジョブｊ１とジョブｊ２、
正の実例はジョブｊ１とジョブｊ３及びジョブｊ１とジ
ョブｊ４である。このように峻別された正の実例と負の
実例を図１０に示す。このとき、負の実例が発見された
制約条件を候補条件とする。例えば、図１０では、負の
実例ジョブｊ１とジョブｊ２が発見された制約条件Ａが
候補条件とされる。

【００４９】続いて、修正案生成部３は、ユーザが選択
した修正規則に基づいて、候補条件に係る修正案を生成
する（ステップ５）。ここでは、ユーザが第１及び第２
の修正規則Ｓ１，Ｓ２を選択しており、これらの修正規
則Ｓ１，Ｓ２に基づいた修正案として、以下の４つを挙
げることができる。

【００５０】［［第１の修正規則に基づくもの］］ ［修正案ＥＸ１１］まず、図１５によれば、ジョブｊ１
は治具ａを使用するので、

【数７】 と修正することが考えられる。

【００５１】［修正案ＥＸ１２］また、図１５によれ
ば、ジョブｊ２は治具ｃを使用するので、

【数８】 と修正することが考えられる。

【００５２】［［第２の修正規則に基づくもの］］ ［修正案ＥＸ２１］また、図１５によれば、ジョブｊ１
は図面Ｋを使用するので、

【数９】 と修正することが考えられる。

【００５３】［修正案ＥＸ２２］また、図１５によれ
ば、ジョブｊ２は図面Ｆを使用するので、

【数１０】 と修正することが考えられる。

【００５４】続いて、修正案評価部４は、ユーザが選択
した評価基準に基づいて、これらの修正案を評価する
（ステップ６）。ここで、ユーザは、第１の評価基準Ｈ
１を選択し、評価値Ｘとして０．５を入力しているの
で、評価基準は、

【数１１】N(T-InsI)/N(T=InsA) ≧0.5 となる。なお、ここで、T-InsAは修正前の候補条件に対
する正の実例の集合であるから、

【数１２】T-InsA＝{(j1 j3),(j1 j4)｝ であり、

【数１３】N(T-InsA）＝２である。

【００５５】この評価基準Ｈ１を前記各修正案に適用す
ると、各修正案ＥＸ１１〜ＥＸ２２は次のように評価さ
れる。

【００５６】［修正案ＥＸ１１］

【数１４】 については、以下のような評価が行われる。

【００５７】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数１５】T-InsB＝｛｝ となる。したがって、T-InsIも、

【数１６】T-InsI＝｛｝ となり、その要素数も０である。したがって、

【数１７】N(T-InsI)/N(T-InsA）＝０／２＝０ である。

【００５８】［修正案ＥＸ１２］

【数１８】 については、以下のような評価が行われる。

【００５９】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数１９】T-InsB＝{(j1 j4)} となる。また、T-InsAは候補条件に対する正の実例の集
合であり、

【数２０】T-InsA＝{(j1 j3),(J1 J4)} であった。したがって、T-InsIは、

【数２１】T-InsI＝{(j1 j4)} となり、その要素数は１である。したがって、

【数２２】N(T-InsI)/N(T-InsA）＝１／２＝０．５ である。

【００６０】［修正案ＥＸ２１］

【数２３】 については、以下のような評価が行われる。

【００６１】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数２４】T-InsB＝｛｝ となる。したがって、T-InsIも、

【数２５】T-InsI＝｛｝ となり、その要素数は０である。したがって、

【数２６】N(T-InsI)/N(T-InsA）＝０／２＝０ である。

【００６２】［修正案ＥＸ２２］

【数２７】 については、以下のような評価が行われる。

【００６３】すなわち、T-InsBは修正案における正の実
例の集合であるから、

【数２８】T-InsB＝{(j1 j3),(j1 j4)} となる。また、T-InsAは修正前の候補条件における正の
実例の集合であり、

【数２９】T-InsA＝{(j1 j3),(j1 j4)} であった。したがって、T-InsIも、

【数３０】T-InsI＝{(j1 j3),(j1 j4)} となり、その要素数は２である。したがって、

【数３１】N(T-InsI)/N(T-InsA）＝２／２＝１．０ である。

【００６４】そして、修正案提示部５が評価基準以上の
修正案とその評価値を表示装置１１に表示してユーザに
修正案の提案を行う（ステップ７）。例えば、上記のよ
うな評価の結果、修正案ＥＸ１１の評価値は０、修正案
ＥＸ１２の評価値は０．５、修正案ＥＸ２１の評価値は
０、修正案ＥＸ２２の評価値は１．０、となる。ここ
で、修正案の提案は評価値が０．５以上のものについて
行うので、候補条件Ａについてユーザに提案されるの
は、修正案ＥＸ１２及びＥＸ２２のみとなる。図１１
は、表示装置１１におけるこのような修正案の表示を示
す図である。

【００６５】また、ユーザが前記第３及び第４の修正規
則Ｓ３，Ｓ４を選択した場合の修正案の提案は次のよう
に行われる。

【００６６】［［［第３の修正規則］］］例えば、修正
規則選択部７においてユーザが第３の修正規則Ｓ３を選
択し、さらに選択する属性をその個数で「３」と入力し
た場合、修正規則選択部７は３つの属性を乱数などの選
択手段によって非決定的に選択する。ここでは、属性の
うち「処理時間」、「機械」、「納期」が選択されたも
のとすると、前記入力データに基づいて、以下のような
６種類の修正案が作成される。

【００６７】［［属性「処理時間」に基づいたもの］］ ［修正案ＥＸ３１］図１５によれば、ジョブｊ１は処理
時間が１であるから、

【数３２】 と修正することが考えられる。

【００６８】［修正案ＥＸ３２］また、図１５によれ
ば、ジョブｊ２は処理時間が１であるから、

【数３３】 と修正することが考えられる。

【００６９】［［属性「機械」に基づいたもの］］ ［修正案ＥＸ３３］図１５によれば、ジョブｊ１は機械
がＲ１であるから、

【数３４】 と修正することが考えられる。

【００７０】［修正案ＥＸ３４］また、図１５によれ
ば、ジョブｊ２は機械がＲ２であるから、

【数３５】 と修正することが考えられる。

【００７１】［［属性「納期」に基づいたもの］］ ［修正案ＥＸ３５］図１５によれば、ジョブｊ１は納期
が３であるから、

【数３６】 と修正することが考えられる。

【００７２】［修正案ＥＸ３６］また、図１５によれ
ば、ジョブｊ２は納期が３であるから、

【数３７】 と修正することが考えられる。

【００７３】［［［第４の修正規則に基づくもの］］］
第４の修正規則Ｓ４は、候補条件を適用範囲が重ならな
い複数の条件に分解し、これら分解された各条件のうち
負の実例に当てはまるもの以外の条件を修正案として提
示するものである。ここで、制約条件一般は、前記のよ
うに、

【数３８】 という形式で表現することができる。

【００７４】このうち、[logical form]は、さらに、[j
obname1]を表現[logical form]の列と、[jobname2]を表
現する[logical form]の列から構成される。このとき、
j[k]＿v[l]がそれぞれｎ個の要素を有する[jobname[k]]
の[value-list]の一つの要素とすると（但しｋ＝１，
２，１≦ｌ≦ｎ）、上記の一般的制約条件の形式は、次
のように分解することができる。

【数３９】 （ （ＣＯＮＳＴ＿ＣＬＡＳＳ [constraint]） （ＴＥＲＭ [jobname1] [jobname2]） （ＣＯＮＤ （[eval]([jobname1][attr])(j1 ＿v1,j1 ＿v2, …j1＿v[n])) ・ ・ （[eval]([jobname2][attr])(j2 ＿v1,j2 ＿v2, …j2＿v[n])) ・ ・ ） ）

【００７５】この制約条件の分解は、[jobname1]を表現
する[logical form]における[value-list]の一つの要素
j1＿v[l]を[value-list]とした、[jobname1]を表現する
[logical form]と、[jobname2]を表現する[logical for
m]における[value-list]の一つの要素j2＿v[l]を[value
-list]とした、[jobname2]を表現する[logical form]と
を組み合わせた条件を作成することである。

【００７６】すなわち、修正規則選択部７においてユー
ザがこの第４の修正規則Ｓ４を選択すると、前記のよう
な入力データについて、以下のように修正案が作成され
る。

【００７７】まず、候補条件Ａは次のようなものであ
る。

【数４０】 そして、この制約条件ＡにおけるJob1の[logical form]
は、

【数４１】（"=="（Job1 治具）（ａ，ｂ）） であり、これを分解すると次の２つの[logical form]が
得られる。

【数４２】（"=="（Job1 治具）（ａ）） （"=="（Job1 治具）（ｂ）） また、制約条件ＡにおけるJob2の[logical form]は、

【数４３】（"=="（Job2 治具）（ｃ，ｄ）） であり、これを分解すると次の２つの[logical form]が
得られる。

【数４４】（"=="（Job2 治具）（ｃ）） （"=="（Job2 治具）（ｄ）） これらの[logical form]を組み合わせると、以下の４つ
の修正案を作成することができる。

【００７８】［修正案ＥＸ４１］

【数４５】 ［修正案ＥＸ４２］

【数４６】 ［修正案ＥＸ４３］

【数４７】 ［修正案ＥＸ４４］

【数４８】

【００７９】ここで、負の実例ジョブｊ１とジョブｊ２
に当てはまる修正案は、ジョブｊ１が治具ａ、ジョブｊ
２が治具ｃを使用することから、修正案ＥＸ４１のみで
あり、修正案ＥＸ４２〜ＥＸ４４はジョブｊ１及びジョ
ブｊ２に当てはまらない。したがって、上記修正案ＥＸ
４２−ＥＸ４４が修正案となる。

【００８０】［［［第２の評価基準］］］次に、修正案
の評価基準として、ユーザが評価基準Ｈ２を選択した場
合の評価について説明する。第２の評価基準Ｈ２は、前
記のように、

【数４９】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ≧Ｘ が成立するものを妥当と認めるという基準である。この
基準を選択したユーザが評価値Ｘとして０．８を入力し
たものとすると、前記第１及び第２の修正規則Ｓ１，Ｓ
２に基づく各修正案ＥＸ１１，ＥＸ１２，ＥＸ２１，Ｅ
Ｘ２２の評価は以下のように行われる。

【００８１】なお、これらの評価において、T-InsAは修
正前の候補条件に対する正の実例の集合であるから、

【数５０】T-InsA＝{(j1 j3),(j1 j4)} となり、その要素数は２である。また、F-InsAは負の実
例の集合であるから、

【数５１】F-InsA＝{(j1 j2)} となり、その要素数は１である。

【００８２】［修正案ＥＸ１１］

【数５２】 については、以下のような評価が行われる。

【００８３】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数５３】T-InsB＝｛｝ となる。したがって、T-InsIも、

【数５４】T-InsI＝｛｝ となり、その要素数も０である。このとき、F-InsAとT-
InsBの共通集合は、

【数５５】F-InsA＝{(J1 J2)} T-InsB＝｛｝ より、｛｝であり、その要素数は０である。したがっ
て、

【数５６】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ＝０／２−０／１＝０である。

【００８４】［修正案ＥＸ１２］

【数５７】 については、以下のような評価が行われる。

【００８５】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数５８】T-InsB＝{j1 j4} となる。したがって、T-InsIも、

【数５９】T-InsI＝{j1 j4} となり、その要素数は１である。このとき、F-InsAとT-
InsBの共通集合は、

【数６０】F-InsA＝{(j1 j2)} T-InsB＝{(j1 j4)} より、｛｝であり、その要素数は０である。したがっ
て、

【数６１】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ＝１／２−０／１＝０．５である。

【００８６】［修正案ＥＸ２１］

【数６２】 については、以下のような評価が行われる。

【００８７】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数６３】T-InsB＝｛｝ となる。したがって、T-InsIも、

【数６４】T-InsI＝｛｝ となり、その要素数は０である。このとき、F-InsAとT-
InsBの共通集合は

【数６５】F-InsA＝{(j1 j2)} T-InsB＝｛｝ より、｛｝であり、その要素数は０である。したがっ
て、

【数６６】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ＝０／２−０／１＝０である。

【００８８】［修正案ＥＸ２２］

【数６７】 については、以下のような評価が行われる。

【００８９】すなわち、T-InsBは修正案に対する正の実
例の集合であるから、

【数６８】T-InsB＝{(j1 j3),(j1 j4)} となる。したがって、T-InsIは、

【数６９】T-InsI＝{(j1 j3),(j1 j4)} となり、その要素数は２である。このとき、F-InsAとT-
InsBの共通集合は、

【数７０】F-InsA＝{(j1 j2)} T-InsB＝{(j1 j3),(j1 j4)} より、｛｝であり、その要素数は０である。したがっ
て、

【数７１】 N(T-InsI)/N(T-InsA)-N(F-InsA＆T-InsB)/N(F-InsA) ＝２／２−０／１＝１．０である。

【００９０】この結果、修正案ＥＸ１１の評価値は０、
修正案ＥＸ１２の評価値は０．５、修正案ＥＸ２１の評
価値は０、修正案ＥＸ２２の評価値は１．０、となる。
ここで、修正案の提案は評価値が０．８以上のものにつ
いて行うので、候補条件Ａについてユーザに提案される
のは、修正案ＥＸ２２のみとなる。

【００９１】以上のように、本実施例によれば制約条件
修正支援装置が修正案の妥当性を評価するので、ユーザ
による修正案評価の負担が軽減される。また、本実施例
では、ユーザが装置の有する修正規則を変更できるの
で、具体的なケースに応じた最適な修正規則を適用する
ことができる。特に、本実施例では、所定の評価基準以
上の修正案のみが提示されるので、質の高い修正案の提
案が行われ、ユーザによる制約条件修正の負担が一層軽
減される。

【００９２】（３）他の実施例 なお、本発明は、上記の実施例に限定されるものではな
く、次のような他の実施例を包含する。例えば、本発明
における修正規則や評価基準は、上記実施例に示したも
のに限定されるものではなく、他の規則や基準を自由に
用いることができる。また、表示装置やキーボードはス
ケジューリング型知識ベースシステムと共用してもよ
い。また、上記実施例の制約条件修正支援装置はコンピ
ュータ上に実現されているが、その機能の全部又は一部
は専用の電子回路上に実現してもよい。

【００９３】

【発明の効果】以上のように、本発明によれば、制約条
件修正支援装置が修正案の妥当性を評価するので、制約
条件の修正におけるユーザの負担が軽減される。

【図面の簡単な説明】

【図１】本発明の実施例の構成図。

【図２】同実施例における修正案提案の手順を示すフロ
ーチャート。

【図３】同実施例における修正規則の画面表示例。

【図４】同実施例における修正規則及び属性の入力画面
の例。

【図５】同実施例における評価基準の画面表示例。

【図６】同実施例における評価基準の入力画面の例。

【図７】同実施例における評価値の入力要求画面の例。

【図８】同実施例における評価値の入力画面の例。

【図９】同実施例における制約条件Ａに対する対象デー
タの当てはめの例。

【図１０】同実施例における属性の峻別の例。

【図１１】同実施例における修正案の画面表示の例。

【図１２】従来及び本発明におけるスケジューリング型
知識ベースシステムの概念図。

【図１３】従来及び本発明の実施例におけるスケジュー
リング結果の例。

【図１４】従来及び本発明の実施例における結果修正例
の一例。

【図１５】従来及び本発明の実施例における対象データ
の一例。

【符号の説明】

１：データ入力部 ２：候補条件検出部 ３：修正案生成部 ４：修正案評価部 ５：修正案提示部 ６：修正規則ファイル ７：修正規則選択部 ８：評価基準ファイル ９：評価基準選択部 １０：Ｉ／Ｏ制御回路 １１：表示装置 １２：キーボード Ｓ：修正規則 Ｈ：評価基準 ＳＴ：手順の各ステップ ＥＸ：修正案

Claims (3)

【特許請求の範囲】
1. 【請求項１】 スケジューリング対象に関する対象デー
   タと、スケジューリングの内容を制約する制約条件と、
   前記対象データ及び前記制約条件に基づくスケジューリ
   ング結果をユーザが修正した結果修正例と、を入力する
   入力手段と、 制約条件修正の内容を一般的に規定する修正規則を保存
   する修正規則保存手段と、 前記対象データ、前記結果修正例及び前記修正規則に基
   づいて前記制約条件の修正案を生成する修正案生成手段
   と、 前記修正案を出力する出力手段とを備えた制約条件修正
   支援装置において、 前記修正案の妥当性を所定の評価基準に基づいて評価す
   る修正案評価手段を備えたことを特徴とする制約条件修
   正支援装置。
2. 【請求項２】 前記修正規則を変更するための修正規則
   変更手段を備えたことを特徴とする請求項１記載の制約
   条件修正支援装置。
3. 【請求項３】 前記評価基準を変更するための評価基準
   変更手段を備えたことを特徴とする請求項１記載の制約
   条件修正支援装置。