JPH01277902A - スケジューリング問題解決支援システム - Google Patents

Abstract

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

Description

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

効率よく妥当なスケジュール解を導出する手段を提供す
ることを目的とし。

決定的な手順により、逐次的にジョブを機械に割り当て
ていき、そのスケジューリングが成功しなかった場合に
、制約条件を緩和することにより。

全ジョブの割り付け状態を生成する第１の処理手段と、
前記第１の処理手段が生成した全ジョブの割り付け状態
をもとに、任意の機械の間で交換可能な割り付け済みジ
ョブまたはジョブ群を抽出し。

それらの機械間でジョブまたはジョブ群を交換した状態
の評価値を計算することによって、より制約条件が充足
される方向に逐次的に改善を行い。

スケジュール解を生成する第２の処理手段とを備えるよ
うに構成する。

〔産業上の利用分野〕

本発明は、所定の制約条件を満足するように。

ジョブを機械に割り当てるという枠組みで捉えることの
できるスケジューリング問題を、計算機によって処理す
るスケジューリング問題解決支援システムに関する。

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

このようなスケジューリング問題は、計画型エキスパー
トシステム等の適用対象問題の１つであるが、この種の
問題が組み合わせ問題に陥りやすいなどの特質から、高
速な解生成が困難であり。

それを解決して、実用的システムを構築できるようにす
る技術的手段が望まれている。

〔従来の技術〕

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

その場合に、各営業所の地理的関係（営業所を結ぶ経路
、その間の運行の所要時間等）、各営業所における荷積
み、尚下ろしその他の所要時間。

営業所の営業時間、営業所ごとの荷の到着および積み出
し等の時刻の要求その他が制約条件として与えられる。

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

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

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

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

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

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

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

そこで１本発明者等は、スケジューリング問題の解を高
速に得るための方式／方法として１次の２種類の技術を
提案している。

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

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

前者の手法では、決定的にジョブを機械に割り付けてい
くので、Ｉｌｌ械やジョブの増加に対して。

組み合わせ問題的な計算時間の増加を避けることができ
る。しかし、場合によっては、すべての制約条件を満た
す完全な解の生成率がよくないことがある。

一方、後者の逐次改善をベースにする手法では。

最初に全ジョブを機械に割り付ける状態によって。

ジョブまたはジョブ群の交換回数が大幅に増加すること
があり、特に大規模データを取り扱うスケジューリング
問題では、高速な解生成が難しくなることがある。

本発明は上記問題点の解決を図り、前記の２つの手法を
組み合わせて２段階制御を行うことにより１両者の長所
を活かし、効率よく妥当なスケジュール解を導出する手
段を提供することを目的としている。

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

第１図は本発明の詳細な説明するための図である。

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

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

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

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

〔作用〕

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

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

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

〔実施例〕

第２図は本発明の一実施例に係るジョブアロケータの処
理フロー、第３図は本発明の一実施例に係るジョブモデ
ィファイヤの処理フロー、第４図はジョブモディファイ
ヤによる処理の例、第５図は本発明の詳細な説明するた
めのスケジューリングデータの例、第６図はジョブおよ
び機械の記述例、第７図はジップアロケークによる強制
割り付け説明図、第８図は本発明の適用例によるスケジ
ューリング結果の例を示す。

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

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

このようなスケジューリング問題の入力に対し。

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

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

その機械を注目機械とする。

次に割り当て候補となるジョブ集合の選択を行うが、こ
の選択にあって２本実施例では、妥当なジョブを対象と
するための時間幅として。

必要最大時間と、可能最小時間の２つの時間パラメータ
を用いる。必要最大時間は、どのジョブを刷り当てても
、その機械はその時間後に割り当て可能になるという時
間であり、可能最小時間は２機械の遊び時間が少なくな
るように。

遊びの許容時間とジョブの発生頻度との関係から定める
時間である。これらの時間は１問題に応じて定数として
与えられるが２試行によるチューニングによって、適当
な値を選ぶようにするとよい。

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

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

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

必要最大ジョブとして、第２図ｆａｌに示すように、ジ
ョブＪ、〜Ｊ４があったとする。まず。

最初のジョブＪ１を処理可能な機械で、最も遅（空きに
なる機械Ｍ、をジョブＪ１に対応づける０次にジョブＪ
□について、同様に機械Ｍ８を対応づける。ジップＪ、
についても同様である。最終的に、ジップＪ４について
も、注目機械以外に割り当て可能である機械Ｍｌがあれ
ば。

必要最大ジップを、注目機械以外で処理可能であること
になる。

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

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

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

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

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

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

処理を終了する。

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

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

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

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

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

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

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

■　現在の割り付け状態を、制約条件に基づいてチエツ
クし、制約条件をすべて満足していれば。

その状態をスケジュール解と判断して、その状態の情報
を、第１図に示すスケジュール解出力部１４を介して出
力する。

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

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

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

■　交換して得られる状態の評価値が、交換前の現状態
の評価値より改善されているかどうかを。

判定条件に基づいて判定する。改善されないと判定した
場合には、処理■へ戻り、別のスワップ候補を検索する
。

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

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

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

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

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

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

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

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

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

（３）各トランクに割り当てる便の所要時間は。

２００分以下でなければならない。

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

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

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

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

スワップ候補の現評価値の一方をｅＩ＋　他方をＣ２と
し、交換実行後の新評価値を、それぞれｎｅ、　、ｎｅ
ｚ　として。

ｗａｘ（ｅ＋　＋　　ｅｘ　）　＞ｗａｘ（ｎｅ＋　、
　ｎｆｌｘ　）または（（ｅ、　＝ｎｅ、　）かつ（ｅ
、　＞ｎｅｔ　）　１または（（ｅ、　＝ｎｅ、　）か
つ（１ｌｌｌ　＞ｎｅｌ　）　１を満足するとき、状態
が改善されるとする。

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

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

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

例えば第４図（ロ）に示す（ａｌ〜（Ｃ１のように、逐
次改善によるスケジュール解が求められる。

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

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

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

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

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

次に、同種のスケジューリング問題であって。

実用上必要となるようなスケジューリング問題の例を説
明する。

トランクによる１日の陸送計画を立てる問題で。

スケジューリングデータとして与えられたデータは１例
えば第５図（Ａ）ないしくＤ）のようなデータである。

スケジューリングのための営業所情報として５例えば第
５図（Ａ）示すように、各営業所ごとに。

営業時間、夜間設備（車庫）の有無、トラックの初期配
置台数、荷積み、荷下ろしの時間および点検時間などの
情報がある。

また、トランク便数の情報として２例えば第５図（Ｂ）
に示すように、出発営業所から目的営業所への必要なト
ラック便数情報が入力情報とされる。ここで、Ｏ印で囲
んだ数値は、出発時刻または出発時間が定められた定期
便を含む便数を示している。

この定期便の情報は、別に例えば第５図（Ｃ）に示すよ
うな情報として入力される。　　゛さらに、出発営業所
から目的営業所までの、トラックでの所要時間情報が２
例えば第５図（Ｄ）に示すような情報として与えられる
。

このようなスケジューリング問題を解くにあたって、ト
ランクは機械として扱われ５便数に応してトランクを移
動させる仕事がジョブとして扱われるが、これを１例え
ば第６図に示すジョブおよび機械の記述のようにまとめ
る。

第６図（イ）に示すジョブの表現において、最早開始時
刻は、このジョブを開始することができる最も早い時刻
である。最遅開始時刻は、このジョブを開始することが
できる最も遅い時刻である。

最早終了時刻、最遅終了時刻は、それぞれこのジョブを
終了することができる最も早い時刻、最も遅い時刻であ
る。ジョブサイズは、ある機械がそのジョブを実行する
のに必要な時間である。

各機械についても、第６図（ロ）に示すように。

ジョブ処理性能、動作開始可能時刻、最遅動作終了時刻
、最初に配置されている位置などの情報の記述にまとめ
られる。

第６図に示すような記述は、第５図（Ａ）ないしＣＤ）
に示す情報を入力するために、ユーザ自身が行ってもよ
く、またユーザインタフェース部において、メニュー等
による入力情報に基づき。

システム内部で自動的に生成するようにしてもよい。

各種制約条件については９例えばプロダクションルール
等で記述することができる。

第１図に示すジョブアロケータ１２は、内部知識として
有するヒユーリスティクスを用いて、各ジョブの割り付
け処理を行う、朝の初期状態では。

例えば第２営業所にある１台のトランクを注目機械とし
て、それを最初のスケジューリング対象とする。ここで
２割り付け候補のジョブ集合は、第１営業所への輸送、
第３営業所への輸送、第４営業所への輸送、・・・であ
る、必要最大時間は１例えば２時間、可能最小時間は３
０分というように適当に定めてよい、。

最初、第２営業所には、４台のトランクがいるので、注
目機械以外の機械は、残りの３台のトラックということ
になる。なお、各トラックのスケジューリングが進み、
必要最大時間内に、他の営業所から到着したトランクが
使用可能になると。

そのトラックも対抗機械の１つとして数えられる。

第２図に従って説明した処理により、注目機械に対する
選択ジップとして、必要最大ジョブを採用するか、可能
最小ジョブを採用するかを決め。

その注目機械（トランク）に、どの営業所へ出発すれば
よいかのジョブを割り付ける。その後５次に現在割り当
て可能であるトラックを注目機械として選択し、同様に
ジョブを選択してスケジューリングを進める。

この結果、すべてのジョブを、制約条件を満たすように
割り付けることができれば１それがスケジュール解とな
る。しかし、第７図（イ）に示すジョブＪ２３．Ｊ２６
．・・・のように、制約条件を満たして割り付けること
ができないジョブが残った場合１例えば時間的な制約条
件を緩和し、未割り付けジョブの開始状態、終了状態の
みを考慮して、第７図（ロ）に示すように、接続可能な
位置に強制的にジョブを押し込む、こうして全ジョブ割
り付け状態を生成し、第１図に示すジョブモディファイ
ヤ１３を起動する。

ジョブモディファイヤ１３は、第３図に示す処理により
、第４図の例と同様な逐次改善を行い。

すべての制約条件を満たずスケジュール解を求める。す
なわち、第７図（ロ）に示す機械（Ｍｌ。

Ｍ２．・・・）に割り付けられたジョブのシーケンスに
対し１部分シーケンスの交換操作を行い、層状態への収
束を図る。

以上の２段階制御によるスケジューリング処理により、
最終的に例えば第８図に示すようなスケジェーリング結
果が得られる。この結果では、最初に第２営業所にいる
トランクＡが、４時００分に第１営業所へ向かって出発
し、第１営業所に５時００分に到着した後、５０分間の
作業時間をとリ、５時５０分に第１営業所から第２営業
所へ戻る。また、第９営業所から第２営業所への定期便
として、このトランクＡが、第９営業所を１６時１０分
に出発するようになっている。他のトランクについても
、それぞれ同様に、現在いる営業所からの出発時刻と、
その目的営業所等が得られる。

もちろん１本発明は、このようなトラックの陸送計画に
限らず、他のスケジューリング問題にも。

同様に適用可能である。

例えば次のような輸送計画のスケジューリングデータに
よる各問題について、実測した処理時間等は、以下のと
おりであった。

（１）　　スケジューリングデータ ここで、ジシブの欄における括弧内の数値は。

定期便のように開始時刻が定められているジョブ（固定
ジョブという）の数である。エリア八では。

全ジョブ４９個のうち、１６個が固定ジョブであること
を意味している。

（２）　　ヒユーリスティクスを用いたスケジューリン
グの結果 （３）逐次改善法だけを用いて、ランダムな初期状態か
ら開始したスケジューリングの結果操作回数は、ジョブ
またはジョブ群の交換回数である。エリアへの場合を除
き、スケジュール解が得られているが、ジョブ数の増加
に伴って、急激に処理時間が楢大している。

（４）本発明により、ヒユーリスティクスを用いる手法
と逐次改善法とを組み合わせて行ったスケジューリング
の結果 このスケジューリングの実験例から明らかなように０本
発明によれば、スケジュール解の生成率が高くなるとと
もに、特にジョブ数が増加した場合に、逐次改善の操作
回数が単独の場合よりもかなり削減されるので、処理時
間も大幅に短縮されることが予想できる。

〔発明の効果〕

以上説明したように１本発明によれば、大規模データを
取り扱うスケジューリング問題についても、高い生成率
でスケジュール解を生成することができるようになり、
またスケジューリングのための計算時間を大幅に短縮す
ることができるようになる。

【図面の簡単な説明】

第１図は本発明の原理説明図。 第２図は本発明の一実施例に係るジョブアロケータの処
理フロー。 第３図は本発明の一実施例に係るジョブモディファイヤ
の処理フロー。 第４図はジョブモディファイヤによる処理の例。 第５図は本発明の詳細な説明するためのスケジューリン
グデータの例。 第６図はジョブおよび機械の記述例。 第７図はジョブアロケータによる強制割り付け説明図。 第８図は本発明の適用例によるスケジューリング結果の
例を示す。 図中、１０は問題、１１は処理袋！１１２はジョブアロ
ケータ、１３はジョブモディフ１イヤ。 １４はスケジュール解出力部、１５はスケジュール解を
表す。

Claims (1)

1. 【特許請求の範囲】 所定の制約条件を満足するように、ジョブを機械に割り
   付けるという枠組みで捉えることのできるスケジューリ
   ング問題を、計算機によって処理するスケジューリング
   問題解決支援システムであって、 決定的な手順により、逐次的にジョブを機械に割り当て
   ていき、そのスケジューリングが成功しなかった場合に
   、制約条件を緩和することにより、全ジョブの割り付け
   状態を生成する第１の処理手段（１２）と、 前記第１の処理手段（１２）が生成した全ジョブの割り
   付け状態をもとに、任意の機械の間で交換可能な割り付
   け済みジョブまたはジョブ群を抽出し、それらの機械間
   でジョブまたはジョブ群を交換した状態の評価値を計算
   することによって、より制約条件が充足される方向に逐
   次的に改善を行い、スケジュール解を生成する第２の処
   理手段（１３）とを備えたことを特徴とするスケジュー
   リング問題解決支援システム。