(57)【要約】【課題】大規模なシステムの変更計画作成における計算量を削減できる高速変更計画システムを提供する。【解決手段】高速変更計画システム１０は、１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部１１と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部１２とを含む。状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、当該状態マシン以外の状態マシンに関連し、状態マシン群分割部１１は、複数の状態マシンに含まれる１つの状態マシンから、複数の状態マシン間の遷移条件が関連する状態マシンを、遷移条件の数だけ順に辿った時に１つの状態マシンに戻る場合、複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割してもよい。【選択図】図２１
2015215886.tif 000002
【特許請求の範囲】
【請求項１】
１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部と、
分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部とを含む
ことを特徴とする高速変更計画システム。
【請求項２】
状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、
状態マシン群分割部は、複数の状態マシンに含まれる１つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記１つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する
請求項１記載の高速変更計画システム。
【請求項３】
状態マシン群分割部は、状態マシングループ内の状態マシンに関連する遷移条件に従って遷移する状態を含む仮状態マシンを前記状態マシングループに追加し、
状態マシン群統合部は、前記仮状態マシンの元である状態マシングループから導出された遷移順序と、前記仮状態マシンが追加された状態マシングループから導出された遷移順序とを統合する
請求項１記載の高速変更計画システム。
【請求項４】
状態マシン群統合部は、所定の条件に従う状態マシングループが複数ある場合、複数の前記状態マシングループから遷移順序をそれぞれ導出する処理を並列的に行う指示を外部装置に出力する
請求項１記載の高速変更計画システム。
【請求項５】
所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されており、かつ前記他の状態マシングループから既に遷移順序が導出されていることである
請求項４記載の高速変更計画システム。
【請求項６】
所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されていないことである
請求項４記載の高速変更計画システム。
【請求項７】
１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、
分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する
ことを特徴とする高速変更計画方法。
【請求項８】
状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、
複数の状態マシンに含まれる１つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記１つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する
請求項７記載の高速変更計画方法。
【請求項９】
コンピュータで実行されるときに、
１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、
分割された前記状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する
高速変更計画プログラム
を記録した非一時的なコンピュータ読み取り可能な記録媒体。
【請求項１０】
コンピュータで実行されるときに、
状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、前記状態マシン以外の状態マシンに関連し、
複数の状態マシンに含まれる１つの状態マシンから、前記複数の状態マシン間の遷移条件が関連する状態マシンを、前記遷移条件の数だけ順に辿った時に前記１つの状態マシンに戻る場合、前記複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割する
請求項９記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速変更計画システム、高速変更計画方法および高速変更計画プログラムに関する。
【背景技術】
【０００２】
変更管理の目的は、あるシステムを変更する際に生じる、変更するシステムの管理者および変更作業者の手間と、変更するシステムの利用者への影響を少なくすることである。変更するシステムが、例えば、複数の部品から構成されるような複雑なシステムである場合、変更作業は複雑になる。変更作業が複雑になると、作業者の手間や、作業者の作業を監督する管理者の手間は増大する。その結果、システム利用者への影響も増大する。
【０００３】
特に、システムを構成する部品間に依存性が存在する場合、各部品に対する変更作業の順序が問題になるため、作業が複雑になりやすい。部品間の依存性は、例えば、部品Ａと部品Ｂがある場合、部品Ａが正しく機能するためには部品Ｂが正しく機能することが必要であるというような、２つの要素間の関係性である。
【０００４】
上記の例の場合、部品Ａは部品Ｂに依存するという。このような部品Ａと部品Ｂから構成されるシステムを構築する作業では、最初に部品Ｂを構築し、次に部品Ａを構築するというように、実施する作業に順序性が求められる。
【０００５】
このような依存性を考慮しつつ、システムの変更に必要な作業の計画を自動的に作成するシステムを変更計画システムと呼ぶ。ただし、本発明における変更計画システムは、各部品の現在の状態（現在状態）と、変更後の要求される状態（要求状態）とを入力データとして、必要な作業と適切な作業手順を導出するシステムである。変更計画システムでは、予め部品間の依存性に関する情報、および部品に対する作業に関する情報が定義されている。
【０００６】
上記の変更計画システムを用いることで、管理者は、複雑な変更作業の実施に効果的な作業手順を効率的に作成できる。また、作業者も、作成された効果的な作業手順に基づいて、効率的に作業を実施できる。その結果、変更されるシステムの利用者への影響も少なくなることが期待される。
【０００７】
このような変更計画システムに関して、既に多数の関連研究や関連製品が知られている。非特許文献１には、管理対象のシステムを複数の状態マシン群として定義する方法が記載されている。非特許文献１に記載された方法では、各状態マシン群が持つ遷移の遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態を用いて記述される。
【０００８】
状態マシンは、システムを構成する部品を表す。状態マシンの状態は、部品がとり得る状態を表す。また、遷移には、部品の状態を変更する際の作業の情報が含まれる。遷移条件は、遷移に含まれる情報に対応する作業が持つ依存性を表す。
【０００９】
以上のようなシステムの定義方法に基づく変更計画は、計画可能な状況が広範である点や、定義の再利用可能な点において、他の手法を用いた変更計画よりも有効であると期待される。本発明において、上記の定義方法に基づくシステムが対象のシステムになる。以下、対象になるシステムを単に変更計画システムと呼ぶ。
【００１０】
状態マシン群として記述されたシステムの変更計画は、全ての状態マシンが現在状態を持ち、少なくとも１つの状態マシンが要求状態を持つとき、遷移条件を満たしつつ要求状態が指定された全ての状態マシンを現在状態から要求状態に遷移させる遷移順序を求めることによって作成される。非特許文献１には、このような変更計画の作成方法が記載されている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】S. Hagen and A. Kemper, “Model-based planning for state-relatedchanges to infrastructure and software as a service instances in largedata centers,” in Cloud Computing (CLOUD), 2010 IEEE 3rd InternationalConference on, July 2010, pp. 11-18.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
非特許文献１に記載されている変更計画システムでは、変更計画の作成に必要な計算量が、対象にする状態マシンの数が増えると指数関数的に増大する点が問題になる。すなわち、大規模なシステムの変更計画を作成するコンピュータは、膨大な計算量が原因で、計算不能になる。非特許文献１に記載されている方法がそのまま用いられた場合、大規模なシステムの変更計画の作成は困難である。
【００１３】
特に、併せて計算することが求められる状態マシンの数を削減することによって変更計画の作成における計算量を削減する、特定の計画手段に適用が限定されない、一般的な計算の効率化手法を明らかにすることが課題である。
【００１４】
そこで、本発明は、大規模なシステムの変更計画作成における計算量を削減できる高速変更計画システム、高速変更計画方法および高速変更計画プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明による高速変更計画システムは、１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部とを含むことを特徴とする。
【００１６】
本発明による高速変更計画方法は、１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合することを特徴とする。
【００１７】
本発明による高速変更計画プログラムを記録した非一時的なコンピュータ読み取り可能な記録媒体は、コンピュータで実行されるときに、１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割し、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する高速変更計画プログラムを記憶する。
【発明の効果】
【００１８】
本発明によれば、大規模なシステムの変更計画作成における計算量を削減できる。
【図面の簡単な説明】
【００１９】
【図１】本発明による高速変更計画システムの第１の実施形態の構成例を示すブロック図である。
【図２】状態マシン群の概念を示す説明図である。
【図３】状態マシン群のテキストによる定義の一例を示す説明図である。
【図４】遷移順序の導出結果の一例を示す説明図である。
【図５】状態マシン群の分割により生成された状態マシングループ群の一例を示す説明図である。
【図６】統合された遷移順序を含む状態マシングループ群の一例を示す説明図である。
【図７】生成された仮状態マシンを含む状態マシングループの一例を示す説明図である。
【図８】状態マシングループごとの遷移順序の統合結果の一例を示す説明図である。
【図９】遷移順序の統合結果の単一の遷移順序への変換結果の一例を示す説明図である。
【図１０】統合された遷移順序を含む状態マシングループ群の他の一例を示す説明図である。
【図１１】生成された仮状態マシンを含む状態マシングループの他の一例を示す説明図である。
【図１２】状態マシングループごとの遷移順序の統合結果の他の一例を示す説明図である。
【図１３】遷移順序の統合結果の単一の遷移順序への変換結果の他の一例を示す説明図である。
【図１４】高速変更計画システム１００による状態マシン群の変更計画処理の動作を示すフローチャートである。
【図１５】高速変更計画システム１００による状態マシン群の分割処理の動作を示すフローチャートである。
【図１６】高速変更計画システム１００による状態マシンの状態マシングループ割り当て処理の動作を示すフローチャートである。
【図１７】状態マシンの状態マシングループへの割り当て時に使用されるスタックの一例を示す説明図である。
【図１８】高速変更計画システム１００による遷移順序の導出処理と統合処理の動作を示すフローチャートである。
【図１９】本発明による高速変更計画システムの第２の実施形態の構成例を示すブロック図である。
【図２０】遷移順序を並列計算可能な状態マシングループ群の一例を示す説明図である。
【図２１】本発明による高速変更計画システムの概要を示すブロック図である。
【発明を実施するための形態】
【００２０】
実施形態１．
［構成の説明］
以下、本発明の第１の実施形態を、図面を参照して説明する。図１は、本発明による高速変更計画システムの第１の実施形態の構成例を示すブロック図である。図１に示す高速変更計画システム１００は、状態マシン群分割部１０１と、状態マシン群統合部１０２とを含む。
【００２１】
状態マシン群分割部１０１は、状態マシン群を状態マシングループ群に分割する機能を有する。
【００２２】
状態マシン群統合部１０２は、状態マシングループごとに導出された遷移順序を統合する機能を有する。
【００２３】
状態マシン群統合部１０２は、状態マシン群分割部１０１と通信ネットワークなどを介して通信可能に接続されている。また、状態マシン群統合部１０２は、高速変更計画システム１００の外部に存在する入出力部２０１および遷移順序導出部２０２とも、通信ネットワークなどを介して通信可能に接続されている。
【００２４】
遷移順序導出部２０２は、状態マシン間の遷移条件を満たしつつ、要求状態が指定された全ての状態マシンを要求状態に遷移させる遷移順序を導出する機能を有する。
【００２５】
状態マシン群統合部１０２は、入出力部２０１を介して入力された状態マシン群を受信する。状態マシン群統合部１０２は、受信した状態マシン群を、状態マシン群分割部１０１に出力する。
【００２６】
状態マシン群分割部１０１は、入力された状態マシン群を、複数の状態マシンを含む状態マシングループにそれぞれ分割する。状態マシン群分割部１０１は、生成した状態マシングループ群を状態マシン群統合部１０２に返す。
【００２７】
次いで、状態マシン群統合部１０２は、入力された状態マシングループ群から状態マシングループを一つずつ順に取り出す。状態マシン群統合部１０２は、取り出した状態マシングループを遷移順序導出部２０２に送信する。
【００２８】
遷移順序導出部２０２は、受信した状態マシングループに基づいて遷移順序を導出する。遷移順序導出部２０２は、導出した遷移順序を状態マシン群統合部１０２に返す。
【００２９】
次いで、状態マシン群統合部１０２は、遷移順序導出部２０２から受信した複数の遷移順序を統合する。状態マシン群統合部１０２は、統合した遷移順序を単一の遷移順序に変換する。統合と変換を繰り返した後、状態マシン群統合部１０２は、最終的に得られた単一の遷移順序を入出力部２０１に送信する。入出力部２０１は、受信した遷移順序を出力する。
【００３０】
本実施形態における状態マシン群は、管理対象になるシステム、および管理対象になるシステムに対する変更要求に対応する。状態マシン群は、１または複数の状態マシンから構成される。状態マシンは、システムを構成する部品を示す。
【００３１】
状態マシンは、複数の状態をとりうる。状態は、同一状態マシン内の他の状態に遷移可能である。状態マシンには、必ず１つの現在状態があり、状態マシンは、任意個（０でもよい。）の要求状態に遷移可能である。すなわち、状態マシンは、複数の状態を含むといえる。ただし、要求状態が複数指定された場合、要求状態は、指定されたいずれかの状態であればよい。要求状態が指定されない場合、要求状態は、どの状態でもよい。また、遷移の遷移条件は、遷移が含まれる状態マシン以外の状態マシン内の状態によって指定される。
【００３２】
図２は、状態マシン群の概念を示す説明図である。図２において、状態マシンを長方形で表す。また、状態を楕円形で表す。また、遷移を実線の矢印で表す。また、遷移条件を点線の矢印で表す。また、現在状態を破線の楕円形で表す。また、要求状態を黒塗りの楕円形で表す。また、遷移を示す矢印の途中に存在する丸印は、遷移条件の矢印の始点を示す。他の図においても、図２と同じ方法で状態マシンなどが示される。
【００３３】
図２は、"e1"と"e2"の２つの状態マシンから構成される状態マシン群を示す。"e1"と"e2"は、共に"s1"と"s2"の２つの状態を含む。
【００３４】
図２に示すように、"e1"における"s1"は、"s2"への遷移を含む。また、"e2"における"s1"と"s2"は、互いの状態への遷移を含む。また、"e2"の"s1"から"s2"への遷移は、"e1"の状態"s2"を遷移条件にする。また、"e1"は、"s1"を現在状態にする。また、"e2"は、"s1"を現在状態にし、"s2"を要求状態にする。
【００３５】
以下、便宜的に、例えば、状態マシン"e1"の状態"s1"のことを"e1(s1)"と記載する。また、状態マシン"e1"の状態"s1"から状態"s2"への遷移を、"e1(s1,s2)"と記載する。
【００３６】
図３は、状態マシン群のテキストによる定義の一例を示す説明図である。図３は、XML(Extensible Markup Language)形式を用いた表現の一例として、図２に示す状態マシン群の定義例を示す。
【００３７】
図３に示すように、例えば、状態マシンは、"stateMachine"タグによって表される。また、状態マシンのIDは、"stateMachine"の"id"属性によって表される。また、状態マシンが持つ状態は、"stateMachine"タグの子要素としての"state"タグによって表される。また、状態のIDは、"state"の"id"属性によって表される。
【００３８】
また、図３に示すように、状態が持つ遷移は、"state"タグの子要素としての"transition"タグによって表される。また、遷移先の状態を示すIDは、"transition"の"to"属性によって表される。
【００３９】
また、図３に示すように、遷移が持つ遷移条件は、"transition"タグの子要素としての"conditions"タグによって表される。遷移が状態マシン"e1"の状態"s2"を遷移条件にする場合、遷移条件は、"conditions"タグの子要素として"depends"タグを記述し、"depends"の"on"属性に"e1(s2)"を記述することによって表される。１つの遷移が複数の遷移条件を持つ場合、複数の遷移条件を記述するには、"conditions"タグの子要素として複数の"depends"タグを記述すればよい。
【００４０】
本実施形態における状態マシン群に基づくシステムの変更計画の作成は、常に全ての遷移条件を満たしつつ、要求状態が指定された全ての状態マシンの状態を現在状態から要求状態へ遷移させるような遷移順序を発見することによって達成される。図２に示す状態マシン群の例であれば、"(e1(s1,s2), e2(s1,s2))"という遷移順序が、最も単純な唯一の解になる。
【００４１】
図４は、遷移順序の導出結果の一例を示す説明図である。図４において、角丸四角形は遷移を示す。また、遷移間の矢印は、遷移間の依存性を表す。すなわち、遷移間の矢印は、"e1(s1,s2)"が実施された後にのみ"e2(s1,s2)"が実施されるという関係性を示す。
【００４２】
図５は、状態マシン群の分割により生成された状態マシングループ群の一例を示す説明図である。図５は、"e1"と"e2"と"e3"と"e4"の４つの状態マシンから構成される状態マシン群が、"G1"と"G2"と"G3"の３つの状態マシングループに分割された様子を示す。なお、図５は図２と異なり、状態マシン自体から他の状態マシン内の状態に関連する遷移条件に対応する矢印を示す。矢印は、状態マシン内の全ての遷移が、矢印に対応する遷移条件と同様の遷移条件を持つことを示す。
【００４３】
本実施形態における遷移条件は、遷移条件として状態が指定される状態マシンに対して、指定された状態への遷移を誘発する。誘発する側の状態マシンと誘発される側の状態マシンの関係が一方的である場合、誘発する側の状態マシンの遷移順序を決定した後に、誘発される側の状態マシンの遷移順序を決定しても、最終的に得られる遷移順序に影響はない。しかし、互いに遷移を誘発する複数の状態マシンを含む状態マシン群の場合、状態マシン間の全ての関係を考慮しつつ遷移順序を決定することが求められる。
【００４４】
そこで、本実施形態における状態マシン群の分割は、状態マシン間の複数の遷移条件が循環を構成しているか否かが考慮された上で実施される。複数の遷移条件が循環を構成する全ての状態マシンが同一の状態マシングループに属するように、状態マシン群は分割される。
【００４５】
図５に示す例では、例えば、"e1"は"e2"への遷移条件を持つが、"e2"から派生する遷移条件を辿って"e1"へ至ることはない。よって、"e1"と"e2"との間に遷移条件の循環は構成されていないため、"e1"と"e2"は、異なる状態マシングループに分割される。
【００４６】
また、図５に示す"e2"は"e3"への遷移条件を持ち、"e3"は"e2"への遷移条件を持つ。よって、"e2"と"e3"との間に遷移条件の循環が構成されているため、"e2"と"e3"は同一の状態マシングループに組み込まれる。
【００４７】
なお、図５に示すような"e2"から"e4"に対する遷移条件ではなく、"e4"から"e2"に対する遷移条件がもし定義されていれば、"e2"と"e3"と"e4"との間に遷移条件の循環が成立する。よって、"e4"から"e2"に対する遷移条件が定義された場合、"e2"と"e3"と"e4"の３つの状態マシンが、同一の状態マシングループに組み込まれる。
【００４８】
状態マシン群統合部１０２は、遷移順序導出部２０２を用いて、生成された状態マシングループにおける遷移順序を計算する。また、状態マシン群統合部１０２は、計算された遷移順序を統合する。
【００４９】
図６は、統合された遷移順序を含む状態マシングループ群の一例を示す説明図である。遷移順序は、遷移を誘発する側の状態マシンを含む状態マシングループの方が先に決定される必要がある。よって、遷移順序は、遷移条件を指定する側の状態マシンである状態マシン"e1"を含む状態マシングループ"G1"に関して最初に計算される。
【００５０】
状態マシングループ"G1"における遷移順序が計算された後、次に状態マシングループ"G2"、最後に状態マシングループ"G3"の順で遷移順序が計算される。計算された状態マシングループ"G1"における遷移順序は、単に１つの遷移"e1(s1,s2)"になる。
【００５１】
"e1(s1,s2)"は、状態マシングループ"G2"内の状態マシンである"e2"に対する遷移条件を含む。よって、状態マシングループ"G2"における遷移順序の計算時には、遷移"e1(s1,s2)"が考慮される必要がある。
【００５２】
そこで、状態マシン群統合部１０２は、遷移順序を計算する状態マシングループ内の状態マシンに遷移条件を持つ遷移を、暫定結果の遷移順序から抽出する。状態マシン群統合部１０２は、抽出した遷移に仮の状態をつなげることで仮状態マシンを構成する。状態マシン群統合部１０２は、計算対象の状態マシングループに仮状態マシンも加えて、遷移順序を計算する。
【００５３】
図７は、生成された仮状態マシンを含む状態マシングループの一例を示す説明図である。図７は、図６に示す遷移"e1(s1,s2)"に基づいて、仮の状態"p1"と"p2"がつなげられた仮状態マシン"pseud"が構成され、"pseud"が状態マシングループ"G2"に追加された様子を示す。図７に示す吹き出しは、遷移"e1(s1,s2)"に基づいて、仮の状態"p1"と"p2"がつなげられていることを意味する。
【００５４】
図７に示すような状態マシングループを元に遷移順序を計算すると、仮の遷移を含む遷移順序が得られる。図８は、状態マシングループごとの遷移順序の統合結果の一例を示す説明図である。
【００５５】
図８に示す、状態マシングループ"G2"内の遷移順序は、図７に示す状態マシングループ"G2"から生成された、仮の遷移を含む遷移順序である。状態マシングループ"G2"内の点線の長方形が、仮の遷移に対応する。図８は、状態マシングループ"G2"内の仮の遷移が、状態マシングループ"G1"内の"e1(s1,s2)"であることを示す。
【００５６】
状態マシン群統合部１０２は、仮の遷移が持つ他の遷移との依存関係を元の遷移に移行することによって、各状態マシングループから得られる遷移順序を統合する。図９は、遷移順序の統合結果の単一の遷移順序への変換結果の一例を示す説明図である。図９は、図８に示す２つの状態マシングループ"G1"と"G2"の遷移順序が、単一の遷移順序に変換された結果を示す。
【００５７】
図１０は、統合された遷移順序を含む状態マシングループ群の他の一例を示す説明図である。図１０は、各遷移順序が統合された状態マシングループ"G1"、"G2"と、状態マシングループ"G3"との関係性を示す。
【００５８】
図１０に示す遷移順序を構成する遷移には、状態マシングループ"G3"内の状態マシンに対して遷移条件を持つ２つの遷移が含まれる。状態マシン群統合部１０２は、状態マシングループ"G3"における遷移順序の計算時に、遷移条件を持つ２つの遷移を仮の遷移として持つ仮状態マシンを構成する。
【００５９】
図１１は、生成された仮状態マシンを含む状態マシングループの他の一例を示す説明図である。図１１は、状態マシングループ"G3"における遷移順序の計算時に用いられる、仮状態マシンを含む状態マシングループ"G3"の様子を示す。
【００６０】
図１１は、仮状態マシン"pseud"が状態マシングループ"G3"に追加された様子を示す。図１１に示す仮状態マシン"pseud"は、図１０に示す遷移"e2(s1,s2)"に基づいて仮の状態"p3"と"p4"がつなげられ、図１０に示す遷移"e3(s1,s2)"に基づいて仮の状態"p4"と"p5"がつなげられることによって構成される。図１１に示す各吹き出しは、遷移"e2(s1,s2)"に基づいて仮の状態"p3"と"p4"がつなげられていること、遷移"e3(s1,s2)"に基づいて仮の状態"p4"と"p5"がつなげられていることをそれぞれ意味する。
【００６１】
図１２は、状態マシングループごとの遷移順序の統合結果の他の一例を示す説明図である。図１２は、計算結果として得られた状態マシングループ"G3"における遷移順序と、状態マシングループ"G1"と"G2"から得られた遷移順序との関係性を示す。
【００６２】
図１２に示す状態マシングループ"G3"内の遷移順序は、図１１に示す状態マシングループ"G3"から生成された、仮の遷移を含む遷移順序である。図１２は、状態マシングループ"G3"内の２つの仮の遷移がそれぞれ、状態マシングループ"G1&G2"内の"e2(s1,s2)"、"e3(s1,s2)"であることを示す。
【００６３】
図１３は、遷移順序の統合結果の単一の遷移順序への変換結果の他の一例を示す説明図である。図１３は、図１２に示す統合された２つの状態マシングループ"G1&G2"と"G3"の遷移順序が変換された単一の遷移順序を示す。図１３に示す遷移順序が、状態マシングループ"G1"、"G2"、"G3"から得られる全ての遷移順序が統合された最終的な結果である。
【００６４】
上記の分割処理と統合処理によって、４つの状態マシンに基づく遷移順序の計算が、状態マシングループ"G1"における遷移順序の計算と、状態マシングループ"G2"における遷移順序の計算と、状態マシングループ"G3"における遷移順序の計算とに分割される。
【００６５】
状態マシングループ"G1"における遷移順序の計算は、１つの状態マシンに基づく。状態マシングループ"G2"における遷移順序の計算は、仮状態マシンも含めると、３つの状態マシンに基づく。状態マシングループ"G3"における遷移順序の計算は、仮状態マシンも含めると、２つの状態マシンに基づく。すなわち、遷移順序の計算において、併せて計算される状態マシンの数が減少する。
【００６６】
なお、本実施形態の状態マシン群分割部１０１および状態マシン群統合部１０２は、例えば、非一時的なコンピュータ読み取り可能な記録媒体に記憶されたプログラムの制御に従って処理を実行するCPU(Central Processing Unit)によって実現される。
【００６７】
［動作の説明］
以下、本実施形態の高速変更計画システム１００の動作を図１４を参照して説明する。図１４は、高速変更計画システム１００による状態マシン群の変更計画処理の動作を示すフローチャートである。
【００６８】
状態マシン群統合部１０２は、入出力部２０１から状態マシン群の情報を受信する。状態マシン群統合部１０２は、受信した状態マシン群の情報を状態マシン群分割部１０１に出力する。
【００６９】
状態マシン群分割部１０１は、入力された状態マシン群を、複数の状態マシングループに分割する。状態マシン群分割部１０１は、生成した状態マシングループ群を状態マシン群統合部１０２に返す（ステップＳ１０１）。
【００７０】
次いで、状態マシン群統合部１０２は、入力された状態マシングループ群から、遷移順序を計算可能な状態マシングループを一つずつ取得する。遷移順序を計算可能な状態マシングループは、状態マシングループ内の状態マシンに遷移条件を持ち、かつ遷移順序が未計算の状態マシングループとの間に依存性がない状態マシングループである。
【００７１】
上記の状態マシングループ間の依存性は、例えば、所定の状態マシングループと、所定の状態マシングループにおける遷移順序を計算するために事前に遷移順序を計算することが求められる状態マシングループとの関係に相当する。
【００７２】
状態マシン群統合部１０２は、状態マシングループにおける遷移順序の計算処理と、計算された遷移順序の統合処理を、全ての状態マシングループに対して繰り返し行う。
【００７３】
状態マシン群統合部１０２は、全ての状態マシングループにおける遷移順序が統合済みであるか否かを判断する（ステップＳ１０２）。全ての状態マシングループにおける遷移順序が統合済みである場合（ステップＳ１０２におけるＹＥＳ）、状態マシン群統合部１０２は、得られた遷移順序の統合結果を最終的な結果として、処理を終了する。
【００７４】
全ての状態マシングループにおける遷移順序が統合済みではない場合（ステップＳ１０２におけるＮＯ）、状態マシン群統合部１０２は、遷移順序を計算可能な任意の未計算の状態マシングループを一つ取得する。状態マシン群統合部１０２は、取得した状態マシングループにおける遷移順序を計算し、計算された遷移順序を暫定結果に統合する（ステップＳ１０３）。統合した後、状態マシン群統合部１０２は、再度ステップＳ１０２における処理を行う。
【００７５】
次に、ステップＳ１０１における処理を図１５を参照して具体的に説明する。図１５は、高速変更計画システム１００による状態マシン群の分割処理の動作を示すフローチャートである。
【００７６】
状態マシン群分割部１０１は、入力された状態マシン群から状態マシンを一つずつ取得する。状態マシン群分割部１０１は、取得した状態マシンを、適切な状態マシングループに割り当てる。状態マシン群分割部１０１は、割り当て処理を全ての状態マシンに対して繰り返し行う。
【００７７】
状態マシン群分割部１０１は、入力された状態マシン群に含まれる全ての状態マシンを状態マシングループに割り当て済みであるか否かを判断する（ステップＳ１１１）。全ての状態マシンを状態マシングループに割り当て済みである場合（ステップＳ１１１におけるＹＥＳ）、状態マシン群分割部１０１は、状態マシンを割り当てた結果を最終結果として、処理を終了する。
【００７８】
全ての状態マシンを状態マシングループに割り当て済みではない場合（ステップＳ１１１におけるＮＯ）、状態マシン群分割部１０１は、任意の未割り当ての状態マシンを一つ取得する。状態マシン群分割部１０１は、取得した状態マシンを状態マシングループに割り当てる（ステップＳ１１２）。
【００７９】
ステップＳ１１２における状態マシンを状態マシングループに割り当てるプロセスは、プロセス内で割り当てる状態マシンに関連する他の状態マシンを状態マシングループに割り当てるプロセスを呼び出すという、プロセスの再起呼び出し構造をとる。
【００８０】
すなわち、プロセスの呼び出しのループが発生する場合、ループにおける再起呼び出しの停止が求められる。呼び出しがループしていることを判断するために、状態マシン群分割部１０１は、プロセスの呼び出し時に、処理中の状態マシンの連鎖の情報を含むスタック型のデータを渡す。
【００８１】
最初のステップＳ１１２における処理において、状態マシン群分割部１０１は、状態マシンを状態マシングループに割り当てるプロセスを最初に呼び出す。すなわち、状態マシン群分割部１０１は、空のスタック型のデータと共にプロセスを呼び出す。状態マシンを状態マシングループに割り当てた後、状態マシン群分割部１０１は、再度ステップＳ１１１における処理を行う。
【００８２】
次に、ステップＳ１１２における処理を図１６を参照して具体的に説明する。図１６は、高速変更計画システム１００による状態マシンの状態マシングループ割り当て処理の動作を示すフローチャートである。
【００８３】
状態マシン群分割部１０１は、処理対象の状態マシンがスタックに含まれているか否かを判断する（ステップＳ１２１）。処理対象の状態マシンがスタックに含まれている場合（ステップＳ１２１におけるＹＥＳ）、状態マシン群分割部１０１は、処理対象の状態マシンが、状態マシングループへの割り当て処理中であって遷移条件の循環を構成する状態マシンの一つであると判断する。
【００８４】
状態マシン群分割部１０１は、遷移条件の循環を構成する全ての状態マシンを、処理対象の状態マシンと同一の状態マシングループに再度割り当てる（ステップＳ１２２）。状態マシンを同一の状態マシングループに割り当てた後、状態マシン群分割部１０１は、処理を終了する。
【００８５】
図１７は、状態マシンの状態マシングループへの割り当て時に使用されるスタックの一例を示す説明図である。図１７に示す上側のスタックは、状態マシン"e1"の割り当て処理中に状態マシン"e2"の割り当て処理が呼ばれ、さらに、状態マシン"e2"の割り当て処理中に状態マシン"e3"の割り当て処理が呼ばれた場合のスタックの様子を示す。
【００８６】
図１７に示す下側のスタックは、上側のスタックが示す状況からさらに、状態マシン"e3"の割り当て処理中に状態マシン"e2"の割り当て処理が呼ばれた場合のスタックの様子を示す。
【００８７】
状態マシン群分割部１０１は、例えば、図１７に示す下側のスタック型のデータから、新たな割り当て処理の対象である状態マシン"e2"がスタックに含まれていると判断する。判断した後、状態マシン群分割部１０１は、スタックの一番上に詰まれた状態マシンから、新たな割り当て処理の対象である状態マシン"e2"までの間にある全ての状態マシンを、状態マシン"e2"と同一の状態マシングループに再度割り当てる。
【００８８】
全ての状態マシンを同一の状態マシングループに再度割り当てる際に、再度割り当てられる状態マシンが属していた状態マシングループに別の状態マシンが含まれている場合、状態マシン群分割部１０１は、含まれている別の状態マシンも新たな状態マシングループに再度割り当てる。
【００８９】
処理対象の状態マシンがスタックに含まれていない場合（ステップＳ１２１におけるＮＯ）、状態マシン群分割部１０１は、処理対象の状態マシンを、処理対象の状態マシンのみが含まれる新たな状態マシングループに割り当てる（ステップＳ１２３）。
【００９０】
次いで、状態マシン群分割部１０１は、処理対象の状態マシン内の状態が遷移する際に従う遷移条件が指定する他の状態マシンを一つずつ取得する。取得される他の状態マシンは、遷移が依存する状態マシンである。
【００９１】
状態マシン群分割部１０１は、取得した他の状態マシンをステップＳ１２３で割り当てた新たな状態マシングループに割り当てる。状態マシン群分割部１０１は、割り当て処理を、処理対象の状態マシン内の遷移が依存する全ての状態マシンに対して繰り返し行う。
【００９２】
すなわち、状態マシン群分割部１０１は、処理対象の状態マシン内の遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みであるか否かを判断する（ステップＳ１２４）。遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みである場合（ステップＳ１２４におけるＹＥＳ）、状態マシン群分割部１０１は、処理を終了する。
【００９３】
遷移が依存する全ての状態マシンに対して、割り当て処理を実施済みではない場合（ステップＳ１２４におけるＮＯ）、状態マシン群分割部１０１は、遷移が依存する実施済みではない状態マシンに対して割り当て処理を実施する（ステップＳ１２５）。割り当て処理を実施した後、状態マシン群分割部１０１は、再度ステップＳ１２４における処理を実施する。
【００９４】
次に、ステップＳ１０３における処理を図１８を参照して具体的に説明する。図１８は、高速変更計画システム１００による遷移順序の導出処理と統合処理の動作を示すフローチャートである。
【００９５】
状態マシン群統合部１０２は、処理対象の状態マシングループ内の状態マシンに対して遷移条件を指定する、暫定結果の遷移順序内の全ての遷移を、遷移順序通りに取得する。状態マシン群統合部１０２は、取得した遷移が任意の状態ではさまれるように、仮の状態を生成し、遷移と仮の状態とを関連付けることによって仮状態マシンを生成する（ステップＳ１３１）。
【００９６】
次いで、状態マシン群統合部１０２は、仮状態マシンを含む処理対象の状態マシングループを、遷移順序導出部２０２に送信する。状態マシン群統合部１０２は、遷移順序導出部２０２から、送信した状態マシングループにおける遷移順序を取得する（ステップＳ１３２）。
【００９７】
次いで、状態マシン群統合部１０２は、取得した遷移順序内の、全ての仮状態マシン由来の遷移に関連する依存性を元の遷移に付け替えることによって、取得した遷移順序を暫定結果に統合する（ステップＳ１３３）。暫定結果に統合した後、状態マシン群統合部１０２は、処理を終了する。
【００９８】
［効果の説明］
本実施形態における高速変更計画システムは、状態マシン群の遷移順序を計算する際、併せて計算することが求められる状態マシンの数を削減できる。併せて計算することが求められる状態マシンの数が削減されることによって、全ての状態マシンを対象にした変更計画作成に求められる計算量が減少し、変更計画の作成が効率化される。
【００９９】
実施形態２．
［構成の説明］
以下、本発明の第２の実施形態を、図面を参照して説明する。図１９は、本発明による高速変更計画システムの第２の実施形態の構成例を示すブロック図である。図１９において、第１の実施形態と同様の構成要素には同一の符号を付し、説明を省略する。
【０１００】
図１９に示すように、本実施形態における高速変更計画システム１００の構成は、第１の実施形態における高速変更計画システム１００の構成と同様である。しかし、本実施形態において、遷移順序導出部２０２が高速変更計画システム１００外部の計算機プール２０３と接続されている点が、第１の実施形態と異なる。
【０１０１】
遷移順序導出部２０２は、計算機プール２０３と通信ネットワークなどを介して通信可能に接続されている。接続されている場合、遷移順序導出部２０２は、計算機プール２０３を用いて、遷移順序を計算する。計算機プール２０３の処理能力が高い場合、遷移順序導出部２０２は、例えば、並列的に複数の状態マシングループにおける遷移順序を計算できる。
【０１０２】
本実施形態における状態マシン群統合部１０２は、同時に遷移順序を計算できる複数の状態マシングループにおける各遷移順序の計算処理を、同時実行的に実施するように遷移順序導出部２０２に依頼する。
【０１０３】
図２０は、遷移順序を並列計算可能な状態マシングループ群の一例を示す説明図である。第１の実施形態で説明したように、状態マシングループにおける遷移順序は、状態マシングループ内の状態マシンに遷移条件を持ち、遷移順序が未計算の状態マシングループとの間に依存性を持たない場合に、計算される。
【０１０４】
図２０に示す例では、状態マシングループ"G1"のみが、他の状態マシングループとの間に依存性を持たない状態マシングループである。よって、分割直後の状態において、遷移順序導出部２０２は、状態マシングループ"G1"に対してのみ遷移順序を計算できる。
【０１０５】
状態マシングループ"G1"における遷移順序の計算を終了した後、遷移順序導出部２０２は、状態マシングループ"G1"に対してのみ依存性を持つ状態マシングループ"G2"および"G3"における遷移順序を計算できる。
【０１０６】
図２０に示す状態マシングループ"G2"と"G3"との間には依存性が存在しないため、遷移順序導出部２０２は、状態マシングループ"G2"と"G3"における遷移順序を同時に計算できる。
【０１０７】
また、状態マシングループ"G2"と"G3"における遷移順序の計算が終了した後、遷移順序導出部２０２は、状態マシングループ"G4"と"G5"における遷移順序を同時に計算できる。
【０１０８】
また、状態マシングループ"G4"と"G5"における遷移順序の計算が終了した後、遷移順序導出部２０２は、状態マシングループ"G6"と"G7"における遷移順序を同時に計算できる。
【０１０９】
状態マシン群統合部１０２は、遷移順序を計算可能な状態マシングループが複数発生した場合、発生した状態マシングループを連続して遷移順序導出部２０２に送信する。また、状態マシン群統合部１０２は、遷移順序導出部２０２から受信した遷移順序の計算結果を、逐次暫定結果の遷移順序に統合する。
【０１１０】
［動作の説明］
以下、本実施形態の高速変更計画システム１００の動作を図１４と図１８を参照して説明する。本実施形態における高速変更計画システム１００による変更計画処理は、基本的に第１の実施形態における変更計画処理と同様である。
【０１１１】
しかし、遷移順序の導出と遷移順序の統合を行うステップＳ１０３における処理が、第１の実施形態のステップＳ１０３における処理と異なる。以下、本実施形態のステップＳ１０３における処理を説明する。第１の実施形態における処理と同様の処理が行われるステップには、第１の実施形態と同様の符号を付し、説明を省略する。
【０１１２】
本実施形態における状態マシン群統合部１０２は、入力された状態マシングループ群の内、遷移順序を計算可能な状態マシングループを、所定の限度数まで取得する。所定の限度数は、遷移順序導出部２０２が計算機プール２０３を用いて並列的に計算できる状態マシングループの最大数である。状態マシン群統合部１０２は、遷移順序導出部２０２を用いた複数の状態マシングループにおける遷移順序の計算処理と、計算された遷移順序の統合処理を、全ての状態マシングループに対する計算が完了するまで繰り返し行う。
【０１１３】
すなわち、全ての状態マシングループにおける遷移順序が統合済みではない場合（ステップＳ１０２におけるＮＯ）、状態マシン群統合部１０２は、遷移順序を計算可能な未計算の状態マシングループを、所定の限度数まで取得する。
【０１１４】
取得された複数の状態マシングループに対して、仮状態マシンの生成（ステップＳ１３１）と、遷移順序の計算（ステップＳ１３２）が連続的に実施される。状態マシン群統合部１０２は、遷移順序導出部２０２から特定の状態マシングループに関する遷移順序を受信すると、直ちに受信した遷移順序を暫定結果の遷移順序に統合する（ステップＳ１３３）。統合した後、状態マシン群統合部１０２は、再度ステップＳ１０２における処理を実施する。
【０１１５】
［効果の説明］
本実施形態の高速変更計画システムは、同時に遷移順序を計算できる複数の状態マシングループが存在し、かつ複数の状態マシングループにおける各遷移順序を並列的に計算できる計算機プールが存在する場合、結果を導出するための全ての計算を高速化できる。
【０１１６】
次に、本発明の概要を説明する。図２１は、本発明による高速変更計画システムの概要を示すブロック図である。本発明による高速変更計画システム１０は、１または複数の状態マシンから構成される状態マシン群を状態マシングループ群に分割する状態マシン群分割部１１（例えば、状態マシン群分割部１０１）と、分割された状態マシングループ群に含まれる状態マシングループごとに導出された遷移順序を統合する状態マシン群統合部１２（例えば、状態マシン群統合部１０２）とを含む。
【０１１７】
そのような構成により、高速変更計画システムは、大規模なシステムの変更計画作成における計算量を削減できる。
【０１１８】
また、状態マシン群に含まれる状態マシン内の状態が他の状態に遷移する時に従う遷移条件が、当該状態マシン以外の状態マシンに関連し、状態マシン群分割部１１は、複数の状態マシンに含まれる１つの状態マシンから、複数の状態マシン間の遷移条件が関連する状態マシンを、遷移条件の数だけ順に辿った時に１つの状態マシンに戻る場合、複数の状態マシンのみを同一の状態マシングループに含むように、状態マシン群を状態マシングループ群に分割してもよい。
【０１１９】
そのような構成により、高速変更計画システムは、状態マシン群に含まれる状態マシン間の複数の遷移条件の循環に基づいて、併せて計算することが求められる状態マシン同士のみから構成される小グループに、状態マシン群を分割できる。
【０１２０】
また、状態マシン群分割部１１は、状態マシングループ内の状態マシンに関連する遷移条件に従って遷移する状態を含む仮状態マシンを状態マシングループに追加し、状態マシン群統合部１２は、仮状態マシンの元である状態マシングループから導出された遷移順序と、仮状態マシンが追加された状態マシングループから導出された遷移順序とを統合してもよい。
【０１２１】
そのような構成により、高速変更計画システムは、状態マシングループ間の遷移条件を考慮した上で、遷移順序を統合できる。
【０１２２】
また、状態マシン群統合部１２は、所定の条件に従う状態マシングループが複数ある場合、複数の状態マシングループから遷移順序をそれぞれ導出する処理を並列的に行う指示を外部装置に出力してもよい。
【０１２３】
そのような構成により、高速変更計画システムは、所定の条件に従う複数の状態マシングループを並列的に処理できる。
【０１２４】
また、所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されており、かつ他の状態マシングループから既に遷移順序が導出されていることでもよい。
【０１２５】
また、所定の条件は、状態マシングループが、他の状態マシングループから遷移条件を指定されていないことでもよい。
【０１２６】
そのような構成により、高速変更計画システムは、状態マシングループ間の依存性を考慮した上で、並列処理を実施できる。
【符号の説明】
【０１２７】
１０、１００  高速変更計画システム
１１、１０１  状態マシン群分割部
１２、１０２  状態マシン群統合部
２０１  入出力部
２０２  遷移順序導出部
２０３  計算機プール
【図１】
2015215886.tif 000003
【図２】
2015215886.tif 000004
【図３】
2015215886.tif 000005
【図４】
2015215886.tif 000006
【図５】
2015215886.tif 000007
【図６】
2015215886.tif 000008
【図７】
2015215886.tif 000009
【図８】
2015215886.tif 000010
【図９】
2015215886.tif 000011
【図１０】
2015215886.tif 000012
【図１１】
2015215886.tif 000013
【図１２】
2015215886.tif 000014
【図１３】
2015215886.tif 000015
【図１４】
2015215886.tif 000016
【図１５】
2015215886.tif 000017
【図１６】
2015215886.tif 000018
【図１７】
2015215886.tif 000019
【図１８】
2015215886.tif 000020
【図１９】
2015215886.tif 000021
【図２０】
2015215886.tif 000022
【図２１】
2015215886.tif 000023