JPH02100860A - 日程計画支援装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、日程計画立案時の計画作業を効率的に支援す
る日程計画支援装置に関する。

Ｂ、従来の技術 第９図に基づいて日程計画の代表的な事例である割当て
計画問題を説明する。

この例では第９図（ａ）に示すように、各１０日間の枠
を有する作業項目割当て枠Ａ、Ｂを想定するとともに、
第９図（ｂ）に示すように、この１０日間に行うべき作
業項目として各３．４，５゜４．３日の標準時間を要す
るａ、ｂ、ｃ、ｄＴ　ｅの５つの作業項目を想定する。

ここで１割当て枠とは、作業項目を実行する担当員、担
当グループ。

作業を実行するに要する設備、実験試供品等の作業対象
そのもの等が考えられ、例えば、Ａ、８２人の担当員が
それぞれ１０日分の日数を持ち。

１０日間で上記ａ　＝　ｄの作業を処理するためには、
各作業項目ａ　＝　ｄをどのよう１こ割当てればよいか
を立案し、第９図（Ｑ）のように計画するのが割当て計
画である。

従来は専ら人手によりこの割当て計画を立案していたが
、最近、コンピュータで計画を立案することも試みられ
ている。この場合、作業項目全ての順列リストを作り、
そのリスト類で割当てが可能かどうかを判定し、不可能
であれば新たな異なる順列リストを作成し、割当て可能
な順列が見つかるまでこの作業を繰り返す。

Ｃ０発明が解決しようとする課題 したがって、作業項目の増加に従って順列の数は階乗で
増加していき、いわゆる組み合わせ的爆発が発生するこ
とから解を得るまでに膨大な処理時間を要することがあ
る６しかも、与えた条件に無理があって割当て不可能な
場合には、最終的に何ら解を得られない。

本発明の技術的課題は、専門家の知識を利用して問題解
決を支援するいわゆるエキスパートシステムの概念を導
入し、全ての順列を検討せずに効率的に計画問題を解決
するとともに、解が得られない場合には、作業項目の優
先度情報に応じて終了要求期限を延期して再度計画を試
行させるようにすることにある。

００課題を解決するための手段 クレーム対応図である第１図により説明すると、本発明
にかかる日程計画支援装置は、作業開始期限、作業終了
期限、標準時間、作業の優先度の各情報を複数の作業項
目に対してそれぞれ設定して記憶するとともに複数の作
業割当枠の各割当て日数を記憶する記憶手段２０１と、
前記複数の作業項目を前記複数の作業割当枠に割当てる
割当手段３００とを有する。

その割当手段３００は、前記作業開始期限の早い順の作
業項目リストを作成する作業項目リスト作成手段３０１
と、作成された作業項目リストの先頭順から順次に１つ
の作業項目を選択する作業項目選択手段３０２と、選択
された作業項目の作業開始期限、作業終了期限、標準時
間を認識し当該作業項目の割当が可能な割当枠を抽出す
る割当て枠抽出手段３０３と、抽出された割当枠のうち
、既に割り付けられた作業項目の総割当て日数を除いた
残りの日数が最小の割当枠を選択する最小割当枠選択手
段３０４とを備え、この最小割当枠選択手段３０４によ
り選択された割当枠に作業項目を割り当てる。

また、割当手段３００で割当てられない作業項目が有る
か否かを判定する判定手段４０１と、割当てられない作
業項目が有ると判定されると、前記優先度に応じて前記
作業終了期限を延長する延長手段４０２と、割当てられ
ない作業項目が有ると判定されると、延長された作業終
了期限に基づいて前記割当手段３００を再起動する再起
動手段４０３とを具備する。以上の構成により、上記技
術的課題を解決する。

８０作用 割当手段３００で割当てられない作業項目が有る場合に
は、優先度に応じて作業終了期限を延長し、延長された
作業終了期限に基づいて割当手段３００を再起動して割
当作業を再実行する。

Ｆ、実施例 第２図〜第８図に基づいて一実施例を説明する。

第２図は日程計画支援袋［１００の全体構成を示す図で
ある。この支援装置１００は１割当て計画を実行する実
行部１１と、作業項目の終了要求期限を変更する変更部
１２とを格納した推論エンジン１０と１作業項目割当て
に関する諸条件を格納した知識ベース２０とを有する。

これらは通常外部記憶装置に記憶され、所定の手続きに
よりこの支援装置１００の記憶領域に移される。またこ
の支援装置ＬＯＯは、インタフェース３０としてプログ
ラムの実行結果や知識ベース２０の内容をユーザに対し
て表示するＣＲＴ３１と、ユーザからの命令入力を受は
付けるキーボード３２とを備える。ＣＲＴ３１に代えて
液晶デイスプレィやプラズマ・デイスプレィなど、また
キーボード３２に代えてマウス、ライトペン、タッチパ
ネルなど、通常のコンピュータに接続可能ないかなる入
出力装置をも用いることができる。

本実施例においては、上述した知識ベース２０が第３図
に示す（１）〜（９）のデータを有しているものとする
。（１）は割当てるべき作業項目が５つあることを示す
。（２）〜（６）は作業項目に関する条件を記述してお
り、 作業項目（項目名、標準時間、終了要求期限。

優先度条件） のフォーマットで指定される。具体的には例えば（２）
の意味は、ｒａＪは「作業項目名」を示し、「３」は［
ａという作業項目は実行に３日かかる」ことを示し、「
１０」は「１０日目までに終了する必要があること」を
示し、ｒｌ」はｒこの期限を守る優先度」を示し、ｒｌ
Ｊが最も優先度が高く、（５）の作業項目ｄの優先度「
３」が最も優先度は低い。（７）は割当て枠（上述した
Ａ、Ｂ）が２個あることを、（８）は割当て枠Ａが１０
日の長さを、（９）は割当て枠Ｂが１０日の長さをそれ
ぞれ持っていることを示している。

第４図〜第８図により処理手順について説明する。

まず第４図の処理１において、各作業項目毎に作業を開
始すべき開始要求期限Ｓを算出する。具体的には終了要
求期限と、標準時間Ｔの差分をとればよい。

次に処理２において、開始要求期限Ｓとペアで。

この開始要求期限Ｓの早い順に作業項目を並べたリスト
Ｌ１を作成する。この結果（開始要求期限Ｓ１作業項目
Ｘ）のペアが開始要求期限の順に並べられたリストＬ１
が第５図（ａ）のように生成される。

次に処理３においては、処理２の結果得られたリストＬ
１の第１番目の要素をまず処理４に引き渡して後述の処
理５，６を実行し、処理７を経て再び処理３で第２番目
の要素を処理４に引き渡して処理５，６を実行するとい
う動作をリストＬ１が空リストになるまで繰り返す。こ
れは良く知られたりスト再帰処理により実現可能である
。

処理４では、処理３から引き渡された（開始要求期限Ｓ
２作業項目Ｘ）のペアで与えられる作業項目を割当てる
ことができる全ての割当て枠を見出してリストＬ２を作
成する。

リストＬ２の作成は以下に説明する第１および第２の条
件が満足するようにして作成される。

■第１の条件　二　開始要求期限Ｓの作業項目Ｘを割当
て枠ＡまたはＢ（以下、Ｑとする）に割当てるためには
、枠Ｑのもつ日数りが作業項目Ｘの標準時間Ｔより長い
こと（ＤＯＴ）が第１の条件である。ここで１割当てが
実施される度に枠Ｑのもつ日数りは割当てた作業項目Ｘ
の標準時間Ｔ分だけ短くする必要があるが、この処理は
後に述べる処理６の中で実施される。

■第２の条件　：　各粋の何日分が割当てずみであるか
を確認する。もし、何日かが既に割当てずみであれば、
その割当てずみ日数Ｒは後述する処理６の中で記憶され
ており、何も記憶していなければ割当てずみ日数Ｒは０
である。この割当てずみ日数Ｒより開始要求期限Ｓが遅
いこと（ＳＩＲ）が第２の条件となる。

例えば、リストＬ１の第１番目の要素（２，ｅ）が第１
および第２の条件を満たすか否かを考える。

今、作業項目ｅの開始要求期限は２日であり、標準時間
Ｔは３日であり、割当て枠Ａ、Ｂが持つ日数りはともに
１０日、割当てずみ日数ＲはともにＯである。すなわち
、上記第１の条件は、枠Ａ。

Ｂとも１０　（＝Ｄ）＞０　（＝Ｒ）　で満足し、第２
の条件も枠Ａ、Ｂとも、２　Ｃ＝Ｓ”）＞Ｏ（＝Ｒ）で
満足する。したがって、この第１番目の要素（２，ｅ）
は、割当て枠Ａ、Ｂのいずれにも割当てられ、リストＬ
２は、 Ｌ２　：　　［８，（１０，Ａ）、（１０，Ｂ）］と表
わせる。この処理４を終了すると作業項目ｅはリストＬ
１から消去され、リストＬ１は第５図（ｂ）のようにな
る。

処理５では処理４の結果得られたりストＬ２が空リスト
であるかどうかを判断する。すなわち。

処理３から引き渡されたデータが第１および第２の条件
を満足しない場合にはりストＬ２は空リストである。も
し空リストであれば、その時点で考慮の対象としている
作業が割当て不可能であるから処理９に進み処理９を行
う。もし空リストでなければ、第１および第２の条件を
満足するデータが存在し割当て可能な枠が少なくとも１
個あることになるので処理６に進む。上述したように、
リストＬ１の第１番目の要素（ｅ、２）についてはりス
トＬ２が作成されるから処理６へ進む。

処理６においては、割当て可能枠がＡ、Ｂであれば１割
当て枠Ａ、Ｂのうち最も残り日数の短くなる割当て枠の
方に作業項目Ｘを割当て、これを記憶する。上述のリス
トＬ２：　　［ａ　（１０，Ａ）。

（１０，Ｂ）］の場合には、枠Ａ、Ｂともに残り日数り
が１０日であるが、この場合５割当て枠Ａを優先してＡ
に作業項目ｅを割当てる。もし、枠Ｂの残り日数りが９
日ならばＢの枠に割り当てられる。そして、割当て枠Ｑ
の残り日数りから、作業項目Ｘの標準時間Ｔを差し引い
た残り（Ｄ−Ｔ）を枠Ｑの新たな残り日数りとして記憶
（知識ベース）を書き換える。上述のりストＬ２の場合
は、割当て枠Ａの残り日数りが７日にされる。さらに、
割当て枠Ｑがその時点までに未使用であればＴを、もし
に日が割当てずみであればに＋Ｔを新たな割当てずみ日
数Ｒとして一時記憶領域に記憶する。

上述のりストＬ２の場合には、割当て枠Ａの割当てずみ
日数Ｒが３日、割当て枠Ｂの割当てずみ日数Ｒが０日と
なる。この処理６が実行されると、リストＬ２から［ｅ
　　（１０，Ａ）、（１０，Ｂ）コが消去される。次い
で処理７でリストＬ１が空リストか否かを判定する。空
リストならば処理８へ、空リストでなければ上述の処理
３〜６を再実行する。

リストＬ１の第２番目以降の要素に対する処理４〜６は
第６図（ａ）〜（ｄ）のようになるが、（ｄ）のに示す
ように、リストＬ１の（７，ａ）の作業項目ａを割当て
枠Ａ、Ｂに割当てようとするとき、上記第１の条件が満
足しないから、リストＬ２が作成できない。したがって
、処理５でリストＬ２が空リストと判定されて処理９へ
進む。

次に、処理ＳでリストＬ２が空リストと判定された場合
について説明する。これは、上述したように与えた条件
の範囲内では解が求まらない場合であり、リストＬ１の
〔開始要求期限Ｓ２作業項目各Ｘ〕が、処理４において
Ａ、Ｂいずれの割当て枠にも割当てられないときにリス
トＬ２が空リストとなり、処理９に進む。

処理９の手順を示す第７図にしたがって説明する。

処理１１において、初期条件を緩和するためのレベルＧ
がＯか否かを判定する。Ｇ＝Ｏならば処理１８において
レベルＧを１にする。Ｇ≠０ならば処理１２でＧ←Ｇ＋
１を実行する。処理１３では、レベルＧのテーブルを参
照して優先度Ｐ、延長日数Ｍを決定する。例えば、Ｇ＝
１のレベル１ではＰ＝３．Ｍ＝１とすると、処理１４で
は知識ベース内から優先度Ｐ＝３を持つ作業項目を見出
し、リストＬ３を作成する。本実施例の場合、リストＬ
３は、 Ｌ３＝　［ｄ：１ と表わされる。処理１５では、このリストＬ３の第１番
目の要素（この場合は［ｄ］のみ）の作業項目の終了要
求期限を１日延長して知識ベースに第８図（ａ）の（２
）′〜（６）′　を新たに書き加える。その後、リスト
Ｌ３の［ｄ］を消去する。

処理１６では、Ｌ３が空きリストか否かを判定し、否定
判定されると処理１５を再実行し、背定判定されるとこ
の第７図の処理を終了して処理１に戻り、第８図（ａ）
の知識ベースに基づいて処理１〜７を再実行する。

本実施例では、先に述べた第８図（ａ）に示す新たな知
識ベースに従うと、第８図（ｂ）のように１割当て枠Ｂ
を１日延長するだけで各作業項目ａ　＝　ｄが割当て枠
Ａ、Ｂに割り当てされる。

次いで処理７に進み、リストＬ１が空リストか否かを判
定する。否定されると処理３に戻り、上述したと同様に
処理３〜処理７を実行する。処理７が肯定されると、す
なわち、リストＬ１が空リストになると処理８に進み、
結果を表示する。例えば、第８図（ｂ）のようなグラフ
表示を行ったり、あるいは作業項目ａは「何日〜何日ま
でに作業を行う」などをＣＲＴに表示する。

なお、レベル１により知識ベースを書き換えた後の処理
でも処理５が肯定されると、第７図の処理に再び進む。

ここで、処理１２でＧ＝２とされるから、処理１３でＧ
＝２のレベル２のテーブルを参照して優先度Ｐ、延長日
数Ｍを決定する。いま、レベル２において、優先度Ｐ＝
３では延長日数Ｍを２日、優先度Ｐ＝２では延長日数Ｍ
を１日とすると、リストＬ３は、 Ｌ３：　　［ｂ、ｃ、ｄｌ となる。そして、このリストＬ３に基づいて処理１３〜
１５を実行すると、知識ベースには第８図（ｃ）で示す
ような（２）”〜（６）”のレベル２の情報が新たに書
き込まれる。

そして、この第８図（ｃ）の（２）”〜（６）”の情報
により処理１〜７を再度実行する。このとき、３たび処
理５が肯定されて処理９に進めば、同様にしてレベル３
の情報により優先度Ｐと延長日数Ｍが決定され、知識ベ
ースをさらに書き換えて割当計画処理が実行される。こ
のようにして、処理５が否定されるまで順次に知識ベー
スを書き換えて行けば、必ず解が求められる。

なお、処理９のレベル１あるいはレベル２では、それぞ
れ１種類の書き換え情報を用意したが、各レベルに複数
種類の書き換え情報を用意し、順次に実行したり、複数
種類の情報をＣＲＴ３１に表示し、作業者にキーボード
３２から選択させるようにしても良い。

また、作業者の自由度を大きくするため、各レベル内で
優先度Ｐや延長日数Ｍをキーボード３２から自由に設定
できるようなセットアツプ機能を処理９の最初のステッ
プに設けても良い。

さらに、■先の実施例のように予め支援装置１００に設
定されたレベルの内容で割当を再実行する方式と、■複
数種類のレベル内情報を作業者が選択し、その情報で割
当を再実行する方式と、■各しベルの優先度Ｐと延長Ｍ
を作業者が入力して割当を再実行する方式とを自由に選
択できるようにしても良い。

Ｇ９発明の効果 本発明によれば、専門家の知識を利用して問題解決を支
援するいわゆるエキスパートシステムの概念を導入し、
全ての順列を検討せずに効率的に計画問題を解決すると
ともに、解が得られない場合には、作業項目の優先度情
報に応じて作業終了期限を延期して再度計画を試行させ
るようにしたので、作業項目などの初期情報が増えても
この種の割当て処理時間が爆発的に増加せず、従来より
も短時間で処理が終了できると共に、初期設定条件に多
少無理があって解が求まらない場合でも、初期条件を再
設定してその条件を緩和して再度割当処理を実行するよ
うにしたので、条件緩和を適切に定めれば必ず解を求め
ることができる。

【図面の簡単な説明】

第１図はクレーム対応図である。 第２図〜第８図は一実施例を説明するもので、第２図が
全体構成図、第３図が知識ベース内を説明する図、第４
図が処理手順を示すフローチャート、第５図がリストＬ
１を示す図、第６図が割当手順を説明する図、第７図が
第４図の処理９の詳細を示すフローチャート、第８図が
割当手順を説明するための図である。 第９図は従来例を説明するための図である。 １０：推論エンジン １１：割当計画実行部 １２：終了要求期限変更部 ３０：インタフェース ３１：ＣＲＴ　　　　　３２：キーボード１００：支援
装置 ２０１：記憶手段　　３００：割当手段３ｏ１：作業項
目リスト作成手段 ３０２：作業項目選択手段 ３０３：割当枠抽出手段 ３０４：最小割当枠選択手段 ４０１：判定手段 ４０２：延長手段 ４０３：再起動手段

Claims (1)

1. 【特許請求の範囲】 作業開始期限、作業終了期限、標準時間、作業の優先度
   の各情報を複数の作業項目に対してそれぞれ設定して記
   憶するとともに複数の作業割当枠の各割当て日数を記憶
   する記憶手段と、前記複数の作業項目を前記複数の作業
   割当枠に割当てる割当手段とを有する日程計画支援装置
   であって、前記割当手段は、 前記作業開始期限の早い順の作業項目リストを作成する
   作業項目リスト作成手段と、 作成された作業項目リストの先頭順から順次に１つの作
   業項目を選択する作業項目選択手段と、選択された作業
   項目の作業開始期限、作業終了期限、標準時間を認識し
   当該作業項目の割当が可能な割当枠を抽出する割当て枠
   抽出手段と、抽出された割当枠のうち、既に割り付けら
   れた作業項目の総割当て日数を除いた残りの日数が最小
   の割当枠を選択する最小割当枠選択手段とを備え、この
   最小割当枠選択手段により選択された割当枠に作業項目
   を割り当てるとともに、 この割当手段で割当てられない作業項目が有るか否かを
   判定する判定手段と、 割当てられない作業項目が有ると判定されると、前記優
   先度に応じて前記作業終了期限を延長する延長手段と、 割当てられない作業項目が有ると判定されると、延長さ
   れた作業終了期限に基づいて前記割当手段を再起動する
   再起動手段とを具備することを特徴とする日程計画支援
   装置。