[go: up one dir, main page]

JP6885459B2 - 計算システム、計算方法および計算プログラム - Google Patents

計算システム、計算方法および計算プログラム Download PDF

Info

Publication number
JP6885459B2
JP6885459B2 JP2019509368A JP2019509368A JP6885459B2 JP 6885459 B2 JP6885459 B2 JP 6885459B2 JP 2019509368 A JP2019509368 A JP 2019509368A JP 2019509368 A JP2019509368 A JP 2019509368A JP 6885459 B2 JP6885459 B2 JP 6885459B2
Authority
JP
Japan
Prior art keywords
task
time
variable
event
expansion
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
JP2019509368A
Other languages
English (en)
Other versions
JPWO2018180741A1 (ja
Inventor
広宣 森
広宣 森
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NEC Corp
Original Assignee
NEC Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by NEC Corp filed Critical NEC Corp
Publication of JPWO2018180741A1 publication Critical patent/JPWO2018180741A1/ja
Application granted granted Critical
Publication of JP6885459B2 publication Critical patent/JP6885459B2/ja
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/10—Office automation; Time management
    • G06Q10/109—Time management, e.g. calendars, reminders, meetings or time accounting
    • G06Q10/1093—Calendar-based scheduling for persons or groups
    • G06Q10/1097—Task assignment
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/10—Office automation; Time management

Landscapes

  • Business, Economics & Management (AREA)
  • Human Resources & Organizations (AREA)
  • Engineering & Computer Science (AREA)
  • Entrepreneurship & Innovation (AREA)
  • Strategic Management (AREA)
  • Economics (AREA)
  • Tourism & Hospitality (AREA)
  • Theoretical Computer Science (AREA)
  • Operations Research (AREA)
  • Quality & Reliability (AREA)
  • Marketing (AREA)
  • Physics & Mathematics (AREA)
  • General Business, Economics & Management (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Development Economics (AREA)
  • Educational Administration (AREA)
  • Game Theory and Decision Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Debugging And Monitoring (AREA)

Description

本発明は、計算システムに関し、特に、割り当て問題を解決する計算システムに関する。
割当問題とは，集合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）
４０４ 記憶装置
４０５ ドライブ装置
４０６ 通信インタフェース
４０７ 入出力インタフェース
４０８ プログラム
４０９ 記録媒体
４１０ ネットワーク

Claims (3)

  1. 所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
    前記複数個のタスクの各々について、当該タスクが取り得る前記開始時刻の各々に対して、当該タスクの開始時間をずらしたイベントを生成し、生成した前記イベントの各々を頂点とし、異なるタスクのイベント間の関連を辺として、スタートおよびゴールをもつ有向グラフに変換し、前記スタートから前記ゴールまでの最長経路を特定するスケジューリング部と、
    特定した前記最長経路を出力する解出力部と、
    を備える計算システム。
  2. コンピュータが
    所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
    前記複数個のタスクの各々について、当該タスクが取り得る前記開始時刻の各々に対して、当該タスクの開始時間をずらしたイベントを生成し、生成した前記イベントの各々を頂点とし、異なるタスクのイベント間の関連を辺として、スタートおよびゴールをもつ有向グラフに変換し、
    前記スタートから前記ゴールまでの最長経路を特定し、
    特定した前記最長経路を出力する計算方法。
  3. 所定の開始時刻から所定の終了時刻までの間に、開始時刻および終了時刻をずらすことが可能である複数個のタスクを、時間重複なく、できるだけ多数実行する場合に、
    前記複数個のタスクの各々について、当該タスクが取り得る前記開始時刻の各々に対して、当該タスクの開始時間をずらしたイベントを生成し、生成した前記イベントの各々を頂点とし、異なるタスクのイベント間の関連を辺として、スタートおよびゴールをもつ有向グラフに変換する手段と、
    前記スタートから前記ゴールまでの最長経路を特定する手段と、
    特定した前記最長経路を出力する手段
    として機能させる計算プログラム。
JP2019509368A 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラム Active JP6885459B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2017069456 2017-03-31
JP2017069456 2017-03-31
PCT/JP2018/010937 WO2018180741A1 (ja) 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラムが記録された記録媒体

Publications (2)

Publication Number Publication Date
JPWO2018180741A1 JPWO2018180741A1 (ja) 2020-01-09
JP6885459B2 true JP6885459B2 (ja) 2021-06-16

Family

ID=63675931

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2019509368A Active JP6885459B2 (ja) 2017-03-31 2018-03-20 計算システム、計算方法および計算プログラム

Country Status (3)

Country Link
US (1) US20200042951A1 (ja)
JP (1) JP6885459B2 (ja)
WO (1) WO2018180741A1 (ja)

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4206653B2 (ja) * 2001-07-13 2009-01-14 日本電気株式会社 タスクスケジューリングシステムおよび方法、プログラム
JP4781089B2 (ja) * 2005-11-15 2011-09-28 株式会社ソニー・コンピュータエンタテインメント タスク割り当て方法およびタスク割り当て装置
JP2008171153A (ja) * 2007-01-10 2008-07-24 Fujitsu Ten Ltd タスク管理装置
JP2013083588A (ja) * 2011-10-12 2013-05-09 Clarion Co Ltd 経路探索装置、経路探索方法
US20160125095A1 (en) * 2014-11-05 2016-05-05 Nec Laboratories America, Inc. Lightweight temporal graph management engine

Also Published As

Publication number Publication date
JPWO2018180741A1 (ja) 2020-01-09
US20200042951A1 (en) 2020-02-06
WO2018180741A1 (ja) 2018-10-04

Similar Documents

Publication Publication Date Title
CN111104222A (zh) 任务处理方法、装置、计算机设备和存储介质
JP3890045B2 (ja) 改善されたｅｄｆスケジューリング方法
EP3282407A1 (en) Assembly line balancing apparatus, method and program
CN110058882B (zh) 一种用于cnn加速的opu指令集定义方法
JP2018197906A (ja) 情報処理装置、マルチスレッド行列演算方法、およびマルチスレッド行列演算プログラム
Singh et al. Improved task scheduling on parallel system using genetic algorithm
Robinson Discrete‐event simulation: A primer
JP6885459B2 (ja) 計算システム、計算方法および計算プログラム
US11409836B2 (en) Optimization problem arithmetic method and optimization problem arithmetic apparatus
Moiseev et al. Infinite-server queueing tandem with MMPP arrivals and random capacity of customers
US9378061B2 (en) Method for prioritizing tasks queued at a server system
JP4540702B2 (ja) データ変換器、流動解析器、構造解析器、データ変換プログラム、流動解析プログラム、構造解析プログラム及びデータ変換方法
Panwalkar et al. An O (n2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
CN113296788A (zh) 指令调度方法、装置、设备、存储介质及程序产品
JP2015170085A (ja) ジョブ実行時間予測方法およびジョブ管理装置
US20220214915A1 (en) Information processing device, schedule specification method, and storage medium
JP5686477B2 (ja) スケジュール作成方法及びスケジュール作成プログラム、並びにスケジュール作成装置
Rudek et al. The solution algorithms for the multiprocessor scheduling with workspan criterion
JP6866921B2 (ja) 計算システム、計算方法および計算プログラム
Kuo et al. Optimal NT policies for a two-phase service M/G/1 system with Bernoulli vacation schedule
US20190392101A1 (en) Information processing device, information processing method, and recording medium
JP7247422B2 (ja) 情報処理装置、情報処理方法、及び情報処理プログラム
WO2019239820A1 (ja) パラメータ最適化装置、方法、およびプログラム
CN106557368B (zh) Spark程序优化方法和装置
Medina-Marin et al. A Petri Net Model to obtain the Makespan in the Flow Shop Scheduling Problem

Legal Events

Date Code Title Description
A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20190905

A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20190905

A131 Notification of reasons for refusal

Free format text: JAPANESE INTERMEDIATE CODE: A131

Effective date: 20201117

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20210115

TRDD Decision of grant or rejection written
A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20210413

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20210426

R150 Certificate of patent or registration of utility model

Ref document number: 6885459

Country of ref document: JP

Free format text: JAPANESE INTERMEDIATE CODE: R150