JP7177349B2 - スケジュールプログラム、スケジュール装置およびスケジュール方法 - Google Patents

Description

本発明はスケジュールプログラム、スケジュール装置およびスケジュール方法に関する。

情報処理の分野では、物理的なコンピュータ（物理マシンや物理ホストと呼ぶことがある）上で、複数の仮想的なコンピュータ（仮想マシンや仮想ホストと呼ぶことがある）を動作させる仮想化技術が利用されている。各仮想マシン上では、ＯＳ（Operating System）などのソフトウェアを実行できる。仮想化技術を利用する物理マシンは、複数の仮想マシンを管理するためのソフトウェアを実行する。例えば、ハイパーバイザと呼ばれるソフトウェアが、ＣＰＵ（Central Processing Unit）の処理能力やＲＡＭ（Random Access Memory）の記憶領域を、演算のリソースとして複数の仮想マシンに割り振ることがある。

複数の物理マシンを含むシステムでは、ある物理マシンで実行される仮想マシンを別の物理マシンに移動することがある。こうした仮想マシンの移動は、マイグレーションと呼ばれることがある。例えば、一つの物理的コンピュータシステムから別の物理的コンピュータシステムへの仮想マシンの有意な中断なしでのマイグレーションは、ライブマイグレーション（ＬＭ：Live Migration）と呼ばれる。

なお、運用上考慮すべき全ての制約を満足し、かつ、運用コストの安価な実際的な運用計画を自動的に迅速に作成する電力系統の需給計画作成装置が提案されている。

特開２０１１－８７８０号公報 特開平１１－２１５７０２号公報

複数の利用者に仮想マシンの利用環境を提供する情報処理システムが利用されている。当該システムでは、物理マシンのメンテナンスが生じ得る。メンテナンスの際、物理マシンの再起動などを伴うことがあるため、運用者は、事前に、メンテナンスを行う物理マシン上の仮想マシンを別の物理マシンに移動させることがある。ただし、移動処理は、該当の仮想マシンの性能低下や、該当の仮想マシンの一時的な利用中断を招くことがある。そこで、運用者は、メンテナンス日程やそれに伴う仮想マシンの移動スケジュールを作成し、利用者に事前に通知することがある。例えば、移動スケジュールは、物理マシンの性能、物理マシン上の仮想マシンの配置状況、仮想マシンの所要性能、各利用者による仮想マシンの利用予定などの各種制約に応じて決定され得る。

一方、実際の運用では、利用者による仮想マシンの利用予定の変化などに応じて、当初の移動スケジュールに対して変更の要望が発生することがある。ところが、仮想マシンの移動予定の変更は、他の利用者が利用する仮想マシンの決定済の移動予定に影響を及ぼし得る。このため、当初の移動スケジュールを変更することは容易ではない。

例えば、変更対象外の仮想マシンに関する決定済の移動予定に関する制約を満たしつつ、変更対象の仮想マシンに対して変更希望の時間帯を満たすように、移動予定の候補となる時間帯を総当りで探索することで、スケジュール調整することも考えられる。しかし、システムに含まれる物理マシンや仮想マシンの数が多く、移動スケジュールの変更対象の仮想マシンの数が多い程、検討対象となる時間帯の組合せが増し、スケジュール調整に時間がかかってしまう。また、全ての制約を満たす変更後の移動予定が存在する保証はなく、全ての制約を満たす変更後の移動予定を決定できないこともある。

１つの側面では、本発明は、仮想マシンの既存の移動予定への影響を抑えた再スケジューリングを可能にするスケジュールプログラム、スケジュール装置およびスケジュール方法を提供することを目的とする。

１つの態様では、スケジュールプログラムが提供される。スケジュールプログラムは、コンピュータに、複数の物理マシンの間での複数の仮想マシンの移動の時間帯を示す既存スケジュールに対して、仮想マシンの移動の時間帯の変更に関する変更情報を取得し、変更情報と既存スケジュールにおける当該仮想マシン以外の、変更の対象外である他の仮想マシンの移動の時間帯とに応じた制約群を含む制約情報を生成し、制約情報のうち、当該制約群に含まれる制約を１つずつ除外した複数の準制約情報を生成し、生成した複数の準制約情報それぞれに基づいて、複数の仮想マシンの移動の再スケジューリングを行うことで、準制約情報毎に再スケジューリング結果を生成し、複数の再スケジューリング結果のうち、再スケジューリング結果および既存スケジュールにおける上記変更の対象外である他の仮想マシンの移動の予定時刻の差が小さくなる再スケジューリング結果を出力する、処理を実行させる。

また、１つの態様では、スケジュール装置が提供される。
また、１つの態様では、スケジュール方法が提供される。

１つの側面では、仮想マシンの既存の移動予定への影響を抑えた再スケジューリングが可能になる。

第１の実施の形態の情報処理システムの例を示す図である。 第２の実施の形態の情報処理システムの例を示す図である。 管理サーバのハードウェア例を示すブロック図である。 ライブマイグレーションの例を示す図である。 管理サーバの機能例を示す図である。 制約集合に対する極小充足不能コアの例を示す図である。 メンテナンス実施期間情報の例を示す図である。 メンテナンス対象マシン情報の例を示す図である。 物理マシン構成テーブルの例を示す図である。 仮想マシン構成テーブルの例を示す図である。 仮想マシン稼働テーブルの例を示す図である。 依存関係テーブルの例を示す図である。 極小充足不能コア情報の例を示す図である。 優先度テーブルの例を示す図である。 優先度の決定例を示す図である。 メンテナンススケジュールテーブル（変更前）の例を示す図である。 ＬＭスケジュールテーブル（変更前）の例を示す図である。 ＬＭ実施日時変更要望情報の例を示す図である。 変更後のスケジュールテーブルの例を示す図である。 制約充足問題における変数の例を示す図である。 変数によるＬＭの表現の例を示す図である。 管理サーバの処理例を示すフローチャートである。 日程再調整例を示すフローチャートである。 制約充足問題の生成例を示すフローチャートである。 日程変更例を示すフローチャートである。 日程変更例（続き）を示すフローチャートである。 入力データの例（その１）を示す図である。 入力データの例（その２）を示す図である。 入力データの例（その３）を示す図である。 入力データの例（その４）を示す図である。 入力データの例（その５）を示す図である。 入力データの例（その６）を示す図である。 出力データの例（その１）を示す図である。 出力データの例（その２）を示す図である。 ＬＭスケジュールの表示画面の例を示す図である。 ＬＭスケジュールの変更入力画面の例を示す図である。 ＬＭスケジュールの変更の結果表示画面の例を示す図である。 メンテナンススケジュール画面の例を示す図である。

以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。

図１は、第１の実施の形態の情報処理システムの例を示す図である。
第１の実施の形態の情報処理システムは、スケジュール装置１０および物理マシン２０，３０，４０，…を有する。スケジュール装置１０および物理マシン２０，３０，４０，…はネットワークＮ１に接続されている。スケジュール装置１０は、物理マシン２０，３０，４０，…における仮想マシンの移動スケジュールを調整する。

物理マシン２０，３０，４０，…それぞれは、ＣＰＵやメモリなどの演算リソースを有し、演算リソースを用いて仮想マシンを実行する。例えば、物理マシン２０，３０，４０，…それぞれは、ハイパーバイザを実行し、ハイパーバイザの機能により、仮想マシンに対する演算リソースの割り当てを行う。例えば、物理マシン２０は、仮想マシン２１を実行する。物理マシン３０は、仮想マシン３１を実行する。物理マシン４０は、仮想マシン４１を実行する。物理マシン２０，３０，４０，…それぞれは、２以上の仮想マシンを実行してもよい。なお、「仮想マシン」を「ＶＭ」（Virtual Machine）と略記することがある。また、仮想マシン２１を識別するための名称（ＶＭ名）を「ｖ_ｘ」とする。仮想マシン３１のＶＭ名を「ｖ_ｙ」とする。仮想マシン４１のＶＭ名を「ｖ_ｚ」とする。

ネットワークＮ１には、端末装置５０も接続されている。端末装置５０は、仮想マシンを利用する利用者Ｕ１によって利用されるクライアントである。端末装置５０は、インターネットなどの他のネットワークを介してネットワークＮ１に接続されてもよい。

物理マシン２０，３０，４０，…は、自物理マシンで動作する仮想マシンを他の物理マシンに移動させる機能を有する。例えば、物理マシン２０，３０，４０，…はライブマイグレーションと呼ばれる技術を用いて仮想マシンの移動を行う。ライブマイグレーションでは、移動対象の仮想マシンに割り当てられた移動元の物理マシンのＣＰＵリソースやメモリリソースの情報を移動先の物理マシンにコピーすることで、仮想マシンの起動状態を保ったまま仮想マシンを移動させる。あるいは、仮想マシンを移動させる技術として、仮想マシンを停止してから該当の仮想マシンの情報を移動先の物理マシンにコピーするコールドマイグレーションを用いることもできる。

システムの運用では、仮想マシンを実現するための基板（インフラ（infrastructure））である物理マシンに対するセキュリティパッチの適用やＯＳのアップグレードなどのメンテナンスが行われることがある。物理マシンのメンテナンスには、物理マシンの停止を伴うことがある。物理マシンを停止させる場合、当該物理マシン上の仮想マシンも停止させることになり、仮想マシンを利用できなくなってしまう。

そこで、物理マシンのメンテナンスの前に、メンテナンス対象の物理マシン上の仮想マシンを、物理マシン２０，３０，４０，…のうちの別の仮想マシンに移動させてから、メンテナンス対象の物理マシンのメンテナンスを行うことがある。これにより、利用者の仮想マシン利用に対する、メンテナンスによる影響を軽減し得る。スケジュール装置１０は、そのための仮想マシンの移動スケジュールの作成を支援する。

例えば、スケジュール装置１０は、物理マシンの性能、物理マシン上の仮想マシンの配置状況、仮想マシンの所要性能、各利用者による仮想マシンの利用予定などの各種制約（制約条件）に応じて、移動スケジュールを作成し、保持する。ただし、当初作成された移動スケジュールを利用者の仮想マシンの利用予定などに応じて変更したいこともある。そこで、スケジュール装置１０は、当初作成された移動スケジュールの変更（再スケジューリング）を支援する。

スケジュール装置１０は、記憶部１１および処理部１２を有する。
記憶部１１は、ＲＡＭなどの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。処理部１２は、ＣＰＵ、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などを含み得る。処理部１２はプログラムを実行するプロセッサでもよい。プロセッサは、複数のプロセッサの集合（マルチプロセッサ）も含み得る。

記憶部１１は、既存スケジュール６１を記憶する。既存スケジュール６１は、物理マシン２０，３０，４０，…のメンテナンスに伴う仮想マシン２１，３１，４１，…の、作成済みの移動スケジュールを示す情報である。既存スケジュール６１は、複数の物理マシンの間での複数の仮想マシンの移動の時間帯を示す。なお、既存スケジュール６１は、現在以降に予定されている未実行の移動スケジュールであり、実行済の移動スケジュールを含まない。

例えば、既存スケジュール６１には、仮想マシン２１，３１，４１，…のうち、ＶＭ名が「ｖ_ｘ」の仮想マシン２１、「ｖ_ｙ」の仮想マシン３１、「ｖ_ｚ」の仮想マシン４１に対する移動予定時間帯が登録されている。既存スケジュール６１には、それ以外の仮想マシンに対する移動予定時間帯も登録されるが、それ以外の仮想マシンについては「…」と略記している。仮想マシン２１の移動予定時間帯は、「ｔ_１～ｔ_２」（時刻ｔ_１～時刻ｔ_２の間の時間帯）である。仮想マシン３１の移動予定時間帯は、「ｔ_３～ｔ_４」（時刻ｔ_３～時刻ｔ_４の間の時間帯）である。仮想マシン４１の移動予定時間帯は、「ｔ_５～ｔ_６」（時刻ｔ_５～時刻ｔ_６の間の時間帯）である。

処理部１２は、既存スケジュール６１に対して、ある仮想マシンの移動の時間帯の変更に関する変更情報６２を取得する。変更対象の仮想マシンは１つでもよいし複数でもよい。例えば、変更情報６２は、利用者Ｕ１による仮想マシン２１の利用予定の変化に応じて、利用者Ｕ１により端末装置５０に入力され、端末装置５０からスケジュール装置１０に入力される。

変更情報６２は、例えば、仮想マシン２１のＶＭ名「ｖ_ｘ」に対して、利用者Ｕ１が物理マシン間の移動を希望する時間帯（移動希望時間帯）を「ｔ_ａ～ｔ_ｂ」（時刻ｔ_ａ～ｔ_ｂの間の時間帯）とすることを示す。なお、変更情報６２は、移動希望時間帯に代えて、移動の回避を希望する時間帯（回避時間帯以外の時間帯での移動を希望していることを示す）を含んでもよい。端末装置５０は、入力された変更情報６２をスケジュール装置１０に送信する。スケジュール装置１０は、端末装置５０により送信された変更情報６２を受信することで、変更情報６２を取得する。あるいは、システム運用者によって、スケジュール装置１０に、変更情報６２が入力されてもよい。

処理部１２は、変更情報６２と既存スケジュール６１における変更対象の仮想マシン以外の他の仮想マシン（変更の対象外の他の仮想マシン）の移動の時間帯とに応じた制約群を含む制約情報７０を生成する。例えば、処理部１２は、変更情報６２に含まれる変更対象の仮想マシン２１の移動希望時間帯に関する制約ｃ１を生成する。制約ｃ１は、「ｔ_ａ≦ｌ_ｔ（ｖ_ｘ）≦ｔ_ｂ」と表される。ここで、変数ｌ_ｔ（ｖ）は、仮想マシンｖの移動実施開始時刻を表す。また、処理部１２は、既存スケジュール６１に含まれる、仮想マシン３１，４１，…それぞれの移動予定時間帯に関する制約ｃ２，ｃ３，…を生成する。例えば、制約ｃ２は、「ｌ_ｔ（ｖ_ｙ）＝ｔ_３」と表される。制約ｃ３は、「ｌ_ｔ（ｖ_ｚ）＝ｔ_５」と表される。

制約情報７０は、仮想マシンの移動の時間帯に応じた制約群（制約ｃ１，ｃ２，ｃ３，…）の他にも、既存スケジュール６１の作成時に用いられた他の制約（物理マシンの性能、物理マシン上の仮想マシンの現在の配置状況、仮想マシンの所要性能）を含み得る。また、制約情報７０は、変更対象の仮想マシン（例えば、仮想マシン２１）に対する既存スケジュール６１の移動予定時間帯に対する制約を含まない。

処理部１２は、制約情報７０のうち、仮想マシンの移動の時間帯に応じた制約群に含まれる制約を１つずつ除外した複数の準制約情報を生成する。例えば、処理部１２は、制約情報７０に基づいて、準制約情報７１，７２，７３，…を生成する。準制約情報７１は、制約情報７０のうち、制約ｃ１を除外したものである。準制約情報７２は、制約情報７０のうち、制約ｃ２を除外したものである。準制約情報７３は、制約情報７０のうち、制約ｃ３を除外したものである。同様に、処理部１２は、制約情報７０から、仮想マシンの移動の時間帯に応じた制約を１つずつ除外することで、他の準制約情報を生成する。

処理部１２は、生成した複数の準制約情報それぞれに基づいて、複数の仮想マシン（仮想マシン２１，３１，４１，…）の移動の再スケジューリングを行うことで、準制約情報毎に再スケジューリング結果の情報を生成する。例えば、処理部１２は、作成した準制約情報７１，７２，７３，…それぞれおよびメンテナンスを行う実施予定期間（現在よりも後の期間）の情報を制約充足判定ソルバに入力し、制約充足判定ソルバの機能により、再スケジューリング結果を作成する。再スケジューリング結果は、調整後のスケジュールを示す情報である。例えば、処理部１２は、制約充足判定ソルバとして、ＭＩＬＰ（Mixed Integer Linear Programming、混合整数線形計画法）ソルバやＳＡＴ（SATisfiability problem、充足可能性問題）ソルバなどを用いることができる。ここで、以下では、制約充足判定ソルバを、単にソルバと称することがある。処理部１２は、複数の準制約情報に対する複数の再スケジューリング結果を作成する（ソルバの機能により、１つの準制約情報から１つの再スケジューリング結果が作成される）。

処理部１２は、複数の再スケジューリング結果のうち、再スケジューリング結果および既存スケジュールにおける変更の対象外の他の仮想マシンの移動の予定時刻の差が小さくなる再スケジューリング結果を出力する。例えば、処理部１２は、再スケジューリング結果で示される仮想マシンの移動の予定時刻と、既存スケジュール６１で示される仮想マシンの移動の予定時刻との差を、制約を除外した仮想マシン毎に求める。ここで、仮想マシンの移動の予定時刻は、例えば、仮想マシンの移動の開始予定時刻、または、終了予定時刻である。時刻の差は、正の値として求められる。例えば、処理部１２は、仮想マシンの移動の予定時刻の差が最小になる再スケジューリング結果を選択する。

処理部１２は、選択した再スケジューリング結果を出力する。例えば、処理部１２は、再スケジューリング結果を端末装置５０に出力し、端末装置５０の表示装置に再スケジューリング結果を表示させることで、再スケジューリング結果を利用者Ｕ１に通知してもよい。あるいは、処理部１２は、スケジュール装置１０に接続された表示装置に再スケジューリング結果を表示させることで、再スケジューリング結果を運用者に通知してもよい。

これにより、仮想マシンの既存の移動予定への影響を抑えた再スケジューリングが可能になる。例えば、処理部１２は、制約情報７０を充足する解を取得できずに再スケジューリングを行えないこともある。一方、準制約情報に基づく充足可能問題をソルバで解くことで、制約情報７０では再スケジューリングを行えない場合でも、充足可能な解（すなわち、適切な再スケジューリング結果）を取得できる可能性を高められる。

ただし、準制約情報では、何れかの仮想マシンで、既存の移動予定時間帯に対する制約が除外されている。このため、準制約情報に基づいて得られた再スケジューリング結果では、変更対象外の仮想マシンについて、既存の移動予定時刻が変更されている可能性がある。そこで、処理部１２は、各準制約情報に対する再スケジューリング結果で示される移動予定時刻のうち、既存の移動予定時刻との差が小さくなる再スケジューリング結果を選択することで、変更対象外の仮想マシンの移動予定への影響を小さくできる。

なお、処理部１２は、準制約情報７１，７２，７３，…を生成する際、各仮想マシンの移動の時間帯についての極小充足不能コア（Minimal Unsatisfiable（UNSAT） Core）に属する制約を、制約情報７０からの除外対象として選択することが考えられる。

ここで、充足不能コア（UNSAT Core）は、与えられた制約充足問題が充足不能であるときの、当該制約充足問題の中に存在する充足不能な部分制約集合である。特に、極小充足不能コアは、局所性をもつ充足不能コアである。充足不能な制約充足問題について、極小充足不能コアの中のどれか１つの制約を取り除くと、充足不能な制約充足問題は充足可能な問題に変化する。極小充足不能コアの抽出には、次の文献に記載された手法を用いることができる。

（文献１）A.Nadel，“Boosting Minimal Unsatisfiable Core Extraction,” in Proc. FMCAD’10，pp.221-229，2010.
論理演算によって表現された制約集合の一例として、式（１）で表される制約ａ１，ａ２，ａ３を有する制約集合が考えられる。

ここで、ｐ，ｑ，ｒは論理変数であり、０または１の値をとる。制約ａ１は、ｐとｑとの排他的論理和である。制約ａ２は、ｐとｒの否定との論理和である。制約ａ３は、ｐとｑとの論理和の否定である。制約ａ１，ａ２，ａ３の全てを真にするｐ，ｑ，ｒの値の組み合わせは存在せず、当該制約集合は充足不能となる。この制約集合の極小充足不能コアは、制約ａ１，ａ３である。すなわち、制約ａ１，ａ２，ａ３を含む制約集合のうち制約ａ１、または、制約ａ３の何れか一方の制約を無効にすると、充足可能になる。

例えば、処理部１２は、まずは、制約情報７０に基づく制約充足問題をソルバにより解くことで再スケジューリングを試みてもよい。そして、処理部１２は、当該制約充足問題を充足する解を取得できた場合には、取得した解を再スケジューリング結果とする。一方、処理部１２は、制約情報７０に基づく制約充足問題が充足不能と判断された場合に、制約情報７０から仮想マシンの移動の時間帯に対する極小充足不能コアを抽出し、準制約情報７１，７２，７３，…を生成して、再スケジューリングを行ってもよい。

また、処理部１２は、極小充足不能コアに属する全ての制約を１つずつ除外して複数の準制約情報を生成してもよいし、極小充足不能コアに属する一部の制約を１つずつ除外して複数の準制約情報を生成してもよい。後者の方法では、前者の方法よりも再スケジューリングを高速化できる。後者の場合、一部の制約を抽出するために、仮想マシン毎の優先度を用いてもよい。例えば、仮想マシンの利用期間や利用料金に応じて仮想マシン毎の優先度を決め、優先度が低い仮想マシンに関する制約を優先的に除外対象とすることも考えられる。例えば、利用期間が長い、または、利用頻度が高い仮想マシンの優先度を上げ、制約の除外対象になる可能性を小さくすることで、利用者による仮想マシンの利用に対する影響を低減できる。

また、上記ソルバに入力される物理マシンに関するメンテナンスの実施予定期間は、メンテナンス対象の物理マシンに対してメンテナンスを行う候補の期間ということもできる。例えば、処理部１２は、物理マシン毎のメンテナンスの所要時間の情報（記憶部１１に予め格納される）に基づいて、物理マシン毎のメンテナンス実施期間に関する制約を更に作成してもよい。処理部１２は、当該制約に基づいて、仮想マシンの移動の再スケジューリングと共に、当該候補期間のうち物理マシン毎のメンテナンスを行う期間を、ソルバにより決定してもよい。この場合、処理部１２は、メンテナンス対象の物理マシン上の仮想マシンを、当該物理マシンのメンテナンスを行う期間よりも前に、他の物理マシンに移動させるように、再スケジューリングを行う。

また、処理部１２は、複数の再スケジューリング結果のうちの１つを出力する際、変更対象外の仮想マシンの移動の新規予定時刻と既存予定時刻との差以外にも、変更対象の仮想マシンの移動の希望時間帯と新規予定時間帯との差を考慮してもよい。ここで、希望時間帯Ｔ_１～Ｔ_２（Ｔ_１＜Ｔ_２）と新規予定時間帯Ｔ_３～Ｔ_４（Ｔ_３＜Ｔ_４）との差ΔＴは、例えば、次のように表される。Ｔ_１≦Ｔ_３＜Ｔ_２かつＴ_１＜Ｔ_４≦Ｔ_２の場合、ΔＴ＝０である。Ｔ_３＜Ｔ_１かつＴ_４≦Ｔ_２の場合、ΔＴ＝Ｔ_１－Ｔ_３である。Ｔ_１≦Ｔ_３かつＴ_２＜Ｔ_４の場合、ΔＴ＝Ｔ_４－Ｔ_２である。Ｔ_３＜Ｔ_１かつＴ_２＜Ｔ_４の場合、ΔＴ＝（Ｔ_１－Ｔ_３）＋（Ｔ_４－Ｔ_２）である。

例えば、処理部１２は、複数の再スケジューリング結果のうち、再スケジューリング結果および既存スケジュール６１における仮想マシン３１，４１，…の移動予定時刻の第１の差、または、変更情報６２および再スケジューリング結果における仮想マシン２１の移動の時間帯の第２の差が小さくなる再スケジューリング結果を出力することも考えられる。一例として、処理部１２は、第１の差または第２の差の何れかが最小になる再スケジューリング結果を選択し、選択した再スケジューリング結果を出力してもよい。あるいは、他の例として、処理部１２は、第１の差と第２の差との合計が最小になる再スケジューリング結果を選択してもよい。これにより、変更対象の仮想マシンに対する移動希望の時間帯での移動可能性を向上しつつ、それ以外の仮想マシンの既存の移動予定時間帯への影響を小さくすることができる。

［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、第２の実施の形態の情報処理システムの例を示す図である。

第２の実施の形態の情報処理システムは、管理サーバ１００および物理マシン２００，３００，４００，…を有する。管理サーバ１００および物理マシン２００，３００，４００，…は、ネットワーク８１に接続されている。ネットワーク８１は、例えば、ＬＡＮ（Local Area Network）である。ネットワーク８１は、ネットワーク８２に接続されている。ネットワーク８２は、ネットワーク８１の外部のネットワークであり、例えば、インターネットやＷＡＮ（Wide Area Network）などである。ネットワーク８２には、利用者端末５００，６００が接続されている。また、ネットワーク８１には、運用者端末７００が接続されている。

ここで、第２の実施の形態の情報処理システムは、クラウドコンピューティングサービスと呼ばれるサービスを提供する。クラウドコンピューティングサービスでは、システムの運用者は、システム上のハードウェア資源をネットワーク経由で複数の利用者（テナント）に提供する。システムの利用者は、提供されるハードウェア資源を用いて、仮想マシンを構築し、当該仮想マシン上で種々の業務アプリケーションを利用する。

第２の実施の形態の情報処理システムでは、サービスの品質を維持するために、インフラ（クラウド基盤）側のメンテナンス（例えば、物理マシン２００，３００，４００，…に対するセキュリティパッチの適用やＯＳのアップグレードなど）が行われる。そこで、物理マシンに対してメンテナンスを行う前に、該当の物理マシン上で動作中の仮想マシンを別の物理マシンに移動する処理が行われる。物理マシン上の仮想マシンを全て移動させた後に、該当の物理マシンのメンテナンスが行われる。第２の実施の形態の例では、仮想マシンの移動に、ライブマイグレーションの技術が利用される（ただし、仮想マシンの移動に、コールドマイグレーションを用いてもよい）。

管理サーバ１００は、物理マシン２００，３００，４００，…における仮想マシンのライブマイグレーションのスケジュールを管理するサーバコンピュータである。管理サーバ１００は、メンテナンス対象の物理マシンおよびメンテナンスの実施期間が入力されると、メンテナンス対象の物理マシン上で動作する仮想マシンのライブマイグレーションのスケジュールを作成する。管理サーバ１００は、作成したスケジュールを、利用者端末５００，６００や運用者端末７００に送信する。また、管理サーバ１００は、作成したスケジュールが確定されると、確定されたスケジュールに従って、メンテナンス対象の物理マシンに仮想マシンのライブマイグレーションを指示する。

また、管理サーバ１００は、利用者による仮想マシンの利用予定の変化などに応じて、当初作成されたスケジュールを変更する。管理サーバ１００は、スケジュールの変更を行った場合、変更後のスケジュールを、利用者端末５００，６００や運用者端末７００に送信する。また、管理サーバ１００は、変更後のスケジュールが確定されると、確定された変更後のスケジュールに従って、メンテナンス対象の物理マシンに仮想マシンのライブマイグレーションを指示する。管理サーバ１００は、第１の実施の形態のスケジュール装置１０の一例である。

物理マシン２００，３００，４００，…は、それぞれがＣＰＵやメモリなどの演算リソースを有し、演算リソースを用いて仮想マシンを実行するサーバコンピュータである。例えば、物理マシン２００，３００，４００，…それぞれは、ハイパーバイザを実行し、ハイパーバイザの機能により、仮想マシンに対する演算リソースの割り当てを行う。物理マシン２００，３００，４００，…は、第１の実施の形態の物理マシン２０，３０，４０，…の一例である。

利用者端末５００，６００は、利用者によって利用されるクライアントコンピュータである。利用者端末５００，６００は、異なる利用者によって利用される。各利用者は、利用者端末５００，６００を操作して、物理マシン２００，３００，４００，…上の仮想マシンを利用する。利用者端末５００の利用者は、利用者端末５００を用いて、管理サーバ１００により提供されるライブマイグレーション（自身が利用する仮想マシンについてのライブマイグレーション）のスケジュールを確認することもある。利用者端末６００の利用者も同様に、利用者端末６００を用いて、管理サーバ１００により提供されるライブマイグレーションのスケジュールを確認することもある。利用者端末５００，６００は、第１の実施の形態の端末装置５０の一例である。

運用者端末７００は、第２の実施の形態の情報処理システムの運用者（システム管理者）によって利用されるクライアントコンピュータである。運用者は、運用者端末７００を用いて、管理サーバ１００により提供される物理マシンのメンテナンスのスケジュールやメンテナンスに伴うライブマイグレーションのスケジュールを確認する。

図３は、管理サーバのハードウェア例を示すブロック図である。
管理サーバ１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６およびＮＩＣ（Network Interface Card）１０７を有する。なお、ＣＰＵ１０１は、第１の実施の形態の処理部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。

ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを含んでもよい。また、管理サーバ１００は複数のプロセッサを有してもよい。以下で説明する処理は複数のプロセッサまたはプロセッサコアを用いて並列に実行されてもよい。また、複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。

ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、管理サーバ１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。

ＨＤＤ１０３は、ＯＳやミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。なお、管理サーバ１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。

画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、管理サーバ１００に接続されたディスプレイ９１に画像を出力する。ディスプレイ９１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなど、任意の種類のディスプレイを用いることができる。

入力信号処理部１０５は、管理サーバ１００に接続された入力デバイス９２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス９２としては、マウス・タッチパネル・タッチパッド・トラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、管理サーバ１００に、複数の種類の入力デバイスが接続されていてもよい。

媒体リーダ１０６は、記録媒体９３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体９３として、例えば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。

媒体リーダ１０６は、例えば、記録媒体９３から読み取ったプログラムやデータを、ＲＡＭ１０２やＨＤＤ１０３などの他の記録媒体にコピーする。読み取られたプログラムは、例えば、ＣＰＵ１０１によって実行される。なお、記録媒体９３は可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体９３やＨＤＤ１０３を、コンピュータ読み取り可能な記録媒体と言うことがある。

ＮＩＣ１０７は、ネットワーク８１に接続され、ネットワーク８１を介して他のコンピュータと通信を行うインタフェースである。ＮＩＣ１０７は、例えば、ネットワーク８１に属するスイッチやルータなどの通信装置とケーブルで接続される。

物理マシン２００，３００，４００，…、利用者端末５００，６００および運用者端末７００も管理サーバ１００と同様のハードウェアを用いて実現できる。
図４は、ライブマイグレーションの例を示す図である。

物理マシン２００，３００，４００，…は、ライブマイグレーションにより、物理マシン間で仮想マシンを移動させる。例えば、物理マシン２００は、ハイパーバイザ２１０および仮想マシン２１１，２１２を有する。物理マシン３００は、ハイパーバイザ３１０および仮想マシン３１１を有する。ハイパーバイザ２１０は、物理マシン２００が備えるＣＰＵやメモリといったハードウェアのリソースを仮想マシン２１１，２１２に割り当てる。ハイパーバイザ３１０も同様に、物理マシン３００が備えるハードウェアのリソースを仮想マシン３１１に割り当てる。例えば、物理マシン２００から物理マシン３００に仮想マシン２１２を移動する場合を想定すると、ライブマイグレーションにより次のような手順を採ることが考えられる。

（１）物理マシン３００上で移動対象の仮想マシン２１２用のＣＰＵ／メモリリソースを予約する。（２）物理マシン２００で移動対象の仮想マシン２１２に割り当てられているメモリリソースのデータを、物理マシン３００で当該仮想マシン２１２用に新たに割り当てたメモリリソースにコピーする。（３）物理マシン２００から物理マシン３００へ仮想マシン２１２に割り当てていたＣＰＵリソースの状態をコピーし、物理マシン２００で仮想マシン２１２を停止させる。（４）物理マシン３００で仮想マシン２１２を再開し、物理マシン２００で仮想マシン２１２に割り当てていたリソースを解放する。これにより、物理マシン２００上で稼働している仮想マシン２１２を、物理マシン３００に移動させることができる。上記の手順はＰｒｅ－Ｃｏｐｙと呼ばれることもある。ただし、ライブマイグレーションにはＰｏｓｔ－Ｃｏｐｙなどの他の手順を用いてもよい。

ここで、以下の説明では、ライブマイグレーションを、ＬＭと略記することがある。
図５は、管理サーバの機能例を示す図である。
管理サーバ１００は、インフラ管理部１１０およびスケジューラ１２０を有する。インフラ管理部１１０およびスケジューラ１２０の機能は、ＣＰＵ１０１により実現される。例えば、ＣＰＵ１０１は、ＲＡＭ１０２に記憶されたスケジュールプログラムを実行することで、インフラ管理部１１０およびスケジューラ１２０の機能を発揮する。インフラ管理部１１０およびスケジューラ１２０は、ＦＰＧＡやＡＳＩＣなどのハードウェアにより実現されてもよい。

インフラ管理部１１０は、各物理マシンのハードウェアの構成や各仮想マシンに割り当てられるリソースの構成を管理する。インフラ管理部１１０は、インフラ構成情報記憶部１１１、ＶＭ性能情報記憶部１１２およびインフラ管理制御部１１３を有する。インフラ構成情報記憶部１１１およびＶＭ性能情報記憶部１１２は、例えば、ＲＡＭ１０２やＨＤＤ１０３の記憶領域を用いて実現される。

インフラ構成情報記憶部１１１は、インフラ構成情報を記憶する。インフラ構成情報は、各物理マシンのハードウェアの構成や各仮想マシンに割り当てられるリソースの構成に関する情報である。インフラ構成情報は、各仮想マシンのＬＭの所要時間に関する情報を含む。

ＶＭ性能情報記憶部１１２は、ＶＭ性能情報を記憶する。また、ＶＭ性能情報は、ＬＭの所要時間の予測結果を得るために用いられた各仮想マシンの負荷の履歴（過去の各時刻における各仮想マシンの負荷の履歴）などを含む。なお、各仮想マシンの負荷の履歴に基づくＬＭの所要時間の予測は、管理サーバ１００により行われてもよい。

インフラ管理制御部１１３は、スケジューラ１２０により決定されたＬＭのスケジュールに従って、各物理マシンに対する仮想マシンのＬＭを指示する。
スケジューラ１２０は、物理マシンのメンテナンスを行う際に、メンテナンス対象の物理マシンで動作する仮想マシンのＬＭのスケジュールを決定する。スケジューラ１２０は、メンテナンス実施期間やメンテナンス対象の物理マシンの情報を運用者端末７００から受け付けると、インフラ構成情報記憶部１１１（およびＶＭ性能情報記憶部１１２）に記憶された情報に基づいて、ＬＭのスケジュールを決定する。

また、スケジューラ１２０は、決定後のＬＭのスケジュールに対する変更を受け付けることもある。例えば、スケジューラ１２０は、利用者による仮想マシンの利用予定の変化に応じて、該当の仮想マシンに関して、当初決定されたスケジュールとは異なるＬＭの実行時間帯の要望を、利用者端末５００，６００から受け付ける。すると、スケジューラ１２０は、当初決定したＬＭのスケジュールを変更する。このスケジュール変更は、変更が要望された仮想マシン以外の他の仮想マシンのＬＭのスケジュールに影響を及ぼすこともある。

スケジューラ１２０は、制約条件記憶部１２１、ＶＭ優先度記憶部１２２、イベント情報記憶部１２３、制約条件生成部１２４、ソルバ部１２５、充足不能コア抽出部１２６、ＶＭ優先度設定部１２７およびスケジュール変更部１２８を有する。制約条件記憶部１２１、ＶＭ優先度記憶部１２２およびイベント情報記憶部１２３は、例えば、ＲＡＭ１０２やＨＤＤ１０３の記憶領域を用いて実現される。

制約条件記憶部１２１は、制約条件生成部１２４により生成された制約条件を記憶する。
ＶＭ優先度記憶部１２２は、仮想マシン毎の優先度を記憶する。仮想マシン毎の優先度は、再スケジューリングの際に除外対象とする制約条件を選択するために用いられる。

イベント情報記憶部１２３は、ソルバ部１２５により作成された各仮想マシンのＬＭのスケジュールの情報や各物理マシンのメンテナンスのスケジュールの情報を記憶する。イベント情報記憶部１２３は、スケジュール変更部１２８による各仮想マシンの変更後のＬＭのスケジュールおよび変更後の各物理マシンのメンテナンスのスケジュールの情報を記憶する。

制約条件生成部１２４は、インフラ構成情報記憶部１１１に記憶されたインフラ構成情報に基づいて、ＬＭのスケジュールの決定に対する制約条件を生成する。制約条件生成部１２４は、ＶＭ性能情報記憶部１１２に記憶されたＶＭ性能情報を更に用いて、ＬＭのスケジュールの決定に対する制約条件を生成してもよい。例えば、各仮想マシンについて、当該仮想マシンの負荷が低い時間帯を優先してＬＭを実施することを制約条件とすることが考えられる。制約条件生成部１２４は、生成した制約条件を制約条件記憶部１２１に格納する。

再スケジューリングの場合、制約条件生成部１２４は、利用者端末５００，６００から入力されたＬＭの実行時間帯の要望に関する制約条件も生成する。また、再スケジューリングの場合、制約条件生成部１２４は、イベント情報記憶部１２３に記憶された既存のスケジュールの情報に基づいて、当該既存のスケジュールに応じた制約条件も生成する。

ソルバ部１２５は、制約条件生成部１２４により生成された制約条件を満足するようにスケジューリングできるかを判定することで、ＬＭのスケジュールの作成を試行する。ソルバ部１２５は、生成された制約条件を最も良く満足するＬＭのスケジュールを、イベント情報記憶部１２３に格納する。ソルバ部１２５としては、ＭＩＬＰソルバやＳＡＴソルバなどを利用することができる。

再スケジューリングの場合も同様に、ソルバ部１２５は、制約条件生成部１２４により生成された制約条件を最も良く満足するＬＭのスケジュールを生成し、イベント情報記憶部１２３に格納する。再スケジューリングの際、ソルバ部１２５は、制約条件生成部１２４により生成された制約条件を全て満足するＬＭのスケジュールを生成できないこともある。

充足不能コア抽出部１２６は、再スケジューリングの際に、ソルバ部１２５がＬＭのスケジュールを生成できない場合、再スケジューリングに用いられた全制約条件のうちのＬＭの実行時間帯に関する制約条件から、極小充足不能コアを抽出する。充足不能コア抽出部１２６は、抽出した極小充足不能コアをスケジュール変更部１２８に提供する。

ＶＭ優先度設定部１２７は、仮想マシン毎の優先度を決定し、ＶＭ優先度記憶部１２２に格納する。例えば、ＶＭ優先度設定部１２７は、利用者による仮想マシンの利用状況に基づいて、仮想マシン毎の優先度を決定する。

スケジュール変更部１２８は、極小充足不能コアおよびＶＭ優先度記憶部１２２に記憶された仮想マシン毎の優先度に基づいて、再スケジューリングに用いられた全制約条件のうち、除外対象とする制約条件を決定する。そして、スケジュール変更部１２８は、当該全制約条件から、除外対象とする制約条件を１つずつ除外した準制約充足問題を、複数生成する。

スケジュール変更部１２８は、生成した各準制約充足問題に基づいて、ソルバ部１２５と同様に、当該準制約充足問題を最も良く満足するＬＭの再スケジューリング結果を生成する。そして、スケジュール変更部１２８は、複数の再スケジューリング結果から、所定の目的関数に基づいて、１つの再スケジューリング結果を選択する。例えば、目的関数は、ＬＭ時間帯の変更が希望された仮想マシンの希望時間帯と変更後の時間帯との差、および、それ以外の仮想マシンの既存のＬＭ予定時刻と変更後のＬＭ予定時刻との差を表す関数である。この場合、スケジュール変更部１２８は、目的関数を最小にする再スケジューリング結果を選択し、変更後のスケジュールの情報として、イベント情報記憶部１２３に格納する。

次に、極小充足不能コアについて説明する。
図６は、制約集合に対する極小充足不能コアの例を示す図である。
例えば、論理演算によって表された制約集合Ｇ１を考える。制約集合Ｇ１は、制約条件ａ１，ａ２，ａ３を含む。制約条件ａ１，ａ２，ａ３は、論理変数ｐ，ｑ，ｒを含む。論理変数ｐ，ｑ，ｒの値は、０または１である。

制約条件ａ１は、「ｐ ＸＯＲ ｑ」である。制約条件ａ２は、「ｐ ＯＲ （￢ｒ）」である。ここで、「￢ｘ」は、ｘの否定を表す。制約条件ａ３は、「￢（ｐ ＯＲ ｑ）」である。

制約条件ａ１，ａ２，ａ３を全て真にするｐ，ｑ，ｒの組は存在しない。したがって、制約集合Ｇ１は、充足不能である。この場合、制約集合Ｇ１から極小充足不能コアＣ１を抽出することができる。制約集合Ｇ１の例では、極小充足不能コアＣ１は、制約条件ａ１，ａ３の組となる。すなわち、制約集合Ｇ１のうち、制約条件ａ１，ａ３の何れか１つの制約を無効にした制約集合（制約条件ａ１，ａ２の集合または制約条件ａ２，ａ３の集合）は、充足可能になる。

充足不能コア抽出部１２６は、例えば、制約集合Ｇ１に対し、極小充足不能コアＣ１として、制約条件ａ１，ａ３の組を抽出する。極小充足不能コアの抽出には、前述の文献１“Boosting Minimal Unsatisfiable Core Extraction”の方法を用いることができる。

図７は、メンテナンス実施期間情報の例を示す図である。
メンテナンス実施期間情報１３１は、運用者端末７００により、スケジューラ１２０に入力される。メンテナンス実施期間情報１３１は、システムに含まれる複数の物理マシンに関するメンテナンスの実施期間の情報である。メンテナンス実施期間情報１３１は、開始日時および終了日時の項目を含む。

開始日時の項目には、メンテナンスの実施期間の開始日時が登録される。終了日時の項目には、メンテナンスの実施期間の終了日時が登録される。例えば、メンテナンス実施期間情報１３１は、開始日時「２０１８－０６－０１Ｔ１２：００：００．０００Ｚ」および終了日時「２０１８－０６－３０Ｔ１１：５９：００．０００Ｚ」という情報を含む。これは、メンテナンス実施期間が２０１８年６月１日１２時００分から２０１８年６月３０日１１時５９分までであることを示す。再スケジューリングの場合、再スケジューリングの起点となる時刻が、メンテナンス実施期間の開始日時となる。

ここで、１つの物理マシンに対するメンテナンス作業は、メンテナンス実施期間のうちの一部の時間範囲を用いて行われる。管理サーバ１００は、各物理マシンのメンテナンス作業が、入力されたメンテナンス実施期間中に完了するようにスケジューリングする。

例えば、管理サーバ１００は、第１の物理マシンに対するメンテナンス作業を行う前に、第１の物理マシン上の全ての仮想マシンを第２の物理マシン（移動先の物理マシンは複数でもよい）に移動させて、第１の物理マシンのメンテナンス作業を行えるようにする。

また、その後、第２の物理マシンのメンテナンス作業を行う場合も考えられる。その場合、管理サーバ１００、第２の物理マシン上の全ての仮想マシンを第１の物理マシンまたは第３の物理マシン（移動先の物理マシンは複数でもよい）に移動させて、第２の物理マシンのメンテナンス作業を行えるようにする。

図８は、メンテナンス対象マシン情報の例を示す図である。
メンテナンス対象マシン情報１３２は、運用者端末７００により、スケジューラ１２０に入力される。メンテナンス対象マシン情報１３２は、物理マシン名およびメンテナンス所要時間の項目を含む。

物理マシン名の項目には、物理マシンの名称が登録される。メンテナンス所要時間の項目には、当該物理マシンのメンテナンスの所要時間が登録される。例えば、メンテナンス対象マシン情報１３２は、物理マシン名「ＰＭ０１」（「ＰＭ」は、Physical Machineの略）、メンテナンス所要時間「０１：００：００．０００」という情報を含む。これは、物理マシン名「ＰＭ０１」で示される物理マシンのメンテナンス作業の所要時間が１時間であることを示す。

メンテナンス対象マシン情報１３２には、メンテナンス対象の他の物理マシンに対しても、同様に物理マシン名とメンテナンス所要時間が登録される。
図９は、物理マシン構成テーブルの例を示す図である。

物理マシン構成テーブル１４１は、インフラ構成情報記憶部１１１に予め格納されている。物理マシン構成テーブル１４１は、物理マシン名、ＣＰＵコア数、メモリ容量およびディスク容量の項目を含む。

物理マシン名の項目には、物理マシンの名称が登録される。ＣＰＵコア数の項目には、当該物理マシンが備えるＣＰＵコアの数が登録される。メモリ容量の項目には、当該物理マシンが備えるメモリ（ＲＡＭ）の容量が登録される。ディスク容量の項目には、当該物理マシンが備えるＨＤＤ（あるいは、当該物理マシンに対して外部ストレージに割り当てられた補助記憶領域）の容量が登録される。

例えば、物理マシン構成テーブル１４１には、物理マシン名が「ＰＭ０１」、ＣＰＵコア数が「６４」、メモリ容量が「２５６ＧＢ」、ディスク容量が「３２ＴＢ」というレコードが登録されている。このレコードは、物理マシン名「ＰＭ０１」で示される物理マシンが備えるＣＰＵコア数が６４個、メモリ容量が２５６ＧＢ、ディスク容量が３２ＴＢであることを示す。

物理マシン構成テーブル１４１には、他の物理マシンに対しても同様に、物理マシン名とＣＰＵコア数とメモリ容量とディスク容量とが登録される。
図１０は、仮想マシン構成テーブルの例を示す図である。

仮想マシン構成テーブル１４２は、インフラ構成情報記憶部１１１に予め格納されている。仮想マシン構成テーブル１４２は、仮想マシン名、ユーザＩＤ（IDentifier）、ＣＰＵコア数、メモリ容量、ディスク容量およびＬＭ所要時間の項目を含む。

仮想マシン名の項目には、仮想マシンの名称が登録される。ユーザＩＤの項目には、該当の仮想マシンを利用する利用者のＩＤが登録される。ＣＰＵコア数の項目には、当該仮想マシンに割り当てられるＣＰＵコア数が登録される。メモリ容量の項目には、当該仮想マシンに割り当てられるメモリの容量が登録される。ディスク容量の項目には、当該仮想マシンに割り当てられるＨＤＤ（あるいは、物理マシンの外部ストレージの補助記憶装置）の容量が登録される。ＬＭ所要時間の項目には、当該仮想マシンのＬＭの所要時間が登録される。

例えば、仮想マシン構成テーブル１４２には、仮想マシン名が「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」、ユーザＩＤが「ｕｓｅｒ１」、ＣＰＵコア数が「２」、メモリ容量が「３２ＧＢ」、ディスク容量が「２ＴＢ」、ＬＭ所要時間が「２５分」というレコードが登録されている。このレコードは、仮想マシン名「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」の仮想マシンが、ユーザＩＤ「ｕｓｅｒ１」の利用者により利用されることを示す。また、当該仮想マシンに対して所要されるＣＰＵコア数が２個、メモリ容量が３２ＧＢ、ディスク容量が２ＴＢであり、ＬＭ所要時間が２５分であることを示す。

仮想マシン構成テーブル１４２には、他の仮想マシンに対しても同様に、仮想マシン名とＣＰＵコア数とメモリ容量とディスク容量とユーザＩＤとＬＭ所要時間とが登録される。

図１１は、仮想マシン稼働テーブルの例を示す図である。
仮想マシン稼働テーブル１４３は、インフラ構成情報記憶部１１１に予め格納されている。仮想マシン稼働テーブル１４３は、各仮想マシンの初期配置先の物理マシンを示す情報である。再スケジューリングの場合、各仮想マシンの初期配置先は、再スケジューリングの対象期間の開始日時における各仮想マシンの配置先となる。仮想マシン稼働テーブル１４３は、物理マシン名、仮想マシン名およびユーザＩＤの項目を含む。

物理マシン名の項目には、物理マシンの名称が登録される。仮想マシン名の項目には、当該物理マシン上で稼働する仮想マシンの名称が登録される。ユーザＩＤの項目には、当該仮想マシンを利用するユーザのユーザＩＤが登録される。

例えば、仮想マシン稼働テーブル１４３には、物理マシン名が「ＰＭ０１」、仮想マシン名が「ｓｅｒｖｅｒ－９０」、ユーザＩＤが「ｕｓｅｒ３」というレコードが登録されている。このレコードは、物理マシン名「ＰＭ０１」で示される物理マシン上で、仮想マシン名「ｓｅｒｖｅｒ－９０」で示される仮想マシンが稼働しており、ユーザＩＤ「ｕｓｅｒ３」のユーザが当該仮想マシンを利用していることを示す。

仮想マシン稼働テーブル１４３には、他の仮想マシンに対しても同様に、配置先の物理マシン名と仮想マシン名とユーザＩＤとが登録される。
図１２は、依存関係テーブルの例を示す図である。

依存関係テーブル１４４は、インフラ構成情報記憶部１１１に予め格納されている。依存関係テーブル１４４は、仮想マシンのグループに対する依存関係を示す情報である。依存関係テーブル１４４は、グループ名、仮想マシン名およびルールの項目を含む。

グループ名の項目には、仮想マシンのグループの名称が登録される。仮想マシン名の項目には、該当のグループに属する仮想マシンの名称の組が登録される。ルールの項目には、該当のグループに属する仮想マシンを同一の物理マシン上で稼働させるか否かを示す情報が登録される。例えば、ルール「ａｆｆｉｎｉｔｙ」は、同一の物理マシン上で稼働させること（ａｆｆｉｎｉｔｙルールと呼ぶ）を示す。また、ルール「ａｎｔｉ－ａｆｆｉｎｉｔｙ」は、同一の物理マシン上で稼働させないこと（ａｎｔｉ－ａｆｆｉｎｉｔｙルールと呼ぶ）を示す。

例えば、依存関係テーブル１４４には、グループ名が「Ｇ０１」、仮想マシン名が「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」および「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３」、ルールが「ａｎｔｉ－ａｆｆｉｎｉｔｙ」というレコードが登録されている。このレコードは、グループ名「Ｇ０１」で示されるグループに、仮想マシン名「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」および「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３」の２つの仮想マシンが所属し、これら仮想マシンを同一物理マシン上で稼働させないことを示す。

また、例えば、依存関係テーブル１４４には、グループ名が「Ｇ０２」、仮想マシン名が「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３」および「ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３」、ルールが「ａｆｆｉｎｉｔｙ」というレコードが登録されている。このレコードは、グループ名「Ｇ０２」で示されるグループに、仮想マシン名「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３」および「ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３」の２つの仮想マシンが所属し、これら仮想マシンを同一物理マシン上で稼働させることを示す。

依存関係テーブル１４４には、仮想マシンの他のグループに対しても同様に、グループ名と仮想マシン名とルールとが登録される。
図１３は、極小充足不能コア情報の例を示す図である。

極小充足不能コア情報１４５は、充足不能コア抽出部１２６により生成され、制約条件記憶部１２１に格納される。充足不能コア抽出部１２６は、仮想マシン名の項目を含む。仮想マシン名の項目には、極小充足不能コアに属する制約条件に対応する仮想マシンの名称が登録される。

例えば、充足不能コア抽出部１２６には、仮想マシン名「ｖｍ－６７」、「ｓｅｒｖｅｒ－９０」、「ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３」、…という情報が登録されている。これは、再スケジューリングに用いられている充足不能な制約集合のうち、仮想マシン名「ｖｍ－６７」、「ｓｅｒｖｅｒ－９０」、「ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３」、…の何れか１つの仮想マシンに対するＬＭの実施時間帯に対する制約条件を除外することで、除外後の制約条件が充足可能になることを示す。ここで、除外対象の仮想マシンが、ＬＭ実施時間帯の変更要望があった仮想マシンの場合、「ＬＭの実施時間帯に対する制約条件」は、要望された実施時間帯（あるいは、要望された実施回避時間帯）となる。また、除外対象の仮想マシンが変更要望の対象外の仮想マシンの場合、「ＬＭの実施時間帯に対する制約条件」は、既存のスケジュールにおけるＬＭの実施予定の時間帯となる。

図１４は、優先度テーブルの例を示す図である。
優先度テーブル１４６は、ＶＭ優先度設定部１２７により生成され、ＶＭ優先度記憶部１２２に格納される。優先度テーブル１４６は、仮想マシン名および優先度の項目を含む。

仮想マシン名の項目には、仮想マシンの名称が登録される。優先度の項目には、該当の仮想マシンの優先度が登録される。優先度は数値で表され、数値が小さいほど、優先される度合いが高いものとする。

例えば、優先度テーブル１４６には、仮想マシン名が「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」、優先度が「２２」というレコードが登録されている。このレコードは、仮想マシン名「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」の仮想マシンの優先度が「２２」である（ＬＭ対象の全仮想マシンのうち２２番目に優先度が高い）ことを示す。

優先度テーブル１４６には、他の仮想マシンに対しても同様に、優先度が登録される。
次に、ＶＭ優先度設定部１２７による仮想マシン毎の優先度の決定例を説明する。
図１５は、優先度の決定例を示す図である。

ＶＭ優先度設定部１２７は、各仮想マシンの利用情報１４６ａによって、優先度を設定する。例えば、利用情報１４６ａは、仮想マシン名と、当該仮想マシンの利用状況と、ＬＭ実施予定時刻とを含む。仮想マシンの利用状況は、各仮想マシンの利用料金や利用者によって利用された期間（利用期間）を含む。ＶＭ優先度設定部１２７は、利用料金が高いほど、該当の仮想マシンの優先度を高くする。また、ＶＭ優先度設定部１２７は、利用期間が長いほど、該当の仮想マシンの優先度を高くする。ＬＭ実施予定時刻は、各仮想マシンの既存のＬＭの実施予定時刻である。ＶＭ優先度設定部１２７は、ＬＭ実施予定時刻が再スケジューリングの実施日時に近いほど、該当の仮想マシンの優先度を高くする。直近の予定が変更された場合、利用者による仮想マシンの利用予定に対して与える影響が大きくなるためである。

利用情報１４６ａの例では、ＶＭ優先度設定部１２７は、仮想マシン名「ｓｅｒｖｅｒ－４２」の仮想マシンを優先度「１」（最高優先度）に設定している。また、ＶＭ優先度設定部１２７は、仮想マシン名「ｍｙｓｑｌ－１０１」の仮想マシンを優先度「２」に設定している。また、ＶＭ優先度設定部１２７は、仮想マシン名「ｗｅｂ－ｄｂ－２５１」の仮想マシンを優先度「３」に設定している。他の仮想マシンに対しても、同様に、利用状況やＬＭ実施予定時刻に応じた優先度が設定される。

図１６は、メンテナンススケジュールテーブル（変更前）の例を示す図である。
メンテナンススケジュールテーブル１５１は、ソルバ部１２５により生成され、イベント情報記憶部１２３に格納される。メンテナンススケジュールテーブル１５１は、ソルバ部１２５によって当初作成されたスケジュールであり、利用者の希望などによるスケジュール変更前の情報である。メンテナンススケジュールテーブル１５１は、物理マシン名、開始日時および終了日時の項目を含む。

物理マシン名の項目には、メンテナンス対象の物理マシンの名称が登録される。開始日時の項目には、当該物理マシンのメンテナンスの開始日時が登録される。終了日時の項目には、当該物理マシンのメンテナンスの終了日時が登録される。

例えば、メンテナンススケジュールテーブル１５１には、物理マシン名が「ＰＭ０１」、開始日時が「２０１８－０６－２０Ｔ１１：３０：００．０００Ｚ」、終了日時が「２０１８－０６－２０Ｔ１２：２９：００．０００Ｚ」というレコードが登録されている。このレコードは、物理マシン名「ＰＭ０１」の物理マシンのメンテナンスを２０１８年６月２０日１１時３０分～２０１８年６月２０日１２時２９分まで行う予定であることを示す。

メンテナンススケジュールテーブル１５１には、メンテナンス対象の他の物理マシンに対しても同様に、物理マシン名と開始日時と終了日時とが登録される。
図１７は、ＬＭスケジュールテーブル（変更前）の例を示す図である。

ＬＭスケジュールテーブル１５２は、ソルバ部１２５により生成され、イベント情報記憶部１２３に格納される。ＬＭスケジュールテーブル１５２は、ソルバ部１２５によって当初作成されたスケジュールであり、利用者の希望などによるスケジュール変更前の情報である。ＬＭスケジュールテーブル１５２は、仮想マシン名、開始日時、終了日時、移動元および移動先の項目を含む。

仮想マシン名の項目には、ＬＭ対象の仮想マシンの名称が登録される。開始日時の項目には、該当の仮想マシンのＬＭの開始日時が登録される。終了日時の項目には、該当の仮想マシンのＬＭの終了日時が登録される。移動元の項目には、ＬＭの移動元の物理マシンの名称（物理マシン名）が登録される。移動先の項目には、ＬＭの移動先の物理マシンの名称（物理マシン名）が登録される。

例えば、ＬＭスケジュールテーブル１５２には、仮想マシン名が「ｓｅｒｖｅｒ－９０」、開始日時が「２０１８－０６－２０Ｔ０９：４５：００．０００Ｚ」、終了日時が「２０１８－０６－２０Ｔ０９：５９：００．０００Ｚ」、移動元が「ＰＭ０１」、移動先が「ＰＭ０２」というレコードが登録されている。

このレコードは、仮想マシン名「ｓｅｒｖｅｒ－９０」のＬＭを２０１８年６月２０日９時４５分に開始し、２０１８年６月２０日９時５９分に終了することを示す。また、当該ＬＭの移動元が物理マシン名「ＰＭ０１」の物理マシンであり、移動先が物理マシン名「ＰＭ０２」の物理マシンであることを示す。

ＬＭスケジュールテーブル１５２には、他の仮想マシンに対しても、仮想マシン名と開始日時と終了日時と移動元と移動先とが登録される。
なお、ＬＭスケジュールテーブル１５２のうち、仮想マシン名、開始日時および終了日時の項目の内容が利用者に提示される内容である。また、ＬＭスケジュールテーブル１５２のうち、仮想マシン名、開始日時、終了日時、移動元および移動先の項目が運用者に提示される内容である。

図１８は、ＬＭ実施日時変更要望情報の例を示す図である。
ＬＭ実施日時変更要望情報１３３は、利用者端末５００，６００により、スケジューラ１２０に入力される。

ＬＭ実施日時変更要望情報１３３は、１以上の仮想マシンに関するＬＭの実施期間の変更内容を示す情報である。ＬＭ実施日時変更要望情報は、仮想マシン名、開始時刻、終了時刻および属性の項目を含む。

仮想マシン名の項目は、仮想マシンの名称が登録される。開始時刻の項目には、開始時刻が登録される。終了時刻の項目には終了時刻が登録される。属性の項目には、開始時刻から終了時刻までの期間において、該当の仮想マシンのＬＭの「回避」または「許容」を示す情報が登録される。「回避」は、該当の期間におけるＬＭを回避することを示す。「許容」は、該当の期間におけるＬＭを許容することを示す。

例えば、ＬＭ実施日時変更要望情報１３３は、仮想マシン名が「ｍｙｓｑｌ－６７」、開始時刻が「２０１８－０６－２０Ｔ１０：４０：００．０００Ｚ」、終了時刻が「２０１８－０６－２０Ｔ１２：５９：００．０００Ｚ」、属性が「回避」という情報を含む。これは、２０１８年６月２０日１０時４０分から２０１８年６月２０日１２時５９分までの期間において、仮想マシン名「ｍｙｓｑｌ－６７」の仮想マシンのＬＭを回避するように要望されていることを示す。なお、該当の仮想マシンについて、属性「回避」が設定されている期間以外の期間で、ＬＭが「許容」されていると考えてもよい。

また、ＬＭ実施日時変更要望情報１３３は、仮想マシン名が「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」、開始時刻が「２０１８－０６－２２Ｔ１８：００：００．０００Ｚ」、終了時刻が「２０１８－０６－２２Ｔ２０：５９：００．０００Ｚ」、属性が「許容」という情報を含む。これは、２０１８年６月２２日１８時００分から２０１８年６月２２日２０時５９分までの期間において、仮想マシン名「ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３」の仮想マシンのＬＭを行うように要望されていることを示す。なお、該当の仮想マシンについて、属性「許容」が設定されている期間以外の期間で、ＬＭの「回避」が設定されていると考えてもよい。

このように、ＬＭ実施日時変更要望情報１３３は、仮想マシンの移動を許容する時間帯、または、仮想マシンの移動を回避する時間帯を示す情報を含む。
図１９は、変更後のスケジュールテーブルの例を示す図である。

メンテナンススケジュールテーブル１５３は、ソルバ部１２５およびスケジュール変更部１２８により生成され、イベント情報記憶部１２３に格納される。メンテナンススケジュールテーブル１５３は、メンテナンススケジュールテーブル１５１に対するスケジュール変更後の情報である。メンテナンススケジュールテーブル１５３のデータ構造は、メンテナンススケジュールテーブル１５１のデータ構造と同様であるため、説明を省略する。

ＬＭスケジュールテーブル１５４は、ソルバ部１２５およびスケジュール変更部１２８により生成され、イベント情報記憶部１２３に格納される。ＬＭスケジュールテーブル１５４は、ＬＭスケジュールテーブル１５２に対するスケジュール変更後の情報である。ＬＭスケジュールテーブル１５４のデータ構造は、ＬＭスケジュールテーブル１５２のデータ構造と同様であるため、説明を省略する。

図２０は、制約充足問題における変数の例を示す図である。
制約条件生成部１２４は、図７～図１２で例示した各情報（再スケジューリングの場合は、更に図１７，図１８の情報）に含まれる値を制約充足問題の入力とする。ソルバ部１２５は、制約充足問題を解くことで、図１６で例示したメンテナンススケジュールテーブル１５１および図１７で例示したＬＭスケジュールテーブル１５２を出力し、イベント情報記憶部１２３に格納する。再スケジューリングの場合、ソルバ部１２５およびスケジュール変更部１２８は、図１９で例示したメンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４を出力し、イベント情報記憶部１２３に格納する。

例えば、制約充足問題における入力変数には次のものがある。
ｔ_ｓは、メンテナンス実施期間の開始日時である。前述のように、再スケジューリングの場合、ｔ_ｓは、再スケジューリングの対象期間の開始日時を示す。ｔ_ｅは、メンテナンス実施期間の終了日時である。Ｔ＝｛ｔ_ｓ，…，ｔ_ｅ｝は、メンテナンス実施期間を分単位に離散化した時刻の集合である。Ｔにおけるある時刻から、その次の時刻（１分後の時刻）の直前までの期間を１つのタイムスロットと呼ぶ。時刻ｔ_ｓおよびｔ_ｅの値は、メンテナンス実施期間情報１３１から得られる。

Ｐは、メンテナンス対象の物理マシン（ＰＭ）の集合である。ｍａｉｎｔＤｕｒａｔｉｏｎ_ｐは、物理マシンｐ（ＰＭｐ）のメンテナンス所要時間である。ここで、ｐは、メンテナンス対象の物理マシンを示す添え字である。ＰおよびｍａｉｎｔＤｕｒａｔｉｏｎ_ｐの値は、メンテナンス対象マシン情報１３２から得られる。

ｃｐｕＣａｐ_ｐは、ＰＭｐのＣＰＵコア数である。ｒａｍＣａｐ_ｐは、ＰＭｐのメモリ容量である。ｄｉｓｋＣａｐ_ｐは、ＰＭｐのディスク容量である。ｃｐｕＣａｐ_ｐ、ｒａｍＣａｐ_ｐおよびｄｉｓｋＣａｐ_ｐの値は、物理マシン構成テーブル１４１から得られる。

Ｖは、ＬＭの日程調整対象の仮想マシン（ＶＭ）の集合である。ｉｎｉｔＡｃｃｏｍｍｏ_ｐｖは、仮想マシンｖ（ＶＭｖ）の初期配置を示し、ＶＭｖの初期配置先がＰＭｐの場合は１、それ以外の場合は０を示す。ここで、ｖは、ＬＭ対象の仮想マシンを示す添え字である。Ｖは、仮想マシン稼働テーブル１４３に登録された仮想マシンのうち、メンテナンス対象マシン情報１３２で指定された物理マシンに対応付けられた仮想マシンの集合となる。ｉｎｉｔＡｃｃｏｍｍｏ_ｐｖの値は、仮想マシン稼働テーブル１４３から得られる。前述のように、再スケジューリングの場合、各仮想マシンの初期配置先は、再スケジューリングの対象期間の開始日時おける各仮想マシンの配置先となる。

ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖは、ＶＭｖのＬＭ所要時間である。ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖの値は、仮想マシン構成テーブル１４２から得られる。
ｃｐｕＲｅｑ_ｖは、ＶＭｖのＣＰＵコア数である。ｒａｍＲｅｑ_ｖは、ＶＭｖのメモリ容量である。ｄｉｓｋＲｅｑ_ｖは、ＶＭｖのディスク容量である。ｃｐｕＲｅｑ_ｖ、ｒａｍＲｅｑ_ｖおよびｄｉｓｋＲｅｑ_ｖの値は、仮想マシン構成テーブル１４２から得られる。

ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）は、ＬＭ実施許容日時（あるいは、ＬＭ実施回避日時）を示し、時刻ｔにＶＭｖのＬＭを実施してもよい場合は１、それ以外の場合は０を示す。ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）の値のデフォルト値は１である。例えば、当初スケジューリングを行う場合に、ある仮想マシンでＬＭ実施回避日時がある場合には、ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）によって、ＬＭ実施回避日時を設定することが可能である。

再スケジューリングの場合、変更要望対象の仮想マシンについて、ＬＭ実施日時変更要望情報１３３に基づいてａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）の値が得られる。再スケジューリングの場合、変更要望対象外の仮想マシンについては、後述の変数ａ_ｐｖ（ｔ），ｌ_ｐｖ（ｔ）によりＬＭの実施予定の時間帯が制約として指定されるため、ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）の制約を作成しなくてよい。ただし、変更要望対象外の仮想マシンについて、既存のスケジュールテーブル１５２に応じた値を、ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）に設定してもよい。

ｎｕｍＧ_ａｆは、ａｆｆｉｎｉｔｙルールが適用されているグループの数である。Ｇ_ａｆ＝｛Ｇ_ａｆ＿１，…，Ｇ_{ａｆ＿ｎｕｍＧａｆ}｝は、ａｆｆｉｎｉｔｙルールが適用されているグループの集合である。ｎｕｍＧ_ａａは、ａｎｔｉ－ａｆｆｉｎｉｔｙルールが適用されているグループの数である。Ｇ_ａａ＝｛Ｇ_ａａ＿１，…，Ｇ_{ａａ＿ｎｕｍＧａａ}｝は、ａｎｔｉ－ａｆｆｉｎｉｔｙルールが適用されているグループの集合である。ｎｕｍＧ_ａｆ、Ｇ_ａｆ、ｎｕｍＧ_ａａ、Ｇ_ａａの値は、依存関係テーブル１４４から得られる。

このように、制約充足問題に関する制約情報は、複数の物理マシンのメンテナンスの実施期間、複数の物理マシンおよび複数の仮想マシンの構成情報および物理マシンから他の物理マシンへの仮想マシンの移動の所要時間を示す所要時間に関する制約を含む。

また、例えば、出力変数には次のものがある。
ｍ_ｐ（ｔ）は、ＰＭ単位のメンテナンス実施期間を示し、時刻ｔにＰＭｐがメンテナンス中の場合は１、それ以外の場合は０を示す。ｍ_ｐ（ｔ）は、メンテナンススケジュールテーブル１５１（再スケジューリングの場合には、メンテナンススケジュールテーブル１５３）の作成に用いられる。

ａ_ｐｖ（ｔ）は、ＶＭの配置先の物理マシンを示し、時刻ｔにＶＭｖがＰＭｐ上で稼働している場合は１、それ以外の場合は０を示す。ｌ_ｐｖ（ｔ）は、ＬＭによるＶＭの配置先の切り替わりを示し、ＶＭｖについて時刻ｔにＰＭｐへのＬＭが完了した場合は１、それ以外の場合は０を示す。ａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）は、ＬＭスケジュールテーブル１５２（再スケジューリングの場合には、ＬＭスケジュールテーブル１５４）の作成に用いられる。

また、再スケジューリングの場合、ＬＭの実施日時の変更要望のない仮想マシンについて、ａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）には、既存のＬＭスケジュールテーブル１５２に応じた値が設定されて、制約充足問題における入力変数（制約条件）としても用いられる。

ここで、上記の変数ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ、ｌ_ｐｖ（ｔ）およびａ_ｐｖ（ｔ）によるＬＭの表現を例示する。
図２１は、変数によるＬＭの表現の例を示す図である。

図２１（Ａ）は、時刻ｔ_ｉ，ｔ_ｉ＋１，…，ｔ_ｉ＋５における、仮想マシンｖ１，ｖ２に対するｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖを例示する。
例えば、ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ１＝２である。これは、各時刻に仮想マシンｖ１のＬＭを完了させるためにタイムスロットを２つ要することを示す。

また、ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ２＝３である。これは、各時刻に仮想マシンｖ２のＬＭを完了させるためにタイムスロットを３つ要することを示す。
第２の実施の形態の例では、各仮想マシンのＬＭの所要時間を、各時刻で一定としている。ただし、仮想マシンのＬＭの所要時間は、該当の仮想マシンの負荷などに応じて変わることも考えられる。その場合、ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ＝ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ（ｔ）とし、時刻毎に、ＬＭを完了させるために所要される異なるタイムスロット数を設定することも可能である。

図２１（Ｂ）は、時刻ｔ_ｉ，ｔ_ｉ＋１，…，ｔ_ｉ＋５における、仮想マシンｖ１，ｖ２に対するｌ_ｐｖ（ただし、ｐ＝Ｃとする）を例示する。
例えば、ｌ_ｐｖ１（ｔ_ｉ＋２）＝１であり、それ以外の時刻ではｌ_ｐｖ１（ｔ）＝０である。これは、時刻ｔ_ｉ＋２に、仮想マシンｖ１の物理マシンＣへのＬＭが完了したことを示す。ここで、図２１（Ａ）によれば、時刻ｔ_ｉ＋２で仮想マシンｖ１のＬＭが完了するには、タイムスロットを２つ要する。したがって、仮想マシンｖ１のＬＭの実施期間は、時刻ｔ_ｉ＋１，ｔ_ｉ＋２で示される２つのタイムスロットの期間である。

また、ｌ_ｐｖ２（ｔ_ｉ＋４）＝１であり、それ以外の時刻ではｌ_ｐｖ２（ｔ）＝０である。これは、時刻ｔ_ｉ＋４に、仮想マシンｖ２の物理マシンＣへのＬＭが完了したことを示す。ここで、図２１（Ａ）によれば、時刻ｔ_ｉ＋４で仮想マシンｖ２のＬＭが完了するには、タイムスロットを３つ要する。したがって、仮想マシンｖ２のＬＭの実施期間は、時刻ｔ_ｉ＋２，ｔ_ｉ＋３，ｔ_ｉ＋４で示される３つのタイムスロットの期間である。

図２１（Ｃ）は、時刻ｔ_ｉ，ｔ_ｉ＋１，…，ｔ_ｉ＋５において、仮想マシンｖ１，ｖ２に対し、ａ_ｐｖ（ｔ）＝＝１となるｐ（物理マシン）を例示する。
例えば、時刻ｔ_ｉ，ｔ_ｉ＋１，ｔ_ｉ＋２では、ａ_ｐｖ１（ｔ）＝＝１となるｐは、物理マシンＡ（仮想マシンｖ１のＬＭの移動元）である。そして、図２１（Ｂ）で例示されるように、仮想マシンｖ１は、時刻ｔ_ｉ＋２で物理マシンＣへのＬＭが完了する。このため、時刻ｔ_ｉ＋３以降では、ａ_ｐｖ１（ｔ）＝＝１となるｐは、物理マシンＣである。

また、時刻ｔ_ｉ，ｔ_ｉ＋１，…，ｔ_ｉ＋４では、ａ_ｐｖ２（ｔ）＝＝１となるｐは、物理マシンＢ（仮想マシンｖ２のＬＭの移動元）である。そして、図２１（Ｂ）で例示されるように、仮想マシンｖ２は、時刻ｔ_ｉ＋４で物理マシンＣへのＬＭが完了する。このため、時刻ｔ_ｉ＋５以降では、ａ_ｐｖ２（ｔ）＝＝１となるｐは、物理マシンＣである。

以上のように、変数ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ、ｌ_ｐｖ（ｔ）およびａ_ｐｖ（ｔ）により、仮想マシンｖ１，ｖ２のＬＭについて、次の内容が表される。
仮想マシンｖ１について、ＬＭ実施期間は時刻［ｔ_ｉ＋１，ｔ_ｉ＋２］（時刻ｔ_ｉ＋１から時刻ｔ_ｉ＋２まで）であり、移動元が物理マシンＡ、移動先が物理マシンＣである。

仮想マシンｖ２について、ＬＭ実施期間は時刻［ｔ_ｉ＋２，ｔ_ｉ＋４］（時刻ｔ_ｉ＋２から時刻ｔ_ｉ＋４まで）であり、移動元が物理マシンＡ、移動先が物理マシンＣである。
制約条件生成部１２４は、上記に例示した各変数を用いた制約条件を生成する。ソルバ部１２５は、生成された制約条件に関する制約充足問題を解くことで、メンテナンススケジュールテーブル１５１およびＬＭスケジュールテーブル１５２を作成する。また、再スケジューリングの場合、ソルバ部１２５およびスケジュール変更部１２８は、生成された制約条件に関する制約充足問題を解くことで、メンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４を作成する。

ここで、制約条件生成部１２４により生成される制約条件の例を示す。
第１の制約条件は、ＶＭｖが初期配置先のＰＭｐ上で起動することである。第１の制約条件は、式（２）で表される。

第２の制約条件は、ＰＭｐに対してメンテナンスを一度実施することである。第２の制約条件は、式（３）（４）で表される。特に、式（３）は、ＰＭｐに対してｍａｉｎｔＤｕｒａｔｉｏｎ_ｐ以上の連続したメンテナンス期間が確保されることを示す。式（４）は、当該メンテナンス期間の合計がｍａｉｎｔＤｕｒａｔｉｏｎ_ｐに等しいことを示す。

第３の制約条件は、一度にメンテナンスを実施できるＰＭ数をＣ_ｍ台以下とすることである。ここで、Ｃ_ｍは、システムに応じて予め定められる定数である。第３の制約条件は、式（５）で表される。

第４の制約条件は、ＶＭｖが何れかのＰＭｐ上で常に稼働することである。第４の制約条件は、式（６）で表される。

第５の制約条件は、ＰＭｐ上で稼働するＶＭの要求資源量の合計がＰＭｐの提供資源量以下であり、かつ、ＰＭｐのメンテナンス中はＰＭｐ上でＶＭを稼働させないことである。第５の制約条件は、式（７）（８）（９）で表される。特に、式（７）は、ＣＰＵコア数に関する制約条件を表す。式（８）は、メモリ容量に関する制約条件を示す。式（９）は、ディスク容量に関する制約条件を表す。

第６の制約条件は、ＶＭｖがＰＭｐ上で稼働する時間がｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ＋１以上であることである。第６の制約条件は、式（１０）で表される。ここで、第６の制約条件は、ＶＭｖがＬＭのためにｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ＋１以上の期間、連続して稼働状態となることを反映している。ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖに“＋１”（１を加算）する理由は、ＬＭが完了した直後に別のＬＭを実施することは考えにくいためである。

第７の制約条件は、ＬＭの検出を示す。第７の制約条件は、式（１１）で表される。ここで、ｌ_ｐｖ（ｔ）は、ＶＭｖについて時刻ｔにＰＭｐへのＬＭが完了した場合は１であり、それ以外の場合は０である。

第８の制約条件は、ＶＭｖのＬＭを実施できるのは許可された期間のみであることである。第８の制約条件は、式（１２）で表される。ただし、前述のように、再スケジューリングの場合、一部の仮想マシン（ＬＭ実施時間帯の変更要望のない仮想マシン）に対して第８の制約条件を作成しないこともある。

第９の制約条件は、ＰＭｐについてメンテナンス中のＬＭが禁止されることである。第９の制約条件は、式（１３）で表される。

第１０の制約条件は、一度にＬＭを行えるＶＭをＣ_ｌ台以下とすることである。ここで、Ｃ_ｌは、システムに応じて予め定められる定数である。第１０の制約条件は、式（１４）で表される。

第１１の制約条件は、ａｎｔｉ－ａｆｆｉｎｉｔｙルールが適用されているグループに属する各ＶＭを同じＰＭ上で稼働させることを禁止することである。第１１の制約条件は、式（１５）で表される。

第１２の制約条件は、ａｆｆｉｎｉｔｙルールが適用されているグループに属する各ＶＭを同じＰＭ上で稼働させることである。第１２の制約条件は、式（１６）で表される。

第１３の制約条件は、制約充足問題の目的関数であり、全体のメンテナンスの終了を早めることである。第１３の制約条件は、式（１７）で表される。例えば、第１３の制約条件は、運用者のメンテナンスを早く終わらせたいという要望に応じた制約条件である。

次に、管理サーバ１００による処理手順を説明する。以下では主に、再スケジューリングの場合を例示する。このため、イベント情報記憶部１２３には、当初作成されたメンテナンススケジュールテーブル１５１およびＬＭスケジュールテーブル１５２が格納されている状態から、以下に示す手順が開始される。

図２２は、管理サーバの処理例を示すフローチャートである。
（Ｓ１）スケジューラ１２０は、利用者端末５００，６００からＬＭ実施日時の変更要望のメッセージを受信する。当該メッセージは、ＬＭ実施日時変更要望情報１３３を含む。ＬＭ実施日時変更要望情報１３３は、複数の仮想マシンに対する変更要望を含み得る。

（Ｓ２）スケジューラ１２０は、運用者端末７００から日程再調整実施のメッセージを受信する。当該メッセージは、メンテナンス実施期間情報１３１およびメンテナンス対象マシン情報１３２を含む。再スケジューリングの場合となるので、メンテナンス実施期間情報１３１で示される開始日時は、再スケジューリングの対象期間の開始日時を示す。

なお、当初のメンテナンス実施開始日時の後に再スケジューリングが行われる場合、一部の物理マシンについては、メンテナンスが実施済みのことがある。この場合、スケジューラ１２０は、メンテナンス実施済みの物理マシンについては、変数ｍ_ｐ（ｔ）を計算しない（当該物理マシンについて制約を充足しなくてよい）。

（Ｓ３）スケジューラ１２０は、日程再調整を実行し、再調整結果（再スケジューリング結果）をイベント情報記憶部１２３に出力する。日程再調整の詳細は後述される。
（Ｓ４）スケジューラ１２０は、利用者端末５００，６００と運用者端末７００に再調整結果を送信する。利用者端末５００，６００および運用者端末７００のそれぞれのディスプレイにより再調整結果が表示される。

（Ｓ５）スケジューラ１２０は、再調整結果を、インフラ管理部１１０に登録する。これにより、インフラ管理制御部１１３によって、再調整結果に基づくＬＭが、各物理マシンに指示される。そして、管理サーバ１００の処理が終了する。

図２３は、日程再調整例を示すフローチャートである。
日程再調整の処理は、ステップＳ３に対応する。
（Ｓ１０）ＶＭ優先度設定部１２７は、仮想マシン（ＶＭ）間の優先度を設定する。例えば、ＶＭ優先度設定部１２７は、図１５で例示したように、仮想マシン毎の利用情報１４６ａに基づいて、仮想マシンの優先度を決定して優先度テーブル１４６を生成し、ＶＭ優先度記憶部１２２に格納する。

（Ｓ１１）制約条件生成部１２４は、利用者要望に応じたＬＭ実施日時に関する制約を含む制約充足問題を生成する。制約充足問題の生成の詳細は後述される。
（Ｓ１２）ソルバ部１２５は、ステップＳ１１で生成された制約充足問題の求解を実行し、再スケジューリングの対象期間の各時刻における各出力変数の値を求める。

（Ｓ１３）ソルバ部１２５は、ステップＳ１２によって、制約充足問題に対する充足解を得たか否かを判定する。充足解を得た場合、ステップＳ１４に処理が進む。充足解を得られなかった場合、ステップＳ１５に処理が進む。

（Ｓ１４）ソルバ部１２５は、ステップＳ１２で得た充足解を再調整結果（再スケジューリング結果）として、イベント情報記憶部１２３に出力する。そして、日程再調整の処理が終了する。

（Ｓ１５）充足不能コア抽出部１２６およびスケジュール変更部１２８は、日程変更を実行する。日程変更の詳細は後述される。そして、日程再調整の処理が終了する。
図２４は、制約充足問題の生成例を示すフローチャートである。

制約充足問題の生成の処理は、ステップＳ１１に相当する。
（Ｓ２０）制約条件生成部１２４は、インフラ構成情報をソルバ部１２５に対する入力データの形式に変換する。ここで、インフラ構成情報は、物理マシン構成テーブル１４１、仮想マシン構成テーブル１４２、仮想マシン稼働テーブル１４３および依存関係テーブル１４４を含む。

（Ｓ２１）制約条件生成部１２４は、仮想マシン（ＶＭ）の依存関係に関する制約条件を生成する。ＶＭの依存関係に関する制約条件は、例えば、前述の第１、第４、第５、第１１および第１２の制約条件である。制約条件生成部１２４は、生成した制約条件を制約条件記憶部１２１に格納する。

（Ｓ２２）制約条件生成部１２４は、ＬＭの再スケジューリング対象の全仮想マシンを再スケジューリング候補に設定する。ただし、全仮想マシンのうち、ＬＭ実施日時の変更要望が発生していない仮想マシンについては、既存のスケジュールが可能な限り維持されるように、再スケジューリングが行われる。

（Ｓ２３）制約条件生成部１２４は、再スケジューリングの対象期間をＬＭ実施の候補日時に設定する。例えば、制約条件生成部１２４は、メンテナンス実施期間情報１３１に基づいて、Ｔ＝｛ｔ_ｓ，…，ｔ_ｅ｝を設定する。

（Ｓ２４）制約条件生成部１２４は、ＬＭ実施時間に関する制約条件を生成する。ＬＭ実施時間に関する制約条件は、例えば、前述の第２、第３、第６～第１０および第１３の制約条件である。ここで、制約条件生成部１２４は、第８の制約条件について、ＬＭ実施日時変更要望情報１３３に基づいて、ＬＭ実施日時の変更対象の仮想マシンに対するａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）の値を設定する。すなわち、ＬＭ実施日時変更要望情報１３３でＬＭ実施が要望されている時間帯（回避希望でない時間帯）でａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）＝１、それ以外の時間帯でａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）＝０とする。

一方、制約条件生成部１２４は、ＬＭ実施日時の変更対象外の仮想マシンについては第８の制約条件を作成しなくてよい。その代わり、制約条件生成部１２４は、ＬＭ実施日時の変更対象外の仮想マシンについては、既存のＬＭスケジュールテーブル１５２に基づいて、既存のＬＭスケジュールを反映するように、各時刻ｔにおける変数ａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）の値を設定する。変数ａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）の値が、ＬＭ実施日時の変更対象外の仮想マシンに対するＬＭ実施時間帯に関する制約条件となる。

（Ｓ２５）制約条件生成部１２４は、ステップＳ２１，Ｓ２４で生成した制約条件を基に制約充足問題を設定する。そして、制約充足問題の生成の処理が終了する。
図２５は、日程変更例を示すフローチャートである。

日程変更の処理は、ステップＳ１５に相当する。
（Ｓ３０）充足不能コア抽出部１２６は、ステップＳ１１（ステップＳ２５）で生成された制約充足問題に含まれる制約集合のうち、仮想マシンのＬＭの実施時刻に関する制約条件から、極小充足不能コアを抽出する。充足不能コア抽出部１２６は、抽出した極小充足不能コア（Ｃ_Ｕ）を、スケジュール変更部１２８に提供する。

（Ｓ３１）スケジュール変更部１２８は、インフラ構成情報および優先度テーブル１４６を取得するとともに、準制約充足問題生成の制限数ｋが設定されているか否かを判定する。制限数ｋが設定されている場合、ステップＳ３３に処理が進む。制限数ｋが設定されていない場合、ステップＳ３２に処理が進む。ここで、制限数ｋは、例えば、制約条件記憶部１２１に予め設定される。

（Ｓ３２）スケジュール変更部１２８は、極小充足不能コアの要素数（極小充足不能コアに属する制約条件の数）を制限数ｋに設定する。すなわち、スケジュール変更部１２８は、ｋ＝｜Ｃ_Ｕ｜とする（｜Ｃ_Ｕ｜は極小充足不能コアＣ_Ｕの要素数を示す）。そして、ステップＳ３３に処理が進む。

図２６は、日程変更例（続き）を示すフローチャートである。
（Ｓ３３）スケジュール変更部１２８は、優先度テーブル１４６に基づいて、仮想マシン（ＶＭ）間の優先度下位ｋ台についてＬＭ実施時刻に関する制約を、該当の制約充足問題から１つ除外した準制約充足問題を生成する。これにより、スケジュール変更部１２８は、ｋ種類の準制約充足問題を生成する。

例えば、ＬＭの実施日時の変更要望があった仮想マシンに対する制約を除外する場合、当該仮想マシンについて、全ての時刻でａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）＝１とする。

また、ＬＭの実施日時の変更要望がなかった仮想マシンに対する制約を除外する場合、当該仮想マシンについて、全ての時刻でａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）＝１とする制約を後述する入力データ１６５に追加する。更に、当該仮想マシンについて、既存スケジュールに対するａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）の制約を入力データ１６６から削除する。

（Ｓ３４）スケジュール変更部１２８は、準制約充足問題毎に、繰り返し、求解の処理を行う。また、ステップＳ３４～Ｓ３６の処理は管理サーバ１００により並列に実行されてもよい。

（Ｓ３５）スケジュール変更部１２８は、該当の準制約充足問題の求解を実行する。スケジュール変更部１２８は、ソルバ部１２５を用いて、準制約充足問題の求解を実行してもよい。

（Ｓ３６）スケジュール変更部１２８は、ｋ種類の準制約充足問題に関する求解を完了すると、求解の処理の繰り返しを完了する。そして、ステップＳ３７に処理が進む。スケジュール変更部１２８は、ｋ種類の準制約充足問題に関する求解の実行により、ｋ個の再スケジューリング結果を得る。

（Ｓ３７）スケジュール変更部１２８は、ｋ個の再スケジューリング結果のうち、目的関数を最小にする結果を１つ選択する。例えば、目的関数は、次の式（１８）（１９）で表される。

ここで、式（１８）は、ＬＭの実施日時の変更の要望があった仮想マシンに対する目的関数である。式（１９）は、ＬＭの実施日時に変更の要望がない仮想マシンに対する目的関数である。変数ｌ_ｔ（ｖ）は、再スケジューリング結果における仮想マシンｖのＬＭ実施開始時刻（今回の再スケジューリング結果）である。変数ｌ’_ｔ（ｖ）は、仮想マシンｖのＬＭ実施開始予定時刻（前回のスケジューリング結果）である。変数ｒ_ｔ（ｖ）は、仮想マシンｖのＬＭ実施についての要望時刻（ＬＭ実施が希望された時刻）である。時間差は、何れも正の値で表される。

式（１８）は、ＬＭの実施日時に変更の要望があった仮想マシンについて、要望された希望時間帯と再スケジューリング後の新規予定時間帯の乖離を最小にすることを示す。
ここで、希望時間帯Ｔ_１～Ｔ_２（Ｔ_１＜Ｔ_２）と新規予定時間帯Ｔ_３～Ｔ_４（Ｔ_３＜Ｔ_４）との差ΔＴは、例えば、次のように表される。Ｔ_１≦Ｔ_３＜Ｔ_２かつＴ_１＜Ｔ_４≦Ｔ_２の場合、ΔＴ＝０である。Ｔ_３＜Ｔ_１かつＴ_４≦Ｔ_２の場合、ΔＴ＝Ｔ_１－Ｔ_３である。Ｔ_１≦Ｔ_３かつＴ_２＜Ｔ_４の場合、ΔＴ＝Ｔ_４－Ｔ_２である。Ｔ_３＜Ｔ_１かつＴ_２＜Ｔ_４の場合、ΔＴ＝（Ｔ_１－Ｔ_３）＋（Ｔ_４－Ｔ_２）である。なお、ある仮想マシンに対してＬＭ実施回避日時が指定された場合など、ＬＭ実施が許容される希望時間帯が複数になる（例えば、ＬＭ実施回避日時によって分断された複数の時間帯になる）こともある。この場合、スケジュール変更部１２８は、各希望時間帯と新規予定時間帯との差のうち、最小の差を、該当の仮想マシンに対する希望時間帯と新規予定時間帯との差として用いる。

式（１９）は、ＬＭの実施日時に変更の要望がない仮想マシンについて、既存の予定時間帯と再スケジューリング後の新規予定時間帯の乖離（ＬＭの開始時刻の時間差）を最小にすることを示す。

（Ｓ３８）スケジュール変更部１２８は、ステップＳ３７で選択した結果を再調整結果（再スケジューリング結果）として、イベント情報記憶部１２３に出力する。そして、日程変更の処理が終了する。

ステップＳ３７では、スケジュール変更部１２８は、ＬＭの実施日時の変更の要望があった仮想マシンに対する目的関数（第１の目的関数）の出力値、または、ＬＭの実施日時に変更の要望がない仮想マシンに対する目的関数（第２の目的関数）の出力値の何れかが最小になる再スケジューリング結果を選択する。あるいは、スケジュール変更部１２８は、第１の目的関数の出力値と第２の目的関数の出力値の合計が最小になる再スケジューリング結果を選択してもよい。

このように、管理サーバ１００は、制約充足問題（制約情報）を充足する再スケジューリング結果を得られない場合に、制約充足問題に属するＬＭ実施時間帯に関する制約群から抽出された極小充足不能コアに含まれる制約を除外対象として選択する。これにより、該当の制約充足問題を充足可能な準制約充足問題に変化させることができ、再スケジューリング結果を取得可能になる。このとき、準制約充足問題では、１つの制約が除外対象になるだけなので、既存のスケジュール結果に対する影響を極力抑えた再スケジューリングが可能である。

また、管理サーバ１００は、除外対象の制約を選択する際に、極小充足不能コアに含まれる全制約のうちの一部の制約を、複数の仮想マシンそれぞれの優先度に基づいて選択する。このため、極小充足不能コアに含まれる全制約を除外対象として準制約充足問題を作成して、再スケジューリングを行うよりも処理を高速化できる。特に、仮想マシン毎の優先度に従って、比較的優先度が高い仮想マシンの制約を除外対象外とできるので、重要な処理を行う仮想マシンに対する影響を抑えられる。

また、管理サーバ１００は、再スケジューリング結果および既存スケジュールにおける変更要望のなかった他の仮想マシンのＬＭ実施時刻の第１の差、または、ＬＭの実施日時の変更要望および再スケジューリング結果における該当の仮想マシンのＬＭ実施時間帯の第２の差が小さくなる再スケジューリング結果を出力する。これにより、既存のＬＭのスケジュールへの影響を抑えつつ、ＬＭの実施日時の変更要望に沿った再スケジューリングが可能になる。

例えば、目的関数に式（１８）を用いることで、ＬＭの実施日時に変更の要望があった仮想マシンについて、可能な限り変更の要望に沿った日時に変更でき、利用者による仮想マシンの利用予定に対する影響を最小限に抑えることができる。また、目的関数に式（１９）を用いることで、ＬＭの実施日時に変更の要望がなかった仮想マシンに対する影響を最小限に抑えることができる。

以下では、再スケジューリング時におけるソルバ部１２５に対する入力データ、および、当該入力データに応じたソルバ部１２５（およびスケジュール変更部１２８）の出力データを例示する。

図２７は、入力データの例（その１）を示す図である。
入力データ１６１は、変数ｔ_ｓ、ｔ_ｅ、Ｐ、ｍａｉｎｔＤｕｒａｔｉｏｎ_ｐ、ｃｐｕＣａｐ_ｐ、ｒａｍＣａｐ_ｐおよびｄｉｓｋＣａｐ_ｐを含む。

ｔ_ｓ：＝０；およびｔ_ｅ：＝４１７５９；はメンテナンス実施期間を示す（ここで、“：＝”は代入を表し、“；”は当該変数への代入終了を表す）。ｔ_ｓ：＝０は、メンテナンス実施期間（再スケジューリング対象期間）の開始日時である２０１８年６月１日１２時００分を示す。ｔ_ｅ：＝４１７５９は、メンテナンス実施期間（再スケジューリング対象期間）の終了日時である２０１８年６月３０日１１時５９分を示す。Ｔは、ｔ_ｓを基準にｔ_ｅまでの時刻を分単位に離散化した値の集合となる。

Ｐ：＝“ＰＭ０１”、“ＰＭ０２”、…；は、物理マシン名（ＰＭ名）の集合である（図中では各行が物理マシン名となる）。
ｍａｉｎｔＤｕｒａｔｉｏｎ_ｐ：＝（“ＰＭ０１” ６０）、（“ＰＭ０２” １２０）、…；は、物理マシン毎のメンテナンスの所要時間（単位は分）である。１つのレコードは、（物理マシン名（ＰＭ名） メンテナンスの所要時間）の組となる。なお、図中では１行が１つのレコードとなる（入力データに含まれる以降の他の変数についても同様である）。

ｃｐｕＣａｐ_ｐ：＝（“ＰＭ０１” ６４）、（“ＰＭ０２” ３２）、…；は、物理マシン毎のＣＰＵコア数である。１つのレコードは、（ＰＭ名 ＣＰＵコア数）の組となる。

ｒａｍＣａｐ_ｐ：＝（“ＰＭ０１” ２５６）、（“ＰＭ０２” １２８）、…；は、物理マシン毎のメモリ容量である。１つのレコードは、（ＰＭ名 メモリ容量）の組となる。

ｄｉｓｋＣａｐ_ｐ：＝（“ＰＭ０１” ３２０００）、（“ＰＭ０２” １２８０００）、…；は、物理マシン毎のディスク容量である。１つのレコードは、（ＰＭ名 ディスク容量）の組となる。

図２８は、入力データの例（その２）を示す図である。
入力データ１６２は、変数ＶおよびｉｎｉｔＡｃｃｏｍｍｏ_ｐｖを含む。
Ｖ：＝“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３”、“ｖｍ－６７”、…；は、仮想マシン名（ＶＭ名）の集合である。

ｉｎｉｔＡｃｃｏｍｍｏ_ｐｖ：＝（…、“ＰＭ０１” “ｍｙｓｑｌ－６７” １）、（“ＰＭ０２” “ｍｙｓｑｌ－６７” ０）、（“ＰＭ０１” “ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３” １）、（“ＰＭ０２” “ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３” ０）、…；は、各仮想マシンの初期配置先の物理マシンを示す。１つのレコードは、（ＰＭ名 仮想マシン名（ＶＭ名） ０ｏｒ１）の組となる（最後の値は、該当の物理マシンが該当の仮想マシンの初期配置先であれば“１”、初期配置先でなければ“０”である）。

図２９は、入力データの例（その３）を示す図である。
入力データ１６３は、変数ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖを含む。
ｍｉｇｒａｔｉｏｎＤｕｒａｔｉｏｎ_ｖ：＝…、（“ｓｅｒｖｅｒ－９０” １５）、（“ｍｙｓｑｌ－６７” １０）、…、（“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３” ２０）、（“ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３” ２０）、…；は、仮想マシン毎のＬＭの所要時間である。１つのレコードは、（ＶＭ名 ＬＭの所要時間（分））の組となる。

図３０は、入力データの例（その４）を示す図である。
入力データ１６４は、変数ｃｐｕＲｅｑ_ｖ、ｒａｍＲｅｑ_ｖおよびｄｉｓｋＲｅｑ_ｖを含む。

ｃｐｕＲｅｑ_ｖ：＝（“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３” ２）、（“ｖｍ－６７” ２）、…；は、仮想マシン毎に割り当てるＣＰＵコア数である。１つのレコードは、（ＶＭ名 ＣＰＵコア数）の組となる。

ｒａｍＲｅｑ_ｖ：＝（“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３” ３２）、（“ｖｍ－６７” ２）、…；は、仮想マシン毎に割り当てるメモリ容量である。１つのレコードは、（ＶＭ名 メモリ容量）となる。

ｄｉｓｋＲｅｑ_ｖ：＝（“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３” ２）、（“ｖｍ－６７” ３２）、…；は、仮想マシン毎に割り当てるディスク容量である。１つのレコードは、（ＶＭ名 ディスク容量）となる。

図３１は、入力データの例（その５）を示す図である。
入力データ１６５は、変数ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）、Ｇ_ａａ＿１およびＧ_ａｆ＿１を含む。

ａｖａｉｌＭｉｇｒａｔｉｏｎＴｉｍｅＳｌｏｔ_ｖ（ｔ）：＝…、（“ｍｙｓｑｌ－６７” ２７２９８ １）、（“ｍｙｓｑｌ－６７” ２７２９９ １）、（“ｍｙｓｑｌ－６７” ２７３００ ０）、（“ｍｙｓｑｌ－６７” ２７３０１ ０）、…；は、仮想マシンのＬＭの実施許容期間または実施回避期間を示す。実施許容は“１”であり、実施回避は“０”である。１つのレコードは、（ＶＭ名 時刻 ０ｏｒ１）となる。

ここで、図中の時刻“２７２９８”は、２０１８年６月２０日１０時５８分を示す。時刻“２７２９９”は、２０１８年６月２０日１０時５９分を示す。時刻“２７３００”は、２０１８年６月２０日１１時００分を示す。時刻“２７３０１”は、２０１８年６月２０日１１時０１分を示す。

Ｇ_ａａ＿１：＝“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－１３”、“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３”；は、ａｎｔｉ－ａｆｆｉｎｉｔｙルールの適用対象の１つ目のグループおよび当該グループに属する仮想マシンを示す。ａｎｔｉ－ａｆｆｉｎｉｔｙルールの適用対象の２つ目以降のグループも同様に設定される。

Ｇ_ａｆ＿１：＝“ａｃｃｏｕｎｔｉｎｇ－ｄｂ－０３”、“ａｃｃｏｕｎｔｉｎｇ－ｗｅｂ－０３”；は、ａｆｆｉｎｉｔｙルールの適用対象の１つ目のグループおよび当該グループに属する仮想マシンを示す。ａｆｆｉｎｉｔｙルールの適用対象の２つ目以降のグループも同様に設定される。

図３２は、入力データの例（その６）を示す図である。
入力データ１６６は、変数ａ_ｐｖ（ｔ）およびｌ_ｐｖ（ｔ）を含む。入力データ１６６におけるａ_ｐｖおよびｌ_ｐｖは、既存のＬＭスケジュールテーブル１５２に基づいて、ＬＭの実施日時の変更要望がない仮想マシンに対する制約として設定される。

ａ_ｐｖ（ｔ）＝…、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３８ １）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３９ １）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２４０ ０）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２４１ ０）、…；は、各ＰＭで稼働するＶＭを示す。１つのレコードは、（ＰＭ名 ＶＭ名 時刻 ０ｏｒ１）の組である（最後の値は、該当のＰＭ上で該当のＶＭが稼働している場合は“１”、稼働していない場合は“０”である）。

ここで、図中の時刻“２７２３８”は、２０１８年６月２０日９時５８分を示す。時刻“２７２３９”は、２０１８年６月２０日９時５９分を示す。時刻“２７２４０”は、２０１８年６月２０日１０時００分を示す。時刻“２７２４１”は、２０１８年６月２０日１０時０１分を示す。

ｌ_ｐｖ（ｔ）＝（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３８ ０）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３９ ０）、…、（“ＰＭ０２” “ｓｅｒｖｅｒ－９０” ２７２３８ ０）、（“ＰＭ０２” “ｓｅｒｖｅｒ－９０” ２７２３９ １）、（“ＰＭ０２” “ｓｅｒｖｅｒ－９０” ２７２４０ ０）、…；は、各仮想マシンの移動先物理マシンへのＬＭ完了時刻を示す。１つのレコードは、（ＰＭ名 ＶＭ名 時刻 ０ｏｒ１）の組である（最後の値は、該当のＰＭ上への該当のＶＭのＬＭが完了した時刻の場合は“１”、それ以外の場合は“０”である）。

図３３は、出力データの例（その１）を示す図である。
ソルバ部１２５は、制約条件生成部１２４により設定された制約充足問題を解くことで、出力データ１６７を出力する。出力データ１６７は、変数ｍ_ｐ（ｔ）およびａ_ｐｖ（ｔ）を含む。

ｍ_ｐ（ｔ）＝…、（“ＰＭ０１” ２７２６８ ０）、（“ＰＭ０１” ２７２６９ ０）、（“ＰＭ０１” ２７２７０ １）、（“ＰＭ０１ ” ２７２７１ １）、…；は、物理マシン毎のメンテナンス実施期間を示す。１つのレコードは、（ＰＭ名 時刻 ０ｏｒ１）の組である（最後の値は、該当ＰＭが該当時刻にメンテナンス中であれば“１”、メンテナンス中でなければ“０”である）。

ここで、図中の時刻“２７２６８”は、２０１８年６月２０日１０時２８分を示す。時刻“２７２６９”は、２０１８年６月２０日１０時２９分を示す。時刻“２７２７０”は、２０１８年６月２０日１０時３０分を示す。時刻“２７２７１”は、２０１８年６月２０日１０時３１分を示す。

ａ_ｐｖ（ｔ）＝…、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３８ １）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２３９ １）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２４０ ０）、（“ＰＭ０１” “ｓｅｒｖｅｒ－９０” ２７２４１ ０）、…；は、各ＰＭで稼働するＶＭを示す。１つのレコードは、（ＰＭ名 ＶＭ名 時刻 ０ｏｒ１）の組である（最後の値は、該当のＰＭ上で該当のＶＭが稼働している場合は“１”、稼働していない場合は“０”である）。

ここで、図中の時刻“２７２３８”は、２０１８年６月２０日９時５８分を示す。時刻“２７２３９”は、２０１８年６月２０日９時５９分を示す。時刻“２７２４０”は、２０１８年６月２０日１０時００分を示す。時刻“２７２４１”は、２０１８年６月２０日１０時０１分を示す。

図３４は、出力データの例（その２）を示す図である。
ソルバ部１２５は、制約条件生成部１２４により設定された制約充足問題を解くことで、更に、出力データ１６８を出力する。出力データ１６８は、変数ｌ_ｐｖ（ｔ）を含む。

ｌ_ｐｖ（ｔ）＝…、（“ＰＭ０１” “ｍｙｓｐｌ－６７” ２７２４８ ０）、（“ＰＭ０１” “ｍｙｓｐｌ－６７” ２７２４９ ０）、…、（“ＰＭ０２” “ｍｙｓｐｌ－６７” ２７２４８ ０）、（“ＰＭ０２” “ｍｙｓｐｌ－６７” ２７２４９ １）、（“ＰＭ０２” “ｍｙｓｐｌ－６７” ２７２５０ ０）、…；は、各仮想マシンの移動先物理マシンへのＬＭ完了時刻を示す。１つのレコードは、（ＰＭ名 ＶＭ名 時刻 ０ｏｒ１）の組である（最後の値は、該当のＰＭ上への該当のＶＭのＬＭが完了した時刻の場合は“１”、それ以外の場合は“０”である）。

ここで、図中の時刻“２７２３８”は、２０１８年６月２０日９時５８分を示す。時刻“２７２３９”は、２０１８年６月２０日９時５９分を示す。時刻“２７２４０”は、２０１８年６月２０日１０時００分を示す。時刻“２７２４１”は、２０１８年６月２０日１０時０１分を示す。時刻“２７２４８”は、２０１８年６月２０日１０時０８分を示す。時刻“２７２４９”は、２０１８年６月２０日１０時０９分を示す。時刻“２７２５０”は、２０１８年６月２０日１０時１０分を示す。時刻“２７２５１”は、２０１８年６月２０日１０時１１分を示す。

ソルバ部１２５は、出力データの内容から各仮想マシンに対するＬＭスケジュールを得る。例えば、ｌ_ｐｖ（ｔ）の出力結果によれば、“ｍｙｓｑｌ－６７”について“ＰＭ０２”へのＬＭ終了時刻は“２７２４９”である。また、仮想マシン構成テーブル１４２によれば、仮想マシン名“ｍｙｓｑｌ－６７”の仮想マシンのＬＭの所要時間は１０分である。したがって、ソルバ部１２５は、“ｍｙｓｑｌ－６７”に対するＬＭスケジュールを、時刻“２７２４０”～“２７２４９”の１０タイムスロットの期間と決定する。

ソルバ部１２５は、出力データで示される期間を年月日時分秒の形式に変換し、メンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４を作成する。また、スケジュール変更部１２８もソルバ部１２５と同様に、メンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４を作成する。ただし、前述のように、スケジュール変更部１２８は、準制約充足問題の求解や、メンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４の作成に、ソルバ部１２５の機能を用いてもよい。

スケジューラ１２０は、ソルバ部１２５またはスケジュール変更部１２８により作成したＬＭスケジュールを利用者に提示し、利用者による確認を促す。次に、管理サーバ１００により利用者端末５００に提供される画面の例を説明する。

図３５は、ＬＭスケジュールの表示画面の例を示す図である。
画面８００は、ＬＭスケジュールテーブル１５２（既存スケジュール）に基づいて、管理サーバ１００から利用者端末５００に対して提供される画面の例である。利用者端末５００は、画面８００に対応する画面情報を管理サーバ１００から受信し、当該画面情報に基づいて、利用者端末５００に内蔵または接続されたディスプレイ（表示装置）により、画面８００を表示する。ここで、利用者端末５００は、ユーザＩＤ「ｕｓｅｒ３」の利用者によって利用されるものとし、当該利用者のユーザ名を「ＡＡＡ」とする。

スケジューラ１２０は、仮想マシン構成テーブル１４２（または、仮想マシン稼働テーブル１４３）に基づいて、ＬＭスケジュールテーブル１５２に登録された各仮想マシンの利用者のユーザＩＤを特定する。また、ユーザＩＤに対応する利用者のユーザ名や端末のアドレスの情報は、ＲＡＭ１０２またはＨＤＤ１０３に予め格納されている。スケジューラ１２０は、当該情報を参照することで、ユーザ名や画面情報の送信先を特定する。

画面８００は、ＶＭシンボル８０１，８０２、ＬＭシンボル８０３，８０４およびボタン８０５，８０６を有する。
ＶＭシンボル８０１，８０２は、該当の利用者が利用する、ＬＭ対象の仮想マシンを示す。例えば、ＶＭシンボル８０１は、仮想マシン名「ｓｅｒｖｅｒ－９０」の仮想マシンを示す。また、ＶＭシンボル８０２は、仮想マシン名「ｍｙｓｑｌ－６７」の仮想マシンを示す。画面８００の例では、ＶＭシンボル８０１，８０２それぞれの行の左側から右側へ向かう方向を時系列の正方向として、各仮想マシンのＬＭスケジュールを示す。

ＬＭシンボル８０３，８０４は、各仮想マシンのＬＭの実施予定の日時を示す。例えば、ＬＭシンボル８０３は、仮想マシン名「ｓｅｒｖｅｒ－９０」の仮想マシンに対して、２０１８年６月２０日９時４５分～同日９時５９分にＬＭを実施することを示す。また、例えば、ＬＭシンボル８０４は、仮想マシン名「ｍｙｓｑｌ－６７」の仮想マシンに対して、２０１８年６月２０日１０時５５分～同日１１時０４分にＬＭを実施することを示す。

ボタン８０５は、画面８００のＬＭスケジュールの確定を入力するためのボタンである。利用者端末５００は、利用者によるボタン８０５の入力を受け付けると、画面８００に表示された各仮想マシンについて、ＬＭスケジュールの確定メッセージを管理サーバ１００に送信する。

ボタン８０６は、画面８００のＬＭスケジュールを変更するための変更入力画面へ遷移するためのボタンである。
図３６は、ＬＭスケジュールの変更入力画面の例を示す図である。

画面８１０は、画面８００のＬＭスケジュールに対する変更要望の内容を入力するための画面である。画面８１０は、利用者によるボタン８０６への入力に応じて、管理サーバ１００から利用者端末５００に提供される画面である。画面８１０は、ＶＭシンボル８１１，８１２、ＬＭシンボル８１３，８１４、ＬＭ実施回避日時シンボル８１５およびボタン８１６，８１７を有する。

ＶＭシンボル８１１は、ＶＭシンボル８０１に相当する。ＶＭシンボル８１２は、ＶＭシンボル８０２に相当する。ＬＭシンボル８１３は、ＬＭシンボル８０３に相当する。ＬＭシンボル８１４は、ＬＭシンボル８０４に相当する。

ＬＭ実施回避日時シンボル８１５は、利用者によるＬＭ実施回避日時の選択を受け付けるためのシンボルである。例えば、利用者は、利用者端末５００に接続されたポインティングデバイスを用いて、所望の仮想マシンの行にＬＭ実施回避日時シンボル８１５を配置する。そして、利用者は、当該ポインティングデバイスを用いて、ＬＭ実施回避日時シンボル８１５の横方向（行方向）の幅を変えることで、当該仮想マシンに対するＬＭ実施回避日時を選択する。利用者は、ＬＭ実施回避日時シンボル８１５をＬＭシンボル８１４に重ねて配置することができる。ＬＭ実施回避日時シンボル８１５の例では、仮想マシン名“ｍｙｓｑｌ－６７”の仮想マシンに対するＬＭ実施回避日時として、２０１８年６月２０日１０時４０分～同日１２時５９分が選択されている。

ボタン８１６は、ＬＭ実施回避日時シンボル８１５によるＬＭ実施回避日時の選択を解除するためのボタンである。
ボタン８１７は、ＬＭ実施回避日時シンボル８１５を用いて選択されたＬＭ実施回避日時を設定するためのボタンである。利用者端末５００は、ボタン８１７に対する入力を受け付けると、選択された仮想マシンのＬＭ実施回避日時を示すＬＭ実施日時変更要望情報１３３を含むメッセージを管理サーバ１００に送信する。

管理サーバ１００は、画面８１０によりＬＭ実施日時変更要望情報１３３を受け付けると、ＬＭ実施時間に関する制約情報を再作成し、ＬＭ実施日時変更要望情報１３３が入力された仮想マシンについてＬＭスケジュールを更新する。管理サーバ１００は、再作成した制約情報に基づいて、当該制約情報を満たすＬＭスケジュールを作成できない場合、制約情報から準制約情報を生成して、ＬＭスケジュールを更新する。管理サーバ１００は、更新したＬＭスケジュールを利用者に再度提示する。

図３７は、ＬＭスケジュールの変更の結果表示画面の例を示す図である。
画面８２０は、ＬＭスケジュールテーブル１５４（変更後のスケジュール）に基づいて、管理サーバ１００から利用者端末５００に対して提供される画面の例である。画面８２０は、画面８１０によるＬＭ実施回避日時の選択に応じて再調整されたＬＭスケジュールを示す。画面８２０は、ＶＭシンボル８２１，８２２、ＬＭシンボル８２３，８２４、ＬＭ実施回避日時シンボル８２５およびボタン８２６を有する。

ＶＭシンボル８２１は、ＶＭシンボル８０１に相当する。ＶＭシンボル８２２は、ＶＭシンボル８０２に相当する。ＬＭシンボル８２３は、ＬＭシンボル８０３に相当する。
ＬＭシンボル８２４は、仮想マシン名「ｍｙｓｑｌ－６７」の仮想マシンに対して、２０１８年６月２０日１０時００分～同日１０時０９分にＬＭを実施することを示す。

ＬＭ実施回避日時シンボル８２５は、ＬＭ実施回避日時シンボル８１５に相当する。
なお、画面８１０において、仮想マシン名「ｓｅｒｖｅｒ－９０」の仮想マシンに対しては、ＬＭ実施回避日時が選択されなかったため、仮想マシン名「ｓｅｒｖｅｒ－９０」の仮想マシンについては最初に決定されたＬＭスケジュールから更新されていない。ただし、仮想マシン名「ｓｅｒｖｅｒ－９０」の仮想マシンに対してＬＭ実施日時が変更されることもある。

ボタン８２６は、仮想マシンのＬＭスケジュールの確認を終了するためのボタンである。利用者端末５００は、ボタン８２６の入力を受け付けると、画面８２０を閉じる。
上記の例では、利用者端末５００に提供される画面８００，８１０，８２０を例示したが、利用者端末６００にも当該利用者端末６００の利用者が利用する仮想マシンに関してＬＭスケジュールを確認するための画面が提供される。

図３８は、メンテナンススケジュール画面の例を示す図である。
画面９００は、メンテナンススケジュールテーブル１５３およびＬＭスケジュールテーブル１５４（変更後のスケジュール）に基づいて、管理サーバ１００から運用者端末７００に対して提供される画面の例である。画面９００は、画面８２０で示される更新後のＬＭスケジュールテーブル１５４に対応する物理マシンのメンテナンススケジュールを示す。運用者端末７００は、画面９００を描画するための画面情報を管理サーバ１００から受信し、当該画面情報に基づいて、運用者端末７００に内蔵または接続されたディスプレイ（表示装置）により、画面９００を表示する。ここで、運用者のユーザ名を「ａａａ」とする。

画面９００は、ＰＭシンボル９０１，９０２、ＶＭスケジュールシンボル９１１，９１２およびメンテナンスシンボル９１３を有する。
ＰＭシンボル９０１，９０２は、メンテナンス対象の物理マシンを示す。例えば、ＰＭシンボル９０１は、物理マシン名「ＰＭ０１」の物理マシンを示す。また、ＰＭシンボル９０２は、物理マシン名「ＰＭ０２」の物理マシンを示す。画面９００の例では、ＰＭシンボル９０１，９０２それぞれの行の左側から右側へ向かう方向を時系列の正方向として、各物理マシン上の仮想マシンの稼働予定、ＬＭ予定およびメンテナンススケジュールを示す。

ＶＭスケジュールシンボル９１１，９１２は、各仮想マシンの稼働予定およびＬＭ予定を示す。ＶＭスケジュールシンボル９１１，９１２は、再スケジューリング後のＬＭスケジュールテーブル１５４の内容を反映している。例えば、ＶＭスケジュールシンボル９１１は、物理マシン名「ＰＭ０１」上の複数の仮想マシンの稼働予定と、当該複数の仮想マシンのＬＭ予定とを示す。また、ＶＭスケジュールシンボル９１２は、物理マシン名「ＰＭ０２」上の複数の仮想マシンの稼働予定と、当該複数の仮想マシンのＬＭ予定とを示す。ＶＭスケジュールシンボル９１１，９１２によれば、運用者は、各仮想マシンがＬＭ実施前には物理マシン名「ＰＭ０１」の物理マシンで稼働し、ＬＭ実施後には物理マシン名「ＰＭ０２」の物理マシンで稼働することを把握できる。

メンテナンスシンボル９１３は、物理マシンのメンテナンススケジュールを示すシンボルである。メンテナンスシンボル９１３は、メンテナンススケジュールテーブル１５３の内容を反映しており、物理マシン名「ＰＭ０１」の物理マシンに対するメンテナンススケジュールを示す。メンテナンスシンボル９１３の例では、物理マシン名「ＰＭ０１」の物理マシンに対して、２０１８年６月２０日１０時３０分～同日１１時２９分の期間に、メンテナンスを行うことを示す。

このように、管理サーバ１００は、再スケジューリング結果を生成する際、準制約充足問題（準制約情報）と、複数の物理マシンそれぞれのメンテナンスの所要時間とに基づいて、メンテナンスの実施期間のうち、各物理マシンに対してメンテナンスを行う期間を決定する。管理サーバ１００は、こうして決定した期間を、運用者端末７００に出力することで、再スケジューリング後の各物理マシンのメンテナンスを行うべき期間を運用者に適切に提示することができる。

以上で説明したように、管理サーバ１００は、仮想マシンのＬＭを伴うクラウド基盤のメンテナンスについて、事前に日程調整したＬＭ実施予定時刻を変更する旨の利用者からの要求を受け付ける。管理サーバ１００は、要求があった仮想マシンについては希望の時間帯にＬＭを実施するように制約化し、それ以外については予定を変更しないように制約化して再スケジューリングを行う。このとき、運用側でメンテナンス作業時に守らなければならない要件を満たすことができなければ、管理サーバ１００は、ＬＭ実施時刻に関する極小充足不能コアを抽出し、その中から下位優先度の仮想マシンについて制約を取り除いて再スケジューリングする。これにより、ＬＭスケジュールの変更箇所を最小限に抑え、仮想マシンの既存の移動予定への影響を抑えた再スケジューリングが可能になる。

ところで、システム運用において、管理サーバ１００が当初決定したスケジュールによって、ＬＭおよび物理マシンのメンテナンスが予定通りに実施される保証はない。例えば、上記のように、利用者による仮想マシンの利用予定の変更により、当初スケジューリングされた仮想マシンのＬＭの時間帯を別の時間帯に変更してほしいという要望が発生することもある。このように、システムの運用では、状況の変化に応じてスケジュールの修正が必要となる。

しかし、制約を充足するようにスケジュールを修正するには、修正要因の箇所以外にも変更が必要になる可能性がある。
再スケジューリングの方法として、動的重み付き制約充足問題による再スケジューリングも考えられる。動的重み付き制約充足問題による再スケジューリングの方法には、例えば、下記の文献２，３が参考になる。

（文献２）特開２００５－２６７５９１号公報
（文献３）Hattori，Ito，Ozono and Shintani， “A Nurse Scheduling System Based on Dynamic Constraint Satisfaction Problem,” In Proc. IEA/AIE 2005，pp.799-808，2005.
文献２，３の方法における再スケジューリングでは、制約に重みを付加し、違反する制約の重みの合計が最小化されるように解を求める動的な制約充足問題を扱う。しかし、文献２，３の方法では、制約に対する最適な重み値を一意に決めることは容易でない。重みは再スケジューリング問題に依存するからである。このため、文献２，３の方法では、最適な再スケジューリング結果を得るには、問題毎に重みの調整が必要となる。また、再スケジューリング失敗（充足不能）時に、適当な重み調整では充足可能になる保証がなく、大規模な問題での最適な重み探索は非現実的となる。

そこで、管理サーバ１００は、ＬＭの再スケジューリング時に与えられた制約充足問題が充足不能であるとき、制約充足問題における制約集合から極小充足不能コアを抽出する。管理サーバ１００は、極小充足不能コアに含まれる制約を１つ取り除いた再スケジューリング問題（準制約充足問題）をｋ種類作成し、ｋ種類の再スケジューリング問題について求解を実行する。このとき、上記のように、管理サーバ１００は、既存のＬＭのスケジュールに対する変更の影響を抑えるために、式（１８）（１９）などで表される目的関数を用いる。そして、管理サーバ１００は、求解した問題の中で変更の影響を最小限に抑えることができる結果を採用する。これにより、変更対象の仮想マシンの変更要望を受け入れつつ、他の仮想マシンの既存のスケジュールへの影響を抑えた再スケジューリングが可能になる。

このとき、極小充足不能コアに属する全ての制約ではなく、そのうちの一部の制約を除外対象とすることで、極小充足不能コアに属する全ての制約を除外対象とするよりも、再スケジューリングの処理を高速化できる。特に、仮想マシンの優先度に応じて、除外対象の制約を選択することで、例えば、重要な処理を実行する仮想マシンの制約が除外対象になる可能性を低減でき、仮想マシンの利用に対する影響を一層抑えられる。

なお、第１の実施の形態の情報処理は、処理部１２にプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、ＣＰＵ１０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体９３に記録できる。

例えば、プログラムを記録した記録媒体９３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体９３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＨＤＤ１０３などの記憶装置に格納し（インストールし）、当該記憶装置からプログラムを読み込んで実行してもよい。

１０ スケジュール装置
１１ 記憶部
１２ 処理部
２０，３０，４０ 物理マシン
２１，３１，４１ 仮想マシン
５０ 端末装置
６１ 既存スケジュール
６２ 変更情報
７０ 制約情報
７１，７２，７３ 準制約情報
Ｎ１ ネットワーク
Ｕ１ 利用者

Claims (10)

1. コンピュータに、
   複数の物理マシンの間での複数の仮想マシンの移動の時間帯を示す既存スケジュールに対して、仮想マシンの移動の時間帯の変更に関する変更情報を取得し、
   前記変更情報と前記既存スケジュールにおける前記仮想マシン以外の、前記変更の対象外である他の仮想マシンの移動の時間帯とに応じた制約群を含む制約情報を生成し、
   前記制約情報のうち、前記制約群に含まれる制約を１つずつ除外した複数の準制約情報を生成し、
   生成した複数の準制約情報それぞれに基づいて、前記複数の仮想マシンの移動の再スケジューリングを行うことで、準制約情報毎に再スケジューリング結果を生成し、
   複数の再スケジューリング結果のうち、前記再スケジューリング結果および前記既存スケジュールにおける前記変更の対象外である前記他の仮想マシンの移動の予定時刻の差が小さくなる前記再スケジューリング結果を出力する、
   処理を実行させるスケジュールプログラム。
2. 前記複数の準制約情報の生成では、前記制約情報を充足する前記再スケジューリング結果を得られない場合に、前記制約群から抽出された極小充足不能コアに含まれる制約を除外対象として選択する、
   請求項１記載のスケジュールプログラム。
3. 前記除外対象の制約の選択では、前記極小充足不能コアに含まれる全制約のうちの一部の制約を、前記複数の仮想マシンそれぞれの優先度に基づいて選択する、
   請求項２記載のスケジュールプログラム。
4. 前記再スケジューリング結果の出力では、前記再スケジューリング結果および前記既存スケジュールにおける前記他の仮想マシンの移動の予定時刻の第１の差、または、前記変更情報および前記再スケジューリング結果における前記仮想マシンの移動の時間帯の第２の差が小さくなる前記再スケジューリング結果を出力する、
   請求項１記載のスケジュールプログラム。
5. 前記再スケジューリング結果の出力では、前記第１の差、または、前記第２の差の何れかが最小である前記再スケジューリング結果を出力する、
   請求項４記載のスケジュールプログラム。
6. 前記変更情報は、前記仮想マシンの移動を許容する時間帯、または、前記仮想マシンの移動を回避する時間帯を示す情報を含む、
   請求項１乃至５の何れか１項に記載のスケジュールプログラム。
7. 前記制約情報は、前記複数の物理マシンのメンテナンスの実施期間、前記複数の物理マシンおよび前記複数の仮想マシンの構成情報および物理マシン間の前記仮想マシンの移動の所要時間に関する制約を含む、
   請求項１乃至６の何れか１項に記載のスケジュールプログラム。
8. 前記再スケジューリング結果の生成では、準制約情報と、前記複数の物理マシンそれぞれのメンテナンスの所要時間とに基づいて、前記メンテナンスの実施期間のうち、前記複数の物理マシンそれぞれに対して前記メンテナンスを行う期間を決定する、
   請求項１乃至７の何れか１項に記載のスケジュールプログラム。
9. 複数の物理マシンの間での複数の仮想マシンの移動の時間帯を示す既存スケジュールの情報を記憶する記憶部と、
   前記既存スケジュールに対して、仮想マシンの移動の時間帯の変更に関する変更情報を取得し、前記変更情報と前記既存スケジュールにおける前記仮想マシン以外の、前記変更の対象外である他の仮想マシンの移動の時間帯とに応じた制約群を含む制約情報を生成し、前記制約情報のうち、前記制約群に含まれる制約を１つずつ除外した複数の準制約情報を生成し、生成した複数の準制約情報それぞれに基づいて、前記複数の仮想マシンの移動の再スケジューリングを行うことで、準制約情報毎に再スケジューリング結果を生成し、複数の再スケジューリング結果のうち、前記再スケジューリング結果および前記既存スケジュールにおける前記変更の対象外である前記他の仮想マシンの移動の予定時刻の差が小さくなる前記再スケジューリング結果を出力する処理部と、
   を有するスケジュール装置。
10. コンピュータが、
    複数の物理マシンの間での複数の仮想マシンの移動の時間帯を示す既存スケジュールに対して、仮想マシンの移動の時間帯の変更に関する変更情報を取得し、
    前記変更情報と前記既存スケジュールにおける前記仮想マシン以外の、前記変更の対象外である他の仮想マシンの移動の時間帯とに応じた制約群を含む制約情報を生成し、
    前記制約情報のうち、前記制約群に含まれる制約を１つずつ除外した複数の準制約情報を生成し、
    生成した複数の準制約情報それぞれに基づいて、前記複数の仮想マシンの移動の再スケジューリングを行うことで、準制約情報毎に再スケジューリング結果を生成し、
    複数の再スケジューリング結果のうち、前記再スケジューリング結果および前記既存スケジュールにおける前記変更の対象外である前記他の仮想マシンの移動の予定時刻の差が小さくなる前記再スケジューリング結果を出力する、
    スケジュール方法。

Images