(57)【要約】【課題】処理要求に対する制約が満たされる可能性を高めること。【解決手段】処理要求管理装置は、それぞれに希望処理完了時刻が指定された複数の処理要求のそれぞれについて、処理の所要時間を推定する推定部と、前記処理要求ごとの前記希望処理完了時刻に対する前記所要時間に基づく推定処理完了時刻の遅延について、前記複数の処理要求における合計が最小となるように、前記複数の処理要求に対する処理の実行順序を決定する決定部と、を有する。【選択図】図３
2020080119.tif 000002
【特許請求の範囲】
【請求項１】
それぞれに希望処理完了時刻が指定された複数の処理要求のそれぞれについて、処理の所要時間を推定する推定部と、
前記処理要求ごとの前記希望処理完了時刻に対する前記所要時間に基づく推定処理完了時刻の遅延について、前記複数の処理要求における合計が最小となるように、前記複数の処理要求に対する処理の実行順序を決定する決定部と、
を有することを特徴とする処理要求管理装置。
【請求項２】
前記各処理要求を順番に受け付け、前記順番の変更が許容されない処理要求群に対して共通の識別情報を付与する受付部を有し、
前記決定部は、前記共通の識別情報が付与された前記処理要求群内において前記順番が維持されるように前記実行順序を決定する、
ことを特徴とする請求項１記載の処理要求管理装置。
【請求項３】
前記複数の処理要求のうち、処理の一部が共通する複数の処理要求を一つに結合する結合部を有し、
前記決定部は、結合された複数の処理要求は一つの処理要求として、前記実行順序を決定する、
ことを特徴とする請求項１又は２記載の処理要求管理装置。
【請求項４】
それぞれに希望処理完了時刻が指定された複数の処理要求のそれぞれについて、処理の所要時間を推定する推定手順と、
前記処理要求ごとの前記希望処理完了時刻に対する前記所要時間に基づく推定処理完了時刻の遅延について、前記複数の処理要求における合計が最小となるように、前記複数の処理要求に対する処理の実行順序を決定する決定手順と、
をコンピュータが実行することを特徴とする処理要求管理方法。
【請求項５】
前記各処理要求を順番に受け付け、前記順番の変更が許容されない処理要求群に対して共通の識別情報を付与する受付手順を前記コンピュータが実行し、
前記決定手順は、前記共通の識別情報が付与された前記処理要求群内において前記順番が維持されるように前記実行順序を決定する、
ことを特徴とする請求項４記載の処理要求管理方法。
【請求項６】
前記複数の処理要求のうち、処理の一部が共通する複数の処理要求を一つに結合する結合手順を前記コンピュータが実行し、
前記決定手順は、結合された複数の処理要求は一つの処理要求として、前記実行順序を決定する、
ことを特徴とする請求項４又は５記載の処理要求管理方法。
【請求項７】
請求項４乃至６いずれか一項記載の処理要求管理方法をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理要求管理装置、処理要求管理方法及びプログラムに関する。
【背景技術】
【０００２】
仮想化技術の進展に伴い、仮想化技術の適用範囲はクラウドコンピューティングの分野のみならず、通信ネットワークの分野にも及んでおり、商用ネットワークにおいても仮想化が進んでいる。仮想化された通信ネットワークでは、オーケストレータやコントローラと呼ばれる制御装置がネットワーク装置を一元的に制御する。ネットワークの利用者及び用者は、ネットワークにサービスの新設（新規開通）・変更・廃止などの操作を行いたい場合は、制御装置にオーダーを投入する。オーダーの種類によっては、長い処理時間を要するため、オーダーが多数発行される場合は、制御装置の処理が間に合わず、オーダーが待機状態となる。制御装置は、実行中の処理が完了した時点で、待機中のオーダーについて処理を実行する。
【０００３】
仮想化ネットワークのサービスに関するオーダーの実行では、オーダー毎の実行制約を考慮することが求められる。ここでは、実行制約として処理完了期限制約及び実行順序制約を考える。処理完了期限制約とは、オーダー発行者が希望する時刻までに処理を完了しなければならい、という実行制約である。リアルタイム性の高いオーダー（例えば、故障に伴うサービス変更）と、そうでないオーダー（例えば、数日後の新規サービス開通）とでは、希望する処理完了時刻は大きく異なるため、期限に合わせて処理順序を変更する必要がある。
【０００４】
一方、実行順序制約とは、あるサービスに対するオーダーの実行順序を入れ替えてはいけない、という実行制約である。あるサービスに対する新規開通のオーダーが投入され、その直後に当該サービスの変更オーダーが投入されたとする。これらのオーダーの実行順序が逆転すると、存在しないサービスに対する変更オーダーが実行されることになり、オーダー投入者が意図しない処理となってしまう。
【０００５】
実行制約は可能な限り守られるべきであるため、実行制約（処理完了期限・実行順序制約）違反のオーダー数を最小化することが求められる。実行制約違反のオーダー数を最小化するための手段として、「実行制約を考慮したオーダーの順序入れ替え」と、「冗長なオーダーの結合」が考えられる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許５５１３９９９号公報
【非特許文献】
【０００７】
【非特許文献１】松尾 啓志、"オペレーティングシステム"、森北出版株式会社、2005年、［online］、インターネット＜ＵＲＬ：http://www.matlab.nitech.ac.jp/~matsuo/OS/OS03.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００８】
オーダーの順序入れ替えについては、従来技術として、代表的なスケジューリング手法である、ＦＩＦＯ（First In First Out）方式、ＰＳ（Priority Scheduling）方式、ＳＰＴＦ（Shortest Processing Time First）方式などがある（非特許文献１）。ＦＩＦＯ方式は、キューに到着した順序で、オーダーをキューから取り出す方式である。ＰＳ方式は、優先度をオーダーに付与し、キュー内で最も優先度の高いものを取り出す方式である。ＳＰＴＦ方式は、キュー内で処理時間の推定値が最も短いオーダーを取り出す方式である。これらの従来技術では、実行制約（処理完了期限・実行順序制約）を考慮した順序入れ替えは困難である。
【０００９】
また、オーダーの結合については、待機中のオーダーのうち、冗長なものをマージする技術が提案されている（特許文献１）。冗長なオーダーを結合すると、本来不要なオーダーの処理時間を他のオーダーの処理に割り当てられるため、希望処理完了期限内にオーダーが実行される可能性が高くなる。しかし、この技術はネットワーク装置へのオーダー投入を対象としているため、仮想化ネットワークのオーダーを対象とした結合は困難である。
【００１０】
上述のように、従来技術では、実行制約違反のオーダー数を最小化することは困難である。
【００１１】
本発明は、上記の点に鑑みてなされたものであって、処理要求に対する制約が満たされる可能性を高めることを目的とする。
【課題を解決するための手段】
【００１２】
そこで上記課題を解決するため、処理要求管理装置は、それぞれに希望処理完了時刻が指定された複数の処理要求のそれぞれについて、処理の所要時間を推定する推定部と、前記処理要求ごとの前記希望処理完了時刻に対する前記所要時間に基づく推定処理完了時刻の遅延について、前記複数の処理要求における合計が最小となるように、前記複数の処理要求に対する処理の実行順序を決定する決定部と、を有する。
【発明の効果】
【００１３】
処理要求に対する制約が満たされる可能性を高めることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態におけるオーダー管理システムの構成例を示す図である。
【図２】本発明の実施の形態におけるオーダー管理装置１０のハードウェア構成例を示す図である。
【図３】本発明の実施の形態におけるオーダー管理装置１０の機能構成例を示す図である。
【図４】オーダー管理システムにおいて実行される処理手順の一例を示す図である。
【図５】オーダーの内容の一例を示す図である。
【図６】処理ラベルが付与されたオーダーの例を示す図である。
【図７】処理時間の傾向の学習の例を説明するための図である。
【図８】オーダー結合の例を説明するための図である。
【図９】オーダー実行順序の決定の例を説明するための図である。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて本発明の実施の形態を説明する。本実施の形態では、仮想化された通信ネットワーク（以下、「仮想化ネットワーク」という。）のサービスに関するオーダーについて、「実行制約を考慮したオーダーの順序入れ替え」及び「冗長なオーダーの結合」を実現することで、「実行制約違反のオーダー数を最小化」を解決するオーダー管理装置１０が開示される。なお、サービスに関するオーダーとは、例えば、サービスの新設（新規開通）、変更、又は廃止等を示す処理要求をいう。サービスの新規開通とは、仮想化ネットワーク上に、新たなサービスを開通（開設）させることをいう。サービスの開通とは、サービスの構成要素（ファイアウォール（ＦＷ）、ロードバランサ（ＬＢ）、Ｗｅｂサーバ等の各種のサーバ）に対応するリソースの割り当てを仮想化ネットワークから受けることをいう。なお、サービスの構成要素の順序付けられた組み合わせを「サービス構成」という。サービスにおいては、サーバ間に順序関係が存在するため、サービス構成は、サービスの構成要素の順序付けられた組み合わせとなる。サービスの変更とは、サービス構成を変更することをいう。サービスの廃止とは、仮想化ネットワーク上において当該サービスに割り当てられたリソースを解放することをいう。
【００１６】
本実施の形態において、「実行制約（処理完了期限制約・実行順序制約）を満たすためのオーダーの順序入れ替え」のそれぞれは、以下の方法で実現される。
【００１７】
処理完了期限制約の充足については、オーダーを依頼するシステム（後述のオーダー依頼装置２０）が、オーダーに希望処理完了時刻を付与する。さらに、「各オーダーにおける希望処理完了時刻と推定処理完了時刻との差」の合計値が最大になるように（すなわち、各オーダーの推定処理完了時刻について希望処理完了時刻に対する遅延について、待機中の全オーダーにおける合計が最小となるように）、待機中のオーダーの実行順序を入れ替えることで対応する。
【００１８】
実行順序制約の充足については、実行順序逆転（オーダーの受付順番の逆転）を許さないオーダー群については、同一の処理ラベルをオーダーに付与し、同一の処理ラベルが付与されたオーダー群は順序を入れ替えないように（受付順番が維持されるように）することで対応する。
【００１９】
「冗長なオーダーの結合」については、待機中の同一サービスに対するオーダーが複数存在する場合には、各オーダーの内容が反映されるように、オーダーを１つに結合することで対応する。なお、オーダーの結合により、結合前に比べて結合されたオーダー群全体の処理時間の削減が期待される。削減された処理時間を他のオーダーに対する処理に割り当てることができるため、処理完了期限制約が満たされる可能性を高めることができる。
【００２０】
図１は、本発明の実施の形態におけるオーダー管理システムの構成例を示す図である。図１において、オーダー管理システムは、オーダー依頼装置２０、オーダー管理装置１０及び制御装置３０を含む。
【００２１】
オーダー依頼装置２０は、オーダーを依頼する１以上のコンピュータである。オーダー管理装置１０は、オーダー依頼装置２０から依頼されたオーダーを受け付け、当該オーダーを制御装置３０へ送信する１以上のコンピュータである。制御装置３０は、オーダーを実行する１以上のコンピュータである。例えば、オーケストレータやコントローラ等が制御装置３０として用いられてもよい。なお、オーダー依頼装置２０、オーダー管理装置１０及び制御装置３０は、共通のコンピュータを用いて実現されてもよい。
【００２２】
図２は、本発明の実施の形態におけるオーダー管理装置１０のハードウェア構成例を示す図である。図２のオーダー管理装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００２３】
オーダー管理装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２４】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってオーダー管理装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２５】
図３は、本発明の実施の形態におけるオーダー管理装置１０の機能構成例を示す図である。図３において、オーダー管理装置１０は、オーダー受付部１１、処理時間推定部１２、キュー管理部１３及びオーダー送信部１４等を有する。これら各部は、オーダー管理装置１０にインストールされた１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。但し、各部は、複数のコンピュータに分散されてもよい。オーダー管理装置１０は、また、処理時間記憶部１５及びキュー１６を利用する。処理時間記憶部１５及びキュー１６等の記憶部は、例えば、補助記憶装置１０２又はメモリ装置１０３等を用いて実現可能である。
【００２６】
オーダー受付部１１は、オーダー依頼装置２０よりオーダーを順番に受け付ける（受信する）。処理時間推定部１２は、オーダーの内容に基づいて、処理時間を推定する。処理時間推定部１２は、推定した処理時間が付与されたオーダーを、オーダー受付部１１が受け付けた順番でキュー１６に登録する。処理時間記憶部１５は、過去に処理したオーダーの内容と処理時間とを対応付けて記憶する。キュー１６には、実行待ちのオーダーが蓄積される。キュー管理部１３は、キュー１６内のオーダー実行順序の決定やオーダー結合を行う。オーダー送信部１４は、キュー１６内のオーダーを抽出し、抽出したオーダーを制御装置３０に送信する。
【００２７】
以下、オーダー管理システムにおいて実行される処理手順について説明する。図４は、オーダー管理システムにおいて実行される処理手順の一例を示す図である。図４の処理手順は、オーダー受付処理、処理時間傾向学習処理、オーダー操作処理、及びオーダー割当処理の４つの処理を含む。以下、各処理を順番に説明する。
【００２８】
［オーダー受付処理］
オーダー依頼装置２０にて、新規にオーダー（以下、「対象オーダー」という。）が生成されると、オーダー依頼装置２０は、希望処理完了時刻を対象オーダーに付与し（Ｓ１０１）、対象オーダーをオーダー管理装置１０へ送信する（Ｓ１０２）。
【００２９】
図５は、オーダーの内容の一例を示す図である。図５に示されるように、本実施の形態において、オーダーは、オーダーＩＤ、オーダー種別、処理ラベル、対象サービス、希望処理完了時刻、推定処理時間、及びサービス構成等の項目を含む。
【００３０】
オーダーＩＤは、オーダーごとの識別情報である。図５において、［］で囲まれている文字列（「オーダー４」）が、オーダーＩＤである。オーダー種別は、オーダーの種別である。本実施の形態において、オーダー種別は、「新規開通」、「サービス変更」又は「サービス廃止」のいずれかである。処理ラベルは、受付順番に対して実行順序の逆転が許容されないオーダー群を識別するための項目である。この時点では、処理ラベルはオーダーに付与されないため、図５において、処理ラベルの値は空となっている。希望処理完了時刻は、オーダーの依頼者が希望する、オーダーに対応する処理の完了時刻である。推定処理時間は、オーダーに対応する処理の所要時間の推定値である。この時点では、推定処理時間は計算されていないため、図５において、推定処理時間の値は空となっている。サービス構成は、対象サービスのサービス構成である。図５の例では、ファイアウォール（ＦＷ）、ロードバランサ（ＬＢ）、及びＷｅｂサーバ（ＷｅｂＳｅｒｖｅｒ）によって対象サービスが構成されることが示されている。すなわち、図５のオーダーは、このようなサービス構成を有するサービスの新規開通を要求するオーダーである。
【００３１】
オーダー管理装置１０のオーダー受付部１１は、対象オーダーを受信すると、予めオーダー受付部１１に設定されている処理ラベルの付与ルールに基づいて、対象オーダーに処理ラベルを付与し（Ｓ１０３）、対象オーダーを処理時間推定部１２に転送する（Ｓ１０４）。処理ラベルは、実行順序の逆転が許容されないオーダー群を識別するための項目である。したがって、処理ラベルは、実行順序逆転を許さないオーダー群を識別可能な識別情報であれば、文字列でも数値でも構わない。本実施の形態では、実行順序の逆転を許さないオーダー群に対して同一の識別情報が処理ラベルとして付与される付与ルールが採用される。例えば、同一サービスに対するオーダーについては、実行順序の逆転が許容できないケースが多いので、サービス毎に処理ラベルを予め固定的に決められてもよい。この場合、オーダー受付部１１は、対象オーダーの対象サービスに対応する付与ラベルを対象オーダーに付与する。また、複数のサービス間でも、オーダーの実行順序逆転が許容できないものについては、複数のサービス間で同一の処理ラベルを与えるような付与ルールが設定されてもよい。
【００３２】
図６は、処理ラベルが付与されたオーダーの例を示す図である。図６では、「サービスＡ」に対応する処理ラベルが「２」である付与ルールが設定されている例が示されている。したがって、図６に示されているオーダーには、処理ラベルとして「２」が付与されている。
【００３３】
続いて、処理時間推定部１２は、後述する処理時間傾向学習処理における学習結果に基づいて、推定処理時間を対象オーダーに付与する（Ｓ１０５）。続いて、処理時間推定部１２が、対象オーダーをキュー１６に送信すると（Ｓ１０６）、対象オーダーがキュー１６に格納される（Ｓ１０７）。
【００３４】
［処理時間傾向学習処理］
処理時間推定部１２は、一定時間毎に処理時間記憶部１５より、過去の各オーダーの内容と処理時間とを取得し（Ｓ１１１）、処理内容と処理時間の傾向を学習する（Ｓ１１２）。そうすることで、オーダー受付処理におけるステップＳ１０５において、リアルタイムな処理時間の推定が可能となる。
【００３５】
図７は、処理時間の傾向の学習の例を説明するための図である。例えば、処理時間推定部１２は、処理時間記憶部１５に記憶されている過去の各オーダーを、サービス種別及びサービス構成の共通性に基づいてグルーピング（分類）する。すなわち、サービス種別及びサービス構成が同じオーダー群が同じグループに分類される。本実施の形態では、サービス種別及びサービス構成が共通するオーダー群については、処理時間が類似する傾向が高いと考えられるからである。
【００３６】
処理時間推定部１２は、グループごとに、当該グループに属する各オーダーの処理時間の平均値を計算する。すなわち、既に実行された過去のオーダーには、推定処理時間ではなく処理時間（の実績値）が記録されている。図７では、サービス種別が「新規開通」であり、サービス構成が「ＦＷ−ＬＢ―ＷｅｂＳｅｒｖｅｒ」であるグループには、過去オーダー１及び過去オーダー２が属し、それぞれの処理時間が、３２秒、２８秒である例が示されている。処理時間推定部１２は、これらの過去のオーダーの平均を当該グループの推定処理時間として計算しておく。ステップＳ１０５において、処理時間推定部１２は、対象オーダーが属するグループに対して計算されている推定処理時間を対象オーダーに付与する。
【００３７】
なお、上記以外の方法で、対象オーダーと類似したオーダーが特定されてもよい。例えば、類似したオーダーのグルーピングや、類似グループごとの処理時間の傾向は、機械学習や深層学習などを用いることで、効率的かつ自動的に学習することが可能である。
【００３８】
［オーダー操作処理］
キュー管理部１３は、一定時間毎に、キュー１６内の全オーダーを取得する（Ｓ１２１）。続いて、キュー管理部１３は、取得した各オーダーの内容に基づいて冗長なオーダー群を特定し、当該オーダー群を結合する（Ｓ１２２）。冗長なオーダー群とは、例えば、一部の処理が共通する（重複する）オーダー群をいう。本実施の形態では、処理ラベル及びサービス種別が同じであるオーダー群が冗長なオーダー群とされる例について説明する。
【００３９】
図８は、オーダー結合の例を説明するための図である。図８では、オーダー９、オーダー６、及びオーダー４等が、キュー１６内に蓄積されているオーダー群の一部である例が示されている。オーダー９、オーダー６、及びオーダー４のそれぞれの処理ラベルは「２」であり、対象サービスは「サービスＢ」である。したがって、本実施の形態では、オーダー９、オーダー６、及びオーダー４が冗長なオーダー群に相当する。なお、このうちの１つは、新規開通オーダーであり、２つは、サービス変更オーダーである。
【００４０】
キュー管理部１３は、これら各オーダーの内容が反映されるように、３つのオーダーを１つのオーダー（オーダー４＋６＋９）に結合する。この際、キュー管理部１３は、結合されたオーダー（以下、「結合オーダー」という。）のオーダー種別を、３つの中で先頭のオーダー（オーダー４）のオーダー種別である「新規開通」とし、サービス構成を、３つの中で末尾のオーダー（オーダー９）のサービス構成とする。キュー管理部１３は、また、結合オーダーの処理ラベルには、処理ラベルは、結合前の各オーダー共通の値を設定し、結合オーダーの希望処理完了時刻には、結合前の各オーダーの希望処理完了時刻のうち最も早い時刻を設定し、結合オーダーの推定処理時間には、結合前の各オーダーの推定処理時間の合計を設定する。但し、結合オーダーの推定処理時間は、結合オーダーの内容に基づいて処理時間推定部１２が再度推定し直してもよい。また、キュー管理部１３は、結合オーダーの実行順序（キュー１６内の位置）を、結合前のオーダーのうち、最も早い実行順序（オーダー４の位置）とする。
【００４１】
続いて、キュー管理部１３は、キュー１６から取得した全オーダーについて実行順序を決定する（Ｓ１２３）。
【００４２】
具体的には、キュー管理部１３は、キュー１６から取得した各オーダー（但し、結合オーダーは、１つのオーダーとして扱われる）の希望処理完了時刻と推定処理完了時刻との差分の合計値Ｅが最大になるように（すなわち、各オーダーの推定処理完了時刻について希望処理完了時刻に対する遅延について、待機中の全オーダーにおける合計が最小となるように）、実行順序の組み合わせを、同一処理ラベルが付与されたオーダー群内において実行順序の逆転が発生しないように探索する。Ｅは、式（１）で定義される。
【００４３】
【数１】
2020080119.tif 000003
ここで、Ｒは、キュー１６内のオーダーの個数を示す変数、ｒは、キュー１６内のオーダーの実行順序を示す変数（ｒ≧０、ｒ＝０は制御装置３０で実行中を示す）である。Ｅｒは、ｒ番目のオーダーの希望処理完了時刻と推定処理完了時刻との差を示しており、式（２）で定義される。
【００４４】
【数２】
2020080119.tif 000004
ここで、Ｏｒｄｅｒ（ｒ）は、実行順序ｒのオーダーを返す関数、ＲｅｑｕｅｓｔｅｄＴｉｍｅ（ｏ）は、オーダーｏの希望完了時刻（オーダーに付与されている値）を返す関数、Ｔｒは、実行順序ｒのオーダーの推定処理完了時刻である。希望処理完了時刻より推定処理完了時刻が早い（希望が満たされている）場合は、評価値が０とされる。一方、希望完了時刻より推定処理完了時刻が遅い（希望が満たされていない）場合は、遅れた時間を負の評価値として設定する。Ｔｒは、式（３）で定義する。
【００４５】
【数３】
2020080119.tif 000005
ここで、ＢｅｇｉｎＴｉｍｅ（ｏ）は、オーダーｏの処理開始時刻を返す関数、ＥｓｔｉｍａｔｉｏｎＴｉｍｅ（ｏ）は、オーダーｏの推定処理時間（オーダーに付与されている値）を返す関数、ＣｕｒｒｅｎｔＴｉｍｅ（）、は現時刻を返す関数である。Ｔ０は、現在の実行中のオーダーの実行完了時刻を示し、Ｔｒ（ｒ≧１）は、一つ前の実行順序ｒ−１のオーダーの推定実行時間Ｔｒ−１に、実行順序ｒのオーダーの推定処理時間を加算することで計算している。
【００４６】
図９は、オーダー実行順序の決定の例を説明するための図である。図９では、オーダーａが実行中で、キュー１６内にｂ、ｃ、ｄ、ｅのオーダーが待機している例が示されている。現時刻は、９：１０：００であり、各オーダーの条件は、図中に記載されている通りである。
【００４７】
実行順序の決定にて、同一処理ラベルのオーダーの順序の入れ替えを制限（図９の例では、ｂ⇒ｄとｃ⇒ｅの順序入れ替えを制限）すると、オーダーの実行順序の組み合わせパターンは、全６パターンである。図中には、それぞれのパターンにおいて推定処理完了時刻Ｔｒと、評価値Ｅとが示されている。図９の場合、キュー管理部１３は、全パターンを比較した結果、評価値Ｅが最大値となるパターン６を実行順序として決定する。ここでは、実行順序の組み合わせを列挙する例を示したが、キュー１６内のオーダー数が多い場合はパターン数が多くなるため、数理最適化のメタヒューリスティクスな解の探索方法（局所探索法、貪欲法、ＧＡなど）を用いることで、短時間な探索も可能である。
【００４８】
続いて、キュー管理部１３は、オーダーの結合結果及び実行順序の決定結果をキュー１６に反映させるべく、キュー１６内のオーダーを操作する（Ｓ１２４）。その結果、キュー１６内におけるオーダーの順番等が入れ替わる（Ｓ１２５）。
【００４９】
［オーダー割当処理］
制御装置３０は、オーダーの処理が完了すると、処理結果をオーダー依頼装置２０へ送信し（Ｓ１３１）、当該オーダーの内容及び当該オーダーの処理時間を処理時間記憶部１５へ送信する（Ｓ１３２）。その結果、当該内容及び当該処理時間が対応付けられて処理時間記憶部１５に記憶される（Ｓ１３３）。続いて、制御装置３０は、処理完了通知をオーダー送信部１４へ送信する（Ｓ１３４）。オーダー送信部１４は、処理完了通知の受信に応じ、キュー１６の先頭にあるオーダーを取得し、当該オーダーを制御装置３０へ送信する。当該オーダーについて処理が完了すると、ステップＳ１３１以降が繰り返される。
【００５０】
なお、制御装置３０は、処理が完了したオーダーが結合オーダーである場合、ステップＳ１３１において、結合前のオーダーごと（図８の例では、オーダー４、６、９ごと）にオーダー依頼装置２０へ処理結果を送信し、ステップＳ１３３において、結合前のオーダーごとに処理完了通知を送信する。
【００５１】
上述したように、本実施の形態によれば、処理要求（オーダー）に対する制約が満たされる可能性を高めることができる。
【００５２】
なお、本実施の形態では、仮想化ネットワーク上におけるサービスに関するオーダーを処理要求の一例として説明したが、希望処理完了時刻が指定される他の処理要求について本実施の形態が適用されてもよい。例えば、スーパーコンピュータ等の高性能な計算機に対する各ジョブの実行要求について、本実施の形態が適用されてもよい。
【００５３】
なお、本実施の形態において、オーダー管理装置１０は、処理要求管理装置の一例である。処理時間推定部１２は、推定部の一例である。キュー管理部１３は、決定部及び結合部の一例である。オーダー受付部１１は、受付部の一例である。
【００５４】
以上、本発明の実施の形態について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５５】
１０          オーダー管理装置
１１          オーダー受付部
１２          処理時間推定部
１３          キュー管理部
１４          オーダー送信部
１５          処理時間記憶部
１６          キュー
２０          オーダー依頼装置
３０          制御装置
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
2020080119.tif 000006
【図２】
2020080119.tif 000007
【図３】
2020080119.tif 000008
【図４】
2020080119.tif 000009
【図５】
2020080119.tif 000010
【図６】
2020080119.tif 000011
【図７】
2020080119.tif 000012
【図８】
2020080119.tif 000013
【図９】
2020080119.tif 000014