(57)【特許請求の範囲】
【請求項１】
複数の制御パラメータを含む制御パラメータ・ベクトルに応じて、複数の主要業績評価指標(ＫＰＩ)に関連付けられたビジネス・プロセス・マネージメント(ＢＰＭ)モデルを最適化する方法であって、コンピュータが、
前記制御パラメータを線形制御パラメータ・ベクトル(Ｘ)及び非線形制御パラメータ・ベクトル(Ｘ')に分離するステップと、
前記制御パラメータ・ベクトルに対する一組の候補値を反復的に計算するステップであって、各候補値は、前記ＢＰＭモデル、前記複数の主要業績評価指標(ＫＰＩ)、及び前記非線形制御パラメータ・ベクトル(Ｘ')の事前選択された値に関連付けられた混合整数計画法(ＭＩＰ)モデルの実行から、前記非線形制御パラメータ・ベクトル(Ｘ')に属する非線形制御パラメータの事前選択された値に関して決定される、前記計算するステップと、
前記制御パラメータ・ベクトルに対する前記候補値の少なくとも１つに基づいて前記ＢＰＭモデルを調節するステップと
を実行することを含み、
前記制御パラメータ・ベクトルに対する一組の候補値を反復的に計算するステップが、
前記ＭＩＰモデルを稼働して、前記制御パラメータ・ベクトルに対する最適値の近似値(Ｘ＊)、前記主要業績評価指標に対する近似値(ｃ＊)、及び前記ＢＰＭモデルの実行に関連するＢＰＭ出力ベクトルの近似値(Ｙ＊)を提供するステップと、
個別のイベント・シミュレーションを含む評価関数を、前記制御パラメータ・ベクトルに対する前記最適値の近似値(Ｘ＊)に適用することによって、前記主要業績評価指標に対する目標値(ｃ＃)及びＢＰＭ出力ベクトルに対する目標値(Ｙ＃)を決定するステップと、
前記主要業績評価指標に対する近似値(ｃ＊)の精度及び前記ＢＰＭ出力ベクトルの近似値(Ｙ＊)の精度と前記主要業績評価指標に対する目標値(ｃ＃)及び前記ＢＰＭ出力ベクトルに対する目標値(Ｙ＃)とをそれぞれ比較して、それぞれが事前定義された基準を満たす場合、前記制御パラメータ・ベクトルに対する最適値の近似値(Ｘ＊)を前記制御パラメータ・ベクトルに対する候補値として選択するステップと
を含む、
前記方法。
【請求項２】
前記選択するステップは、
精度インジケータが、事前定義された閾値よりも劣っているかどうかを決定するステップ
を含み、
前記精度インジケータＰＲが次式
ＰＲ＝|(ｃ＃,Ｙ＃)−(ｃ＊,Ｙ＊)|／|(ｃ＃,Ｙ＃)|
に従って決定される、
請求項１に記載の方法。
【請求項３】
前記制御パラメータ・ベクトルに対する一組の候補値を反復的に計算するステップは、
前記主要業績評価指標に対する目標値(ｃ＃)及び前記ＢＰＭ出力ベクトルに対する目標値(Ｙ＃)に関して前記主要業績評価指標に対する近似値(ｃ＊)及び前記ＢＰＭ出力ベクトルの近似値(Ｙ＊)が事前設定された閾値よりも小さい場合、ローカル・サーチ機構を使って前記制御パラメータ・ベクトルに対する前記最適値の近似値(Ｘ＊)を精細化するステップと、
前記制御パラメータ・ベクトルに対する前記最適値の近似値(Ｘ＊)に対して得られた前記精細値に関して、前記稼動するステップ、前記決定するステップ、前記選択するステップ、及び前記精細化するステップを反復するステップと
を更に含む、請求項１又は２に記載の方法。
【請求項４】
前記ローカル・サーチ機構は、
前記制御パラメータ・ベクトルに対する最適値の近似値(Ｘ＊)の近隣を計算するステップ、及び、
前記制御パラメータ・ベクトルに対する最適値の近似値(Ｘ＊)に対する精細値として前記近隣における次の値を選択するステップ
を遂行する、請求項３に記載の方法。
【請求項５】
前記精細化するステップは、少なくとも１つの停止条件の非満足を被る、請求項３又は４に記載の方法。
【請求項６】
非線形制御パラメータ・ベクトル(Ｘ')に属する非線形制御パラメータの前記事前選択された値は非線形制御パラメータ・ベクトルに関してローカル・サーチ機構を使用して決定される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記ローカル・サーチ機構は、
非線形制御パラメータ・ベクトルの現在値の近隣を計算するステップ、及び、
前記非線形制御パラメータ・ベクトル(Ｘ')の事前選択された値として前記近隣における次の値を選択するステップ
を遂行する、請求項６に記載の方法。
【請求項８】
コンピュータに、請求項１〜７のいずれか一項に記載の方法のステップを実行させる、コンピュータ・プログラム。
【請求項９】
請求項８に記載のコンピュータ・プログラムをエンコードされているコンピュータ可読媒体。
【請求項１０】
請求項１〜７のいずれか一項に記載の方法のステップを実行するように適応した手段を含むシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、ビジネス・プロセス・マネージメント(ＢＰＭ)・システムに関し、特に、ＢＰＭモデルを最適化するための方法及びシステムに関する。
【背景技術】
【０００２】
ビジネス・プロセス・マネージメント・システムは大量の情報を編成及び管理するために使用される。
【０００３】
ビジネス・プロセス・マネージメント(ＢＰＭ)は、組織とクライアントの要求とを調整することに焦点を合わせる。先進的なワークフロー技術を用いて、ＢＰＭは、企業におけるビジネス・プロセスの面から全方位マネージメントを行ない、ビジネス・プロセスの改善を持続させることを支援する。それは、企業内及び企業間の様々なビジネスに関して、統一的にモデリングし、実施し、及び監視する環境を提供する。ＢＰＭ技術は、ビジネス要件及びＩＴシステムの間のミスマッチ、生産性の向上、並びに、運営コスト及び開発コストの縮小を可能にする。
【０００４】
ビジネス・プロセスは、所定の要件を満たすサービス又は製品をもたらす関連の構造化された活動の集合体である。ビジネス・プロセスは、それらが収益を上げるが、多くの場合、コストのかなりの部分を占めるので、ビジネス組織には不可欠である。 
【０００５】
ビジネス・プロセス・マネージメントは、組織のビジネス・プロセスをモデリングし、開発し、実施し、管理するための方法、技術、及びツールのセットを包含する。ＢＰＭは、ビジネス・アナリストがビジネス・プロセス・モデルを作成することを可能にする。そのビジネス・プロセス・モデルは、その後ＩＴ技術者によって実施可能なモデルに精細化される。実施可能なプロセス・モデルはプロセス・エンジンに展開され、そのエンジンは、タスクを資源(人間及びサービス)に託することによってそのプロセスを実施する。
【０００６】
ＢＰＭシステムにおけるビジネス・プロセスのパフォーマンスは、主要業績評価指標(ＫＰＩ)に基づいて測定される。ＫＰＩは、一般にＢＰＭ設計者によって明示される。
【０００７】
ＢＰＭ設計者は、所定数の制御パラメータを調整することによって、ＢＰＭモデルをＫＰＩに関して最適化することに重点的に取り組む。
【０００８】
ＢＰＭシステムは、ビジネス・プロセスに関するステップ、ルール、及びＫＰＩを説明するために、及び、予測されるパフォーマンスを、個別のイベント・シミュレーションを介して推定するために、ビジネス・アナリストの役割を決定する初期モデリング・フェーズに依存する。
【０００９】
ＢＰＭシステムのパフォーマンスを高めるための現在のソリューションは、ＫＰＩの取得に関する情報を提供する。しかし、ＫＰＩを最適化する必要があるとき、一般に、どの制御パラメータがビジネス・アナリストによるその後の調節を必要とするかを決定することが必要とされる。しかし、多くの場合、ＫＰＩは幾つもの測定基準に依存するので、副次的最適性(sub-optimality)の要因を特定することは難しい。
【００１０】
同様に、初期のモデリング・フェーズに関与したＢＰＭモデル製作者は、制御パラメータの幾つかの値を変更するというインパクトを知る必要があり得る。現在、それらのパラメータの変更は手操作で行なわれており、これらの変更の影響は、個別のイベント・シミュレーションが所望のＫＰＩを戻し始めることによって試される。しかし、このプロセスは非常に長くなり得るし、ＢＰＭのエキスパートの入力を必要とする。幾つかの既存のＢＰＭツールは、制御パラメータ・ベクトルの調整を加速するローカル・サーチ機構を備えている。しかし、ローカル・サーチ・エンジンは、ＢＰＭネットワークの構造に関する知識を持たず、制御パラメータを調整するためには、このローカル・サーチのソリューションは、ＫＰＩの結果をシミュレーションから簡単に得るが、問題の構造を無視しており、それを極めて遅くしている。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従って、本発明の目的は、ＫＰＩに関して最適の制御パラメータ値を決定するための方法およびシステムの改善を提供することにある。
【課題を解決するための手段】
【００１２】
本発明によれば、請求項１によってＢＰＭモデルを最適化する方法が提供され、請求項９によってコンピュータ・プログラムが提供され、請求項１０によってコンピュータ可読媒体が提供され、請求項１１によってシステムが提供される。好ましい実施例は、それぞれの従属項において定義される。
【００１３】
本発明は、手操作のテスト・ステップやトライ・ステップを必要とせずに、ＢＰＭ設計プロセスにおいて生じる複雑なＢＰＭパラメトリック最適化の問題を自動的に解決することを可能にする。
【００１４】
本発明によれば、混合整数計画法(ＭＩＰ)が最適化エンジンとして使用され、離散型事象のシミュレーションがシミュレーション・エンジンとして使用されて、最適化とシミュレーションが同じレベルで動作することを可能にする。ＢＰＭシステムのＭＩＰ近似値を有効化及び精細化するためにシミュレーションが使用され、ＢＰＭ問題の制御パラメータがコミュニケーション・ベクトルとして使用される。
【００１５】
本発明の別の利点は、混合整数計画法(ＭＩＰ)によってモデリングされ得るデータを、混合整数計画法によってモデリングされ得ないデータから分離し、この区別を自動ローカル・サーチのための「部分的」ヒントとして反復的に使用することである。更に、本発明の別の利点は、両サイド間のコミュニケーションを制御パラメータのみに縮小することである。
【００１６】
本発明は、ＭＩＰの結果の質と、ローカル・サーチがシミュレーション時に精細化することにより与えられた精度との両方から利益を受けることを可能にする、ＭＩＰ及びシミュレーションの間の相乗作用を生じる。
【００１７】
当業者には本発明の更なる利点が、図面及び詳細な説明の精査時に明らかになるであろう。いずれの付加的利点もこれに組込み得るものと考えられる。
【図面の簡単な説明】
【００１８】
【図１】本発明を使用し得る例示的なハードウェア・アーキテクチャを示すブロック図である。
【図２】本発明の実施例によるＢＰＭ最適化ユニットの高レベルのブロック図である。
【図３】本発明の実施例によるＢＰＭ最適化ユニットに関する詳細なブロック図である。
【図４】本発明の実施例に従ってＢＰＭ最適化ステップを示すフローチャートである。
【発明を実施するための形態】
【００１９】
図１は、本発明を実施し得るビジネス・プロセス・マネージメント (ＢＰＭ)・システムの例示的なハードウェア・アーキテクチャ１００を概略的に示す。
【００２０】
ＢＰＭアーキテクチャ１００は、グローバル・インターネットのような広域ネットワーク(ＷＡＮ)、専用のＷＡＮ、ローカル・エリア・ネットワーク(ＬＡＮ)、通信ネットワーク、又は上記のネットワークの任意の組み合わせのようなネットワーク１０６を介して一組のクライアント・コンピュータ１０２、１０３、１０４と対話するサーバ１０１を含む。サーバ１０１は、ビジネス・プロセスを管理するためにユーザによって使用され得る。
【００２１】
サーバ１０１は、データ及び／又はユーザ機能をクライアント・コンピュータ１０２、１０３、１０４に配信するビジネス・プロセス・マネージメント(ＢＰＭ)ソフトウェア・エンジンを含み得る。図１は、１つのサーバ１０１及び３つクライアント・コンピュータ１０２、１０３、１０４しか示してないが、本発明のシステムが、ネットワーク１０６によって接続される任意の数のサーバ及びクライアント・コンピュータをサポートする、ということを留意されたい。
【００２２】
様々な実施例において、ＢＰＭシステムは、ユーザがビジネス・プロセスのパフォーマンスを知ることを可能にするために、そのネットワークを介してアクセスし得る少なくとも１つのグラフィカル・ユーザ・インターフェース(ＧＵＩ)１０５を含む。
【００２３】
アーキテクチャ１００は、主要業績評価指標(ＫＰＩ)によって表わされるＢＰＭパフォーマンス基準を最適化するために、ＢＰＭ最適化ユニット１５を更に含む。
【００２４】
ＢＰＭ最適化ユニット１５は、本発明の様々な機能を遂行するコンピュータ命令を生じさせるようにコンパイルされたソース・コード、スクリプト記述言語コード、又は解釈済み言語コードを含み得る。
【００２５】
ＢＰＭ最適化ユニット１５はアーキテクチャ１００の他のコンポーネントから分離されているものとして示されているが、それが、サーバ１０１上に代替的に、又は、サーバ１０１及びクライアント・コンピュータ１０２、１０３、１０４上に分散態様で存在し得るということは当業者には容易に明らかであろう。本発明の１つの実施例では、ＢＰＭ最適化ユニット１５は、クライアント・コンピュータ１０２、１０３、１０４のコンピュータ上に存在するクライアント部分、およびサーバ１０１上に存在するサーバ部分を有するクライアント・サーバ・アプリケーションである。
【００２６】
ＢＰＭサーバ１０１は、ビジネス・プロセスのためのステップ、ルールのセット、及び主要業績評価指標(ＫＰＩ)について記述したプロセス・モデル１１１(以後、ＢＰＭモデル又はビジネス・プロセス・モデルとも呼ばれる)を生成するためにビジネス・アナリストによって使用され得るプロセス・モデル生成ツール１１を含む。ビジネス・プロセス・モデルは、ＢＰＭＮ(ビジネス・プロセス・モデリング表記法)またはＸＰＤＬ(ＸＭＬプロセス定義言語)のような任意の適切な言語を使用して定義され得る。ＢＰＭモデリング・フェーズ中に、主要業績評価指標(ＫＰＩ)及びそれらの目標値は、ビジネス目標、プロセス・パフォーマンス・メトリクスのような多くのキー制御パラメータ、およびサービスの質(ＱｏＳ)メトリクスのような技術的パラメータに基づいて定義される。
【００２７】
このようにして生成されたプロセス・モデルは、ビジネス・プロセスにおけるステップのシーケンスを記述する。そのモデルは、各ステップを遂行する責任のあるソフトウェア・システム又は人間の役割、及びステップの実行を管理するルールを指定する。プロセス・モデルは、更に、プロセス・ステップにおける必要なコスト及び各資源の使用可能な量、各ステップの予測される処理期間、及び処理パス内の様々な分岐におけるブランチ比率を指定し得る。
【００２８】
第２フェーズでは、ＢＰＭサーバがプロセス・モデルをアセンブルし、ソフトウェア・リポジトリ１２から検索された一組のソフトウェア・コンポーネントを使ってそれを実装する。プロセス・アセンブリは、プロセス・モデルから自動的に生成されてもよい。
【００２９】
ＢＰＭサーバ１０１は、アセンブルされたプロセス・モデルを配置するための一組の実行エンジン１３を更に含む。実行エンジン１３は、プロセス・モデルの実行を自動化するために提供される。実行エンジン１３は、アセンブルされたプロセス・モデルにおいて定義されたステップに従って作業の各インスタンスを経路指定する。実行エンジン１３は、更に、その処理が、事前定義されたルールに従うことを保証すると共に、モデリングされたビジネス・プロセスで定義されたＢＰＭを自動化及び管理する。
【００３０】
ＢＰＭ最適化ユニット１５は、最適化技術だけでなく個別のイベント・シミュレーションも使用して、ＫＰＩのための最適な制御パラメータを計算することによって、ＢＰＭプロセス(以後、ＢＰＭモデル、ＢＰＭプロセス・モデル、或いはプロセス・モデルと呼ばれる)を最適化するように適応する。
【００３１】
図２は、ＢＰＭモデル最適化ユニット１５の高レベル・ブロック図である。シミュレートされたＫＰＩからの偏倚している場合又はプロセス実行フェーズを上流に偏倚している場合、最適化された制御パラメータを計算するために、ＢＰＭ最適化ユニット１５は、ビジネス・プロセスを記述したプロセス・モデル１１０(アセンブルされているとき)、最適化されるべき対象を構成するＫＰＩパラメータ又はＫＰＩベクトル１５２の事前定義された線形結合、及び制御パラメータ・ベクトルを形成する一組の制御パラメータ１５４を使用する。制御パラメータ・ベクトル及びＫＰＩセットは、ユーザによって事前定義されたパラメータからＢＰＭモデルの一部として選定される。その事前定義された制御パラメータおよびＫＰＩのうちの或るものはＭＩＰモデルにおいて実装され(従って、ＭＩＰ最適化エンジンによって処理されるであろう)、一方、他のものはすべてシミュレーション・エンジンと一緒にローカル・サーチ・アルゴリズムによって処理されるであろう。
【００３２】
ＢＰＭモデル最適化ユニット１５は、プロセス・モデル１１０、ＫＰＩベクトル１５２、及び制御パラメータ・ベクトル１５４から、ＫＰＩベクトル１５２に関して最良のパフォーマンスを提供する最適の制御パラメータ・ベクトル２００を決定するように適応する。
【００３３】
決定された最適の制御パラメータ・ベクトル２００は、プロセス・モデルを実行または再実行するために実行エンジン１３に提供されるであろう。従って、ＫＰＩパラメータは満足される。
【００３４】
図３は、本発明の種々の実施例に従ってＢＰＭ最適化ユニット１５の構造を概略的に示す。
【００３５】
ＢＰＭ最適化ユニット１５は、最適化されるべき一組の制御パラメータを含む制御パラメータ・ベクトル１５４を線形制御パラメータ・ベクトルＸ及び非線形制御パラメータ・ベクトルＸ'に分離するための制御パラメータ・セパレータ３０１を含む。制御パラメータ・ベクトル１５４は、以後、ベクトル(Ｘ,Ｘ')として指定されるであろう。
【００３６】
制御パラメータ・セパレータ３０１によって提供される非線形制御パラメータ・ベクトルＸ'は、非線形パラメータに関してローカル・サーチを行ない且つ非線形制御パラメータＸ'に関して反復的にヒントを供給するサーチ・ユニット３０２に送られる。
【００３７】
本発明の或る実施例によれば、線形制御パラメータＸは混合整数計画法(ＭＩＰ)モデルにおける定数として取り込まれるであろう。一方、非線形パラメータＸ'はＭＩＰモデルから排除され、その代りに、ローカル・サーチ機構を使用して最適化されるであろう。非線形制御パラメータＸ'に対するローカル・サーチによって提供された非線形制御パラメータ・ヒントは、ＭＩＰモデルにおける定数として使用されるであろう。
【００３８】
混合整数計画法は、種々の実務的な最適化問題の解決のために使用される技術を指す。一般に、混合整数計画法(ＭＩＰ)は、次のような形式で表わされる最適化問題である。
ｆ(x)を最小化する
なお、Ｇ(ｘ)＝ｂ
ｌ＜＝ｘ＜＝ｕ
一部またはすべてのｘｊが整数である 、と仮定する
この場合、ｘは変数のベクトルであり、ｌ及びｕは境界のベクトルであり、ｆ(x)は客体的表現であり、Ｇ(x)＝ｂ は制約表現のセットである。
【００３９】
上記のモデルは最小化目的であるが、モデルが最大化目的を有し得るということは当業者には明らかであろう。
【００４０】
ＭＩＰモデルの最も単純な且つ最も広く用いられている形式は、次のような形式における混合整数線形計画法(ＭＩＬＰ)である。
ｃ＜Ｔ＞ｘ  を最小化する
なお、Ａｘ＝ｂ
ｌ＜＝ｘ＜＝ｕ
一部またはすべてのｘｊが整数である、と仮定する
但し、Ａは制限行列と呼ばれるｍ＊ｎのマトリクスであり、ｃは線形オブジェクティブ・ベクトルである。 ＭＩＬＰは、変数の一部又はすべてに関して整数性の制約を有する線形計画法(ＬＰ)である。
【００４１】
混合整数計画法の形式における数学的モデルは、ビジネス・プロセス・マネージメント問題を表わすために使用され得る。そのデータ・モデルは、資源、資源カテゴリ、プロセス・ステップ、及びタイム・バケットによってインデックス付けされる。特に、ＭＩＰ計画法は、ＢＰＭモデルにおいて資源割当てを決定するために使用し得るし、ビジネス・プロセスをシミュレートして資源割当て提言を作成するために及びその資源割当て提言を将来の実行に適用して最適な環境を提供するために使用し得る。
【００４２】
本発明は、ＭＩＰがローカル・サーチを使用してすべての制御パラメータ・ベクトルＸ'に１つの値を提供することによりカップリング・シミュレーションを可能にする。サーチ・ユニット３０２は、非線形制御パラメータ・ベクトルＸ'に関するヒントを反復的に決定するために、任意の適切なローカル・サーチ機構(例えば、ヒル・クライミング、タブー、又はシミュレートされたアニーリング方法)を適用し得る。本発明の実施例によれば、サーチ・ユニットによって提供されるヒントは、その後ＭＩＰモデルに関する定数になり、分岐限定法(branch and bound)／分岐切除法(branch and cut)等によって解決することができる。
【００４３】
線形制御パラメータ・ベクトルＸは、サーチ・ユニット３０２によって計算された非線形パラメータに対するヒント値と共に個別のイベント・シミュレーション・ユニット３０３に提供される。
【００４４】
シミュレーション・ユニット３０３は、第１のフォーマットで受け取られたプロセス・モデル１１０を第２のフォーマットに変換するために設けられたモデル・フォーマット変換器３０４を含む。その変換器３０４は、ＭＩＰモデルの生成及び実行に必要な情報だけが第２のフォーマットでプロセス・モデル内に維持されることを保証するために、その受け取られたプロセス・モデル１１０の或るデータをフィルタするものである。本発明の１つの実施例では、プロセス・モデル１１０の第１のフォーマットはＢＰＭＮフォーマットであり、第２のフォーマットはタイプ・エンティティ／リレーション・シップ・フォーマットである。本発明のこの実施例によれば、プロセス・モデル１１０は、１つ又は複数のエンティティ・リレーションシップ・テーブルの形式で変換器３０４により変換される。
【００４５】
変換器３０４によって変換されたプロセス・モデル１１０は、ＭＩＰモデル生成及び実行ユニット３０５(以下では、「ＭＩＰモデル・ユニット」とも呼ばれる)に供給される。
【００４６】
ＭＩＰモデル・ユニット３０５は、非線形制御パラメータ・ベクトルＸ'に対して決定されたヒント値、変換器３０４によって変換されたプロセス・モデル１１０、及びＫＰＩパラメータ１５２に基づいて、ＭＩＰモデルを作成及び実行する。
【００４７】
ＭＩＰモデル・ユニット３０５は、ＢＰＭパラメトリック調整問題のかなりの副部分を取り込むことにより、米国特許出願２００９／０２２８３０９号に記載されたソリューションのような任意の適切なソリューションに従ってＭＩＰモデルを生成し得る。そのようなソリューションは、最適化問題全体のうちのかなりの副部分を最適化するが、実際には、制御パラメータの(ＭＩＰ追跡可能な)サブセット、ＫＰＩの(ＭＩＰ追跡可能な)サブセット、及びＢＰＭモデルの(ＭＩＰ追跡可能な)近似モデルだけを説明する。それは、例えば、如何なる資源配分問題及び如何なる資源サイジング問題も解決することを可能にする。それは、最小のコストで一定の資源における最大の処理能力を見つけること、又は目標処理能力に対する最安価の資源用途を見つけることを可能にする。他の例は、１つの項目当たりのコストを最小化するための最良の構成を見つけることを無制限に含む。
【００４８】
ＭＩＰモデル・ユニット３０５は、このように生成されたＭＩＰモデルを稼動し、ＭＩＰモデルのための最適な線形制御パラメータＸの近似値Ｘ*を計算する。それは、更に、ＫＰＩパラメータの近似値ｃ*及びＢＰＭ出力値の近似値Ｙ*を提供する。ＢＰＭ出力値は、制御パラメータでもＫＰＩでもないが、ＢＰＭモデル設計者にとって多少の興味のあるそのＢＰＭモデルからのどのような統計結果も表わす。ＢＰＭ出力値の一例は、各資源に対するアイドル時間、又はすべての資源に関する平均的アイドル時間である。
【００４９】
Ｘに関する線形制御パラメータ・ベクトルに対して生じる近似値Ｘ*は、その後、個別のイベント・シミュレーション・モジュール(シミュレータ)３０６によってテストされる。シミュレータ３０６は、ＭＩＰモデル実行ユニット３０５によって計算された最適な線形制御パラメータの近似Ｘ*から正確なＫＰＩパラメータ値「ｃ＃」(ＫＰＩに対する「目標値」とも呼ばれる)及び正確なＢＰＭ出力値「Ｙ＃」(ＢＰＭ出力に対する「目標値」と呼ばれる)を決定する。その「正確な」という用語は、ここでは、ＢＰＭモデルの複雑さをほぼ完全に取り込む数学的モデルによって計算された値を指すために使用される。
【００５０】
しかる後、パフォーマンス・シミュレータ３０６によって得られたＫＰＩパラメータの近似値は、シミュレーションの精度を評価するために精度比較器３０８によって使用される。精度比較器３０８は、ＭＩＰモデル実行ユニットによって提供されたＭＩＰソリューション(ｃ＊,Ｙ＊)を、パフォーマンス・シミュレータ３０６の出力(ｃ＃,Ｙ＃)と比較する。
【００５１】
正確な値(ｃ＃,Ｙ＃)に関するＭＩＰソリューション(ｃ*,Ｙ*)の精度が満足するものでない(絶対距離または相対距離の上限がユーザによって提供される)ことを精度比較器３０８が決定する場合、制御パラメータの近似値Ｘ*は、ローカル・サーチ機構を使用ことによって、最適制御パラメータの近似値Ｘ*を精細化する精細化ユニット３１０に送られる。(精度または反復回数に関する条件のような)停止条件が満たされるとき、その精細化フェーズは終了する。
【００５２】
値(ｃ＃,Ｙ＃)に関するＭＩＰソリューション(ｃ＊,Ｙ＊)の精度が満足なものであることを精度比較器３０８が決定する場合、停止条件が検知されるまで、プロセスは、非線形制御パラメータＸ'(サーチ・ユニット３０２によって提供された)の近隣値に関して繰り返される。
【００５３】
本発明は、一組の制御パラメータ及び適切なＫＰＩ(ＭＩＰ追跡可能なＫＰＩのサブセット)のための混合整数計画法モデルにおけるプロセス・モデル・インフラストラクチャの一部をモデリングすることによって、及び、そのサブ問題を解決するためにＭＩＰ問題解決アルゴリズム(例えば、シンプレックス、分岐切除法、分岐限定法)を使用することによって、ローカル・サーチ・プロセスを劇的に高速化する。本発明の実施例によるＢＰＭ最適化ソリューションは、ＫＰＩに関する最適化された制御パラメータを提供するためにシミュレーション及びＭＩＰモデルの間に結合機構を提供する。
【００５４】
ＢＰＭ最適化ユニット１５は、線形制御パラメータＸによって表わされる、ＢＰＭパラメトリック調整問題のかなりのサブ部分を取り込むＭＩＰモデルを生成することによって、ＫＰＩパラメータに関連した制御パラメータを自動的に最適化する。しかし、複雑すぎるか或いは混合整数計画法モデルにおいてモデリングされるように適応しないＢＰＭパラメトリック調整問題のわずかな部分(非線形パラメータＸ'によって表わされた)に関しては、ローカル・サーチ機構が使用される。しかる後、ＢＰＭ最適化ユニット１５はその２つの部分を結合して、最適化された制御パラメータ・ベクトル２００を提供する。
【００５５】
従って、ＢＰＭ設計のパフォーマンスは、ローカル・サーチの評価関数として使用される個別のイベント・シミュレーション及びＭＩＰ問題最適化(その両方とも効率的に完全に取り込むことはできない)を結合することによって最適化され得る。その両サイドの連携は、選択された制御パラメータ値のみを交換することにより達成される。
【００５６】
本発明が如何なる制御パラメータ・ベクトル及びＫＰＩベクトルに限定されなくても、本発明は、制御パラメータ及びＫＰＩが事前定義のＭＩＰモデル間に重要なサブセットを有するとき、多少の利点を有する。
【００５７】
図４は、本発明の或る実施例に従って、ＫＰＩに関連する最適の制御パラメータを計算するためのフローチャートである。
【００５８】
ステップ４００において、プロセス・モデルに関連した制御パラメータ・ベクトルが受け取られ、ステップ４０２において、その制御パラメータ・ベクトルが線形パラメータＸ及び非線形パラメータＸ'に分離される。
【００５９】
ＫＰＩ制御パラメータを最適化する方法は、次のように数式化され得る。
(Ｘ,Ｘ')／max ｃ／(ｃ,Ｙ)＝ｆ(Ｘ,Ｘ')
なお、Ａ(Ｘ').Ｘ＜Ｂ(Ｘ')の制約を受ける。
この数式において、
ｆは、個別のイベント・シミュレーションを含む評価関数を表わす。
Ｘは、線形制御パラメータ(または変数)を表わす。
Ｘ'は、非線形制御パラメータを表わす。
Ｙは、ＢＰＭ出力変数を表わす。
ｃは、ＫＰＩ目的ベクトルを表わす。本発明の好ましい実施例では、それは、ソリューションが満足なものかどうか(例えば、他のものよりも良い、他のものと同等、または他のものよりも悪い)を決定することを可能にするＫＰＩの順序付けられた有限のセットを含む。
Ａ及びＢは、線形の(ＭＩＰ)マトリックス及びベクトルであり、Ｘに関する既知のＭＩＰ制約を表わすＸ’の関数である。
【００６０】
評価関数ｆは、制御パラメータによって提供されるソリューションを評価するためにローカル・サーチ方法によって使用されるであろう。本発明の実施例によれば、その評価関数は、ＢＰＭモデルをシミュレートすること及びＫＰＩ結果を観察することによって具現化される。
【００６１】
非線形制御パラメータＸ'は、最適化／シミュレーション・ブランチ４５によって使用されるその非線形制御パラメータ・ベクトルＸ'のためのヒントを決定するために、ローカル・サーチ機構(ブロック４１によって表わされる)によって処理されるであろう。
【００６２】
更に詳しく云えば、ローカル・サーチ・ブランチ４１のステップ４０４において、いずれの適切なローカル・サーチ機構(ヒル・クライミング、タブー、又はシミュレートされたアニーリングのような)も、例えば、第１のヒントＸ'０のようなその非線形制御パラメータＸ'に対する１つ又は複数の値を提供するように反復的に適用される。非線形制御パラメータＸ'に対する選択された値は、それらが(例えば、分岐限定法／分岐切除法によって)解決され得るよう、ＭＩＰモデルに対する定数になるであろう。
【００６３】
ステップ４０６において、プロセス・モデルが第１のフォーマット(例えば、ＢＰＭＮフォーマット)から第２のフォーマット(例えば、エンティティ・リレーションシップ・フォーマット)に変換される。
【００６４】
ステップ４０７において、ＭＩＰモデルが、第１のヒントＸ'０、線形制御パラメータＸ、ビジネス・プロセス・モデル１１０、及びＫＰＩベクトル１５２に基づいて生成される。
【００６５】
ステップ４０８において、ＭＩＰモデルが実行されて、最適制御パラメータの近似値Ｘ＊、ＫＰＩベクトルの近似値ｃ＊、及びビジネス・プロセス出力の近似値Ｙ＊の近似値を決定する。ＭＩＰ近似値は次のような問題の数式によって決定される。
max ｃ＝Ｇ(Ｘ').(Ｘ,Ｙ)
Ｌ(Ｘ').(Ｘ,Ｙ)＜Ｅ(Ｘ')
Ａ(Ｘ')Ｘ＜Ｂ(Ｘ')
上記の数式において、Ｇは、ｆの線形の近似値であり、Ｌ及びＥは、線形の(ＭＩＰ)マトリックス及びベクトルを表わし、Ｘ'の関数は、更なる内部変数ベクトルＹ(入力変数及び出力変数の間のリンクの線形近似値)と共にＢＰＭシステムを表わす。
【００６６】
ステップ４１０において、Ｘに対して決定された結果の近似値Ｘ＊は、シミュレーションｆ(Ｘ＊,Ｘ')によってテストされる。このフェーズでは、Ｘ＊は最適化問題のソリューションにおいて線形制御パラメータＸに対するヒントとして使用され、シミュレーションはＫＰＩ値ｃ＃(以下では「正確なＫＰＩ値」とも呼ばれる)及びＢＰＭ出力値Ｙ＃(以下では、「正確なＢＰＭ出力値」とも呼ばれる)を供給する。
【００６７】
ステップ４１２において、シミュレーションの精度が、ＫＰＩ及びＢＰＭシステム変数(Ｘ＊,Ｙ＊)に対する近似値をそれらの正確な値(ｃ＃,Ｙ＃)＝ｆ(Ｘ,Ｘ')と比較することによって計算される。このステップでは、精度インジケータＰＲが(ｃ＃,Ｙ＃)及び(ｃ＊,Ｙ＊)に基づいて決定され得るし、しかる後、閾値(Ｐ−許容値)に比較され得る。この精度条件は、シミュレートされた結果がＭＩＰ最適化結果に完全に等しいことを期待されない、ということを表わす。或るユーザ定義のパーセンテージまたはユーザ定義の最大の絶対的スラックまでの近似等価性は満足のいくものであり得る。パフォーマンス・インジケータＰＲは、特に、次のものに等しいとして決定される。
ＰＲ＝|(ｃ＃,Ｙ＃)―(ｃ＊,Ｙ＊)|／|(ｃ＃,Ｙ＃)| 
【００６８】
精度が満足のいくもの(ＰＲ＞Ｐ−許容値)である場合、停止条件が満たされなければ非線形パラメータＸ’に対する次の値を提供するために、ローカル・サーチ機構(ブランチ４１)が繰り返される。
【００６９】
ブランチ４１のローカル・サーチ機構が非線形パラメータ・ベクトルＸ'に新しいヒントを供給する。ステップ４１５において、ベクトルＸ'の近隣が計算される。次に、ステップ４１６において、精度に関する条件、ローカル・サーチ反復の数(カウンタにより追跡される)関する条件、またはＫＰＩに関する条件のような、事前定義された停止条件が満たされるかどうかが決定される。停止条件が満たされる場合、ステップ４１７においてそのループは終了する。停止条件が満たされない場合、ステップ４０４がＸ'の近隣値Ｘ'nextをＸ'に対する次の値として選び、ＭＩＰモデルを決定するための定数としてこの値を使用する。ステップ４０６乃至４１４が新しい値Ｘ'nextを用いて反復される。
【００７０】
しかる後、単に最良のソリューションだけを保持するために、各ヒントＸ'に対して見つかった種々の近似値Ｘ＊が比較される。
【００７１】
精度が満足のいくものでない(ＰＲ＜Ｐ−許容値)ということをステップ４１４において決定される場合、制御パラメータの近隣値Ｘ＊自体が、ローカル・サーチ機構を使用する精細化ブランチ４５によって精細化される。精細化ブランチ４５のローカル・サーチ機構は、ローカル・サーチ・ブランチ４１又は他のサーチ・ブランチにおいて使用されるものと同じであってもよい。
【００７２】
精細化ブランチ４５は、線形制御パラメータの近似値Ｘ＊を精細化するようにローカル・サーチ機構を適用する。
【００７３】
ステップ４１８において、ベクトルＸ＊の近隣が計算され、Ｘ＊の近隣値ＸnextがＸ＊に対する次の値として選択される。ステップ４１９において、Ｘ＊の近隣値Ｘnextがシミュレーション値(ｃ＃,Ｙ＃)＝ｆ(Ｘ,Ｘ')を再計算するために使用される。ステップ４２０において、精度に関する条件、ローカル・サーチ反復の数(カウンタを用いて追跡される)に関する条件、又はＫＰＩに関する条件(例えば、ＫＰＩにおけるインクリメントの検出)のような事前定義された停止条件が満たされるかどうかが決定される。その停止条件が満たされる場合、新しいヒントが、ローカル・サーチ・ブランチ４１のステップ４１５及び４１６を反復することによって決定される。停止条件が満たされない場合、ステップ４１８及び４１９が反復される。
【００７４】
それぞれのローカル・サーチ機構と関連してステップ４１６及び４２０において使用される停止条件は機能強化の低下を検知するために定義される。ステップ４２０においてＫＰＩのベクトルに関して計算された最適化目標ｃに対する例示的な停止条件は、現在の最適なソリューションがｘ％以上(例えば、０.１％〜１％)に強化されていないかどうかを判断すること、および、この条件が満たされる場合、この考察されたプロセスを停止することを含み得る。この相対的な機能強化閾値「ｘ％」は絶対的な閾値と置換されてもよい。
【００７５】
本明細書では、ステップ４１６及び４２０のローカル・サーチ機構に関連して使用される用語「近隣」が任意の適切な基準に従って所与のソリューション(又は所与の値)に近いソリューション(又は値)を指定するために使用され得るということは当業者には容易に明らかであろう。例えば、所与のソリューションの近隣は、距離の基準に基づいて決定され得る。例えば、所与のソリューションの近隣は、事前定義された距離内にあるソリューション又は値を含むものとして定義され得る。距離は、三角不等式、例えば、デカルト距離(２つのベクトルの要素間のスラックの２乗の和の平方根)、マンハッタン距離(２つのベクトル間のスラックの絶対値の和)等を満たすメトリクスであってもよい。
【００７６】
以上は、単に本発明の原理を説明するものとみなされたい。更に、当業者は数多くの修正及び変更を容易に想起し得るであろうが、図示及び記述された正確な構造及びオペレーションに本発明を限定することは望ましくなく、従って、本発明の範囲内にあるすべての適当な修正及び均等物を用いることが可能である。特に、本発明は、精細化ユニット及びサーチ・ユニットによって使用されるローカル・サーチ機構に限定されない。更に、本発明は、制御パラメータ又はＫＰＩオブジェクティブの任意のセットに適用する。本発明は、本発明の或る実施例に関しては上述のアプリケーションに限定されず、それは、システムのかなりの部分を取り込んだＭＩＰモデルが提供される、制御パラメータに依存したＫＰＩを含む任意のアプリケーションに適用され得る。
【００７７】
ＭＩＰ最適化コンポーネントをローカル・サーチ機構と結合することによって、本発明は、手操作反復の必要性を取り除いたＢＰＭモデルのより速い調整を可能にする。それによって、本発明はオペレーション・リサーチ技術(ローカル・サーチ混合整数計画法)と個別のイベント・シミュレーション技術との結合を得るが、そのような結合は従来技術では互換性がないと考えられている。本発明の種々の実施例によれば、ＢＰＭモデルは、ＭＩＰモデルによって「近似的に」取り込まれ、シミュレーション・モデルによって「正確に」取り込まれる。
【００７８】
本発明は、全体的にハードウェアの実施例、全体的にソフトウェアの実施例、又はハードウェア及びソフトウェア要素の両方を含む実施例の形体を取り得る。好ましい実施例では、本発明は、ファームウェア、駐在ソフトウェア、マイクロコード等を含むがそれらに限定されないソフトウェアで実施される。
【００７９】
更に、本発明は、コンピュータ又は任意の命令実行システムによる使用又はそれらに関連した使用のためのプログラム・コードを提供するコンピュータ使用可能媒体又はコンピュータ可読媒体からアクセスし得るコンピュータ・プログラムの形式を取り得る。説明の便宜上、コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置、又はデバイスによる使用又はそれらに関連した使用のためのプログラムを含み、格納し、通信し、伝播し、又は搬送し得る任意の装置であってよい。
【００８０】
その媒体は、電子的、磁気的、光学的、電磁気的、赤外線、もしくは半導体システム(又は装置又はデバイス)、或いは伝播媒体であってもよい。コンピュータ可読媒体の例は、半導体又はソリッド・ステート・メモリ、磁気テープ、取外し可能コンピュータ・ディスケット、ランダム・アクセス・メモリ(ＲＡＭ)、読取り専用メモリ(ＲＯＭ)、固定磁気ディスク、及び光ディスクを含む。光ディスクの現在の例は、コンパクト・ディスク−読取り専用メモリ(ＣＤ−ＲＯＭ)、コンパクト・ディスク 読取り／書込み(ＣＤ−Ｒ／Ｗ)、及びＤＶＤを含む。
【００８１】
プログラム・コードを格納及び／又は実行するに適したデータ処理システムは、システム・バスを介してメモリ素子に直接又は間接的に結合された少なくとも１つのプロセッサを含むであろう。メモリ素子は、プログラム・コードの実際の実行中に使用されるローカル・メモリ、大容量記憶装置、及びキャッシュ・メモリを含み得る。キャッシュ・メモリは、プログラム・コードが実行中に大容量記憶装置から検索されなければならない回数を減らすために少なくとも幾つかのプログラム・コードの一時的記憶装置を提供する。
【００８２】
入出力装置、即ち、Ｉ／Ｏ装置(キーボード、ディスプレイ、ポインティング装置等を含むが、これらに限定されない)は、システムに直接又は、介在するＩ／Ｏコントローラを介して結合され得る。
【図１】
0005754709.tif 000002
【図２】
0005754709.tif 000003
【図３】
0005754709.tif 000004
【図４】
0005754709.tif 000005