JP2012032991A - インセンティブ決定方法、プログラム及びシステム - Google Patents

Abstract

【課題】公平且つ、計算量的にも妥当なインセンティブの計算方法を提供する。
【解決手段】x個の案件の集合X={1,2,…,x}と、各担当者の処理時間{t(i)}(1<=i<=n)を入力し、各担当者iに割り当てられる案件の集合W(A,X,t(i),t(-i))を与えるステップであって、ここでAは所与のステップと、MaxInc(X,t(i))=Σ_{w∈X}t(i,Kind(w))+max_{s(i)∈Slower(t(i))}MaxInc(X,s(i))を再帰的に解くことによって、MaxInc(X,t(i))を求め、NewInc(A,X,t(i),t(-i))=Σ_{w∈W(A,X,t(i),t(-i))}t(i,Kind(w))+max_{s(i)∈Slower(t(i))}MaxInc(X,s(i))により各担当者iのインセンティブNewInc(A,X,t(i),t(-i))を決定する。
【選択図】図３

Description

この発明は、仕事の報酬（インセンティブ）を決定する技法に関し、より詳しくは、公平な働きぶりを促進するためのインセンティブ決定方法、プログラム及びシステムに関するものである。

従来より、ローンの査定、保険新契約査定、保険金支払いの査定などの事務ワークフローにおいて、「難しい案件を高スキル/高コスト者、簡単な案件を低スキル/低コスト者に割り当てる」といった最適な案件割り当てによりコスト削減が行われてきている。そのような最適化がすでに行われている場合、さらなるコスト削減のためには、各担当者のスキルアップが必要となる。

そのためには、各担当者のスキルアップを促すようなインセンティブの設計を適切に行い、仕事の速い担当者が報われる必要がある。インセンティブを設計するためには、各担当者の貢献度合いを指標として可視化する必要がある。しかし、単に、一定期間中の処理件数を指標にしても、簡単な案件ばかりを選んだ結果、処理件数が多いだけかもしれない。また、一件あたりの平均の処理時間を指標としても、１０分で処理できるものを、わざと３０分かけて処理している可能性もある。以上のような問題があり、可視化は容易ではない。

特開２００４−２９５５７９号公報は、サービス提供システムにおいて、担当者の評価を自動的に行うことを目的とするものであり、ここで開示されている評価装置は、ワークフローを利用した業務を処理する共通の部門を集中化して、申請された業務を担当者が処理するサービス提供システムに適用される。評価装置は、担当者が処理した業務について、業務内容の重要度とワークフローにおける決済の重要度とを取得し、取得した業務内容の重要度と決済の重要度とに基づいて、業務ごとに、その業務を処理した担当者の評価点数を計算する。この評価点数に基づいて、担当者の報酬額等の評価がされ、また、担当者のスキルレベルが決定される。しかし、ここで開示されている評価装置では、上記のような手抜きの問題に適切に対処できない。

そこで、ゲーム理論におけるMechanism Designの考え方に基づき、「各担当者が本気で働かざるをえない」ようなインセンティブの指標が提案されている。例えば、Nisan, Noam and Amir Ronen, "Algorithmic mechanism design," Games and Economic Behavior (35): pp. 166-196, 2001、及びNoam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, “Algorithmic Game Theory,” Cambridge University Press, 2007などを参照されたい。

これら既知のインセンティブの計算方法の多くは、特定のスケジューリング・アルゴリズム（各担当者への案件の割り当てを行う）に対してのみ機能する。その結果、既存のワークフロー・システムに対して、そのようなインセンティブ指標を導入する際、スケジューリング・アルゴリズムの変更が導入の障壁になる可能性がある。したがって、任意のスケジューリング・アルゴリズムに対しても機能するようなインセンティブの指標が望まれる。

本発明では、、インセンティブは、ワークフロー・システムから算出される各担当者の案件の処理に要する時間の実績値を用いて計算されるが、そのような実績値を用いた場合、任意の（静的な）スケジューリング・アルゴリズムに対しても機能するようなインセンティブの指標が存在することが知られている（例えば、Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano, "The power of verification for one-parameter agents," Journal of Computer and System Sciences, Volume 75, Issue 3 (May 2009)を参照されたい）。

特開２００４−２９５５７９号公報

Nisan, Noam and Amir Ronen, "Algorithmic mechanism design," Games and Economic Behavior (35): pp. 166-196, 2001 Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, "Algorithmic Game Theory," Cambridge University Press, 2007 Vincenzo Auletta, Roberto De Prisco, Paolo Penna, and Giuseppe Persiano, "The power of verification for one-parameter agents," Journal of Computer and System Sciences, Volume 75, Issue 3 (May 2009)

しかし、その既知のインセンティブの計算方法には、次の３つの欠点がある。
1.同じ処理時間（実績値）の担当者が同じ案件を処理しても、与えられるインセンティブの値が異なる可能性があるという意味で、公平性に欠ける。
2.スケジューリング・アルゴリズムが使用されておらず手動で案件を割り振っているようなワークフロー・システムには適用できない。また、スケジューリング・アルゴリズムが使用されていたとしても、そのアルゴリズムが静的ではなく、実行時の情報を用いるような場合に適用できない。
3.インセンティブの計算に指数関数的な計算量が必要となる。

本発明の目的は、上記既知のインセンティブの計算方法を改善して、より公平且つ、計算量的にも妥当なインセンティブの計算方法を提供することにある。

本発明は、上記目的を達成するためになされたものであり、コンピュータの処理により、複数の作業者の間のインセンティブを決定する方法を与える。

このとき先ず、以下のように、定義と前提を与える。
k個の案件の種類をK={1,2,…,k}とし、
n人の担当者をM={1,2,…,n}とし、
担当者iが種類jの案件を処理するのに必要な時間をt(i,j)とし、
案件wの種類をKind(w)とし、
t(i)はベクトル(t(i,1), t(i,2), …, t(i,k))を表すものとし、
t(-i)は、n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）とし、
案件の種類毎にt(i,j)のとりうる値は有限であり、全ての担当者に共通であるとし、
種類jの処理時間の有限集合をT(j)とし、
T(j）は処理時間を要素とする順序集合であり、
順序集合内の処理時間のインターバルは案件種類毎に一定であるとし、
T=T(1)×…×T(k)は担当者の処理時間ベクトル集合を表すものとし、
t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合をSlower(t)とする。ただし、２つの処理時間ベクトルt(1)とt(2)が与えられたとき、少なくとも一つの案件種類jにおいてt(1,j) < t(2,j)が成り立ち、かつ、全ての案件種類jにおいてt(1,j)<=t(2,j)が成り立つときに、t(2)がt(1)よりも遅いと定義する。したがって、Slower(t)の集合にはt自身は含まれない。

そこで、本発明によれば、コンピュータの処理によって、
x個の案件の集合X={1,2,…,x}と、各担当者の処理時間{t(i)} (1<= i <=n)を入力し、各担当者iに割り当てられる案件の集合 W(A,X,t(i),t(-i))を与えるステップであって、ここでAは所与のスケジューリング・アルゴリズムであるステップと、
MaxInc(X, t(i)) = Σ_{w ∈ X} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))を再帰的に解くことによって、MaxInc(X, t(i))を求めるステップと、
MaxInc(X, t(i))を求めるステップを用いて、NewInc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))により、インセンティブNewInc(A, X, t(i), t(-i)) を計算するステップを実行することによって、担当者iのインセンティブが決定される。

このとき、好適には、MaxInc(X, t(i))を求めるステップは、
処理時間t∈T(j)が与えられたとき、次に遅い処理時間をOneLevelSlower(t)とし、種類がjの案件だけを含むような案件集合Xの部分集合をX(j)とし、
(a) 所与の変数resultを0に初期化するステップと、
(b) result=result+Σ_{w ∈ X} t(i, Kind(w))を計算するステップと、
(c) Diff=Σ_{w ∈ X(j)} OneLevelSlower(t(i, j)) - Σ_{w ∈ X(j)} t(i, j) が最大となるような案件の種類jを計算し選択するステップであって、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しない場合はresultを出力してreturnするステップと、
(d) 選択した案件種類jに対応する処理時間t(i,j)をOneLevelSlower(t(i, j))で置き換えたものを新しいt(i)として、つまり、t(i)=(t(i,1),t(i,2),…,t(i,j-1),OneLevelSlower(t(i,j)),t(i,j+1),…,t(i,k))を計算して、ステップ(b)に戻るステップを有する。

この発明によれば、担当者が本気で働いているとき適切にインセンティブが与えられ、且つ、計算量も妥当であるインセンティブの決定方法が提供される。

本発明を実施するためのハードウェアの一例のブロック図である。 本発明を実施するための機能ブロックの図である。 本発明のインセンティブ計算処理のフローチャートを示す図である。 本発明のインセンティブ計算処理から呼び出されるサブルーチンの処理のフローチャートを示す図である。

以下、図面に基づき、この発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。尚、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことを理解されたい。

図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・パス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のＰｅｎｔｉｕｍ（商標） ４、Ｃｏｒｅ（商標）２ Ｄｕｏ、Ｘｅｏｎ（商標）、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量をもつものである。ハードディスク・ドライブ１０８は、好適には例えば、３２０ＧＢ以上の容量をもつものである。

ハードディスク・ドライブ１０８には、個々に図示しないが、オペレーティング・システムが、予め格納されている。オペレーティング・システムは、Ｌｉｎｕｘ（商標）、マイクロソフト社のＷｉｎｄｏｗｓ（商標）７、Ｗｉｎｄｏｗｓ ＸＰ（商標）、Ｗｉｎｄｏｗｓ（商標）２０００、アップルコンピュータのＭａｃ ＯＳ（商標）などの、ＣＰＵ１０４に適合する任意のものでよい。

ハードディスク・ドライブ１０８にはさらに、図２に関連して後述する業務（ワークフロー）ログのファイル２０２、処理時間計測モジュール２０４、スケジューリング・モジュール２０６、インセンティブ計算モジュール２０８などが格納されている。これらのモジュールは、Ｃ、Ｃ＋＋、Ｃ＃、Ｊａｖａ(R)などの既存のプログラミング言語処理系で作成することができ、オペレーティング・システムの働きで、これらのモジュールは適宜主記憶１０６にロードされて実行される。

キーボード１１０及びマウス１１２は、上述の業務ログの収集処理、処理時間計測モジュール２０４、スケジューリング・モジュール２０６、インセンティブ計算モジュール２０８などを起動したり、文字を打ち込んだりするために使用される。

ディスプレイ１１４は、好適には、液晶ディスプレイであり、例えば、ＸＧＡ（１０２４×７６８の解像度）、またはＵＸＧＡ（１６００×１２００の解像度）などの任意の解像度のものを使用することができる。ディスプレイ１１４は、業務ログから生成されたグラフを表示するためなどに使用される。

図１のシステムは更に、バス１０２に接続された通信インターフェース１１６を介して、ＬＡＮ、ＷＡＮなどの外部ネットワークに接続されている。通信インターフェース１１６は、イーサネット（商標）などの仕組みにより、外部ネットワーク上にあるサーバなどのシステムとデータのやりとりを図る。

サーバ（図示しない）には、担当者が操作するクライアント・システム（図示しない）が接続され、サーバ上で、担当者が操作した結果の業務ログが、ネットワークを介して、サーバ上に蓄積される。すると、業務ログのファイル２０２は実際上は、図１のシステムではなく、サーバ上にあってもよいし、あるいは、一部または全部を、ネットワークを介して、図１のシステムのハードディスク・ドライブ１０８に転送してもよい。

次に、図２を参照して、本発明に関連して、ハードディスク・ドライブ１０８に保存されたファイル及び機能モジュールの働きを説明する。

図２において、業務ログ２０２は、ハードディスク・ドライブ１０８に保存されたファイルであり、業務の開始時間、業務の終了時間、業務の種類、その業務を行った担当者のＩＤなどのデータを含む。業務ログ２０２のエントリは、好適には、担当者が操作するクライアント・システム（図示しない）からネットワークを介して一旦サーバに集められ、図１のシステムに送信することによって収集されたものである。この業務ログ２０２の形式は、ＣＳＶ、ＸＭＬなど、コンピュータの処理に適合する任意のものを用いることができる。

処理時間計測モジュール２０４は、業務ログ２０２のエントリを走査して、次のような情報を統計的に計算する。
k個の案件の種類：K={1,2,…,k}
n人の担当者のＩＤ：M={1,2,…,n}
担当者iが種類jの案件を処理するのに必要な時間：t(i,j)
種類jの処理時間の有限集合:T(j)

さらにまた、以下のような値を定義して使用する。
ベクトル(t(i,1), t(i,2), …, t(i,k))であるt(i)
n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）であるt(-i)
担当者の処理時間ベクトル集合であるT=T(1)×…×T(k)
t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合であるSlower(t)

すなわち、本発明によれば、各担当者iの処理時間ベクトルt(i)が、過去の一定期間の業務ログ（ワークフロー・システム）の実行ログから算出される。例えば、平均値として算出してもよいし、あるいは、Fast,Medium,Slowを意味する1,2,3の３つのレベルとして算出してもよい。また、各担当者のt(i)は定期的に更新してもよい。

担当者iの真の処理時間をt(i)で表現し、ワークフロー・システムのログから算出した処理時間をb(i)で表現すると、以下の３つの場合が考えられる。
ケース１：b(i)=t(i) ： 担当者iが本気で仕事をしている場合が、この場合に対応する。
ケース２：b(i) ∈Slower(t(i)) ： 担当者iが手を抜いている場合である。例えば、実際には１０分で完了できている案件を、ワークフロー・システム上では、わざと２０分で完了させているような場合である。つまり、実際にはもっと速く案件を処理できることを意味する。
ケース３：t(i) ∈Slower(b(i)) ： 上とは逆の場合であり、「実際には案件の処理にもっと時間がかかっている」ことを意味する。しかし、b(i)をワークフロー・ログから算出している限り、この場合は、起こりえないと仮定できる。

すなわち、本発明の目的は、ケース１の場合に担当者に担当者に与えられるインセンティブが最大化され、ケース２のような不正を行う担当者が報われないようにするためのインセンティブを設計することである。

スケジューリング・モジュール２０６は、案件の集合X={1,2,…,x}を入力し、処理時間計測モジュール２０４から提供されるデータを用いて、各担当者iに割り当てられる案件の集合W(A,X,t(i),t(-i))を計算して出力する。ここでAは、所定のスケジューリング・アルゴリズムである。

一般のスケジューリングでは、各担当者の処理時間{t(i)}を考慮し、全案件が完了するまでの処理時間が最小になるようなスケジューリングが行われる。本発明では、具体的なスケジューリング・アルゴリズムは仮定しない。特に、手動でのスケジューリングであってもよい。また、オンライン・アルゴリズムでもオフライン・アルゴリズムのいずれでもよい。ただし、オンライン・アルゴリズムの場合は、入力となる案件集合Xが、空集合で始まり、案件が一つずつ付加されていくのとする。ともかく、以下では、ある特定のスケジューリング・アルゴリズムAが使用されると仮定する。

インセンティブ計算モジュール２０８は、処理時間計測モジュール２０４から提供されるデータと、スケジューリング・モジュール２０６から提供される各担当者iに割り当てられる案件の集合W(A,X,t(i),t(-i))の値を用いて、本発明のアルゴリズムに従い、各担当者iのインセンティブNewInc(A,X,t(i),t(-i))を計算して出力する。NewInc(A,X,t(i),t(-i))の計算については、図３及び図４のフローチャートに従って、詳細に説明する。

図３において、ステップ３０２では、処理時間計測モジュール２０４が、業務ログ２０２のエントリを走査して、上述した、K={1,2,…,k}、M={1,2,…,n}、t(i,j)、T(j)を計算する。また、ベクトル(t(i,1), t(i,2), …, t(i,k))であるt(i)、n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）であるt(-i)、担当者の処理時間ベクトル集合であるT=T(1)×…×T(k)、t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合として、Slower(t)を定義する。

ステップ３０４では、スケジューリング・モジュール２０６が、案件の集合X={1,2,…,x}を入力し、処理時間計測モジュール２０４から提供されるデータを用いて、各担当者iに割り当てられる案件の集合W(A,X,t(i),t(-i))を計算して出力する。

ステップ３０６では、インセンティブ計算モジュール２０８が、MaxInc(X, t(i))を計算して、NewInc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))により、担当者iのインセンティブNewInc(A, X, t(i), t(-i)) を計算する。インセンティブ計算モジュール２０８は、担当者i毎に、この計算結果を出力する。ただし、max_{s(i) ∈ Slower(t(i))}による最大値を計算するために、Slower(t(i))に含まれる全ての処理時間ベクトルを考慮する必要はない。Slower(t(i))の部分集合であるOneLevelSlower(t(i))に含まれる処理時間ベクトルだけを考慮すればよい。つまり、max_{s(i) ∈ Slower(t(i))}をmax_{s(i) ∈ OneLevelSlower(t(i))}で置き換えてもよい。OneLevelSlower(t(i))は以下のように定義される。処理時間ベクトルt(i)=(t(i,1), t(i,2), …, t(i,k))が与えられたとき、一要素だけを、次に遅い処理時間で置き換えた処理時間ベクトルの集合をOneLevelSlower(t(i))と定義する。つまり、OneLevelSlower(t(i))={
(OneLevelSlower(t(i,1)), t(i,2), …, t(i,k)),
(t(i,1), OneLevelSlower(t(i,2)), …, t(i,k)),
…,
(t(i,1), t(i,2), …, OneLevelSlower((t(i,k)))
}
と定義する。ただし、OneLevelSlower(t(i,j))が存在しない案件種類jに対応する処理時間ベクトルは、OneLevelSlower(t(i))には含まれないものとする。その結果、OneLevelSlower(t(i))のサイズは、せいぜい案件種類数kであるので、max_{s(i) ∈ OneLevelSlower(t(i))}の計算は容易である。

その際、インセンティブ計算モジュール２０８は、MaxInc(X, t(i)) = Σ_{w ∈ X} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))を再帰的に解くことによって、MaxInc(X, t(i))を計算する。この計算は、具体的に、後述する図４のフローチャートで示すサブルーチンを呼び出すことによって計算される。

なお、Σ_{w ∈ X} t(i, Kind(w))とは、より数学的に慣用の表現では、

である。
また、max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))も、より数学的に慣用の表現では

である。
このような便宜的な表記法は、この明細書を通じて共通である。

次に、図４のフローチャートを参照して、MaxInc(X, t(i))を計算するサブルーチンの処理を説明する。

ステップ４０２では、サブルーチンは、result = 0と初期化する。

ステップ４０４では、サブルーチンは、result=result+Σ_{w ∈ X} t(i, Kind(w))を計算する。

ステップ４０６では、サブルーチンは、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しないかどうかを判断する。ここで、OneLevelSlower(t)とは、処理時間t∈T(j)が与えられたとき、次に遅い処理時間である。もし存在しないなら、サブルーチンは、ステップ４１２でresultを返し、処理を終る。

ステップ４０６で、サブルーチンが、ある案件の種類jに対してOneLevelSlower(t(i, j))が存在すると判断すると、処理はステップ４０８に進む。

ステップ４０８では、サブルーチンは、種類がjの案件だけを含むような案件集合Xの部分集合をX(j)とし、Diff=Σ_{w ∈ X(j)} OneLevelSlower(t(i, j)) - Σ_{w ∈ X(j)} t(i, j) が最大となるような案件の種類jを計算し選択する。

サブルーチンは次に、ステップ４１０に進み、選択した案件種類jに対応する処理時間t(i,j)をOneLevelSlower(t(i, j))で置き換えたものを新しいt(i)として、つまり、t(i)=(t(i,1),t(i,2),…,t(i,j-1),OneLevelSlower(t(i,j)),t(i,j+1),…,t(i,k))を計算して、ステップ４０４に戻る。

なお、案件の種類毎に処理時間t(i,j)のとりうる値は有限の集合T(j)であり、全ての担当者に共通であると仮定する。例えば、T(j)={t1,t2,…tn}でありt1<t2<…<tnという順序関係が成り立つ場合、t1が一番速く、tnが一番遅いことを意味する。ある処理時間t∈T(j)が与えられたとき、次に遅い処理時間が、上述したOneLevelSlower(t)である。また、処理時間のインターバルは案件種類毎に一定であると仮定する。つまり、案件種類毎にOneLevelSlower(t)-tの値は常に一定である。このような前提では、t(i,j)のとりうる値は有限であるので、ステップ４０４からステップ４１２のループの循環の中で、ステップ４０６で、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しないという状態に必ず行き当たり、サブルーチンは適切にreturnすることができる。

次に、本発明の効果を実証するために、インセンティブの具体的な計算例を示す。その際、計算の便宜上、次の例を考える。
M={1,2}: すなわち、担当者は2人だけと仮定する。
K={1,2}: 案件は、2種類の案件だけと仮定する。
各種類の処理時間のとりうる値は、T(1)={1,2,3}, T(2)={4,5,6}であると仮定する。
X={1,2,3,4}: 案件は、4件だけと仮定する。
各案件の種類は、Kind(1)=1, Kind(2)=2, Kind(3)=1, Kind(4)=2であると仮定する。
以下のように、２人の処理時間ベクトルは同じであると仮定する。
t(1)={t(1,1)=2, t(1,2)=5}
t(2)={t(2,1)=2, t(2,2)=5}
この例においては、Slower({2,5})={{3,5}, {2,6}, {3,6}}となる。

このようなデータが与えられたとき、先ず、非特許文献３に基づく、従来の方法で計算した場合の例を示す。非特許文献３に基づく方法では、下記の式で、担当者iのインセンティブInc(A, X, t(i), t(-i))を計算する。
Inc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} Inc(A, X, s(i), t(-i))

下記の表は、担当者１の処理時間ベクトルと、担当者１に割り当てられた案件の対応を示すものである。案件の割当ては、スケジューリング・モジュール２０６によって、スケジューリング・アルゴリズムＡを用いて、与えられたものである。つまり、処理時間ベクトルがt(1)={2,5}である担当者１には、案件{2,5}が割り当てられる。また、例えば、処理時間ベクトルが{3,5}∈Slower(t(1))であると仮定した場合は、案件{1}が割り当てられる。

表１の案件割り当てが行われると仮定した場合、担当者１のインセンティブの計算は、下記のとおりとなる。t(1)={2,5}の場合のインセンティブであるInc(A,X,{2,5},t(-1))が、担当者１のインセンティブである。
t(1)={3,6}の場合のインセンティブ
Inc(A, X, {3,6}, t(-1))
= Σ_{w ∈ {1,2}} t(1,Kind(w)) + max_{s ∈ Slower({3,6})} Inc(A, X, s, t(-1))
= 9 + 0 = 9
t(1)={3,5}の場合のインセンティブ
Inc(A, X, {3,5}, t(-1))
= Σ_{w ∈ {1}} t(1,Kind(w)) + max_{s ∈ Slower({3,5})} Inc(A, X, s, t(-1))
= 3 + max_{s∈ Slower({3,5})} Inc(A, X, s, t(-1))
= 3 + 9 = 12
t(1)={2,6}の場合のインセンティブ
Inc(A, X, {2,6}, t(-1))
= Σ_{w ∈ {2}} t(1,Kind(w)) + max_{s ∈ Slower({2,6})} Inc(A, X, s, t(-1))
= 6 + max_{s ∈ Slower({2,6})} Inc(A, X, s, t(-1))
= 6 + 9 =15
t(1)={2,5}の場合のインセンティブ
Inc(A, X, {2,5}, t(-1))
= Σ_{w ∈ {1,2}} t(1,Kind(w)) + max_{s ∈ Slower({2,5})} Inc(A, X, s, t(-1))
= 7 + max_{s ∈ Slower({2,5})} Inc(A, X, s, t(-1))
= 7 + 15 = 22

下記の表は、担当者２の処理時間ベクトルと、担当者２に割り当てられた案件の対応を示すものである。案件の割当ては、スケジューリング・モジュール２０６によって、スケジューリング・アルゴリズムＡを用いて、与えられたものである。

表２の案件割り当てが行われると仮定した場合、担当者２のインセンティブの計算は、下記のとおりとなる。t(2)={2,5}の場合のインセンティブであるInc(A,X,{2,5},t(-2))が、担当者２のインセンティブである。
t(2)={3,6}の場合のインセンティブ
Inc(A, X, {3,6}, t(-2))
= Σ_{w ∈ {3,4}} t(2,Kind(w)) + max_{s ∈ Slower({3,6})} Inc(A, X, s, t(-1))
= 9 + 0 = 9
t(2)={3,5}の場合のインセンティブ
Inc(A, X, {3,5}, t(-2))
= Σ_{w ∈ {3,4}} t(2,Kind(w)) + max_{s ∈ Slower({3,5})} Inc(A, X, s, t(-2))
= 8 + max_{s∈ Slower({3,5})} Inc(A, X, s, t(-2))
= 8 + 9 = 17
t(2)={2,6}の場合のインセンティブ
Inc(A, X, {2,6}, t(-2))
= Σ_{w ∈ {3,4}} t(2,Kind(w)) + max_{s ∈ Slower({2,6})} Inc(A, X, s, t(-2))
= 8 + max_{s ∈ Slower({2,6})} Inc(A, X, s, t(-2))
= 8 + 9 =17
t(2)={2,5}の場合のインセンティブ
Inc(A, X, {2,5}, t(-2))
= Σ_{w ∈ {3,4}} t(2,Kind(w)) + max_{s ∈ Slower({2,5})} Inc(A, X, s, t(-2))
= 7 + max_{s ∈ Slower({2,5})} Inc(A, X, s, t(-2))
= 7 + 17 = 24

上記で、担当者１と担当者２は、同じ種類の案件を同じ数だけ割り当てられたにもかかわらず、そのインセンティブは、22と24とで異なる値となる。つまり、この従来技術のスキームでは、同じ能力と想定した担当者の間でも、インセンティブが公平に計算されないことが見て取れる。

次に、本発明の方法で計算した場合の例を示す。

下記の表は、担当者１の処理時間ベクトルと、担当者１に割り当てられた案件の対応を示すものである。案件の割当ては、スケジューリング・モジュール２０６によって、スケジューリング・アルゴリズムＡを用いて、与えられたものである。本発明の方法では、Slower(t(1))の処理時間ベクトルの場合の案件割り当ては考慮しないので表中でも省略されている。

表３の案件割り当てが行われると仮定した場合、インセンティブの計算は、下記のとおりとなる。
t(1) = {3,6}の場合のMaxIncの計算
MaxInc(X,t(1))
= Σ_{w ∈ {1,2,3,4}} t(1,Kind(w)) + max_{s∈ Slower({3,6})} MaxInc(X, s)
=18 + 0 =18
t(1) = {3,5}の場合のMaxIncの計算
MaxInc(X,t(1))
= Σ_{w ∈ {1,2,3,4}} t(1,Kind(w)) + max_{s ∈ Slower({3,5})} MaxInc(X, s)
= 16 + 18
= 34
t(1) = {2,6}の場合のMaxIncの計算
MaxInc(X,t(1))
= Σ_{w ∈ {1,2,3,4}} t(1,Kind(w)) + max_{s ∈ Slower({2,6})} MaxInc(X, s)
= 16 + 18
= 34
t(1) = {2,5}として、担当者１のインセンティブは以下のように計算される。
NewInc(A, X, {2,5}, t(-1))
= Σ_{w ∈ {1,2}} t(1,Kind(w)) + max_{s ∈ Slower({2,5})} MaxInc(X, s)
= 7+max_{s ∈ Slower({2,5})} MaxInc(X, s)
= 7+34
= 41

下記の表は、担当者２の処理時間ベクトルと、担当者２に割り当てられた案件の対応を示すものである。案件の割当ては、スケジューリング・モジュール２０６によって、スケジューリング・アルゴリズムＡを用いて、与えられたものである。本発明の方法では、Slower(t(2))の処理時間ベクトルの場合の案件割り当ては考慮しないので表中でも省略されている。

表４の案件割り当てが行われると仮定した場合、インセンティブの計算は、下記のとおりとなる。MaxInc()の値は、上記の計算例と同じであるので省略する。t(2)={2,5}として、担当者２のインセンティブは
NewInc(A, X, {2,5}, t(-2))
= Σ_{w ∈ {3,4}} t(2,Kind(w)) + max_{s ∈ Slower({2,5})} MaxInc(X, s)
= 7+max_{s ∈ Slower({2,5})} MaxInc(X, s)
= 7+34
= 41
となって、担当者１のインセンティブと計算結果は全く同じとなる。すなわち、本発明のインセンティブの計算では、従来技術の不公平さが解消される。

また、従来の方法において、max_{s(i) ∈ Slower(t(i))} Inc(A, X, s(i), t(-i))という項を計算する必要があるが、max部分の計算には、擬似的な処理時間ベクトルs(i)を用いて、スケジューリング・アルゴリズムAをシミュレートする必要がある。したがって、手動で案件の割り当てを行っているような場合には適用できない。また、人間が行う案件の処理の完了時間は、通常、様々な理由から遅くなったり速くなったりするので、完了するまでの正確な時間はわからない。スケジューリング・アルゴリズムAが、そのような実行時の情報を用いる場合には、適用できない。それに対して、本発明は、任意のスケジューリング・アルゴリズムAに対して適用可能である。

さらに、Slower(t(i))の集合のサイズは、案件の種類数に対して、指数関数的に増加するので、max部分の計算量が膨大になる。あるいはスケジューリング・アルゴリズムAの特性を考慮して、効率的なアルゴリズムを、別途、設計する必要がある。

本発明のインセンティブの計算には、このmax部分の計算にスケジューリング・アルゴリズムは最早現れず、図４のフローチャートで示すアルゴリズムを使用することにより効率的に計算可能である。従って、本発明は、計算量の点でも、上記従来の方法よりも有利である。すなわち、従来技術では、案件の種類数に対応してほぼ指数時間の計算量がかかっていたのを、本発明によると、多項式時間程度に削減することができる。

以上のように、特定の実施例に従い、本発明を説明してきたが、本発明は、特定のオペレーティング・システムやプラットフォームに限定されず、任意のコンピュータ・システム上で実現可能である。また、ネットワークに接続されたシステムではなく、スタンドアロンであってもよい。

１０２ システム・パス
１０２ バス
１０４ ＣＰＵ
１０６ 主記憶
１０８ ハードディスク・ドライブ
１１０ キーボード
１１２ マウス
１１４ ディスプレイ
１１６ 通信インターフェース
２０２ 業務ログ
２０４ 処理時間計測モジュール
２０６ スケジューリング・モジュール
２０８ インセンティブ計算モジュール

Claims (6)

1. コンピュータの処理により、複数の作業者の間のインセンティブを決定する方法であって、
   k個の案件の種類をK={1,2,…,k}とし、
   n人の担当者をM={1,2,…,n}とし、
   担当者iが種類jの案件を処理するのに必要な時間をt(i,j)とし、
   案件wの種類をKind(w)とし、
   t(i)はベクトル(t(i,1), t(i,2), …, t(i,k))を表すものとし、
   t(-i)は、n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）とし、
   案件の種類毎にt(i,j)のとりうる値は有限であり、全ての担当者に共通であるとし、
   種類jの処理時間の有限集合をT(j)とし、
   T(j）は処理時間を要素とする順序集合であり、
   順序集合内の処理時間のインターバルは案件種類毎に一定であるとし、
   T=T(1)×…×T(k)は担当者の処理時間ベクトル集合を表すものとし、
   t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合をSlower(t)とする定義と前提の下で、
   前記コンピュータの処理により、x個の案件の集合Xと、各担当者の処理時間{t(i)} (1<= i <=n)を入力し、各担当者iに割り当てられる案件の集合を W(A,X,t(i),t(-i))を与えるステップであって、ここでAは所与のスケジューリング・アルゴリズムであるステップと、
   前記コンピュータの処理により、MaxInc(X, t(i)) = Σ_{w ∈ X} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))を再帰的に解くことによって、MaxInc(X, t(i))を求めるステップと、
   前記コンピュータの処理により、前記MaxInc(X, t(i))を求めるステップを用いて、NewInc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))により、各担当者iのインセンティブNewInc(A, X, t(i), t(-i)) を計算するステップを有する、
   インセンティブを決定する方法。
2. 前記MaxInc(X, t(i))を求めるステップは、
   処理時間t∈T(j)が与えられたとき、次に遅い処理時間をOneLevelSlower(t)とし、
   (a) 所与の変数resultを0に初期化するステップと、
   (b) result=result+Σ_{w ∈ X} t(i, Kind(w))を計算するステップと、
   (c) Diff=Σ_{w ∈ X(j)} OneLevelSlower(t(i, j)) - Σ_{w ∈ X(j)} t(i, j) が最大となるような案件の種類jを計算し選択するステップであって、ここでX(j)は、種類がjの案件だけを含むような案件集合Xの部分集合であり、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しない場合はresultを出力してreturnするステップと、
   (d) 選択した案件種類jに対応する処理時間t(i,j)をOneLevelSlower(t(i, j))で置き換えたものを新しいt(i)として、つまり、t(i)=(t(i,1),t(i,2),…,t(i,j-1),OneLevelSlower(t(i,j)),t(i,j+1),…,t(i,k))を計算して、ステップ(b)に戻るステップとを有する、請求項１に記載の方法。
3. コンピュータの処理により、複数の作業者の間のインセンティブを決定するプログラムであって、
   k個の案件の種類をK={1,2,…,k}とし、
   n人の担当者をM={1,2,…,n}とし、
   担当者iが種類jの案件を処理するのに必要な時間をt(i,j)とし、
   案件wの種類をKind(w)とし、
   t(i)はベクトル(t(i,1), t(i,2), …, t(i,k))を表すものとし、
   t(-i)は、n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）とし、
   案件の種類毎にt(i,j)のとりうる値は有限であり、全ての担当者に共通であるとし、
   種類jの処理時間の有限集合をT(j)とし、
   T(j）は処理時間を要素とする順序集合であり、
   順序集合内の処理時間のインターバルは案件種類毎に一定であるとし、
   T=T(1)×…×T(k)は担当者の処理時間ベクトル集合を表すものとし、
   t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合をSlower(t)とする定義と前提の下で、
   前記コンピュータに、
   、x個の案件の集合X={1,2,…,x}と、各担当者の処理時間{t(i)} (1<= i <=n)を入力し、各担当者iに割り当てられる案件の集合を W(A,X,t(i),t(-i))を与えるステップであって、ここでAは所与のスケジューリング・アルゴリズムであるステップと、
   MaxInc(X, t(i)) = Σ_{w ∈ X} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))を再帰的に解くことによって、MaxInc(X, t(i))を求めるステップと、
   前記MaxInc(X, t(i))を求めるステップを用いて、NewInc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))により、各担当者iのインセンティブNewInc(A, X, t(i), t(-i)) を計算するステップを実行させる、
   インセンティブを決定するプログラム。
4. 前記MaxInc(X, t(i))を求めるステップは、
   処理時間t∈T(j)が与えられたとき、次に遅い処理時間をOneLevelSlower(t)とし、
   (a) 所与の変数resultを0に初期化するステップと、
   (b) result=result+Σ_{w ∈ X} t(i, Kind(w))を計算するステップと、
   (c) Diff=Σ_{w ∈ X(j)} OneLevelSlower(t(i, j)) - Σ_{w ∈ X(j)} t(i, j) が最大となるような案件の種類jを計算し選択するステップであって、ここでX(j)は、種類がjの案件だけを含むような案件集合Xの部分集合であり、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しない場合はresultを出力してreturnするステップと、
   (d) 選択した案件種類jに対応する処理時間t(i,j)をOneLevelSlower(t(i, j))で置き換えたものを新しいt(i)として、つまり、t(i)=(t(i,1),t(i,2),…,t(i,j-1),OneLevelSlower(t(i,j)),t(i,j+1),…,t(i,k))を計算して、ステップ(b)に戻るステップとを有する、請求項３に記載のプログラム。
5. コンピュータの処理により、複数の作業者の間のインセンティブを決定するシステムであって、
   k個の案件の種類をK={1,2,…,k}とし、
   n人の担当者をM={1,2,…,n}とし、
   担当者iが種類jの案件を処理するのに必要な時間をt(i,j)とし、
   案件wの種類をKind(w)とし、
   t(i)はベクトル(t(i,1), t(i,2), …, t(i,k))を表すものとし、
   t(-i)は、n人の担当者のうち担当者iを除くn-1人の担当者の処理時間を表すベクトル（t(1), t(2),…, t(i-1), t(i+1), …t(n)）とし、
   案件の種類毎にt(i,j)のとりうる値は有限であり、全ての担当者に共通であるとし、
   種類jの処理時間の有限集合をT(j)とし、
   T(j）は処理時間を要素とする順序集合であり、
   順序集合内の処理時間のインターバルは案件種類毎に一定であるとし、
   T=T(1)×…×T(k)は担当者の処理時間ベクトル集合を表すものとし、
   t∈Tが与えられたとき、tより遅いすべての処理時間ベクトルの集合をSlower(t)とする定義と前提の下で、
   、x個の案件の集合X={1,2,…,x}と、各担当者の処理時間{t(i)} (1<= i <=n)を入力し、各担当者iに割り当てられる案件の集合を W(A,X,t(i),t(-i))を与える手段であって、ここでAは所与のスケジューリング・アルゴリズムである手段と、
   MaxInc(X, t(i)) = Σ_{w ∈ X} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))を再帰的に解くことによって、MaxInc(X, t(i))を求める手段と、
   前記MaxInc(X, t(i))を求める手段を用いて、NewInc(A, X, t(i), t(-i)) = Σ_{w ∈ W(A,X,t(i),t(-i))} t(i, Kind(w)) + max_{s(i) ∈ Slower(t(i))} MaxInc(X, s(i))により、各担当者iのインセンティブNewInc(A, X, t(i), t(-i)) を計算する手段を有する、
   インセンティブを決定するシステム。
6. 前記MaxInc(X, t(i))を求める手段は、
   処理時間t∈T(j)が与えられたとき、次に遅い処理時間をOneLevelSlower(t)とし、
   (a) 所与の変数resultを0に初期化する手段と、
   (b) result=result+Σ_{w ∈ X} t(i, Kind(w))を計算する手段と、
   (c) Diff=Σ_{w ∈ X(j)} OneLevelSlower(t(i, j)) - Σ_{w ∈ X(j)} t(i, j) が最大となるような案件の種類jを計算し選択する手段であって、ここでX(j)は、種類がjの案件だけを含むような案件集合Xの部分集合であり、いかなる案件の種類jに対してもOneLevelSlower(t(i, j))が存在しない場合はresultを出力してreturnする手段と、
   (d) 選択した案件種類jに対応する処理時間t(i,j)をOneLevelSlower(t(i, j))で置き換えたものを新しいt(i)として、つまり、t(i)=(t(i,1),t(i,2),…,t(i,j-1),OneLevelSlower(t(i,j)),t(i,j+1),…,t(i,k))を計算する手段を有し、
   前記手段(d)の後、前記手段(b)を実行する、
   請求項５に記載のシステム。

Images