(57)【要約】【課題】複数のジョブ実行装置が並列にジョブを実行することであってジョブの順次実行を含むものに係る全ジョブを早期に実行終了しやすくする。【解決手段】評価値計算部１５は、スケジュール情報作成部１３により作成されたスケジュール情報内のジョブＩＤを複数含むジョブＩＤ情報に対応する時間関数どうしを畳み込み積分し、得た時間関数を用いて評価値を計算する。スケジュール情報出力部１６は、複数作成されたスケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、該評価値で最高のものを選択し、該評価値に対応するスケジュール情報を出力する。【選択図】図１
2009069883.tif 000002
【特許請求の範囲】
【請求項１】
同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置であって、
対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部と、
ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成するスケジュール情報作成部と、
前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める時間関数取得部と、
ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算する評価値計算部と、
複数作成された前記スケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、該評価値で最高のものを選択し、該評価値に対応するスケジュール情報を出力するスケジュール情報出力部と
を備えることを特徴とするスケジュール情報出力装置。
【請求項２】
同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置であって、
対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部と、
ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成するスケジュール情報作成部と、
前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める時間関数取得部と、
ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算する評価値計算部と、
前記評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるという前記スケジュール情報の修正を行うスケジュール情報修正部と、
前記評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力するスケジュール情報出力部と
を備えることを特徴とするスケジュール情報出力装置。
【請求項３】
ジョブの実行に要した所要時間長が記憶される所要時間長記憶部と、
前記所要時間長記憶部に記憶された複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応する前記ジョブ属性情報記憶部のジョブ属性情報を修正するジョブ属性情報修正部と
を備えることを特徴とする請求項１または２記載のスケジュール情報出力装置。
【請求項４】
同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置が行うスケジュール情報出力方法であって、
前記スケジュール情報出力装置が、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部を備え、
前記スケジュール情報出力方法は、
前記スケジュール情報出力装置のスケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、
前記スケジュール情報出力装置の時間関数取得部が、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、
前記スケジュール情報出力装置の評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、
前記スケジュール情報出力装置のスケジュール情報出力部が、複数作成された前記スケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、該評価値で最高のものを選択し、該評価値に対応するスケジュール情報を出力する
ことを特徴とするスケジュール情報出力方法。
【請求項５】
同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置が行うスケジュール情報出力方法であって、
前記スケジュール情報出力装置が、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部を備え、
前記スケジュール情報出力方法は、
前記スケジュール情報出力装置のスケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、
前記スケジュール情報出力装置の時間関数取得部が、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、
前記スケジュール情報出力装置の評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、
前記スケジュール情報出力装置のスケジュール情報修正部が、前記評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるという前記スケジュール情報の修正を行い、
前記スケジュール情報出力装置のスケジュール情報出力部が、前記評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力する
ことを特徴とするスケジュール情報出力方法。
【請求項６】
前記スケジュール情報出力装置が、ジョブの実行に要した所要時間長が記憶される所要時間長記憶部を備え、
前記スケジュール情報出力方法は、
前記スケジュール情報出力装置のジョブ属性情報修正部が、前記所要時間長記憶部に記憶された複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応する前記ジョブ属性情報記憶部のジョブ属性情報を修正する
ことを特徴とする請求項４または５記載のスケジュール情報出力方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のジョブ実行装置が並列にジョブを実行することのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置およびスケジュール情報出力方法に関するものである。
【背景技術】
【０００２】
複数のジョブ実行装置が並列にジョブを実行するというジョブの実行について要終了時点が設定される場合がある。つまり、全てのジョブを要終了時点までに終了しなければならないのである。このような要求に対し、過去に実行されたジョブの所要時間長が予め記憶され、この所要時間長と要終了時点とを基にスケジュール、つまり、各ジョブ実行装置へのジョブの割り当てが実行される。こうして、全てのジョブを要終了時点までに終了させるのである。
【特許文献１】特開２００３−５８５１８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、過去に実行された１回の所要時間長を使用すると、所要時間長のバラツキにより、要終了時点を過ぎてしまうことになりやすい。
【０００４】
特に、同一のジョブ実行装置がジョブを順次実行することを含むものにおいては、バラツキが加算されるので、要終了時点を過ぎる可能性が高まる。
【０００５】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、複数のジョブ実行装置が並列にジョブを実行することのスケジュールであってジョブの順次実行を含むもののスケジュール情報を出力するスケジュール情報出力装置およびスケジュール情報出力方法により全ジョブを早期に実行終了しやすくすることにある。
【課題を解決するための手段】
【０００６】
上記の課題を解決するために、請求項１の本発明は、同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置であって、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部と、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成するスケジュール情報作成部と、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める時間関数取得部と、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算する評価値計算部と、複数作成された前記スケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、該評価値で最高のものを選択し、該評価値に対応するスケジュール情報を出力するスケジュール情報出力部とを備えることを特徴とするスケジュール情報出力装置をもって解決手段とする。
【０００７】
請求項２の本発明は、同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置であって、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部と、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成するスケジュール情報作成部と、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める時間関数取得部と、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算する評価値計算部と、前記評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるという前記スケジュール情報の修正を行うスケジュール情報修正部と、前記評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力するスケジュール情報出力部とを備えることを特徴とするスケジュール情報出力装置をもって解決手段とする。
【０００８】
請求項３の本発明は、ジョブの実行に要した所要時間長が記憶される所要時間長記憶部と、前記所要時間長記憶部に記憶された複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応する前記ジョブ属性情報記憶部のジョブ属性情報を修正するジョブ属性情報修正部とを備えることを特徴とする請求項１または２記載のスケジュール情報出力装置をもって解決手段とする。
【０００９】
請求項４の本発明は、同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置が行うスケジュール情報出力方法であって、前記スケジュール情報出力装置が、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部を備え、前記スケジュール情報出力方法は、前記スケジュール情報出力装置のスケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、前記スケジュール情報出力装置の時間関数取得部が、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、前記スケジュール情報出力装置の評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、前記スケジュール情報出力装置のスケジュール情報出力部が、複数作成された前記スケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、該評価値で最高のものを選択し、該評価値に対応するスケジュール情報を出力することを特徴とするスケジュール情報出力方法をもって解決手段とする。
【００１０】
請求項５の本発明は、同一のジョブ実行装置が１ジョブを実行する又は複数ジョブを順次実行することが複数のジョブ実行装置で並列に実行されることのスケジュールを示すスケジュール情報を出力するスケジュール情報出力装置が行うスケジュール情報出力方法であって、前記スケジュール情報出力装置が、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶したジョブ属性情報記憶部を備え、前記スケジュール情報出力方法は、前記スケジュール情報出力装置のスケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、前記スケジュール情報出力装置の時間関数取得部が、前記スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報を前記ジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、前記スケジュール情報出力装置の評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する前記時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、ジョブＩＤを複数含むジョブＩＤ情報に対応する前記時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、前記スケジュール情報出力装置のスケジュール情報修正部が、前記評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるという前記スケジュール情報の修正を行い、前記スケジュール情報出力装置のスケジュール情報出力部が、前記評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力することを特徴とするスケジュール情報出力方法をもって解決手段とする。
【００１１】
請求項６の本発明は、前記スケジュール情報出力装置が、ジョブの実行に要した所要時間長が記憶される所要時間長記憶部を備え、前記スケジュール情報出力方法は、前記スケジュール情報出力装置のジョブ属性情報修正部が、前記所要時間長記憶部に記憶された複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応する前記ジョブ属性情報記憶部のジョブ属性情報を修正することを特徴とする請求項４または５記載のスケジュール情報出力方法をもって解決手段とする。
【発明の効果】
【００１２】
本発明によれば、ジョブ属性情報記憶部に、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶しておき、スケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、時間関数取得部が、スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報をジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報に対応する時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、評価値計算部が、ジョブＩＤを複数含むジョブＩＤ情報に対応する時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、スケジュール情報出力部が、複数作成されたスケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し、スケジュール情報出力部が、該評価値で最高のものを選択し、スケジュール情報出力部が、該評価値に対応するスケジュール情報を出力することで、このスケジュール情報により、ジョブの順次実行を含んでいるにも拘わらず、全ジョブを早期に実行終了しやすくできる。
【００１３】
また、本発明によれば、ジョブ属性情報記憶部に、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶しておき、スケジュール情報作成部が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し、時間関数取得部が、スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報をジョブ属性情報記憶部から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め、評価値計算部が、ジョブＩＤを１つのみ含むジョブＩＤ情報に対応する時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し、評価値計算部が、ジョブＩＤを複数含むジョブＩＤ情報に対応する時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し、スケジュール情報修正部が、評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるというスケジュール情報の修正を行い、スケジュール情報出力部が、評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力することで、このスケジュール情報により、ジョブの順次実行を含んでいるにも拘わらず、全ジョブを早期に実行終了しやすくできる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態を図面を参照して説明する。
【００１５】
［第１の実施形態］
図１は、第１の実施形態に係るスケジュール情報出力装置１の利用形態を示す図である。
【００１６】
スケジュール情報出力装置１は、複数のジョブ実行装置２とともに使用される。ここでは、同一のジョブ実行装置２が１ジョブを実行する又は複数ジョブを順次実行することが、複数のジョブ実行装置２で並列に実行される。スケジュール情報出力装置１は、ジョブ全体の実行のスケジュールを示すスケジュール情報を作成し出力するものである。
【００１７】
図２に示すように、例えば、実行すべき４ジョブＸ、Ｙ、Ｚ、Ｗを、ジョブＸ、ＺとジョブＹ、Ｗに２分したなら、要終了時点ＴＥを過ぎて全ジョブの実行が終了しやすい場合にあって、スケジュール情報出力装置１は、そのようになりにくいスケジュール、例えば、４ジョブをジョブＸ、ＹとジョブＺ、Ｗに２分して行うことのスケジュールを示すスケジュール情報を出力するものである。
【００１８】
スケジュール情報出力装置１は、上記の２つのスケジュール情報のように複数のスケジュール情報を作成し、その中の最も早期終了しやすいものを選択して出力するものである。なお、スケジュール情報は、可能な限り多く作成してもよいが、スケジュール情報出力装置１にかかる負荷が大きくなるので、スケジュール情報の数は、負荷の大きさに鑑みて決めればよい。
【００１９】
スケジュール情報出力装置１は、１つのコンピュータまたは複数のコンピュータを通信回線で接続したコンピュータシステムに構成される。
【００２０】
ジョブ実行装置２は、１つコンピュータに構成され、ジョブ実行装置２が構成されるコンピュータは、スケジュール情報出力装置１が構成されるコンピュータやコンピュータシステムに対して通信回線で接続される場合が多いと考えられる。
【００２１】
なお、同一の中央演算装置を時分割使用するいわゆるマルチタスク型のコンピュータが複数のジョブ実行装置２を実質的に構成してもよい。また、中央演算装置を複数有するいわゆるマルチコアのコンピュータにおいて各中央演算装置がジョブ実行装置２を構成してもよい。また、スケジュール情報出力装置１と各ジョブ実行装置２を同一のコンピュータやコンピュータシステムに構成してもよい。
【００２２】
スケジュール情報出力装置１は、ジョブの属性を示すジョブ属性情報が記憶されるジョブ属性情報記憶部１１と、スケジュール情報を作成するスケジュール情報作成部１３と、実行すべきジョブを記憶した要実行ジョブ記憶部１２と、ジョブ属性情報記憶部１１からジョブ属性情報を読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める時間関数取得部１４と、ジョブの実行や順次実行の早期終了しやすさを示す評価値を計算する評価値計算部１５と、作成された複数のスケジュール情報の１つを出力するスケジュール情報出力部１６と、ジョブの実行に要した所要時間長が記憶される所要時間長記憶部１７と、記憶された所要時間長を基にジョブ属性情報を修正するジョブ属性情報修正部１８を備える。
【００２３】
図示しないが、スケジュール情報出力装置１は、ジョブ実行装置２と通信する通信部を備える。
【００２４】
要実行ジョブ記憶部１２には、例えば、実行すべきジョブＸを示すジョブ識別情報（以下、識別情報をＩＤという）である「Ｘ」（ジョブＩＤ「Ｘ」と表記し、他のジョブＩＤも同様に表記する。また、ジョブＩＤ以外の情報についても、内容を示す場合は、それを「」で囲み、名前に後続させる。）、実行すべきジョブＹを示すジョブＩＤ「Ｙ」、実行すべきジョブＺを示すジョブＩＤ「Ｚ」および実行すべきジョブＷを示すジョブＩＤ「Ｗ」が記憶される。
【００２５】
要実行ジョブ記憶部１２には、さらに、全ジョブが終了していなければいけない時点である要終了時点ＴＥが記憶される。
【００２６】
図３は、ジョブ属性情報記憶部１１の構成と内容を例示した図である。
【００２７】
ジョブ属性情報記憶部１１は、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶している。
【００２８】
例えば、ジョブの終了がポアソン過程に従っており、これにより、所要時間長の確率分布を示すものとして、式（１）の時間関数ｐ（ｔ｜λ）を定義した場合、パラメータはλである。図３は、ジョブＸ、Ｙ、Ｚ、Ｗのジョブ属性情報が、それぞれパラメータλｘ、λｙ、λｚ、λｗである場合の状態を示している。
【数１】
2009069883.tif 000003
【００２９】
または、所要時間長の確率分布を示すものとして、式（２）に示す時間関数ｐ（ｔ＊）を定義できる場合、パラメータはα’とβ’である。また、パラメータは平均と分散でもよい。
【００３０】
かかるパラメータからなるジョブ属性情報を記憶するジョブ属性情報記憶部１１には、また、ジョブＩＤに対応づけて、実行すべきプログラム、その格納場所を示す情報などが記憶される。
【００３１】
図４は、所要時間長記憶部１７の構成と内容を例示した図である。
【００３２】
所要時間長記憶部１７には、実行されたジョブのジョブＩＤに対応づけて、各回の実行に要した所要時間長が記憶されるようになっている。
【００３３】
図５は、第１の実施形態に係るスケジュール情報出力方法を示すフローチャートである。
【００３４】
例えば、予め設定された時点になると、スケジュール情報作成部１３が、要実行ジョブ記憶部１２から、実行すべき各ジョブのジョブＩＤを読み出し、このジョブＩＤを含むスケジュール情報を複数作成する（Ｓ１）。スケジュール情報は、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むものである。しかも、スケジュール情報は、ジョブＩＤを２以上含むジョブＩＤ情報を含むものである。
【００３５】
例えば、スケジュール情報作成部１３は、ジョブ実行装置２Ａ、２Ｂがジョブを実行すべきことを記憶しており、それらのジョブ実行装置２Ａ、２Ｂがそれぞれ実行すべきスケジュールＳＣ１、ＳＣ２を示すものとして、スケジュール情報ＳＣＩ１、ＳＣＩ２を作成する。
【００３６】
具体的には、ジョブＩＤ「Ｘ」とジョブＩＤ「Ｙ」を含むジョブＩＤ情報ＳＣＩ１１ならびにジョブＩＤ「Ｚ」とジョブＩＤ「Ｗ」を含むジョブＩＤ情報ＳＣＩ１２を作成し、ジョブＩＤ情報ＳＣＩ１１とジョブＩＤ情報ＳＣＩ１２を含むスケジュール情報ＳＣＩ１を作成する。
【００３７】
また、ジョブＩＤ「Ｘ」とジョブＩＤ「Ｚ」を含むジョブＩＤ情報ＳＣＩ２１ならびにジョブＩＤ「Ｙ」とジョブＩＤ「Ｗ」を含むジョブＩＤ情報ＳＣＩ２２を作成し、ジョブＩＤ情報ＳＣＩ２１とジョブＩＤ情報ＳＣＩ２２を含むスケジュール情報ＳＣＩ２を作成する。
【００３８】
４ジョブを２つのジョブ実行装置２で実行する場合、これより多くのスケジュール情報を作成できるが、便宜的にスケジュール情報の数を２とした。
【００３９】
スケジュール情報ＳＣＩ１は、ジョブ実行装置２ＡがジョブＩＤ「Ｘ」に対応するジョブＸとジョブＩＤ「Ｙ」に対応するジョブＹをこの順序でまたは逆の順序で順次に実行することと、ジョブ実行装置２ＢがジョブＩＤ「Ｚ」に対応するジョブＺとジョブＩＤ「Ｗ」に対応するジョブＷをこの順序でまたは逆の順序で順次に実行することとが並列に行われることのスケジュールＳＣ１を示すものである。
【００４０】
スケジュール情報ＳＣＩ２は、ジョブ実行装置２ＡがジョブＸとジョブＺをこの順序でまたは逆の順序で順次に実行することと、ジョブ実行装置２ＢがジョブＹとジョブＷをこの順序でまたは逆の順序で順次に実行することとが並列に行われることのスケジュールＳＣ２を示すものである。
【００４１】
次に、時間関数取得部１４が、例えば、ジョブＩＤ情報ＳＣＩ１１〜ＳＣＩ２２内のジョブＩＤに対応づけられたジョブ属性情報（パラメータ）をジョブ属性情報記憶部１１から読み出し、これらを基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める（Ｓ３）。ここでは、時間関数取得部１４が、式（１）のλや（２）のα’とβ’や正規分布を示す式（図示せず）にジョブ属性情報のパラメータを代入して時間関数を求める。
【００４２】
次に、評価値計算部１５が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、そのジョブＩＤ情報に対応する時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算する（Ｓ５）。評価値計算部１５は、例えば、対応する時間関数を、０から後述する時点Ｔまでの範囲で積分する。得た積分値が評価値である。  時点Ｔとして、要終了時点ＴＥまでの時間長に応じた値が使用される。なお、要終了時点ＴＥが記憶されていない場合、予め決めてある値や無限遠点（∞）を時点Ｔとして使用すればよい。
【００４３】
また、評価値計算部１５は、ジョブＩＤを複数含むジョブＩＤ情報がある場合は、そのジョブＩＤ情報に対応するジョブの順次実行の早期終了しやすさを示す評価値を計算する（Ｓ７）。
【００４４】
ここでは、まず、複数のジョブＩＤに対応する時間関数どうしを畳み込み積分する。
【００４５】
ここで、「畳み込み積分」について説明する。
【００４６】
図６に示すようなジョブＡの実行に要する所要時間長の確率分布を時間関数ｐＡ（ｔ）で表し、また、同図に示すようなジョブＢの実行に要する所要時間長の確率分布を時間関数ｐＢ（ｔ）で表すと、同図に示すようなジョブＡ、Ｂの順次実行に要する所要時間長の確率分布を表す時間関数は、式（３）により得られる。
【００４７】
これを畳み込み積分という。このような畳み込み積分を式（４）のように表現する場合、Ｎ個のジョブＪ１，Ｊ２，…，ＪＮの順次実行に要する所要時間長の確率分布は、式（５）によって表現される。
【００４８】
この全ての畳み込みを解析的に求めるためには、ラプラス変換による畳み込み定理を用いる。ラプラス変換をＬと表す場合、畳み込み定理により、式（６）となり、右辺を解析的に求めることによって、上記のＮ個のジョブの順次実行に要する所要時間長の確率分布が求められる。
【００４９】
評価値計算部１５は、式（７）に示すように、畳み込み積分より得られた時間関数を、０から時点Ｔの範囲で積分する。得た積分値が評価値である。
【００５０】
ジョブＩＤ情報ＳＣＩ１１〜ＳＣＩ２２の評価値について具体的に説明する。
【００５１】
評価値計算部１５は、ジョブＩＤ「Ｘ」とジョブＩＤ「Ｙ」の各ジョブ属性情報により求めた時間関数どうしを畳み込み積分し、得られた時間関数について、０から時点Ｔまでの範囲で積分を行う。こうして得られた積分値が、ジョブＩＤ情報ＳＣＩ１１の評価値Ｈ１１である。
【００５２】
また、評価値計算部１５は、ジョブＩＤ「Ｚ」とジョブＩＤ「Ｗ」の各ジョブ属性情報により求めた時間関数どうしを畳み込み積分し、得た時間関数を同じ範囲で積分する。得た積分値がジョブＩＤ情報ＳＣＩ１２の評価値Ｈ１２である。
【００５３】
また、評価値計算部１５は、ジョブＩＤ「Ｘ」とジョブＩＤ「Ｚ」の各ジョブ属性情報により求めた時間関数どうしを畳み込み積分し、得た時間関数を同じ範囲で積分する。得た積分値がジョブＩＤ情報ＳＣＩ２１の評価値Ｈ２１である。
【００５４】
また、評価値計算部１５は、ジョブＩＤ「Ｙ」とジョブＩＤ「Ｗ」の各ジョブ属性情報により求めた時間関数どうしを畳み込み積分し、得た時間関数を同じ範囲で積分する。得た積分値がジョブＩＤ情報ＳＣＩ２２の評価値Ｈ２２である。
【００５５】
次に、スケジュール情報出力部１６が、作成された各スケジュール情報につき、スケジュール情報内のジョブＩＤ情報について計算された評価値で最低のものを選択する（Ｓ９）。この評価値に対応する１ジョブの実行や複数ジョブの順次実行が最も早期終了しにくいのである。
【００５６】
スケジュール情報出力部１６は、例えば、評価値Ｈ１１、Ｈ１２の低い方、例えば、評価値Ｈ１１を選択する。この場合は、ジョブＸ、Ｙの順次実行の方が、ジョブＺ、Ｗの順次実行よりも早期終了しにくいのである。
【００５７】
また、スケジュール情報出力部１６は、評価値Ｈ２１、Ｈ２２の低い方、例えば、評価値Ｈ２１を選択する。この場合は、ジョブＸ、Ｚの順次実行の方が、ジョブＹ、Ｗの順次実行よりも早期終了しにくいのである。
【００５８】
次に、スケジュール情報出力部１６が、これらの選択された評価値で最高のものを選択する（Ｓ１１）。
【００５９】
スケジュール情報出力部１６が評価値Ｈ１１を選択した場合、ジョブＸ、Ｙの順次実行方が、ジョブＸ、Ｚの順次実行よりも早期終了しやすいのである。つまり、スケジュールＳＣ１の方が、スケジュールＳＣ２よりも早期終了しやすいのである。
【００６０】
次に、スケジュール情報出力部１６が、この選択された評価値に対応するジョブＩＤ情報を含むスケジュール情報を通信部に出力する（Ｓ１３）。スケジュール情報出力部１６は、例えば、早期終了しやすいスケジュールＳＣ１に対応するスケジュール情報ＳＣＩ１を出力するのである。
【００６１】
次に、スケジュール情報ＳＣＩ１に基づき、スケジュール情報出力装置１からジョブ実行装置２Ａに対し、ジョブＸとジョブＹをこの順序でまたは逆の順序で順次に実行することが指示され、また、ジョブ実行装置２Ｂに対し、ジョブＺとジョブＷをこの順序でまたは逆の順序で順次に実行することが指示される。
【００６２】
例えば、ジョブＩＤ「Ｘ」、ジョブＩＤ「Ｙ」に対応づけられた各プログラムがジョブ属性情報記憶部１１から読み出され、これがジョブ実行装置２Ａに送信される。
【００６３】
また、ジョブＩＤ「Ｚ」、ジョブＩＤ「Ｗ」に対応づけられた各プログラムがジョブ属性情報記憶部１１から読み出され、これがジョブ実行装置２Ｂに送信される。
【００６４】
ジョブ実行装置２Ａは、指示があると、例えばすぐにジョブＸを実行し、終了後すぐにジョブＹを実行する。
【００６５】
一方、ジョブ実行装置２Ｂは、指示があると、例えばすぐにジョブＺを実行し、終了後すぐにジョブＷを実行する。
【００６６】
こうして、ジョブ実行装置２Ａ、２Ｂでは、並列にジョブを実行し、実行に要した所要時間長をスケジュール情報出力装置１に通知する。スケジュール情報出力装置１では、所要時間長記憶部１７が、通知された所要時間長を記憶する。
【００６７】
ジョブ属性情報修正部１８は、所要時間長記憶部１７に記憶された複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応するジョブ属性情報記憶部１１内のジョブ属性情報を修正する（Ｓ１５）、こうして一連の処理が終わる。
【００６８】
ステップＳ１５では、以下のようにパラメータを求める。ここでは、複数回の所要時間長を所要時間列Ｄと定義する。
【００６９】
まず、上記の式（１）を用いた場合の例を説明する。
【００７０】
式（８）が成立することとする。つまり、ポアソン分布の共役事前分布はガンマ分布であることとする。
【数２】
2009069883.tif 000004
【００７１】
ジョブ属性情報修正部１８は、最大事後確率推定法によりλを求める。つまり、式（９）を最大化するλを求める。具体的には、式（１０）によりλを求める。そして、このλで、対応するジョブ属性情報記憶部１１のλを上書きする。
【００７２】
次に、式（２）を用いた場合の例を説明する。
【００７３】
ジョブ属性情報修正部１８は、ベイス推定を用いる。具体的には、式（１１）、式（１２）により、α’とβ’を求める。そして、このα’とβ’で、対応するジョブ属性情報記憶部１１のα’とβ’を上書きする。
【００７４】
推定時間ｔ＊の最適事後予測分布の確率密度関数はガンマ−ポアソン分布として、ガンマ関数Γを用いて、式（１１）のように求められるのである。
【００７５】
（変形例１）
なお、上記のステップＳ７は、以下のように変えてもよい。
【００７６】
評価値計算部１５は、畳み込み積分に続き、式（１３）に示すように、得られた時間関数に時間変数ｔを掛け、こうして得た時間関数について、０から時点Ｔまでの範囲で積分する。こうして得られた積分値が大きいほど小さくなる値、例えば逆数が評価値である。
【数３】
2009069883.tif 000005
【００７７】
この変形例におけるステップＳ５は、以下のように変えればよい。
【００７８】
評価値計算部１５は、対応する時間関数に時間変数ｔを掛け、こうして得た時間関数について、０から時点Ｔまでの範囲で積分する。こうして得られた積分値が大きいほど小さくなる値、例えば逆数が評価値である。
【００７９】
（変形例２）
なお、上記のステップＳ７は、以下のように変えてもよい。
【００８０】
評価値計算部１５は、畳み込み積分に続き、式（１４）に示すように、得られた時間関数に後述する時間関数ｆ（ｔ）を掛け、こうして得た時間関数について、０から時点Ｔまでの範囲で積分する。例えば、時間関数ｆ（ｔ）が時点Ｔ’（＜Ｔ）で負から正に反転するものであるなら、得られた積分値が大きいほど小さくなる値、例えば逆数が評価値である。一方、時間関数ｆ（ｔ）が正から負に反転するものであるなら、得られた積分値が評価値である。
【００８１】
この変形例におけるステップＳ５は、以下のように変えればよい。
【００８２】
評価値計算部１５は、対応する時間関数に時間関数ｆ（ｔ）を掛け、こうして得た時間関数ついて、０から時点Ｔまでの範囲で積分する。時間関数ｆ（ｔ）が負から正に反転するものであるなら、得られた積分値の逆数が評価値である。一方、時間関数ｆ（ｔ）が正から負に反転するものであるなら、得られた積分値が評価値である。
【００８３】
したがって、第１の実施形態によれば、ジョブ属性情報記憶部１１に、対象のジョブを示すジョブＩＤに対応づけて、実行に要する所要時間長の確率分布を示すパラメータからなるジョブ属性情報を記憶しておき、スケジュール情報作成部１３が、ジョブＩＤを１つ以上含むジョブＩＤ情報を複数含むスケジュール情報であり且つジョブＩＤを複数含むジョブＩＤ情報を含むスケジュール情報を作成し（Ｓ１）、時間関数取得部１４が、スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報をジョブ属性情報記憶部１１から読み出し、このジョブ属性情報を基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求め（Ｓ３）、評価値計算部１５が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、対応する時間関数を用いて、対応するジョブの実行の早期終了しやすさを示す評価値を計算し（Ｓ５）、評価値計算部１５が、ジョブＩＤを複数含むジョブＩＤ情報がある場合は、対応する時間関数どうしを畳み込み積分して得られる時間関数を用いて、対応するジョブの順次実行の早期終了しやすさを示す評価値を計算し（Ｓ７）、スケジュール情報出力部１６が、複数作成されたスケジュール情報のそれぞれにつき、対応する評価値で最低のものを選択し（Ｓ９）、スケジュール情報出力部１６が、該評価値で最高のものを選択し（Ｓ１１）、スケジュール情報出力部１６が、該評価値に対応するスケジュール情報を出力する（Ｓ１３）ことで、このスケジュール情報により、ジョブの順次実行を含んでいるにも拘わらず、全ジョブを早期に実行終了しやすくできる。
【００８４】
また、ジョブ属性情報修正部１８が、ジョブの実行に要した複数回分の所要時間長を基に、対応するジョブの実行に要する所要時間長の確率分布を示すパラメータを求め、このパラメータで、対応するジョブ属性情報記憶部のジョブ属性情報を修正することで、いわゆる実測によって、上記の効果をより得やすくすることができる。
【００８５】
［第２の実施形態］
次に、本発明の第２の実施形態を説明する。
【００８６】
図７は、第２の実施形態に係るスケジュール情報出力装置１Ａの利用形態を示す図である。第１の実施の形態に係る要素と同一のものには同一符号を付し、詳細説明は省略する。また、特に言及しないことは第１の実施形態のものと同様であることとする。
【００８７】
スケジュール情報出力装置１Ａは、１つのスケジュール情報を作成し、これを早期終了しやすいものへと修正していき、出力するものである。
【００８８】
スケジュール情報出力装置１Ａは、ジョブ属性情報記憶部１１と、スケジュール情報作成部１３と、要実行ジョブ記憶部１２と、時間関数取得部１４と、評価値計算部１５と、スケジュール情報の修正を行うスケジュール情報修正部１９と、修正後のスケジュール情報を出力するスケジュール情報出力部１０Ａとを備える。
【００８９】
図７は、第２の実施形態に係るスケジュール情報出力方法を示すフローチャートである。
【００９０】
ここでは、評価値の計算とスケジュール情報の修正の回数を示す回数値Ｋに係る初期値「０」と、回数のしきい値ＴＨ（例えば、ＴＨ＝１０）が記憶されていることとする。
【００９１】
スケジュール情報作成部１３は、上記のステップＳ１と同様に、しかしここではスケジュール情報を１つだけ作成する（Ｓ２１）。
【００９２】
次に、時間関数取得部１４が、スケジュール情報内のジョブＩＤに対応づけられたジョブ属性情報（パラメータ）をジョブ属性情報記憶部１１から読み出し、これらを基に、対応するジョブの実行に要する所要時間長の確率分布を示す時間関数を求める（Ｓ２３）。
【００９３】
次に、評価値計算部１５が、ジョブＩＤを１つのみ含むジョブＩＤ情報がある場合は、そのジョブＩＤ情報に対応する評価値を計算する（Ｓ２５）。また、評価値計算部１５は、ジョブＩＤを複数含むジョブＩＤ情報がある場合は、そのジョブＩＤ情報に対応する評価値を計算する（Ｓ２７）。
【００９４】
次に、スケジュール情報修正部１９が、スケジュール情報の修正を行う（Ｓ２９）。ここでは、スケジュール情報修正部１９は、評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加える。この評価値に対応する１ジョブの実行や複数ジョブの順次実行が最も早期終了しにくいのである。
【００９５】
次に、スケジュール情報出力部１０Ａが、回数値Ｋに１を加算し、その回数値Ｋがしきい値ＴＨに達しているか否かを判定する（ステップＳ３１）。
【００９６】
達していないと判定された場合は、ステップＳ２５に戻る。この後の各ステップは、直前の修正後のスケジュール情報についてなされる。
【００９７】
こうして評価値の計算とスケジュール情報の修正とが予め決められた回数行われ、ステップＳ３１で、回数値Ｋがしきい値ＴＨに達していると判定された場合、スケジュール情報出力部１０Ａは、直前の修正後のスケジュール情報を出力する（Ｓ３３）。
【００９８】
この後の動作、各変形例については、第１の実施形態と同様なので、説明を省略する。  したがって、第２の実施形態によれば、特に、スケジュール情報修正部１９が、ステップＳ２９で、まず、評価値で最低のものを選択し、この評価値に対応するジョブＩＤ情報内のジョブＩＤを取り出して他のジョブＩＤ情報に加えるというスケジュール情報の修正を行い、スケジュール情報出力部１０Ａが、ステップＳ３３で、評価値の計算とスケジュール情報の修正とが予め決められた回数行われた後のスケジュール情報を出力することで、このスケジュール情報により、ジョブの順次実行を含んでいるにも拘わらず、全ジョブを早期に実行終了しやすくできる。
【００９９】
また、第１の実施形態との比較で、スケジュール情報の作成と評価値の計算の回数を低減でき、もって、スケジュール情報出力装置にかかる負荷を軽減できる。
【０１００】
なお、上記のスケジュール情報出力方法をスケジュール情報出力装置に実行させるコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に格納し、陳列などして流通させたり、当該コンピュータプログラムをインターネットなどの通信網を介して伝送させてもよい。
【図面の簡単な説明】
【０１０１】
【図１】第１の実施形態に係るスケジュール情報出力装置１の利用形態を示す図である。
【図２】早期終了しにくいスケジュールと早期終了しやすいスケジュールとを模式的に例示した図である。
【図３】ジョブ属性情報記憶部１１の構成と内容を例示した図である。
【図４】所要時間長記憶部１７の構成と内容を例示した図である。
【図５】第１の実施形態に係るスケジュール情報出力方法を示すフローチャートである。
【図６】畳み込み積分の説明図である。
【図７】第２の実施形態に係るスケジュール情報出力装置１Ａの利用形態を示す図である。
【図８】第２の実施形態に係るスケジュール情報出力方法を示すフローチャートである。
【符号の説明】
【０１０２】
１、１Ａ…スケジュール情報出力装置
２…ジョブ実行装置
１１…ジョブ属性情報記憶部
１２…要実行ジョブ記憶部
１３…スケジュール情報作成部
１４…時間関数取得部
１５…評価値計算部
１６、１０Ａ…スケジュール情報出力部
１７…所要時間長記憶部
１８…ジョブ属性情報修正部
１９…スケジュール情報修正部
【図１】
2009069883.tif 000006
【図２】
2009069883.tif 000007
【図３】
2009069883.tif 000008
【図４】
2009069883.tif 000009
【図５】
2009069883.tif 000010
【図６】
2009069883.tif 000011
【図７】
2009069883.tif 000012
【図８】
2009069883.tif 000013