(57)【特許請求の範囲】
【請求項１】
スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータで行う方法であって、
中央処理手段は、
スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、
上記記憶手段に記憶された一部区間をスケジュール対象として、或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間について終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行うことを特徴とするスケジューリング方法。
【請求項２】
上記中央処理手段は、上記一部区間を対象としてスケジューリング処理を行うときに、上記記憶手段に記憶された一部区間についての直前のスケジューリング結果である順列の後ろから少なくとも１個のスケジュール対象要素と、それに続いて並べられている上記直前のスケジューリング段階では未処理の少なくとも１個のスケジュール対象要素とを対象とした一部区間のスケジューリング処理を、上記スケジュール対象要素の順列の全区間をカバーするまで一部区間を移動しながら制御処理することを特徴とする請求項１に記載のスケジューリング方法。
【請求項３】
上記中央処理手段は、上記記憶手段に記憶された一部区間を対象としたスケジューリング処理が上記スケジュール対象要素の順列の全区間をカバーする毎に、上記一部区間の大きさを変えて、上記記憶手段に記憶された前回までのスケジューリング結果を用いて更にスケジューリングを行うようにした制御処理することを特徴とする請求項１又は２に記載のスケジューリング方法。
【請求項４】
上記中央処理手段は、上記記憶手段に記憶された一部区間の大きさを徐々に小さくしていくようにしたことを特徴とする請求項３に記載のスケジューリング方法。
【請求項５】
上記中央処理手段は、上記記憶手段に記憶された一部区間の大きさを徐々に小さくしていき、所定の大きさより小さくなったときに、上記一部区間の大きさを徐々に大きくしていくようにしたことを特徴とする請求項４に記載のスケジューリング方法。
【請求項６】
上記中央処理手段は、スケジューリング処理の際に使用する評価項目の内容を記憶手段に記憶させ、上記評価項目の内容に応じて上記一部区間を対象としたスケジューリング処理を実行することを特徴とする請求項１〜５の何れか１項に記載のスケジューリング方法。
【請求項７】
上記中央処理手段は、スケジューリング処理の対象とする区間が大きくなるほど上記評価項目の数を少なくし、区間が小さくなるほど上記評価項目の数を大きくするようにしたことを特徴とする請求項６に記載のスケジューリング方法。
【請求項８】
上記中央処理手段は、上記順序決めを行うためのスケジューリング処理を、スケジュール対象要素の順列の全区間を対象として行った後に一部区間を対象として行うことを特徴とする請求項１〜７の何れか１項に記載のスケジューリング方法。
【請求項９】
スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
上記コンピュータの中央処理手段が、
スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、
上記記憶手段に記憶された一部区間をスケジュール対象としてスケジューリング処理を行い、
或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行う処理を実行するためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
上記コンピュータの中央処理手段が、
スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、
上記記憶手段に記憶された一部区間をスケジュール対象としてスケジューリング処理を行い、
或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行い、
スケジューリング処理の際に使用する評価項目の内容を上記記憶手段に記憶させ、上記評価項目の内容に応じて上記一部区間を対象としたスケジューリング処理を行う処理を実行するためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
上記コンピュータの上記中央処理手段が、上記順序決めを行うためのスケジューリング処理を、スケジュール対象要素の順列の全区間を対象として行った後に一部区間を対象として行う処理を実行するためのプログラムを記録した請求項９又は１０に記載のコンピュータ読み取り可能な記録媒体。
【請求項１２】
スケジュール対象要素の順番決めを行うためのスケジューリング装置において、
スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として記憶するスケジュール対象記憶手段と、
スケジュール処理の際に使用する評価項目の内容を記憶する評価項目記憶手段と、
上記スケジュール対象記憶手段に記憶された或る一部区間について評価項目を満たしたスケジューリング処理を行った後、上記スケジュール対象記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記スケジュール対象記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記スケジュール対象記憶手段に記憶させ、前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行う制御処理手段とを備え、
上記制御処理手段は、スケジューリング処理の対象とする上記一部区間が小さくなるほど上記評価項目の数を多くしてスケジューリング処理を実行することを特徴とするスケジューリング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、スケジューリング方法、コンピュータ読み取り可能な記録媒体及びスケジューリング装置に関し、特に、順序決めを行う計画型問題について最適なスケジュールを決定する解探索方法に用いて好適なものである。
【０００２】
【従来の技術】
鉄鋼を始めとする多くの産業における製造プロセスでは、複数の製品を様々な工程で処理して製造している。このような製造プロセスでは、プロセス内における物流制御あるいは処理順序計画の最適化を人手を介さずに自動的に行うことが望まれている。また、このような製造プロセス以外の分野においても、作業の順序を決める様々な計画型問題について、最適化の自動化が望まれている。
【０００３】
そのために、コンピュータ等を用いて作業や処理等の最適な順序を決定するためのスケジューリング方法が従来提案されている。一般に、コンピュータを用いたジョブスケジューリング等の最適化問題は、少なくとも１つ以上の変数とこれらの変数によって定義される評価関数とが与えられ、所定の制約条件の下でこの評価関数を最大あるいは最小とする変数の組を求める問題である。
【０００４】
【発明が解決しようとする課題】
しかしながら、順序を決める計画型問題では、実際の問題は取り扱う要素の数が非常に多いのが通常である。例えば、製鉄所において通板順やロット順決めを行うスケジューリングでは、取り扱う板数やロット数は１００、２００という数以上であることが当たり前である。この場合に、解の最適化を狙うとなると、全ての順列（例えば、取り扱う要素が１００個であれば、順列は全部で１００！通りと膨大なものとなる）をテストしなければならないが、このように大きな規模で最適な順列を決めることは、従来大変困難であった。
【０００５】
そこで、このように取り扱う要素の数が多いことや、評価関数が複雑であることなどの理由により、解析的には最適解を得ることができない、あるいは最適解を得るのに時間がかかり過ぎるなどの場合のために、数学的算法や近似算法により解を得る手法も提案されている。しかしながら、これらの手法によって得られる解は、必ずしも最良なものではないという問題があった。産業界においては、生産性の向上を図るためにも、時間をかけて最適解を得るよりも、実用時間内に求まる最良解の方が重要であり、短時間で最良解を得ることが望ましい。
【０００６】
本発明は、このような問題を解決するために成されたものであり、順序を決める計画型問題について、取り扱う要素の数が多い場合でも最良解を短時間で探索できるようにすることを目的とする。
【０００７】
【課題を解決するための手段】
本発明のスケジューリング方法は、スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータで行う方法であって、中央処理手段は、スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、上記記憶手段に記憶された一部区間をスケジュール対象として、或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間について終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行うことを特徴とする。
本発明のコンピュータ読み取り可能な記録媒体の第１の態様は、スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、上記コンピュータの中央処理手段が、スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、上記記憶手段に記憶された一部区間をスケジュール対象としてスケジューリング処理を行い、或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行う処理を実行するためのプログラムを記録したことを特徴とする。
本発明のコンピュータ読み取り可能な記録媒体の第２の態様は、スケジュール対象要素の順序決めを行うためのスケジューリング処理をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、上記コンピュータの中央処理手段が、スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として設定して記憶手段に記憶させ、上記記憶手段に記憶された一部区間をスケジュール対象としてスケジューリング処理を行い、或る一部区間についてスケジューリング処理を行ってスケジューリング結果を上記記憶手段に記憶させた後、上記設定して記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記記憶手段に記憶させ、上記記憶手段に記憶された前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行い、スケジューリング処理の際に使用する評価項目の内容を上記記憶手段に記憶させ、上記評価項目の内容に応じて上記一部区間を対象としたスケジューリング処理を行う処理を実行するためのプログラムを記録したことを特徴とする。
本発明のスケジューリング装置は、スケジュール対象要素の順番決めを行うためのスケジューリング装置において、スケジュール対象要素の順列の全区間のうちの一部区間をスケジュール対象として記憶するスケジュール対象記憶手段と、スケジュール処理の際に使用する評価項目の内容を記憶する評価項目記憶手段と、上記スケジュール対象記憶手段に記憶された或る一部区間について評価項目を満たしたスケジューリング処理を行った後、上記スケジュール対象記憶手段に記憶された複数の一部区間について上記スケジュール対象要素の順列の全区間のスケジューリング処理が終了したかどうかを判断し、終了していない場合には、新たな一部区間を上記スケジュール対象記憶手段に記憶された前回の一部区間と一部重複する位置に設定して上記スケジュール対象記憶手段に記憶させ、前回のスケジューリング結果を用いて上記新たな一部区間について全区間のスケジューリング処理が終了するまでスケジューリング処理を繰り返し行う制御処理手段とを備え、上記制御処理手段は、スケジューリング処理の対象とする上記一部区間が小さくなるほど上記評価項目の数を多くしてスケジューリング処理を実行することを特徴とする。
【００１８】
【発明の実施の形態】
以下、本発明の一実施形態を図面に基づいて説明する。
図１は、本実施形態によるスケジューリング方法を説明するための動作説明図である。ここでは、一例として、製鉄所における通板順やロット順決めのスケジューリングを行う場合について説明する。
【００１９】
図１において、△，▲，▽，▼，○，●，◎，◇，◆の記号は、それぞれ通板やロットを表すものであり、同じ記号どうしは互いに同じ種類の通板やロットであることを示し、異なる記号どうしは互いに異なる種類の通板やロットであることを示している。また、これらの記号が並べられた水平方向は時間軸を示しており、通板やロットに対して行う各種の作業が当該時間軸上に配置されている。すなわち、各記号の横並びは、図の左側から右側方向に順に各通板や各ロットの作業を行っていくというスケジュールを示している。
【００２０】
本実施形態のスケジューリング方法では、まず最初に、図１（ａ）に示すように、作業開始から作業終了までの全区間に対して、非常に粗い精度で順序決めを行う。非常に粗い精度の順序決めとは、本実施形態の場合、スケジューリング結果を評価するための評価項目の数を少なくして順序決めを行うことである。例えば、この最初の段階では「作業すべき時間」という１つの評価項目だけを用いて順序決めを行う。これにより、より優先して処理すべき通板やロットがより前の方に並べられたスケジュールが得られる。
【００２１】
また、このスケジューリングの際、順序決めのための解探索の一手法として、本実施形態では、遺伝的アルゴリズムを利用した場合を例に挙げて説明する。遺伝的アルゴリズムは、生物の進化過程をモデルとした遺伝的操作を用いて、与えられた問題に対する解を求める手法である。すなわち、遺伝的アルゴリズムでは、幾つかの解候補を生成してそれぞれについて適応度を評価し、評価値の高い解候補を選択してそれらに対して交差、突然変異などの操作を加えることにより、より適応度の高い解候補を求めていく。そして、評価値がある値に達したときの解候補を、求める解とする。
【００２２】
このように、作業開始から作業終了までの全区間を対象とし、通板やロット等のスケジュール対象物の数が非常に多い最初の段階では、評価項目の数を少なくして評価関数を簡素化し、非常に粗い精度で順序決めを行っているので、その少ない評価条件を満たす好ましいスケジュールの解を遺伝的アルゴリズムによって比較的簡単に求めることができる。
【００２３】
次に、図１（ｂ）に示すように、図１（ａ）のように粗い精度でスケジューリングされた結果のうち、最初の部分から全体の３／４程の一部区間（図１（ｂ）中に両矢印で示した区間）に対して、図１（ａ）の最初の段階よりも精度を上げて順序決めを行う。例えば、上述した「作業すべき時間」という評価項目に加えて、「通板やロットの並び順」という評価項目を加えて順序決めを行う。この場合も、順序決めのための解探索手法として遺伝的アルゴリズムを利用する。
【００２４】
これにより、より優先して処理すべき通板やロットがより前の方に並べられるとともに、例えば連続して処理すべきものが連続して並べられたスケジュールが上記一部区間内で得られる。この図１（ｂ）の段階では、スケジュール対象物の数を少なくして順序決めを行っており、しかも、２つの評価項目のうち一方の評価項目に沿って既にスケジューリングした結果を対象として順序決めを行っているので、評価項目の数を２つに増やして順序決めを行っても、その２つの評価条件を満たす好ましいスケジュールの解を比較的簡単に求めることができる。
【００２５】
次に、図１（ｃ）の段階では、図１（ｂ）でスケジューリングされた結果を用いて、図１（ｂ）で採用した区間の一部とオーバーラップさせた別の一部区間（これも全体の３／４程の区間で、図１（ｃ）中に両矢印で示している）に対して、図１（ｂ）の場合と同じ精度で（同じ評価項目を用いて）遺伝的アルゴリズムによって順序決めを行う。
【００２６】
すなわち、この図１（ｃ）の段階では、図１（ｂ）の段階で一部区間内で並べ替えられた結果である順列の後ろからＬ個のスケジュール対象物と（この部分がオーバーラップ区間となる）、それらに続いて並べられている図１（ｂ）の段階では未処理のＭ個のスケジュール対象物とを対象として（本実施形態の場合、これらの合計数が全区間の３／４程となる）、図１（ｂ）の場合と同じ精度で順序決めを行う。
【００２７】
このように各一部区間をオーバーラップさせる理由は、各一部区間間でスケジュール対象物の移動を可能にするためである。すなわち、例えば図１（ａ）の最初の段階で「作業すべき時間」のみを評価項目として順序決めを行った結果、前半部に並べられたスケジュール対象物でも、「通板やロットの並び順」の評価項目を増やして評価を行った場合には、より後ろの方にスケジューリングされる方が良いことがある。
【００２８】
この場合に、各一部区間をオーバーラップさせておかないと、評価項目を増やした場合のスケジュール対象物の並べ替えの範囲がその一部区間の範囲内に限定されてしまい、一部区間を越えては移動できないことになってしまう。これに対して本実施形態のようにオーバーラップの区間を設けることにより、一部区間毎にスケジューリングを行った場合でも、スケジュール対象物は全区間内を自由に移動することができ、より好ましい順に並べ替えることが可能となる。
【００２９】
このように順次設定した各一部区間内でスケジューリングを夫々行い、順序決め対象の最初から最後をカバーするまで実行したら（本実施形態の場合は２回の実行でカバーしている。ただし、一部区間の移動量を少なくする、すなわち、オーバーラップ量を多くすることによって更に多くの回数で全区間をカバーすることも可能である）、次には図１（ｄ）に示すように、取り扱う一部区間を全体の１／２程度に更に小さくして、上記図１（ｂ）（ｃ）と同様に当該一部区間を全区間内で移動するように順次設定して各一部区間内でスケジューリングを夫々行う。
【００３０】
本実施形態では、全体の１／２程度の一部区間のオーバーラップ量を当該一部区間の半分程度にすることにより、各一部区間内のスケジューリングを３回実行して順序決め対象の最初から最後までをカバーするようにしている。すなわち、この図１（ｄ）では３回のスケジューリングをまとめて示しているが、実際には、順序決めの最初の部分から全体の１／２程の一部区間▲１▼に対して順序決めを行った後、その結果として得られる順列の後ろから数個のスケジュール対象物と、それらに続いて並べられている上記一部区間▲１▼の段階では未処理の数個のスケジュール対象物とを対象とした一部区間▲２▼に対して、更に順序決めを行う。
【００３１】
さらに、この一部区間▲２▼に対する順序決めの結果として得られる順列の後ろから数個のスケジュール対象物と、それらに続いて並べられている上記一部区間▲１▼、▲２▼の段階では未処理の数個のスケジュール対象物とを対象とした一部区間▲３▼に対して、更に順序決めを行う。このときの各一部区間▲１▼〜▲３▼内でのスケジューリングにおいては、図１（ｂ）（ｃ）の段階に比べて更に評価項目の数を増やすことにより、更に精度を上げて順序決めを行う。
【００３２】
以下同様にして、順序決め対象の最初から最後をカバーするまで各一部区間のスケジューリングを実行する毎に、一部区間の大きさを１／３、１／４、……と小さくしていくとともに、評価項目の数を増やしていく。図１（ｅ）は、全体の１／３程度に一部区間の大きさを設定し、各一部区間内のスケジューリングを５回実行することによって順序決め対象の最初から最後までをカバーする様子を示している。
【００３３】
このように本実施形態では、スケジューリング対象とする順列の区間を徐々に小さくすることにより順序決めの精度を徐々に良くしていくことによって、スケジューリング結果を徐々に最良のものに近づけていくことができる。しかも、一部区間の大きさが小さくなるほど、すなわち、スケジュール対象物の数が少なくなるほど、その一部区間内では全順列の探索が可能となるので、それぞれの細かい範囲内では最適解に近いスケジューリング結果を得ることができる。
【００３４】
したがって、本実施形態のスケジューリング方法によれば、全ての順列を試行するという手法によることなく、従来よりも最良の解を得る可能性を高くすることができるとともに、そのための処理を短時間で行うことができる。また、順序決めのための全区間を細かい小区間に分けてスケジューリングを行っているので、その狭い範囲の中で、計算された結果を人が評価しやすいというメリットもある。すなわち、例えばどのように評価項目を変更すれば更に良いスケジュールが得られるかを容易に判断することができる。
【００３５】
なお、以上の実施形態では、最初にスケジュール対象物の順列の全区間を対象としてスケジューリング処理を行った後で一部区間を対象として行うようにしているが、最初から一部区間を設けてスケジューリング処理を行うようにしても良い。また、上述の実施形態では、一部区間の大きさを全体の３／４、１／２、１／３、１／４、……と細かくしていく例を挙げたが、一部区間の大きさはこれに限定されるものではない。
【００３６】
また、一部区間の大きさは、順序決め対象の最初から最後までをカバーするまでは同じ大きさとしているが、異なる大きさの一部区間を設定するようにしても良い。さらに、一部区間のオーバーラップ量も、図１に示したものに限定されるものではなく、少なくとも１個オーバーラップしていれば良い。これらの一部区間の大きさやオーバーラップ量は、実用上は処理時間との兼ね合いで適当に決めれば良い。
【００３７】
図２は、上述のような本実施形態によるスケジューリング方法の処理の流れを示すフローチャートである。図２において、まず最初にステップＳ１で、スケジューリングを行う対象区間の大きさを設定する。最初の段階では、図１（ａ）に示したように、順序決めを行う作業開始から作業終了までの全区間を設定する。次に、ステップＳ２では、遺伝的アルゴリズムによるスケジューリングを行う際の評価項目を設定する。最初の段階では、非常に少ない数の評価項目を設定することにより、非常に粗い精度で順序決めを行うようにする。
【００３８】
次に、ステップＳ３では、設定された区間の大きさが一定の大きさよりも小さいかどうかを判断する。そして、その判断の結果が否定の場合は、ステップＳ４に進み、そのとき設定されている区間を対象として、同じくそのとき設定されている評価項目に従ってスケジューリングを行う。その後、ステップＳ５で、順序決めの全区間についてスケジューリングが終了したかどうかを判断し、終わっていればステップＳ１の処理に戻る。上述のように、最初の段階では全区間を指定してスケジューリングを行っているので、ステップＳ１に戻る。
【００３９】
ステップＳ１における区間の大きさを設定する処理では、現在設定している区間の大きさを例えば図示しないＲＡＭなどのメモリに記憶しておき、ステップＳ５から再びステップＳ１の処理に移行してきたときには、当該メモリに記憶されている区間の大きさよりも小さい区間を設定する。なお、このステップＳ１では、全区間よりも小さい一部区間を設定するときは、順序決め行う最初の部分に位置を設定する。
【００４０】
次のステップＳ２の処理でも上記ステップＳ１の処理と同様に、現在設定している評価項目の内容を例えば図示しないＲＡＭなどのメモリに記憶しておき、ステップＳ５からステップＳ１を介して再びステップＳ２の処理に移行してきたときには、当該メモリに記憶されている評価項目に加えて別の評価項目を設定するようにする。
【００４１】
なお、上述したように、本実施形態では一部区間をオーバーラップさせてスケジュール対象物を一部区間間で移動できるようにしている。そのため、前回使った評価項目をもう一度使わなければ、必ずしも前回のスケジューリング結果を反映した結果が得られるとは限らない。そこで、評価項目の数を増やすときは、前回使った評価項目を必ずもう一度使うようにしている。
【００４２】
このようにしてステップＳ１，Ｓ２にてスケジューリング対象とする一部区間および評価項目を新たに設定したら、それらの内容に従って、直前に得られたスケジューリング結果（この場合は全区間のスケジューリング結果）に対してステップＳ４で更にスケジューリングを行う。そして、ステップＳ５で順序決めの全区間についてスケジューリングが終了したかどうかを判断し、終わっていなければステップＳ６に進んで一部区間の位置を移動させる（このとき、移動前後の各一部区間の一部をオーバーラップさせる）。
【００４３】
そして、ステップＳ６からステップＳ４に戻り、直前に得られたスケジューリング結果（この場合は最初の一部区間に対してのみスケジューリングした結果）に対して更にスケジューリングを行う。このように一部区間を順次移動してスケジューリングを夫々行うことにより、順序決めの全区間についてスケジューリングが終了すると、ステップＳ５からステップＳ１に戻って更に小さな一部区間を設定する。
【００４４】
以上のような処理を繰り返していき、その後ステップＳ３で設定区間の大きさが一定値よりも小さいと判断したときは、ステップＳ７に進み、そのとき得られているスケジューリング結果を最良解のスケジュールとして出力し、スケジューリング処理を終了する。
【００４５】
なお、ここでは、順列の探索区間の大きさが一定値より小さくなったときに処理を終了するようにしているが、最良解を得るための収束条件はこれに限定されるものではない。例えば、スケジューリング処理を行った回数をカウントするようにし、所定回数繰り返したところで処理を終了するようにしても良い。また、スケジューリングされた結果の評価値を記憶しておくようにし、前回の評価値との差分が一定値以内となったところで処理を終了するようにしても良い。さらに、ユーザが設定した評価項目を全て使ってスケジューリングし終わったところで処理を終了するようにしても良い。
【００４６】
また、以上の実施形態では、スケジューリング対象区間の大きさを徐々に小さくしていくとともに、評価項目の数を徐々に多くしていき、区間の大きさが一定値より小さくなったときに処理を終了するようにしている。これに対して、区間の大きさが一定値より小さくなったときに、それまでとは逆方向に、スケジューリング対象区間の大きさを徐々に大きくしていくとともに、評価項目の数を徐々に少なくしていきながらスケジューリングを更に行うようにしても良い。
【００４７】
上述の実施形態のように、一部区間の大きさを徐々に小さくする方向に対してのみスケジューリングを行うと、一部区間間でのスケジュール対象物の移動は、順列の前の方から後の方への移動が可能となるのみである。これに対して、一部区間の大きさを徐々に大きくする方向にもスケジューリングを行うと、スケジュール対象物は、順列の後の方から前の方へも移動することが可能となり、より最良の解を得る可能性を更に高くすることができる。
【００４８】
以上のような本実施形態のスケジューリング方法を実現するための装置は、例えば図３に示すように、ＣＰＵ１、ＲＯＭ２、ＲＡＭ３などが相互にバス４で接続されて成るマイクロコンピュータにより構成される。そして、そのようなスケジューリングを行うためのＣＰＵ１の作業プログラムは、上記ＲＯＭ２に格納される。この場合、上記作業プログラムを格納したＲＯＭ２は、本発明の記録媒体を構成する。
【００４９】
また、上記マイクロコンピュータに周辺インタフェース５を介してハードディスク６を接続し、このハードディスク６に上記作業プログラムを格納するようにしても良い。このハードディスク６には上記作業プログラムを外部から供給することが可能であり、この場合、ハードディスク６や上記作業プログラムを供給するための手段、例えば上記作業プログラムを格納した記録媒体も、本発明の記録媒体を構成する。
【００５０】
なお、上記作業プログラムを格納するための記録媒体としては、ＲＯＭ２やハードディスク６の他に、例えばフロッピーディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード等を用いることができる。
【００５１】
また、本明細書では、解探索手法として、一貫して遺伝的アルゴリズムを利用した場合について述べてきたが、言うまでもなく解探索手法としてはこれに限られるものではなく、例えば、モンテカルロ法のようなランダム探索手法や、探索木の縦型探索手法などの手法を用いることができる。
【００５２】
【発明の効果】
本発明によれば、一部区間毎にスケジューリングを行った場合でも、スケジュール対象物は全区間内を自由に移動することができ、より好ましい順に並べ帰ることが可能となる。
また、本発明の他の特徴によれば、一部区間の大きさが小さくなるほど、すなわち、スケジュール対象要素の数が少なくなるほどスケジューリングの精度を良くすることが可能となり、それぞれの細かい範囲内で最適解に近いスケジューリング結果を得ることができる。よって、従来よりも最良の解を得る可能性を高くすることができる。
【図面の簡単な説明】
【図１】本発明の一実施形態によるスケジューリング方法を説明するための動作説明図である。
【図２】本実施形態によるスケジューリング方法の処理の流れを示すフローチャートである。
【図３】本実施形態のスケジューリング方法を実現するための装置の概要を示すブロック図である。
【符号の説明】
１  ＣＰＵ
２  ＲＯＭ
３  ＲＡＭ
４  バス
５  周辺インタフェース
６  ハードディスク
【図１】
0004255524.tif 000002
【図２】
0004255524.tif 000003
【図３】
0004255524.tif 000004