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

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 計算機により、在庫管理・生産管理などの分野で必要と
なるスケジューリングを行うスケジューリング問題解決
システムに関し。

ジョブを機械に割り当てるにあたって、ジョブと機械の
選択を分離し、解空間を部分空間に限定することにより
、計算時間の短縮を可能とすることを目的とし。

現在割当て可能状態にある１つの機械を注目機械として
選択する機械選択部と、該注目機械が処理可能な候補ジ
ョブ集合を、各ジョブ対応の割当て開始可能時間に関す
る必要最大時間および可能最小時間と、該注目機械以外
の機械との関係により９選択ジョブ集合に絞り込む処理
を行うジョブ選択部と、上記選択ジョブ集合の中のジ習
ブに。

上記注目機械を割り当てる処理を行う部分空間探索処理
部とを備えるように構成する。

〔産業上の利用分野〕

本発明は、計算機により、在庫管理・生産管理などの分
野で必要となるスケジューリングを行うスケジューリン
グ問題解決システムに関する。

スケジューリングは、エキスパートシステムなどのソフ
トウェア技術の向上により、ますます注目され、その実
現の需要が高まっている。このスケジューリングは、在
庫管理・生産管理などの広い分野で必要となる作業であ
るが、−船釣には。

所定の制約条件に従って、ジープを機械に割り当てるこ
とである。しかし、実際に適用対象となるスケジューリ
ングは、探索空間が広く、容易には実用化できない、そ
こで、スケジューリングの探索空間を小さクシ、計算時
間を短縮する技術が必要とされている。゛。

〔従来の技術〕

例えば、トラックによる集配所から集配所への一日の陸
送計画を立てる問題を考える。

スケジューリングすべきデータは、集配所ごとに「〜行
きトラック便」といった形式で与えられる。与えられる
トラック便の便数は、集配所により異なる。各集配所で
は、荷積、荷下ろしの時間および点検時間などの作業時
間を確保しなければならない、必要な作業時間は、集配
所により異なる。各トラックの集配経路は、夜間設備と
しての車庫のある集配所で始まり、車庫のある集配所で
終わる０例えば、魚市場からの鮮魚輸送など、集配所の
管轄市場の要求により、定期便として、特定時間に輸送
を行わなければならないものがある。

また、集配−所ごとに営業時間が定められている。

このような条件のもとで、どのように各トラックを運行
させるかという問題を、計算機により解く場合、トラッ
クを機械、輸送しなければならない仕事をジョブとして
、各ジョブにどの機械を割り当てるかを、探索によって
決定する。

従来方式によれば、このようなスケジューリングを行う
場合、ジョブと機械との時間軸上におけるすべての組み
合わせについての探索を行い、満足する解が得られるま
で、１つ１つのケースについて、制約条件をチエツクす
るようにされていた。

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

従来方式によれば、スケジューリングを実現する場合に
、事例に応じて８個別に解を求めるようにされ、解空間
のすべてについて制約条件のチエツクを行うようにされ
ているため、計算時間が膨大なものとなり、高性能計算
機を用いても、必要とする解を得ることができない場合
があった。

本発明は上記問題点の解決を図り、ジョブを機械に割り
当てるにあたって、ジョブと機械の選択を分離し、解空
間を部分空間に限定することにより、計算時間の短縮を
可能とすることを目的としている。

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

第１図は本発明の原理説明図である。

第１図において、１０はＣＰＵおよびメモリ等からなる
処理装置、１１は注目機械を選択する機械選択部、１２
は選択対象となるシップを抽出するジョブ選択部、１３
は割当て可能開始時間に関する必要量大時間内のジョブ
を選択する必要最大ジョブ選択部、１４は割当て可能開
始時間に関する可能最小時間内のジョブを選択する可能
最小ジョブ選択部、１５は必要最大ジョブ選択部１３お
よび可能最小ジョブ選択部１４が選択したジョブの中か
ら注目機械に割り当てるべきジョブ集合を選ぶジョブ集
合選択部、１６はジョブ集合選択部１５によって選択さ
れたジョブ集合について必要に応じて制約条件のチエツ
クを行いつつ注目機械に割り当てるべきジョブを決定す
る探索を行う部分空間探索処理部、１７は制約条件のチ
エツクを行う制約条件チェンク部を表す。

処理装置ｌＯに対する人力情報は、ジョブ、機械および
制約条件に関する情報である。出力情報は、各ジョブに
各機械をいつ割り当てればよいかというスケジューリン
グ結果の情報である。ジョブは、ある時間に処理されな
ければならない仕事であり１機械は、その仕事を実行す
る資源である。

一般に、ジョブは、ａ械に割当て可能な時間軸上の範囲
を持つ、スケジューリングの問題は、これらのジョブを
、各機械により、どのように処理していくかという問題
である。

機械選択部１１は、ある時点において１割当て可能状態
にある１つの機械または最も早くジョブから解放される
機械を、注目機械として選択する処理を行うものである
。ジョブ選択部１２は、この注目機械に対し、必要最大
ジョブ選択部１３および可能最小ジョブ選択部１４によ
り、必要最大ジョブおよび可能最小ジョブをそれぞれ選
択する。

ここで、必要量大ジョブは９例えば第１図ｔａ＞に示す
ジョブＪ１．Ｊ３．Ｊ４のようなジョブであり、可能最
小ジョブは３例えば第１図（ｂｌに示すジョブＪ１．Ｊ
ｘ、Ｊｓのようなジョブである。なお、第１図（Ｍｌ、
　（ｂｌにおいて、Ｗ、　〜Ｗ、１は９例えばトラック
を何時から何時までの間に出発させなければならないか
というような割当て開始可能時刻である。Ｔ１は必要最
大時間、Ｔｔは可能最小時間であり、ｔ、は、注目機械
の少ツブ開始可能時間＋　　ｔｌは、ｔｏに必要最大時
間Ｔ１を加えた時刻、ｔ！は、【。に可能最小時間Ｔ２
を加えた時刻である。

ここで、必要最大時間Ｔ１は、どのジョブを割り当てて
も、Ｔ１時間後のジョブには間に合うという時間であり
、可能最小時間Ｔ、は１機械の遊び時間が少なくなるよ
うに、遊びの許容時間とジョブの発生顛度との関係から
定める時間である。

これらの時間は２問題に応じて定数として与えられるが
、試行によるチューニングによって、最適値を選択する
ようにすればよい。

必要最大ジョブ選択部１３は１割当て開始可能時間の最
終時刻が、ｔ、より以前のジョブ集合を選択し、可能最
小ジョブ選択部１４は１割当て開始可能時間の最初の時
刻が＋　　ｔ８より以前のジョブ集合を選択する。

ジョブ集合選択部１５は、必要最大ジョブ選択部１３が
選択した必要最大ジョブを、注目機械以外の機械によっ
て処理可能であるか否かにより。

必要最大ジョブまたは可能最小ジョブを選択ジョブ集合
として採用する。

部分空間探索処理部１６は、この選択ジョブ集合につい
て、制約条件チエツク部１７により、制約条件のチエツ
クを行い、注目機械が処理すべきジョブを決定する。そ
の後２次の注目機械について同様にスケジューリングを
繰り返す。

〔作用〕

本発明では、ジョブおよび機械を別々に選択し。

制約条件を満たすスケジューリングを行う、ジョブの選
択とは、少なくとも１個の機械が割当て可能であるとき
、どのジョブを割り当てるかを決定することである。こ
こで、ジョブの選択にあたって、必要最大時間を導入し
、１個の機械が連続して処理する可能性のあるジョブ数
を探索する際の部分空間にとる０機械については、今割
当て可能な機械以外に、「必要最大時間内に含まれるジ
ョブ数個」の機械を考慮すれば、今割当て可能な機械が
いくつのジョブを処理しなければならないのかが分かる
。そこで、ジョブを選択する際の探索空間として、非常
に小さな部分空間をとればよいことになる。

また、必要最大時間内に含まれるジョブ（必要最大ジョ
ブ）を、注目機械以外の機械によって処理可能であると
き、現在の注目機械の遊び時間をできるだけ小さくする
のが望ましい、そこで、この場合には、可能最小時間に
含まれるジョブ（可能最小ジョブ）を選択ジョブの候補
として探索を行う、これにより、効率のよいスケジュー
リングが行われることになる。

〔実施例〕

第２図は本発明の一実施例処理説明図、第３図は本発明
の詳細な説明するためのスケジューリングデータの例、
第４図は本発明の詳細な説明するためのスケジューリン
グ結果の例を示す。

本発明は２例えば第２図に示すような処理によって実現
される。以下の説明における■〜＠は。

第２図に示す処理■〜＠に対応する。

■　現時点において割当て可能な注目機械を選択する。

なお１割当て可能な機械がない場合には。

最も早（ジョブから解放される機械に着目し。

その解放される時点まで時間を進めて、その機械を注目
機械とする。

■　注目機械を基準として、必要最大ジョブの集合Ｊｓ
Ｌを抽出する。

■　また、注目機械を基準として、可能最小ジョブの集
合Ｊｓ２を抽出する。

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

必要最大ジョブとして、第２図（ａ）に示すように、ジ
ョブＪＩ−Ｊａがあったとする。まず。

最初のジョブＪ、を処理可能な機械で、最も遅く空きに
なる機械Ｍ、をシップＪＩに対応づける０次にジ僧プＪ
８について、同様に機械Ｍ８を対応づける。シップＪＳ
につル１ても同様である。最終的にジョブＪ４について
も、注目機械以外に割当て可能である機械Ｍ、があれば
、必要最大ジョブを、注目機械以外で処理可能であるこ
とになる。

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

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

■　選択ジョブの中から注目機械に割り当てるジョブを
決定する０選択ジ茸ブ集合の要素を評価し、最も評価の
よいジョブを割り当てるようにするとよい。

■　制約条件があれば、その制約条件をチエツクする。

制約条件を満足する解が得られない場合。

スケジュール不可であるので、その時点における機械・
ジョブ・制約条件などの参考情報を必要に応じて出力し
、処理を終了する。

■　スケジユールが終了したか否か、すなわち。

する、スケジュールが終了した場合、処理Ｏへ制御を移
す。

［株］　時間の経過や条件の変更などにより、新しいシ
ップの生成が必要になったか否かを判定する。

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

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

＠　スケジェーリング対象のシップがな（なった場合、
内部テーブルに記憶しているスケジュール情報を出力し
、処理を終了する。

本発明は０例えば（従来の技術〕の欄で説明したような
、トランクによる集配所から集配所への一日の陸送計画
を立てる問題等について適用することができる。

このトラックによる陸送計画の問題で、スケジェーリン
グデータとして与えられたデータは１例えば第３図（Ａ
）ないしくＤ）のようなデータである。

スケジユーリングのための営業所情報として。

例えば第３図（Ａ）に示すように、各営業所ごとに、営
業時間、夜間設備（車庫）の有無およびトランクの初期
配置台数、荷積、ｆＩ下ろしの時間および点検時間など
の情報が入力情報とされる。

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

この定期便の情報は、別に例えば第３図（Ｃ）に示すよ
うな情報として入力される。

さらに、出発営業所から目的営業所までの、トラックで
の所要時間情報が２例えば第３図（Ｄ）に示すような情
報として与えられる。

このようなスケジェーリングデータに基づいて、　　　
　′スケジューリングを行うにあたって、ここでは。

トランクが機械として扱われ、また第３図（Ｂ）に示す
トラック便数に応じて、トランクを移動させる仕事が、
ジョブとして扱われる。

まず、朝の初期状態では１例えば第２営業所にある１台
のトラックを注目機械として、それを最初のスケジュー
リング対象とする。ここで、候補ジョブ集合は、第１営
業所への輸送、第３営業所への輸送、第４営業所への輸
送、・・・である、この例では、定期便以外については
２割当て開始可能時間の開始点は現時点で、その終了点
は、各営業所における営業終了時刻から、トランクでの
所要時間および作業時間を引いた時刻となる。定期便に
ついては、その出発時刻または時間によって。

割当て開始可能時間が定まる。

必要最大時間は９例えば２時間、可能最小時間は、３０
分というように適当に定めてよい、なお。

必要最大時間が短いほど探索効率は向上するが。

この必要最大時間が短すぎると、最適解が見つからない
可能性がある。

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

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

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

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

以上のスケジューリング処理により、！柊的に。

例えば第４図に示すようなスケジューリング結果が得ら
れる。この結果では　ｌ初に第２営業所にいるトラック
Ａが、４時ＯＯ分に第１営巣所へ向かって出発し、第１
営業所に５時００分に到着した後、５０分間の作業時間
をとり、５時５０分に。

第１営業所から第２営業所へ戻る。また、第９営業所か
ら第２営業所への定期便として、このトラックＡが、第
９営業所を１６時ｌＯ分に出発するようになっている。

他のトラックについても、それぞれ同様に、現在いる営
業所からの出発時間と。

その目的営業所が、順次、スケジューリングによって決
められる。

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

同様に適用可能である。

〔発明の効果〕

以上説明したように２本発明によれば、シップと機械の
すべての組み合わせによる探索空間を探索することなく
、非常に小さな部分空間を探索するだけで、スケジュー
リングを行うことができるので、スケジューリングのた
めの計算時間を大幅に短縮することが可能になる。

【図面の簡単な説明】

第１図は本発明の原理説明図。 第２図は本発明の一実施例処理説明図。 第３図は本発明の詳細な説明するためのスケジューリン
グデータの例。 第４図は本発明の詳細な説明するためのスケジューリン
グ結果の例を示す。 図中、ＩＯは処理装置、１１は機械選択部、１２はジョ
ブ選択部、１３は必要最大ジョブ選択部。 １４は可能最小ジョブ選択部、１５はジョブ集合選択部
、１６は部分空間探索処理部、１７は制約条件チエツク
部を表す。

Claims (1)

1. 【特許請求の範囲】 計算機によって、与えられたジョブに、そのジョブを処
   理すべき機械を割り当てるスケジューリングを行うスケ
   ジューリング問題解決システムにおいて、 現在割当て可能状態にある１つの機械を注目機械として
   選択する機械選択部（１１）と、 該注目機械が処理可能な候補ジョブ集合を、各ジョブ対
   応の割当て開始可能時間に関する必要最大時間および可
   能最小時間と、該注目機械以外の機械との関係により、
   選択ジョブ集合に絞り込む処理を行うジョブ選択部（１
   ２）と、 上記選択ジョブ集合の中のジョブに、上記注目機械を割
   り当てる処理を行う部分空間探索処理部（１６）とを備
   えたことを特徴とするスケジューリング問題解決システ
   ム。