JPH04367973A - スケジュール自動作成処理方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はスケジュール作成方式に
係り、特に、一定の制約条件の下での複数のジョブと複
数のリソースとの間の割当てを効率的に行うスケジュー
ル作成高速化方式に関する。

【０００２】

【従来の技術】複数のジョブと複数のリソースとの間の
割当てを一定の制約条件の下で行うことは、例えば、人
間の交代制勤務スケジュール作成、工場の生産工程のス
ケジュール作成、ＡＶ機器などの録画、録音のスケジュ
ール作成等、多種多様な分野で日常的に行われている作
業である。

【０００３】従来、このような割当て作業は専ら人手に
より、専門家のノウハウを用いて行われていたが、近年
コンピュータ技術の発達により、機械による自動化が盛
んに進められている。この自動化の手法としては、数理
計画法によるアプローチと知識工学的アプローチがある
。前者は、制約条件が等式や不等式で記述できる場合な
ど制約条件の形式が整った場合にのみ有効である。しか
しながら、現実の問題では、より複雑な形式で制約条件
が記述される場合が多い。従って、後者のアプローチを
ベースにしヒューリスティックを加えた手法の方がより
適用範囲の広いものである。これに関連のある公知例と
しては、例えば特開昭６３−１６３６６９号公報に、最
も制約条件の厳しいジョブから割当てを行う手法が記載
されている。

【０００４】

【発明が解決しようとする課題】スケジュール作成問題
に対する知識工学的アプローチとしては、従来、以下の
処理手順が採用されている。

【０００５】（１）複数のジョブをスケジュール単位と
なるコマとして表現し、順序づけして格納する。 （２）先頭のコマを取り出す。 （３）複数のリソースから一つのリソースを取り出す。 （４）取り出したリソースが割当ての制約条件を満たし
ているかどうかをチエックする。 （Ａ）適合すれば、そのコマに対する割当てを決定する
。 （Ｂ）適合しなければ、次のリソースを取り出して制約
条件のチエックを行う。 （Ｃ）取り出すリソースがなくなった場合は、先に処理
したコマの処理を取り消し、（３）の処理から再開する
。即ち、バックトラック処理を行う。 （５）（２）に戻り、次のコマの割当て処理を行う。 さらに、割当てられていないコマがなくなるまで、（２
）から（５）までの処理を繰り返す。

【０００６】以上の手順でスケジュールを作成する場合
、作成にかかる時間は割当てのやり直しを行うバックト
ラック処理の回数に大きく依存する。先の特開昭６３−
１６３６６９号公報に記載の手法は、各ジョブに対する
割当て可能なリソースの数を、厳しさの度合を表わす指
標として採用し、その値が小さいジョブから割当ててゆ
くというものである。しかしながら、この手法をスケジ
ュール作成に適用する場合、複数の制約条件間の関係を
考慮していないため、必ずしもリソース割当てのやり直
し回数が少なくなるとは限らないという問題点がある。

【０００７】本発明の目的は、バックトラック処理の回
数を少なくすることにより、スケジュール作成の高速化
を実現することにある。

【０００８】

【課題を解決するための手段】上記目的を達成するため
に、本発明は、複数のジョブと複数のリソースとの間の
割当てを制約条件に従って行いスケジュールを自動作成
する方式において、ジョブをスケジュール単位となるコ
マへ展開し、コマ同士の制約条件の束縛関係から各コマ
のリソース割当て順序を決定し、該決定した順序に従っ
て、各コマへリソースを制約条件の下で割当てていくよ
うにしたものである。

【０００９】

【作用】バックトラック処理の回数を少なくするために
、あらかじめスケジュール単位となるコマへリソースを
割当てる際の効率のよい順序付けを、次のようにしてコ
マ同士の制約条件の束縛関係から探し出す。 （１）スケジュールに課せられた制約条件をグラフで表
現する。ここではコマをノードとし、二つのコマの間に
制約条件が課せられている場合、ノード間のリンクを張
る。 （２）各リンクに対して、制約条件の重要度を表わす重
みづけをする。 （３）各ノードに番号を与え順序づけをする。 （４）各ノードに対して、隣合うノードとの距離の最大
値を求める。この距離はリンク上の重みとノード番号の
差などを利用して定義する。 （５）（４）で求めた距離のすべてのノードに関する最
大値を求める。 （６）（５）で求めた最大値が（３）で与えた順序づけ
の特徴量となる。 この特徴量を最小にするような順序づけを探し、最終的
なコマ割当て順序とする。

【００１０】上述の処理によって決定したコマへのリソ
ース割当て順序は、制約条件によって互いに束縛しあっ
ている複数のコマを、可能な限り近いタイミングで割当
てるような順序になっている。このため、あるコマに対
して割当てるべきリソースがなくなってしまい、バック
トラック処理を行う場合も、割当てをやり直すために遡
るコマ数が可能な限り少ないものとなっており、スケジ
ュール作成の高速化が可能となる。

【００１１】

【実施例】以下、図を用いて本発明の一実施例について
説明する。

【００１２】図１は本発明のスケジュール作成方式を実
現する情報処理システムの一実施例のブロック図である
。本システムは、ジョブ記憶装置１、リソース記憶装置
２、制約条件記憶装置３、ジョブ選択装置４、リソース
選択装置５、割当て決定装置６及び割当て状況記憶装置
７で構成され、ジョブ選択装置４は、更にスケジュール
単位展開部４１、割当て順序決定部４２及び割当て順序
記憶部４３からなる。

【００１３】記憶装置１には、図２のような各ジョブに
対する情報が格納されている。例えば、ジョブ番号１と
しては、ジョブ名Ａ、作業時間は１日の午前、作業人員
３名、必要な資格はＢレベル、作業内容はＣで場所はＡ
、などの情報が記憶されている。リソース記憶装置２に
は、図３のような各リソースに対する情報が格納されて
いる。例えば、リソース番号１としては、リソース名Ａ
、保有している資格ＢおよびＣ、可能な作業Ａ、Ｂ、Ｄ
、時間の条件は特になし、場所の条件はＡ、Ｅ、Ｆ、な
どの情報が記録されている。制約条件記憶装置３には、
図４のようなジョブとリソースの関係に対する情報が格
納されている。例えば、制約条件番号１としては、内容
「夜間の勤務は資格Ｂ以上の人員が少なくとも１名必要
」などの情報が記録されている。

【００１４】ジョブ選択装置４では、まず、スケジュー
ル単位展開部４１が、ジョブ記憶装置１からジョブを読
出し、各ジョブを展開してコマの形式に変換する。例え
ば、コマＡはジョブ１の１日午前勤務を行う１回目の人
員、コマＢは同様に２回目の人員、コマＣはジョブ２の
１日午後勤務を行う１回目の人員、などと展開する。コ
マは各リソースを割つけてゆくときの単位である。次に
、割当て順序決定部４２は、各コマへのリソースの割当
ての順序を決定するが、その際、最も効率良くスケジュ
ールが作成できるような割当ての順序を計算し、割当て
順序記憶部４３に格納する。この割当て順序決定部４２
の導入が、本発明の特徴とするところである。

【００１５】リソース選択装置５は、リソース記憶装置
２からリソースを読出し、一つずつ選択していく。割当
て決定装置６は、ジョブ選択装置４およびリソース選択
装置５によって選択されたジョブ（コマ単位）とリソー
スが、制約条件記憶装置３に格納されている制約条件に
違反しないかどうかを調べる。そして、制約条件をすべ
て満たす場合は割当てを決定し、割当て状況記憶装置７
に格納する。制約条件を一つでも満たさない場合は別の
割当てを検討し、制約条件をすべて満たす割当てを探す
。

【００１６】図５は、ジョブ選択装置４における処理手
順を示したフローチャートである。まず、スケジュール
単位展開部４１においてジョブ記憶装置１から読出した
ジョブをスケジュール単位となるコマへ展開し、制約条
件記憶装置３の制約条件を参照して、複数のコマの関係
として課せられた制約条件と合わせてグラフで表現する
（ステップ５０１，５０２）。ここで、コマはノード、
制約条件はリンクで表される。さらにリンクで表された
制約条件に重み付けをし、制約条件に強弱を付ける（ス
テップ５０３）。次に割当て順序決定部４２において、
グラフのノードとして表わされた各コマに対して番号を
つけ、一つの割当て順序を決める（ステップ５０５）。 この順序づけに対して、コマ同士の制約条件の束縛関係
を反映した特徴量を計算する（ステップ５０６）。この
特徴量の計算法の一例について図６で詳述する。求まっ
た現在の特徴量を既に得ている前の特徴量（初期値は、
考えられる最大の特徴量とする）と比較し（ステップ５
０７）、現在の特徴量の方が大きければ、直ちに次の割
当てに移り、現在の特徴量の方が小さければ、現在の順
序とその特徴量を保存した後（ステップ５０８）、次の
割当てに移る。このようにして、すべてのコマの各順序
づけに対して特徴量を計算し、最も小さい順になったと
きの順序づけを探し、結果を割当て順序記憶部４３に格
納する（ステップ５０４，５０９）。

【００１７】図６はステップ５０６の特徴量計算の詳細
フローチャートである。まず、コマを一つ決め、これに
隣接する各コマとの距離を計り、その最大値を求める（
ステップ６０２，６０３）。コマ間の距離は、各コマに
付けられた番号の差、コマとコマとを結ぶリンク上に付
けられた重み付けの値などに基づいて定義する。現在の
計算結果と前の計算結果を比較して大きい方を保存しな
がら（ステップ６０４，６０５）、各コマについてこれ
らの距離の最大値を計算し、最も大きいものをこの順序
づけの特徴量として採用する（ステップ６０１，６０６
）。

【００１８】ジョブ選択装置４の割当て順序決定部４２
において、以上の処理手順にしたがって得られた割当て
順序は、通常スケジュール作成においてのやり直しとし
て行われるバックトラック処理の回数を、最も少なくす
るものである。

【００１９】例えば図７の（ａ）と（ｂ）は、６個のコ
マＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆに関する制約条件をグラフで
表現したものである。ここで、制約条件の重み付けはす
べて等しいとしている。図７（ａ）では、コマ間の距離
を番号の差の絶体値として定義し、出来るだけ小さい特
徴量になるように順序づけを行ったものである。一方、
図７（ｂ）は各コマに対して無作為に順序づけをしたも
のである。数字が割当て順序を示す。

【００２０】図７の（ａ）と（ｂ）の如く順序づけをし
たコマに対して、割当て決定装置６でのリソース割当て
に伴うバックトラック処理の様子を示したのが、それぞ
れ図８の（ａ）と（ｂ）である。ここでは、すべてのコ
マに対するリソースはそれぞれ２個ずつであるとしてい
る。数字は割当て順序、「×」は割当てに失敗したこと
を示す。また、太線は実際に割当てが行われたこと、細
線は割当てを行わなくて済んだこと、点線はまだ割当て
を検討していないことを示す。

【００２１】図８（ａ）および（ｂ）の例は、コマＣと
コマＤとの間に制約条件があるため、コマＣにあるリソ
ースを割当てたことの影響でコマＤに割当てるべきリソ
ースがなくなってしまい、バックトラック処理が起きた
状況を示している。この場合、図８（ａ）ではコマＣへ
の割当てのやり直しが行われるまでに３回のバックトラ
ック処理で済んでいるが、図８（ｂ）では１５回も行わ
れており、無駄な割当て処理が多くなっている。

【００２２】

【発明の効果】以上の説明から明らかなように、本発明
によれば、複数のジョブと複数のリソースとの間の割当
てを制約条件に従って行うスケジューリングにおいて、
スケジューリング単位となるコマへリソースを割当てる
際、複数のコマに対する複数の制約条件間の関係を考慮
し、あるコマに対するリソース割当てを、制約条件で強
く結びつけられている隣り合ったコマと出来るだけ近い
タイミングで行われるような順序づけを計算して、割当
てのやり直しが少なくなるような順序を採用しているこ
とにより、バックトラック処理の回数が大幅に少なくな
り、スケジュール作成の高速化が可能になる。

【図面の簡単な説明】

【図１】本発明のスケジュール作成方式を実現する情報
処理システムの一実施例の構成図である。

【図２】ジョブの具体例を示す図である。

【図３】リソースの具体例を示す図である。

【図４】制約条件の具体例を示す図である。

【図５】ジョブ選択装置における割当て順序決定処理手
順のフローチャートである。

【図６】割当て順序決定部における特徴量計算手順の詳
細フローチャートである。

【図７】制約条件のグラフ表現の具体例を示す図で、（
ａ）は本発明による割当て順序を各ノードに付けたもの
であり、（ｂ）は無作為な順序を各ノードに付けたもの
である。

【図８】リソース割当て時のバックトラック処理発生状
況を示す図で、（ａ）および（ｂ）はそれぞれ図７（ａ
）および（ｂ）に示された順序で割当てを行ったときの
ものである。

【符号の説明】

１　　ジョブ記憶装置 ２　　リソース記憶装置 ３　　制約条件記憶装置 ４　　ジョブ選択装置 ４１　　スケジュール単位展開部 ４２　　割当て順序決定部 ４３　　割当て順序記憶部 ５　　リソース選択装置 ６　　割当て決定装置 ７　　割当て状況記憶装置

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　複数のジョブと複数のリソースとの間
   の割当てを制約条件に従って行いスケジュールを自動作
   成する方式において、ジョブをスケジュール単位となる
   コマへ展開し、コマ同士の制約条件の束縛関係から各コ
   マのリソース割当て順序を決定し、該決定した順序に従
   って、各コマへリソースを制約条件の下で割当てていく
   ことを特徴とするスケジュール作成方式。