JPH02226467A - 動的ジョブ処理を含むスケジューリング問題解決支援システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 所定の制約条件を満足するように、動的ジョブを含むジ
ョブを機械に割り当てるという枠組みで捉えることので
きるスケジューリング問題を１計算機によって処理する
動的ジョブ処理を含むスケジューリング問題解決支援シ
ステムに関し。

動的にジョブを生成しあるいは消去しつつ効率よく妥当
なスケジュール解を導出する手段を提供することを目的
とし。

決定的な手順により、逐次的にジョブを機械に割り当て
ていき、そのスケジューリングが成功しなかった場合に
、制約条件を緩和することにより全ジョブの割り付け状
態を生成する第１の処理手段と、前記第１の処理手段が
生成した全ジョブの割り付け状態をもとに、任意の機械
の間で交換可能な割り付け済みジョブまたはジョブ群を
抽出しそれらの機械間でジョブまたはジョブ群を交換し
た状態の評価値を計算することによって、より制約条件
が充足される方向に逐次的に改善を行いスケジュール解
を生成する第２の処理手段とを備えると共に、動的ジョ
ブ制御機構を備えるよう構成する。

〔産業上の利用分野〕

本発明は、所定の制約条件を満足するように動的ジョブ
を含むジョブを機械に割り当てるという枠組みで捉える
ことのできるスケジューリング問題を、計算機によって
処理する動的ジョブ処理を含むスケジューリング問題解
決支援システムに関する。

スケジューリング問題の多くは、「ジョブを機械に割り
付ける問題」と捉えることができる。機械とは、ジョブ
によって一定時間拘束される対象であって２割り当てら
れたジョブを実行するものである。例えば、トラックに
より、所要の地点間で貨物を輸送する場合に、貨物を運
搬するトラック等が機械であり、貨物輸送要求がジョブ
となる。

このようなスケジューリング問題は、計画型エキスパー
トシステム等の適用対象問題の１つであるが、この種の
問題が組み合わせ問題に陥りやすいなどの特質から、高
速な解生成が困難でありそれを解決して、実用的システ
ムを構築できるようにする技術的手段が望まれている。

〔従来の技術〕

例えば、ｎ個所の営業所とｍ台のトラックが与えられ、
それらの営業所間に所要数の便を実現するようなトラン
クの運行計画を行うスケジューリング問題の処理を考え
る。

その場合に、各営業所の地理的関係（営業所を結ぶ経路
、その間の運行の所要時間等）、各営業所における荷積
み、荷下ろしその他の所要時間営業所の営業時間、営業
所ごとの荷の到着および積み出し等の時刻の要求その他
が制約条件として与えられる。

この問題の解は１例えば各トランクＴ１．Ｔ２・・・が
、どの営業所を何時に出発して、どの営業所に何時に到
着し、そこで何分間作業し、さらに他の営業所へ向かっ
て何時に出発し、・・・というような１日のスケジュー
ルであり、この解を前記の制約条件を満足するように求
めることが必要とされる。

このようなスケジューリング問題は、一般にトラックを
「機械」とし、ある営業所から他の営業所への運行等を
、その機械で処理される「ジョブ」として、８！１械に
ジョブを割り付ける問題として１足えることができる。

この種の問題を解く場合に２間面を数式化して数学的に
解を求める。いわゆるオペレーション・リサーチ等の解
析手法があるが、前記のような現実の問題では１問題を
大幅に単純化しない限り。

それを数式化することが極めて困難であり、そのため、
実際に適用できない場合が多い。

また、数式化が可能であっても、制約条件の変更がある
と、一般に数式の構成から再検討を要することになり、
事態の変化に対応することが困難な場合が多い。

一方、解析的手法ではなく、ａ械に対するジョブυｊり
当ての１時間軸上におけるすべての組み合わせについて
、制約条件を満足するものを、網羅的に探索する方式も
考えられているが、探索空間が広すぎるため、一般に実
用的な処理時間でスケジュール解を得ることが困難であ
る。

そこで５本発明者等は、スケジューリング問題の解を裔
速に得るための方式／方法として９次のような技術を提
案している。

その１つは、ヒユーリスティクスを用いて決定的なスケ
ジューリングを行うものであり２機械とジョブのｉ！沢
を分離し、解空間を部分空間に限定することにより、計
算時間を短縮するものである（特願昭６２−２６７５６
１号）。

また、１つは、とりあえず制約条件を緩和して全ジョブ
を機械に割り付け９機械間で交換可能なジョブまたはジ
ョブ群を、評価値の計算結果に従って逐次交換すること
により、新たな状態を生成していき、最終的にすべての
制約条件を満たすスケジュール解を求めるものである（
特願昭６２−２７４０８９号）。

更に前記２つの技術を段階的に適用するようにしたスケ
ジューリング問題解決支援システム（特願昭−１０７３
３０号）を提案している。以下、当該段階的に適用する
技術について延べておく。

第４図は段階的適用を説明するための図である。

第４図において、１０はスケジューリングの対象として
入力される問題、１１はＣＰＵおよびメモリ等からなる
処理装置、１２はヒユーリスティクスを用いてジョブの
選択および機械に対するｖｌり付けを行うジョブアロケ
ータ、１３は状態の改善を行いスケジュール解を生成す
るジョブモディファイヤ、１４は得られたスケジュール
解を出力するスケジュール解出ノｊ部、１５は与えられ
た問題ＩＯに対するスケジュール解を表す。

ジョブアロケータ１２は、ジョブ、機械および制約条件
により規定された問題ｌＯが与えられると、ジョブを機
械に対して時間軸上で割り当てるという枠組みのもとで
、ヒユーリスティクスを用いることにより、決定的な手
順でジョブを機械に割り付けていき、スケジューリング
を行っていく。

最終的に、すべてのジョブが制約条件を満たして各機械
に割り付けられれば、スケジューリング成功として、そ
の結果をスケジュール解１５とする。

決定的なジョブの割り付けにあたって、制約条件を満た
すことができず、未割り付けのジョブが残された場合、
与えられた制約条件を緩和することにより、未割り付け
のジョブを制約条件未充足のままｉ械に割り付け、−９
全ジョブの削り付け状態を生成して、その結果をジョブ
モディフプイヤ１３に通知する。

ジョブモディファイヤ１３は、ジョブアロケータ１２が
スケジ１−ル解を導出できず、制約条件が未充足の全ジ
ョブδすり付け状態情報を通知してきた場合２その全ジ
ョブ割り付け状態を初期状態として、異なる機械の間で
交換可能な割り付け済みジョブまたはジョブ群を抽出し
、それらの機械間でジョブまたはジョブ群を交換した状
態の評価値を計算することによって、より制約条件が充
足される方向に逐次的に改善を行い、スケジュール解を
生成する処理を行う。こうして得られたスケジュール解
を、スケジュール解出力部Ｉ４を介して出力する。

本発明では、ジョブアロケータ１２によるヒユーリステ
ィクスを用いた決定的なスケジューリングと、ジョブモ
ディファイヤ１３による逐次改善法をヘースにしたスケ
ジューリングの２段階制御によって、スケジュール解の
生成を行うようにしている。

ジョブアロケータ１２では２　ジョブを決定的に機械に
割り付けていくので、ジョブ数が増加しても、全ジョブ
に対する処理時間は、リニアに増加するだけである。ま
た、スケジュール解に到達できない場合でも、ある程度
、解に近い割り付け状態を生成して終了する。従って、
ジョブアロケータ１２によって生成した状態から、ジョ
ブモディファイヤ１３によって逐次改善を行っていけば
５解に近い状態からの改善によって、少ない状態の評価
およびジョブ等の交換の回数で、スケジュール解に到達
することができるようになる。

すなわち、単独にジョブモディファイヤ１３だけで、初
期状態を生成して、その逐次改善を行った場合には、ジ
ョブ数の増加に伴い、交換実行回数等の組み合わせ問題
的増加が生しることになるが、ジョブアロケータ１２と
の連携により、交換実行回数等を削減し、大規模データ
を取り扱うようなスケジューリング問題についても、高
速な解生成を実現することが可能になる。

第５図はジョブアロケータの処理フロー、第６図はジョ
ブモディファイヤの処理フロー、第７図はジョブモディ
ファイヤによる処理の例を示す。

トラックによる一日の陸送計画を立てるスケジューリン
グ問題では２例えば機械としてｍ台のトラックが指定さ
れ、ｎ個所の営業所間について。

「営業所Ｐから営業所Ｑへの便」というようなジョブが
指定される。また、営業所間の所要時間その他の制約条
件が設定される。

このようなスケジューリング問題の入力に対し第４図に
示すジョブアロケータ１２は、第５図に示すような処理
により、決定的なスケジューリングを行う。以下の説明
における■〜０は、第５図に示す処理■〜＠に対応する
。

■　現時点において、δＩＪり当て可能な注目機械を選
択する。なお１割り当て可能な機械がない場合には、最
も早くジョブから解放される機械に着目し、その解放さ
れる時点まで時間を進めてその機械を注目機械とする。

次に割り当て候補となるジョブ集合の選択を行うが、こ
の選択にあって、−例として、妥当なジョブを対象とす
るための時間幅として、必要最大時間と、可能最小時間
の２つの時間パラメータを用いる。必要最大時間は、ど
のジョブを割り当てても、その機械はその時間後に割り
当て可能になるという時間であり、可能最小時間は１機
械の遊び時間が少なくなるように、最びの許容時間とジ
ョブの発生鋲度との関係から定める時間である。これら
の時間は１問題に応して定数として与えられるが１試行
によるチューニングによって、適当な値をぶふようにす
るとよい。

■　注目機械を基準として、ジョブの割り当て開始可能
時間の最終時刻が、現時刻から必要最大時間内に含まれ
るジョブ（以下、必要最大ジョブという）の集合Ｊｓｌ
を抽出する。

■　また、注目機械を基準として、ジョブの割り当て開
始可能時間の最初の時刻が、現時刻から可能最小時間内
に含まれるジョブ（以下、可能最小ジョブという）の集
合Ｊｓ２を抽出する。

■　次に、注目機械以外の機械が、必要最大ジョブの集
合Ｊｓｌを処理可能であるか否かを判断する。ここでは
１次のような判断を行う。

必要最大ジョブとして、第５図図中の（ａ）に示すよう
に、ジョブＪ１〜ｊ４があったとする。

まず、最初のジョブＪ、を処理可能な機械で最も遅く空
きになる機械Ｍ３をジョブＪ１に対応づける。次にジョ
ブＪ２について、同様に機械Ｍ２を対応づける。ジョブ
Ｊ、についても同様である。、最終的に、ジョブＪ４に
ついても注目機械以外に割り当て可能であるｇｌ　織Ｍ
　、があれば、必要最大ジョブを、注目機械以外で処理
可能であることになる。

■　注目機械以外の機械で、必要最大ジョブの集合Ｊｓ
ｌを処理できない場合１選択ジョブとしてこの集合Ｊｓ
ｌを採用する。

■　注目機械以外の機械で、必要最大ジョブの集合Ｊｓ
ｌを処理できる場合、注目機械を早く稼動させたほうが
よいので、可能最小ジョブの集合Ｊｓ２を選択ジョブと
して採用する。

■　選択ジョブの中から注目機械に割り当てるジョブを
決定する。制約条件を考慮するとともに。

選択ジョブ集合の要素を評価し、最もよいジョブを割り
当てるようにする。

■　制約条件を満たすジョブの割り付けが可能であった
かどうかを判定し、制約条件を満たす解が得られなかっ
た場合、処理＠へ移る。

■　全ジョブについてのスケジュールが終了したかどう
かを判定する。全ジョブについてのスケジュールが終了
した場合、必要とするスケジュール解が得られたことに
なるので、第４図に示すスケジュール解出力部１４に結
果を通知し。

処理を終了する。

［相］　処理すべきジョブが残っている場合７時間の経
過や条件の変更に応じて、新しいジョブの生成が必要に
なったかどうかを調べる。ジョブの生成が必要でない場
合、処理■へ制御を戻し。

同様に処理を繰り返す。例えば、営業時間の終了時刻が
近づいたときに、トランクが車庫のない営業所にいる場
合には、そのトラックを車庫のある営業所へ移すための
ジョブの生成が必要になる。

■　ジョブの生成が必要になった場合には、そのジップ
を生成して内部テーブル（図示省略）に設定し、処理■
へ制御を戻して同様に処理を繰り返す。

■　制約条件を満たすジョブの割り付けができなくなっ
た場合、制約条件を緩和して１強制的に未割り付けジョ
ブを機械に割り付ける。そして。

その結果を第４図に示すジョブモディファイヤ１３に通
知し、ジョブアロケータ１２の処理を終了する。

ジリブモディファイヤ１３では、ジョブアロケータ１２
からの通知により１例えば第６図に示す処理■〜■のよ
うな処理を実行する。

■　まず、制約条件が未充足である全ジョブ割り付け状
態の情報を受は取る。それを初期状態として、以下の処
理による逐次改善を行う。

■　現在の割り付け状態を、制約条件に基づいてチエツ
クし、制約条件をすべて満足していればその状態をスケ
ジュール解と判断して、その状態の悄叩を、第４図に示
すスケジュール解出力部１４を介して出力する。

■　状態が制約条件を満足していない場合、そのジョブ
の割り付け状態から、任意の機械に割り付けられている
ジョブの部分集合で、相互に交換可能な部分集合を検索
して、それをスワップ候補とする。

交換可能な部分集合として１例えば異なる２つの機械に
割り当てられているジョブで、出発営業所を同じくする
ジョブ以降に並ぶ１以上のジョブからなる各ジョブの列
、あるいは出発営業所を同しくするジョブから、到着営
業所を同しくするジョブまでの各ジョブの列その他を選
ぶことができる。また、一方の部分集合が空な場合を含
めて、単にある機械に割り当てられているジョブまたは
ジョブの列を、他の機械に移動する場合もスワップ候補
となる。

■　スワップ候補がヰ★索されると、その候補のジョブ
部分集合を、該当する機械間で交換して得られる状態に
ついて、制約条件に関連する評価値を計算する。この評
価値として１例えば各便の超過時間を採ることができる
。

■　交換して得られる状態の評価値が、交換前の現状態
の評価値より改善されているかどうかを判定条件に基づ
いて判定する。改善されないと判定した場合には、処理
■へ戻り、別のスワップ候補を検索する。

■　交換によって改善される場合には、スワップ候補の
ジョブまたはジョブ群の交換を実行し。

状態を新しい状態に更新した後、処理■へ制御を戻して
、行状態が解になっているかどうかをチエツクする。以
下７処理■ないし処理■を繰り返し、状態を逐次改善し
て、スケジュール解を求める。

このジョブモディファイヤ１３による逐次改善の処理を
、第７図に示す具体例に従って説明する。

なお、説明を簡単にするために、ここでは、ジョブアロ
ケータ１２による処理とは独立した処理として説明する
。

例えば第７図（イ）に示すように、営業所Ａ〜営業所り
の４個所の営業所があり、営業所Ａ−Ｂ間で４便（２往
復）、他のすべての営業所間でそれぞれ２便のジョブが
あったとする。そのジョブを実行する機械であるトラッ
ク（Ｔ１．Ｔ２゜Ｔ３）は、３台あったとする。

また１次のような制約条件が与えられたとする。

（１）トランクＴｌ、Ｔ２．Ｔ３は、各々営業所Ａ。

Ｂ、Ｃに初期配置されている。

（２）各営業所間の所要時間は、すべて５０分を要する
。

（３）各トラックに割り当てる便の所要時間は２００分
以下でなければならない。

（４）　　全トラックを運行する。

（５）各トラックは、終了時に営業所Ａ、Ｂ、Ｃに配備
されなければならない。

ここで、各トラックに割り当てた便の総研要時間のうち
２００分を超える時間の値を評価値とし。

判定条件として１次の条件を指定する。

スワップ候補の現評価値の一方をｅＩ＋　他方を８２と
し、交換実行後の新評価値を、それぞれｎ　ｅ　＋　＋
　ｎ　ｅ　ｔとして ＋Ｈｘ（ｅ、　　、　ｅｚ　　）　　＞　　ｍａｘ（ｎ
ｅＩ　、ｎｅｚ　　）または（（ｅ１＝ｎｅ、）かつ（
ｅｚ　＞ｎｅｚ　）　）または（（ｅｚ　＝［ｊ２）か
つ（ｅ、　＞ｎｅｌ）　１を満足するとき、状態が改善
されるとする。

ここで、スワップ候補におけるジョブの部分集合の交換
は、出発点と到着点が同一のバスを構成するジョブの列
について行うループスワップと。

ある出発点以降の全パスを構成するジョブの列について
行うテールスワップの２種類とし５　このような条件の
バスで出発点を同じくするバスを異なるジョブ集合から
検索して、スワップ候補とする。

以上を条件としてスケジューリングを行うと。

例えば第７図（ロ）に示すｔａ＋〜ｆｃｊのように、逐
次改善によるスケジュール解が求められる。

すなわち、ジョブモディファイヤが処理する初期状態が
、仮に（ａ）のようであったとすると１例えばトラック
ＴｌとＴ２間のスワップ候補として。

図に点線の枠で示した部分をとりあげ、ループスワップ
の対象とする。なお、ここでジョブの割り当てがないト
ラックＴ２およびＴ３には、それぞれ営業所ＢからＢ、
営業所ＣからＣへのダミーの便があるものと見ることが
できる。

（ａｌの状態における評価値は、トラックＴ１について
、５０Ｘ１２−２００＝４００であり、Ｔ２については
、−２００である。ここで、前記のループスワンプを行
った場合、評価値は、トラックＴ１について０１　トラ
ックＴ２について２００となる。従って５前記判定条件
により、改善が得られると判断し、交換を実行して、（
ｂ）の新状態を得る。

次に、評価値の間隔の大きいトラックＴ２とＴ３との間
のスワップ候補を検索し、（ｂ）において点線の枠で示
した部分のテールスワップをとりあげるとすると、その
スワップ候補を交換した場合の評価値は、トランクＴ２
．Ｔ３のいずれについても、０になる。従って１判定条
件により、改善が得られることがわかり、交換を実行す
る。これにより、（Ｃ）の状態を得る。この状態は、制
約条件をすべて満足するので、スケジュール解となる。

第７図（ロ）に示すｆａ）の初期状態などを、あらかじ
め第４図に示すジョブアロケータ１２によって生成し、
スケジュール解に近い状態から逐次改善を行うので、も
っと複雑な問題に対しても、高速にスケジュール解を得
ることができる。

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

口１記第４図に示した如き処理の場合には２割りつける
べきジョブをいわば静的な集合の各要素として扱い、こ
の静的なジョブに対してスケジューリングの解を生成す
るものに相当している。この処理は２例えば、旅客機の
フライト・スケシュリングを立案する問題に対応してい
る。しかし例えば石油貯蔵タンクへのタンク操りのスケ
ジューリング問題の場合においては、輸送する船の大き
さやタンク内の石油の消費状況などにもとづいて、いつ
までに次の輸送を行うべきか、あるいはいつ以降におい
て輸送すべきかが定まってくるもので、スケジューリン
グ処理の進行の状態によって、ジョブが動的に生成され
たり消去されたりする必要がある。このために、前記第
４図に示した技術のみでは、正しく対処することができ
ないことが生しる。

本発明は、動的にジョブを生成しあるいは消去しつつ効
率よく妥当なスケジュール解を導出する手段を提供する
ことを目的としている。

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

第１図は本発明の原理構成図を示す。回申の符号１０は
スケジューリングの対象として入力される問題、１１は
ＣＰＵおよびメモリ等からなる処理袋で、１２はヒユー
リスティクスを用いてジョブの選択および機械に対する
割り付けを行うジョブアロケーク、１３は状態の改善を
行いスケジュール解を生成するジョブモディフプイヤ、
１５は与えられた問題１０に対するスケジュール解２０
は本発明においてもうけられる動的ジョブ制御機構、２
１は割り付け状態評価部、２２は動的ジョブ属性記述部
、２３は動的ジョブ生成／消去条件管理部、２４はジョ
ブプール管理部、２５はジョブ生成／消去機構を表わし
ている。

動的ジョブ制′４′！５機構２０は１割り付け状態評価
部２１とジョブ生成／消去機構２５とに分けられる。ジ
ョブ生成／消去機構２５は、スケジューリング処理の進
行の間に現実にジョブを生成させおよび／または消去さ
せる働きをする。割り付け状態評価部２１は、動的ジョ
ブ属性記述部２２と動的ジョブ生成／消去条件管理部２
３と、ジョブプール管理部２４とをそなえている。

動的ジョブ属性記述部２２は、スケジューリング処理の
進行に対応し新しく動的にジョブを生成しおよび／また
は消去する条件を含む属性情報が記述される。

動的ジョブ生成／消去条件管理部２３は、動的ジョブ属
性記述部２２の内容を参照しつつ、ジョブアロケータ１
２における処理の進行と、ジョフモディファイヤ１３に
おける処理の進行とに対応して、動的にジョブを生成す
るかおよび／または消去するかを管理する。

ジョブプール管理部２４は、スケジューリング処理が開
始される以前から与えられている静的ジョブと、スケジ
ューリング処理の進行に対応して生成および／消去され
た動的ンヨプとをプールして管１里する。

〔作用〕

ジョブアロケータ１２が決定的な手順によるジョブの割
り付けを行う間に、またジョブモディファイヤ１３が割
り付け状態の逐次改善を行う間に。

割り付け状！声評価部２１における動的ジョブ生成／消
去条件管理部２３は、動的ジョブ属性記述部２２の内容
を参照しつつ、動的にジョブを生成しおよび／または動
的にジョブを消去する。そして。

その結果は、ジョブプール管理部２４においてプールさ
れ管理される。

ジョブ生成／消去機構２５は、生成されるべきジョブを
生成し、また消去されるべきジョブを消去する。

〔実施例〕

第２図はジョブ生成などを説明する説明図、第３図は本
発明の一実施例処理態様を示す。

第２図においては、成る石油タンクにＩＱＯが貯えられ
ている状況の下でスケジューリング処理が進行されてゆ
くが、時点Ｌ２において当該石油タンクの量がロワー・
リミットに達することが判明し５時点も、において＃１
ＳＨＩＰによって量ｑｌが運搬されたものとして示され
ている。

ンヨブアロケータ１２の処理の間に、第２図図示の如き
場合においては１時点ｔ２以前に当該石油タンクに対し
て石油を運搬すべきものとしてジョブが生成されて、ジ
ョブプール管理部２４にプールされることとなる。

ジョブアロケータ１２における処理において時点ｔ１に
おける＃　Ｉ　Ｓ　ＨＩ　Ｐによる運搬が仮決定されて
いるものとし、この状態の下でジョブモディファイヤ１
３が１時点１．における運搬としては＃２ＳＨＩＰによ
る運搬の方がより好ましいとの改善を行ったとする。

このような場合においては２時点ｔ４以前に当該石油タ
ンクに対して石油を運搬すべきものとするジョブが生成
されることとなる。即ち、ジョブモディファイヤ１３に
おける処理の間にも、新しくジョブが生成されることと
なる。勿論、場合においては、ジョブの消去が行われる
こととなる。

動的ジョブ制御機構２０は、概念的には、第２図に関連
して延べた如き処理を実行するものと考えてよい。

第３図において、符号１２．１３は夫々第１図に対応し
ている。処理は次の如く行われる。即ち。

（１）　　まず、初期状態として、動的ジョブをその時
点で生成する必要があるか否かがチエツクされる。必要
ならば生成される。

（２）　　ジョブアロケータ１２によるスケジューリン
グ処理が実行される。

（３）　　ジョブの割り付けを行い２割り付け状態評価
部２１への通知が行われる。

（４）割り付け状態の評価が行われ、ジョブを生成する
必要があるか否かチエツクされる。

（５）生成する場合にはジョブ生成の後に、ジョブアロ
ケータ１２によるスケジューリング処理に戻る。また生
成する必要のない場合には１図示を省略しているが、ジ
ョブプール管理部２４内に未割り付けのジョブが残って
いる限り、ジョブアロケータ１２によるスケジューリン
グ処理に戻る。

（６）　　ジョブ　アロケータ１２による処理が仮終了
すると、ジョブモデイファイヤ１３によるスケジューリ
ング処理が実行される。

（７）　　ジョブモディファイヤ１３により状態の改善
処理が実行され２割り付け状態評価部２１への通知が行
われる。

（８）割り付け状態の評価が行われ、ジョブを生成する
必要があるか、またジョブを消去する必要があるかがチ
エツクされる。

（９）生成する必要がある場合には、ジョブの生成が行
われた後に、その時点でジョブアロケーク１２によるス
ケジューリング処理に戻る。

００１　　消去する必要がある場合には、ジョブの消去
が行われた後に、ジョブモディファイヤ１３によるスケ
ジューリング処理に戻る。

０υ　勿論、必要に応して、ジョブモディファイヤ１３
による処理が終了した後に、再度ジョブアロケータ１２
による処理を行うようにされることもある。

〔発明の効果〕

以上説明した如く１本発明によれば、動的ジョブを含む
スケジューリング処理の問題を、ジョブを機械に割り付
けるという枠組みの下で処理することが可能となる。

図中、１０は入力される問題、１１は処理装置１２はジ
ョブアロケータ、１３はジョブモディファイヤ、１５は
スケジュール解、２０は動的ジョブ制御機構、２１は割
り付け状態評価部、２２は動的ジョブ属性記述部、２３
は動的ジョブ生成／消去条件管理部、２４はジョブプー
ル管理部、２５はジョフ生成／消去機構を表わす。

Claims (1)

1. 【特許請求の範囲】 所定の制約条件を満足するように、ジョブを機械に割り
   付けるという枠組みで捉えることのできるスケジューリ
   ング問題を、計算機によって処理するスケジューリング
   問題解決支援システムであって、 決定的な手順により、逐次的にジョブを機械に割り当て
   ていき、そのスケジューリングが成功しなかった場合に
   、制約条件を緩和することにより、全ジョブの割り付け
   状態を生成する第１の処理手段（１２）と、 前記第１の処理手段（１２）が生成した全ジョブの割り
   付け状態をもとに、任意の機械の間で交換可能な割り付
   け済みジョブまたはジョブ群を抽出し、それらの機械間
   でジョブまたはジョブ群を交換した状態の評価値を計算
   することによって、より制約条件が充足される方向に逐
   次的に改善を行い、スケジュール解を生成する第２の処
   理手段（１３）と共に、 少なくとも、 スケジューリング処理の進行に対応し新しく動的にジョ
   ブを生成しおよび／または消去する条件を含む属性情報
   が記述される動的ジョブ属性記述部（２２）と、 前記動的ジョブ属性記述部（２２）の内容を参照しつつ
   、前記第１の処理手段（１２）における処理の進行と、
   前記第２の処理手段（１３）における処理の進行とに対
   応して、動的にジョブを生成するかおよび／または消去
   するかを管理する動的ジョブ生成／消去条件管理部（２
   ３）と、 スケジューリング処理が開始される以前から与えられて
   いる静的ジョブと、前記生成および／または消去された
   動的ジョブとをプールして管理するジョブプール管理部
   （２４）と を有する割り付け状態評価部（２１）が用意され、かつ
   スケジューリング処理の進行の間に現実にジョブを生成
   させおよび／または消去させるジョブ生成／消去機構（
   ２５）が用意され、 前記割り付け状態評価部（２１）と前記ジョブ生成／消
   去機構（２５）とが動的ジョブ制御機構（２０）内に構
   成されており、 スケジューリング処理の進行の間にジョブを生成しおよ
   び／または消去しつつスケジューリング処理を実行する
   ようにした ことを特徴とする動的ジョブ処理を含むスケジューリン
   グ問題解決支援システム。