(57)【要約】  割当問題において、要素の数が増えても、適切な組み合わせを求めることが可能な計算システム等を提供する。本発明の計算システムは、所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、スタートからゴールまでの最長経路を特定するスケジューリング部と、特定した最長経路を出力する解出力部とを備える。
2018180741.tif 000002
【特許請求の範囲】
【請求項１】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、前記スタートから前記ゴールまでの最長経路を特定するスケジューリング手段と、
特定した前記最長経路を出力する解出力手段と、を備える
計算システム。
【請求項２】
前記スケジューリング手段は、
前記有向グラフへの変換において、1つのタスクをそのタスクがとりうる複数の開始時刻それぞれに対応する複数の頂点に変換する、
請求項１に記載の計算システム。
【請求項３】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、
前記スタートから前記ゴールまでの最長経路を特定し、
特定した前記最長経路を出力する
計算方法。
【請求項４】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換する処理と、
前記スタートから前記ゴールまでの最長経路を特定する処理と、
特定した前記最長経路を出力する処理と、をコンピュータに実行させる
計算プログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算システムに関し、特に、割り当て問題を解決する計算システムに関する。
【背景技術】
【０００２】
割当問題とは，集合Aの要素（a1,a2,a3…）を集合Bの要素（b1,b2,b3…）のどれに割り当てるかを決定する問題である(図１)。一般に、割当問題においては、要素の数が増えると、組み合わせの数は階乗のオーダーで増大する。その膨大な組み合わせの中から、最適な組み合わせを探索しようとすると、膨大な処理時間がかかる。このため、一般に、割当問題においては、要素の数が増えるほど、最適な組み合わせを求めることは困難になる（組み合わせ爆発）。【０００３】
たとえば、作業者Cと作業者Dに空き時間にいずれか一人でしかできない作業をしてもらうことにしたときに、作業時間の合計をできるだけ大きくするためには、どの時間に誰に作業を頼むと良いか、という問題を考える。作業者CおよびDの1日の空き時間は、図２上の通りとする。これはつまり、作業者CおよびDの1日の空き時間という集合の要素を、作業時間という集合の要素に割り当てる問題である。【０００４】
この問題を解決するにあたり、次の条件を満たすものとする。（１）作業を行うための設備が1台しかなく、複数人同時の作業ができない。（２）必ず、空き時間の開始から終了まで作業をし、空き時間の途中から作業を始めたり、空き時間の途中で作業をやめたりはしない。以上の条件のもとで作業時間の合計を最大化する。【０００５】
結果として、図２下のようにすると、最大の「１３時間」作業してもらうことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−０６４０８１号公報
【特許文献２】特表２０１２−５０４８００号公報
【特許文献３】特開２０１３−２５４３６８号公報
【特許文献４】特開２００３−２９９８８号広報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記の例では考慮すべき要素の数が少なくなるように設定したため、わずかな試行錯誤を繰り返すことで最適な組み合わせを求めることができる。ところが、作業者の数を増やしたり、作業を行うための設備を増やしたり、空き時間の途中で作業を交代できるようにしたりなどすると、考慮すべき要素の数が増えて、最適な組み合わせを求めることは困難になっていく。本発明は上述した課題を解決することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の計算システムは、所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、スタートからゴールまでの最長経路を特定するスケジューリング部と、特定した最長経路を出力する解出力部とを備える。【０００９】
本発明の計算方法は、所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、スタートからゴールまでの最長経路を特定し、特定した最長経路を出力する。【００１０】
本発明の計算プログラムは、所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換する処理と、スタートからゴールまでの最長経路を特定する処理と、特定した最長経路を出力する処理と、をコンピュータに実行させる。【００１１】
なお、本発明の目的は、上記計算プログラムが記録された記録媒体によって達成されてもよい。
【発明の効果】
【００１２】
本発明によれば、割当問題において最適な組み合わせを効率よく求めることができる。
【図面の簡単な説明】
【００１３】
【図１】割当問題の概念図である。
【図２】割当問題の例題の説明図である。
【図３】本発明の実施形態にかかる一般化された割当問題の説明図である。
【図４】本発明の実施形態にかかるタスクデータのデータ構造を示す図である。
【図５】本発明の実施形態にかかる計算システムの構成を示すブロック図である。
【図６】本発明の実施形態にかかる計算システムの全体の動作を示すフローチャートである。
【図７】本発明の実施形態にかかる計算システムの初期化の処理を示すフローチャートである。
【図８】本発明の実施形態にかかる（ａ）from候補一覧（ｂ）イベントキュー（ｃ）展開タスク情報のデータ構造を示す図である。
【図９】本発明の実施形態にかかる計算システムのスケジューリングの処理を示すフローチャートである。
【図１０】本発明の実施形態にかかるタスクを展開しイベントキューに設定の処理を示すフローチャートである。
【図１１】本発明の実施形態にかかるタスク間の関連を設定の処理を示すフローチャートである。
【図１２】本発明の実施形態にかかるfrom候補一覧を更新の処理を示すフローチャートである。
【図１３】本発明の実施形態にかかる解の出力の処理を示すフローチャートである。
【図１４】本発明の実施形態に係るコンピュータ装置のハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下に、図面を参照しながら、本発明の実施形態について詳細に説明する。なお、以下の説明では、同じ機能を有するものには同じ符号をつけ、その説明を省略する場合がある。
【００１５】
図３は本発明の実施形態にかかる一般化された割当問題の説明図である。本発明の実施形態では、次のように一般化された割当問題を解決する。すなわち、開始時刻Tsから終了時刻Teまでの間に、複数のタスクを、時間重複なく、できるだけ多く配置する割当問題を解決する。タスクとは、作業のことである。タスクは最早開始時刻tsから最遅終了時刻teまでの間の所要時間dだけ連続した時間実行する作業であり、開始時刻および終了時刻をずらすことが可能であるものとしてあらかじめ定義する。複数の定義されたタスクをまとめてタスクデータと呼ぶ。
【００１６】
図４は、本発明の実施形態にかかるタスクデータのデータ構造を示す図である。タスクデータとは、タスクNo.、最早開始時刻ts、最遅終了時刻te、所要時間dの項目をもつデータである。
【００１７】
（構成）
図５は本発明の実施形態にかかる計算システムの構成を示すブロック図である。本発明の実施形態にかかる計算システム１００は、初期化部１０１、スケジューリング部１０２、解出力部１０３をもつ。
【００１８】
（作用）
図６は本発明の実施形態にかかる計算システムの全体の動作を示すフローチャートである。全体の動作は、大きく分けて初期化S1、スケジューリングS2、解の出力S3の3つの処理に分けられる。以下に各処理の詳細について説明する。
【００１９】
図７は本発明の実施形態にかかる計算システムの初期化の処理を示すフローチャートである。以下に初期化S1の処理について説明する。
【００２０】
初期化部１０１は、from候補一覧の、タスクNo.の列のすべての要素へ「空」を代入し、展開No.の列のすべての要素へ「空」を代入する（ステップS101）。
【００２１】
図８は、本発明の実施形態にかかる（ａ）from候補一覧（ｂ）イベントキュー（ｃ）展開タスク情報のデータ構造を示す図である。from候補一覧とは、タスクNo.、展開No.、の列項目をもつ２次元配列の構造を持つデータである。イベントキューとは、type、time、タスクNo.、展開No.、の列項目をもつ２次元配列の構造を持つFIFOキューである。typeは、Task,Start,Endの３種類の値をとりうる。展開タスク情報は、タスクNo.、展開No.、start、point、score、history、del、fromの列項目をもつ２次元配列の構造を持つデータである。
【００２２】
次に、初期化部１０１は、イベントキューの、typeの列のすべての要素へ「Task」を代入し、timeの列の各要素へタスクNo.に対応するタスクデータの最早開始時刻tsを代入し、タスクNo.の列の各要素へ１からNまでの値１つずつ代入し、展開No.の列のすべての要素へ「空」を代入する（ステップS102）。
【００２３】
次に、初期化部１０１は、イベントキューをtimeで昇順にソートする（ステップS103）。
【００２４】
次に、初期化部１０１は、展開タスク情報のすべての列の各要素を空にする（ステップS104）。ステップS104が終了したら、初期化部１０１は、初期化S1の処理を終了する。
【００２５】
以上が、初期化S1の処理である。
【００２６】
図９は本発明の実施形態にかかる計算システムのスケジューリングの処理を示すフローチャートである。以下にスケジューリングS2の処理について説明する。スケジューリングS2の処理は、複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、前記スタートから前記ゴールまでの最長経路を特定する処理である。
【００２７】
スケジューリング部１０２は、イベントキューにデータがあるか否か判断する（ステップS201）。イベントキューにデータがある場合（ステップS201においてYes）、スケジューリング部１０２は、イベントキューの先頭データを取り出す（ステップS202）。ステップS202の後はステップS203へ進む。イベントキューにデータがない場合（ステップS201においてNo）、スケジューリング部１０２は、スケジューリングS2の処理を終了する。
【００２８】
スケジューリング部１０２は、ステップS202で取り出したデータを変数eventに代入する（ステップS203）。
【００２９】
スケジューリング部１０２は、変数eventのtypeが何であるか判断する（ステップS204）。
【００３０】
ステップS204において変数eventのtypeがTaskであった場合（ステップS204においてTask）、スケジューリング部１０２は、タスクを展開しイベントキューに設定（ステップS205）の処理を行う。ステップS205の後はステップS201へ進む。
【００３１】
ステップS204において変数eventのtypeがStartであった場合（ステップS204においてStart）、スケジューリング部１０２は、タスク間の関連を設定（ステップS206）の処理を行う。ステップS206の後はステップS201へ進む。
【００３２】
ステップS204において変数eventのtypeがEndであった場合（ステップS204においてEnd）、スケジューリング部１０２は、from候補一覧を更新（ステップS207）の処理を行う。ステップS20７の後はステップS201へ進む。
【００３３】
以上が、スケジューリングS2の処理である。
【００３４】
ここから、タスクを展開しイベントキューに設定（ステップS205）の処理についてより詳細に説明する。
【００３５】
図１０は本発明の実施形態にかかるタスクを展開しイベントキューに設定の処理を示すフローチャートである。ここで、タスクを展開するとは、そのタスクの最早開始時刻から最遅終了時刻までの間でとりうる開始時刻または終了時刻に対応する複数のイベント（以降展開タスク）を作成することである。開始時刻に対応する展開タスクと終了時刻に対応する展開タスクとはそれぞれ別に作成される。
【００３６】
スケジューリング部１０２は、変数taskへ変数eventのタスクNo.に対応するタスクデータを代入する（ステップS2051）。次に、スケジューリング部１０２は、変数t0へ変数taskの最早開始時刻tsを代入し、変数t1へ変数taskの最遅終了時刻teと変数taskの所要時間dとの差の値を代入し、変数jへ1を代入する（ステップS2052）。
【００３７】
次に、スケジューリング部１０２は、t0≦t1であるか否か判定する（ステップS2053）。
【００３８】
ステップS2053において、t0≦t1である場合（ステップS2053においてYes）、次に、スケジューリング部１０２は、イベントキューへtype=Start、time=t0、タスクNo.=eventのタスクNo.、展開No.=jのデータを登録する（ステップS2054）。ステップS2054の後はステップS2055へ進む。
【００３９】
ステップS2053において、t0≦t1ではない場合（ステップS2053においてNo）、次に、スケジューリング部１０２は、イベントキューをtimeで昇順にソートする（ステップS2058）。ステップS2058が終了したら、スケジューリング部１０２は、スケジューリングS2の処理を終了する。
【００４０】
スケジューリング部１０２は、イベントキューへtype=End、time=変数t0と変数taskの所要時間dとの和の値、タスクNo.= eventのタスクNo.、展開No.=jのデータを登録する（ステップS2055）。
【００４１】
次に、スケジューリング部１０２は、展開タスク情報へ、タスクNo.＝変数eventのタスクNo.、展開No.＝変数eventの展開No.、 start=t0、point=taskの所要時間d、score=0、history=(空)、del=(空)、from=(空)のデータを登録する（ステップS2056）。
【００４２】
ステップS2056におけるpointの設定の仕方を変えることでタスクの優先順位を設定することができる。
【００４３】
次に、スケジューリング部１０２は、変数t0へ変数t0+DTの値を代入し、変数jへj+1の値を代入する（ステップS2057）。DTは予め設定する時刻の刻み幅である。時刻の刻み幅が細かいほどスケジューリングの精度が向上する。一方で時刻の刻み幅が細かいほどCPU負荷は大きくなる。ステップS2057の後はステップS2053へ進む。
【００４４】
以上が、タスクを展開しイベントキューに設定（ステップS205）の処理の詳細である。
【００４５】
ここから、タスク間の関連を設定（ステップS206）の処理についてより詳細に説明する。
【００４６】
図１１は本発明の実施形態にかかるタスク間の関連を設定の処理を示すフローチャートである。関連を設定するとは、有向グラフの辺を作成することである。
【００４７】
スケジューリング部１０２は、変数iへ1を代入する（ステップS2061）
次に、スケジューリング部１０２は、i≦from候補一覧のデータ件数であるか否か判断する（ステップS2062）。
【００４８】
ステップS2062においてi≦from候補一覧のデータ件数である場合（ステップS2062においてYes）、次に、スケジューリング部１０２は、変数fromへfrom候補一覧のi番目のデータを代入する（ステップS2063）。ステップS2063の後はステップS2064へ進む。
【００４９】
ステップS2062においてi≦from候補一覧のデータ件数ではない場合（ステップS2062においてNo）、スケジューリング部１０２は、タスク間の関連を設定（ステップS206）の処理を終了する。
【００５０】
スケジューリング部１０２は、変数fromのタスクNo.≠変数eventのタスクNo.であるか否か判断する（ステップS2064）。この処理によって同一のタスクへの処理を省いている。
【００５１】
ステップS2064において変数fromのタスクNo.≠変数eventのタスクNo.である場合（ステップS2064においてYes）、次に、スケジューリング部１０２は、変数historyへ変数fromのタスクNo.および展開No.の組に対応する展開タスク情報のhistoryを代入する（ステップS2065）。ステップS2065の後はステップS2066へ進む。
【００５２】
ステップS2064において変数fromのタスクNo.≠変数eventのタスクNo.ではない場合（ステップS2064においてNo）、ステップS20617へ進む。
【００５３】
スケジューリング部１０２は、historyにeventのタスクNo.が含まれていないか否か判断する（ステップS2066）。この処理によって、すでに関連性を設定したタスクへの処理を省いている。
【００５４】
ステップS2066において変数historyにeventのタスクNo.が含まれていない場合（ステップS2066においてYes）、次に、スケジューリング部１０２は、変数endへ変数fromのタスクNo.および展開No.の組に対応する展開タスク情報のstartと変数fromのタスクNo.に対応するタスクデータの所要時間dとの和を代入する（ステップS2067）。ステップS2067の後はステップS2068へ進む。
【００５５】
ステップS2066において変数historyにeventのタスクNo.が含まれている場合（ステップS2064においてNo）、ステップS20617へ進む。
【００５６】
スケジューリング部１０２は、変数end＜変数eventのtimeであるか否か判断する（ステップS2068）。
【００５７】
ステップS2068において変数end＜変数eventのtimeである場合（ステップS2068においてYes）、次に、スケジューリング部１０２は、変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のdelに変数fromのタスクNo.と展開No.を追加する（ステップS2069）。
ステップS2069の後はステップS20610へ進む。
【００５８】
ステップS2068において変数end＜変数eventのtimeではない場合（ステップS2068においてNo）、ステップS20617へ進む。
【００５９】
スケジューリング部１０２は、変数pointへ変数fromのタスクNo.および展開No.の組に対応する展開タスク情報のpointを代入し、変数scoreへ変数fromのタスクNo.および展開No.の組に対応する展開タスク情報のscoreを代入する（ステップS20610）。
【００６０】
次に、スケジューリング部１０２は、変数score0へ変数pointと変数scoreの和の値を代入する（ステップS20611）。
【００６１】
次に、スケジューリング部１０２は、変数score1へ変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のscoreを代入する（ステップS20612）。
【００６２】
次に、スケジューリング部１０２は、変数score0>変数score1であるか否か判断する（ステップS20613）。
【００６３】
ステップS20613において変数score0＞変数score1である場合（ステップS20613においてYes）、次に、スケジューリング部１０２は、変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のscoreへscore0を代入する（ステップS20614）。ステップS20614の後はステップS20615へ進む。
【００６４】
ステップS20613において変数score0＞変数score1ではない場合（ステップS20613においてNo）、ステップS20617へ進む。
【００６５】
スケジューリング部１０２は、変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のfromへ変数fromを代入する（ステップS20615）。
【００６６】
次に、スケジューリング部１０２は、変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のhistoryへ変数fromのタスクNo.を追加する（ステップS20616）。
【００６７】
次に、スケジューリング部１０２は、変数i へ変数i+1の値を代入する（ステップS20617）。ステップS20617の後はステップS2062へ進む。
【００６８】
以上が、タスク間の関連を設定（ステップS206）の処理の詳細である。
【００６９】
ここから、from候補一覧を更新（ステップS207）の処理についてより詳細に説明する。
【００７０】
図１２は本発明の実施形態にかかるfrom候補一覧を更新の処理を示すフローチャートである。
【００７１】
スケジューリング部１０２は、変数delへ変数eventのタスクNo.および展開No.の組に対応する展開タスク情報のdelを代入する（ステップS2071）。
【００７２】
次に、スケジューリング部１０２は、from候補一覧から変数delに設定されているタスクNo.および展開No.の組を削除する（ステップS2072）。
【００７３】
次に、スケジューリング部１０２は、from候補一覧に変数eventのタスクNo.および展開No.の組を追加する（ステップS2073）。
【００７４】
以上が、from候補一覧を更新（ステップS207）の処理の詳細である。
【００７５】
図１３は本発明の実施形態にかかる解の出力の処理を示すフローチャートである。以下に解の出力S3の処理について説明する。解の出力S3の処理は、特定した最長経路を出力する処理である。
【００７６】
解出力部１０３は、変数expへ、from候補一覧のタスクNo.および展開No.の組に対応する展開タスク情報の中で最もscoreの大きいデータを代入する（ステップS301）。
【００７７】
次に、解出力部１０３は、変数tiへ変数expのタスクNo.を代入し、変数tjへ変数expの展開No.を代入する（ステップS302）。
【００７８】
次に、解出力部１０３は、変数rootへ空の配列を設定する（ステップS303）。
【００７９】
次に、解出力部１０３は、変数rootへ変数tiと変数tjの組を追加する（ステップS304）。
【００８０】
次に、解出力部１０３は、展開タスク情報(タスクNo.=ti,展開No.=tj)のfromが空か否か判断する（ステップS305）。
【００８１】
ステップS305において変数展開タスク情報(タスクNo.=ti,展開No.=tj)のfromが空である場合（ステップS305においてYes）、解出力部１０３は、rootに格納されているデータを末尾から先頭に向かって出力する（ステップS306）。ステップS306が終了したら、解出力部１０３は、解の出力S3の処理を終了する。
【００８２】
ステップS305において変数展開タスク情報(タスクNo.=ti,展開No.=tj)のfromが空ではない場合（ステップS305においてNo）、解出力部１０３は、変数tiへ展開タスク情報(タスクNo.=ti,展開No.=tj)のfromのタスクNo.を代入し、変数tjへ展開タスク情報(タスクNo.=ti,展開No.=tj)のfromの展開No.を代入する（ステップS307）。ステップS307の後はステップS304へ進む。
【００８３】
以上が、解の出力S3の処理である。
【００８４】
（効果）
本実施形態によれば、割当問題において最適な組み合わせを効率よく求めることができる。さらに、本実施形態によれば、複数の作業を並行して実施する場合のリソース競合を回避するためのスケジューリングや、多くのタスクを複数人に振り分けて全体の作業時間を最小化するスケジューリングに応用できる。これらは一般にジョブショップスケジューリングと呼ばれている。
（ハードウェア構成）
図１４は、本発明の実施形態に係るコンピュータ装置のハードウェア構成の一例を示すブロック図である。コンピュータ装置４００は、上述した計算システム１００を実現する装置の一例である。コンピュータ装置４００は、ＣＰＵ（Central Processing Unit）４０１と、ＲＯＭ（Read Only Memory）４０２と、ＲＡＭ（Random Access Memory）４０３と、記憶装置４０４と、ドライブ装置４０５と、通信インタフェース４０６と、入出力インタフェース４０７とを備える。計算システム１００は、図１４に示される構成（又はその一部）によって実現され得る。
【００８５】
ＣＰＵ４０１は、ＲＡＭ４０３を用いてプログラム４０８を実行する。プログラム４０８は、ＲＯＭ４０２に記憶されていてもよい。また、プログラム４０８は、フラッシュメモリなどの記録媒体４０９に記録され、ドライブ装置４０５によって読み出されてもよいし、外部装置からネットワーク４１０を介して送信されてもよい。通信インタフェース４０６は、ネットワーク４１０を介して外部装置とデータをやり取りする。入出力インタフェース４０７は、周辺機器（入力装置、表示装置など）とデータをやり取りする。通信インタフェース４０６及び入出力インタフェース４０７は、データを取得又は出力する手段として機能することができる。
【００８６】
なお、初期化部１０１、スケジューリング部１０２、解出力部１０３等のそれぞれは、単一の回路（プロセッサ等）によって構成されてもよいし、複数の回路の組み合わせによって構成されてもよい。ここでいう回路（circuitry）は、専用又は汎用のいずれであってもよい。また、初期化部１０１、スケジューリング部１０２、解出力部１０３等は、これらが単一の回路によって構成されてもよい。
【００８７】
本発明は上記実施形態に限定されることなく、請求の範囲に記載の発明の範囲内で、種々の変形が可能であり、それらも本発明の範囲内に含まれるものであることはいうまでもない。即ち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【００８８】
この出願は、２０１７年３月３１日に出願された日本出願特願２０１７−０６９４５６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００８９】
１００    計算システム
１０１    初期化部
１０２    スケジューリング部
１０３    解出力部
４００    コンピュータ装置
４０１    ＣＰＵ（Central Processing Unit）
４０２    ＲＯＭ（Read Only Memory）
４０３    ＲＡＭ（Random Access Memory）
４０４    記憶装置
４０５    ドライブ装置
４０６    通信インタフェース
４０７    入出力インタフェース
４０８    プログラム
４０９    記録媒体
４１０    ネットワーク
【図１】
2018180741.tif 000003
【図２】
2018180741.tif 000004
【図３】
2018180741.tif 000005
【図４】
2018180741.tif 000006
【図５】
2018180741.tif 000007
【図６】
2018180741.tif 000008
【図７】
2018180741.tif 000009
【図８】
2018180741.tif 000010
【図９】
2018180741.tif 000011
【図１０】
2018180741.tif 000012
【図１１】
2018180741.tif 000013
【図１２】
2018180741.tif 000014
【図１３】
2018180741.tif 000015
【図１４】
2018180741.tif 000016
【手続補正書】
【提出日】令和1年9月5日(2019.9.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、前記スタートから前記ゴールまでの最長経路を特定するスケジューリング手段と、
特定した前記最長経路を出力する解出力手段と、を備える
計算システム。
【請求項２】
前記スケジューリング手段は、
前記有向グラフへの変換において、1つのタスクをそのタスクがとりうる複数の開始時刻それぞれに対応する複数の頂点に変換する、
請求項１に記載の計算システム。
【請求項３】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換し、
前記スタートから前記ゴールまでの最長経路を特定し、
特定した前記最長経路を出力する
計算方法。
【請求項４】
所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
前記複数個のタスクの分布を示すデータであるタスクデータを、スタートおよびゴールをもつ有向グラフに変換する処理と、
前記スタートから前記ゴールまでの最長経路を特定する処理と、
特定した前記最長経路を出力する処理と、をコンピュータに実行させる
計算プログラム。
【国際調査報告】
2018180741.tif 000017
2018180741.tif 000018
2018180741.tif 000019
2018180741.tif 000020