(57)【要約】【課題】複数のＡ要素（研修プログラム）のそれぞれと、複数のＢ要素（参加者）のそれぞれとの間でマッチングを行うマッチングシステムにおいて、各Ａ要素に割り当てられるＢ要素の数のバランスを調整できるマッチングシステムを提供する。【解決手段】マッチングシステムは、Ａ要素に割り当て可能なＢ要素の最大数としての定員上限数と、バランス調整の基準としての定員とを定義する研修プログラムマスタファイル１を格納する。マッチングシステムは、Ａ要素の定員超過を許容する仮マッチングを行いつつ、定員を超過しているＡ要素については、一定の条件でＢ要素の仮マッチングを取り消す。【選択図】図２
2012118818.tif 000002
【特許請求の範囲】
【請求項１】
集合Ａに含まれる複数のＡ要素のそれぞれと、集合Ｂに含まれる複数のＢ要素のそれぞれとの間でマッチングを行うマッチングシステムであって、
前記Ａ要素の少なくとも１つは、複数の前記Ｂ要素とマッチ可能であり、
前記Ｂ要素はそれぞれ、多くとも１つのみの前記Ａ要素とマッチされる
マッチングシステムにおいて、
前記マッチングシステムは、
前記集合Ａについて定義され、前記Ｂ要素の全部または一部を一意に順位付ける第一の優先度リストと、
前記Ｂ要素のそれぞれについて定義され、前記Ａ要素の全部または一部を一意に順位付ける第二の優先度リストと、
前記集合Ａとマッチ可能な前記Ｂ要素の最大数を表す集合Ａ定員数と、
前記Ａ要素のそれぞれについて、そのＡ要素とマッチ可能な前記Ｂ要素の最大数を表すＡ要素定員上限数と、
前記Ａ要素のそれぞれについて、前記Ａ要素定員上限数以下の所定の数を表すＡ要素定員数と
を記憶し、
前記マッチングシステムは、前記第一の優先度リストに含まれる前記Ｂ要素のそれぞれについて、前記第二の優先度リストに従って前記Ａ要素のそれぞれとの組合せについて順次仮マッチング処理を行うとともに、前記仮マッチング処理の結果として得られる仮マッチ集合に基づいてマッチングを行うものであり、
前記仮マッチング処理において、以下の条件：
‐前記集合Ａに関して前記仮マッチ集合に含まれている組合せの数が、前記集合Ａ定員数より小さい
‐仮マッチング処理中の前記Ａ要素に関して前記仮マッチ集合に含まれている組合せの数が、そのＡ要素のＡ要素定員上限数より小さい
の双方が満たされる場合には、仮マッチング処理中の組合せを前記仮マッチ集合に加え、
前記条件のいずれかが満たされない場合には、仮マッチング処理中の前記組合せを前記仮マッチ集合に加えるとともに、前記仮マッチ集合に含まれる組合せのいずれかを前記仮マッチ集合から除外する仮マッチ除外処理を行い、
前記仮マッチ除外処理は、前記Ａ要素定員数を超える数の組合せが仮マッチ集合に含まれている前記Ａ要素に関する組合せのいずれかを対象として行われる
マッチングシステム。
【請求項２】
前記仮マッチ除外処理において、前記仮マッチ除外処理の対象となる前記組合せは、前記第一の優先度リストに基づいて決定される、請求項１に記載のマッチングシステム。
【請求項３】
前記マッチングシステムは、前記仮マッチ除外処理において、
仮マッチング処理中の前記Ａ要素に関して前記仮マッチ集合に含まれる組合せの数が、前記仮マッチング処理中のＡ要素の前記Ａ要素定員上限数以下である場合には、すべての前記Ａ要素のうち前記Ａ要素定員数を超える数の組合せが前記仮マッチ集合に含まれているＡ要素を前記仮マッチ除外処理の候補とし、
前記仮マッチング処理中の前記Ａ要素に関して前記仮マッチ集合に含まれる組合せの数が、前記仮マッチング処理中のＡ要素の前記Ａ要素定員上限数を超える場合には、前記仮マッチング処理中のＡ要素のみを前記仮マッチ除外処理の候補とし、
前記マッチングシステムは、前記仮マッチ除外処理の前記候補となるＡ要素に関する組合せのうち、前記第一の優先度リストにおいて最も順位が低い前記Ｂ要素に関するものを、前記仮マッチ除外処理の対象と決定する
請求項２に記載のマッチングシステム。
【請求項４】
コンピュータを、請求項１〜３のいずれか一項に記載のマッチングシステムとして機能させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、それぞれ複数の要素を含む２つの集合の間で各要素を対応付けるマッチングシステムに関し、特に、双方向のそれぞれの希望をもとに組合せを決めるマッチングシステムに関する。
【背景技術】
【０００２】
例えば、就職志願者の集合と志願者を受け入れる企業の集合の間のマッチング問題のように、双方向に優先度を持つ集合間のマッチング問題においてマッチングを行うための手法が提案されつつある（例えば、非特許文献１参照。）。
【０００３】
ここで、各志願者は自分が就職したい企業を好みにより順位づけした優先度リストを持ち、一方各企業の方も受け入れたい志願者を順位づけした優先度リストを持つものとする。志願者ａの優先度リストＲＯＬ（ａ）は、企業の集合の部分集合であり、順位によって等号を含まない不等号によって順序づけられた全順序集合である。ここでは、志願者ａがｐをｐ’より好む場合に、ｐ＜ｐ’と書くことにする（具体例を挙げれば、ｐが優先度第１位で、ｐ’は優先度第３位の場合には、ｐ（＝１）＜ｐ’（＝３）となる。）。また、企業ｐの志願者に対する優先度リストＲＯＬ（ｐ）についても同様である。また、各企業には志願者を受け入れる採用枠（定員）がある。企業ｐの定員Ｑ（ｐ）は０以上の整数である。マッチングＸとは、志願者と企業とのペア（ａ，ｐ）からなる集合であって次の２つの条件を満たすものとする。
【０００４】
１．  任意の志願者ａに関して、ａを含むペア（ａ，ｐ）はＸにおいて１個以下である。
２．  任意の企業ｐに関して、ｐを含むペア（ａ，ｐ）はＸにおいて、企業の定員Ｑ（ｐ）個以下である。
【０００５】
マッチングの一例を図１９に示す。図１９では、志願者の集合｛ａ１，ａ２，ａ３，ａ４，ａ５，ａ６，ａ７｝と企業の集合｛ｐ１，ｐ２，ｐ３，ｐ４｝の間のマッチングとして、｛（ａ１，ｐ１），（ａ２，ｐ３），（ａ３，ｐ４），（ａ５，ｐ３），（ａ６，ｐ４）｝が得られている。このマッチングでは、志願者ａ４，ａ７と企業ｐ２にはマッチング相手が存在しない。
【０００６】
また、図２０に志願者と企業の優先度リストの例を示す。それぞれの優先度リストでは上に記載されているものほど好ましい相手を示す。言い換えれば、下に行くほど順位が大きくなる。図２０の例では、志願者は３つの企業に対して、ｐ１＜ｐ４＜ｐ３という順序をつけている。企業は６人の志願者にａ７＜ａ１＜ａ４＜ａ３＜ａ５＜ａ６という順序をつけている。マッチングすることをまったく望まない相手は優先度リストに記載しない。
【０００７】
マッチング問題とは、志願者の集合と企業の集合と志願者および企業の優先度リストとが与えられたときに、志願者と企業の間の組合せを求める問題のことを言う。マッチング方法とは、マッチング問題に対する解法、すなわち、志願者と企業の間の組合せを求める方法のことである。従って、マッチングシステムとは、マッチング方法を実行するシステムのことである。
【０００８】
また、上記のようなマッチングには安定性を定義することができる。マッチングＸが安定であるのは、次の２つの条件が共に満たされる場合を言う。
【０００９】
１．すべての志願者（企業）は、自分の優先度リストに載せた企業（志願者）としかマッチングしない。
２．志願者と企業のすべてのペア（ａ，ｐ）のうち、マッチングＸに含まれないものは、いずれもブロッキングペアではない。ここで、ブロッキングペアとは次の３つの条件を共に満たすものである。
２．０．  ａはｐの優先度リストに記載され、かつ、ｐはａの優先度リストに記載されている。
２．１．  Ｘにおいてａはどの企業ともマッチングしていないか、またはＸにおいてａはｐ’とマッチングしていて、ａの優先度リストにおいてｐ＜ｐ’が成り立つ。
２．２．  Ｘにおいてｐがマッチングしている志願者数は定員Ｑ（ｐ）より少ないか、または、Ｘにおいてｐがマッチングしているある志願者ａ’が存在し、ｐの優先度リストにおいてａ＜ａ’が成り立つ。
【００１０】
マッチング問題においては、安定なマッチングを生成する方法が求められる。不安定なマッチングが得られた場合、自分が優先度リストに記載していない相手、すなわち、自分のまったく望まない相手とマッチングした志願者または企業が存在するか、あるいは、ブロッキングペアが存在する。ブロッキングペアを構成する志願者と企業の両者にとって、得られたマッチングよりブロッキングペアの相手の方が好ましいため、不安定なマッチングは公平でない。つまり、不安定なマッチングを生成する方法ではマッチングに対する信頼性が無くなり、マッチングの対象者がマッチングに参加する意思を損なうことになる。
【００１１】
図２１に、上記非特許文献１に書かれているＧａｌｅ−Ｓｈａｐｌｅｙアルゴリズムを用いた従来のマッチング方法を示すフローチャート図を示す。全志願者が順番に、まず自分の優先度リストで順位の一番小さい企業（すなわち、第１希望）から順番にプロポーズを行なうのが特徴である。
【００１２】
図２１の説明を行う前に、図２２を用いて簡単に概要を説明する。図２２の例は、４つの病院の集合と、それらの病院に就職を希望する８人の志願者の集合とのマッチング問題を想定している。明石さんから工藤さんまでの全志願者が順番に、まず自分の優先度リストで順位の一番小さい企業から順番にプロポーズを行なう。
【００１３】
明石さんは、第１希望が双川病院であるので、先ず、はじめに、明石さんは双川病院にプロポーズする。双川病院では、明石さんが優先度リストの４位にあるので、（明石，双川病院）が仮マッチングされる。
次に、井上さんがプロポーズを行う。井上さんの優先度リストにおいては、第１希望が双川病院であるので、井上さんは双川病院にプロポーズする。双川病院では、井上さんが優先度リストの５位にあり、かつ、双川病院の定員は２名でまだ１名分空いているので、（井上，双川病院）が仮マッチングされる。
次に、上野さんがプロポーズを行う。上野さんの優先度リストにおいては、第１希望が双川病院であるので、上野さんは双川病院にプロポーズする。双川病院では、上野さんが優先度リストの６位にあり、かつ、双川病院の定員は空きがないので、優先度リストの第２希望の病院にプロポーズを行う。第２希望の一山病院では、上野さんは１位であるので、（上野，一山病院）が仮マッチングされる。
【００１４】
次に、江口さんは、第１希望の一山病院にプロポーズするが、一山病院の優先度リストに江口さんの名前はないため、拒絶され、第２希望の双川病院にプロポーズするが、双川病院の優先度リストの７位で、かつ、定員に空きがないため、拒絶され、第３希望の美村病院にプロポーズすると、６位に名前があるため、（江口，美村病院）が仮マッチングされる。
次に、大川さんは、第１希望の双川病院にプロポーズする。双川病院の優先度リストで、大川さんは３位である。定員は２名であり、すでに２名が仮マッチングされている。しかしながら、仮マッチングされているのは、優先度リストにおける４位の明石さんと５位の井上さんである。このため、最も順位の大きい井上さんが除外され、（大川，双川病院）が仮マッチングされる。
除外された井上さんは、双川病院の次に自分の優先度リストでの順位が小さい病院に対してプロポーズをやり直す。当該病院は一山病院である。しかしながら、一山病院の優先度リストに井上さんの名前はないため、拒絶される。井上さんの優先度リストには第２希望までしか登録されていないため、井上さんは、すべての病院から拒絶されたことになる。
【００１５】
次に、川口さんの処理を行う。川口さんの優先度リストにおいては、第１希望が双川病院であるので、川口さんは双川病院にプロポーズする。双川病院では、川口さんは優先度リストの８位にあり、かつ、双川病院の定員は空きがないので、優先度リストの第２希望の病院にプロポーズを行う。第２希望の美村病院の優先度リストでは、川口さんの名前はないので、拒絶される。第３希望の一山病院でも同様に拒絶され、第４希望の四谷病院で、優先度リストの６位に名前があるので、（川口，四谷病院）が仮マッチングされる。
次に、木村さんは、第１希望の双川病院にプロポーズする。双川病院の優先度リストで、木村さんは１位である。定員は２名であり、すでに２名が仮マッチングされている。しかしながら、仮マッチングされているのは、優先度リストにおける４位の明石さんと３位の大川さんである。このため、最も順位の大きい明石さんが除外され、（木村，双川病院）が仮マッチングされる。
【００１６】
除外された明石さんは、双川病院の次に自分の優先度リストでの順位が小さい病院に対してプロポーズをやり直すが、明石さんの優先度リストには第１希望の双川病院しか登録されていないため、明石さんは、すべての病院から拒絶されたことになる。
次に、工藤さんは、第１希望の四谷病院にプロポーズする。四谷病院の優先度リストで、工藤さんは５位である。定員は２名であり、すでに１名が仮マッチングされているが、空きが１名分ある。そのため、（工藤，四谷病院）が仮マッチングされる。
【００１７】
ここで、すべての志願者が、いずれかの病院と仮マッチングされるか、または、自分の優先度リストに記載した病院すべてから拒絶されたので、処理は終了する。
マッチングの結果は、（大川，双川病院）、（木村，双川病院）、（上野，一山病院）、（江口，美村病院）、（川口，四谷病院）、（工藤，四谷病院）となり、明石さんと井上さんは自分の優先度リストに記載したすべての病院から拒絶されたことになった。
【００１８】
上記の図２１のフローチャートを用いて、図２２を例にして行ったこの処理について説明する。ステップＳ１００において、あらかじめ仮マッチングを空集合にする。ステップＳ１０１において、未処理の志願者がなければ終了し、あればその志願者の１人ａに対して以下の処理を行う。ステップＳ１０２において、志願者ａが優先度リストＲＯＬ（ａ）の何番目の企業に対してプロポーズするかの指標であるａ．ｉを１に設定する。これは、全志願者は順番に、まず自分の優先度リストで順位の一番小さい企業に対してプロポーズを行うことを示す。ステップＳ１０３において、優先度リストＲＯＬ（ａ）の要素数がａ．ｉより小さければ、志願者ａは最終的にどの企業ともマッチングできなかったことになり、ステップＳ１０１に戻る。一方、ステップＳ１０３において、優先度リストＲＯＬ（ａ）の要素数がａ．ｉより小さくなければ、ステップＳ１０４において、優先度リストＲＯＬ（ａ）のａ．ｉ番目の企業をｐとする。ステップＳ１０５において、ａがｐの優先度リストＲＯＬ（ｐ）に含まれなければ、ａ．ｉをａ．ｉ＋１に設定し直して、ステップＳ１０３に戻る。これは、プロポーズされた企業ｐはプロポーズした志願者ａがＲＯＬ（ｐ）に記載されていなければ拒絶し、拒絶された志願者ａは、自分の優先度リストＲＯＬ（ａ）での順位が企業ｐの次に小さい企業にプロポーズをやり直すことに相当する。一方、ステップＳ１０５において、ａがｐの優先度リストＲＯＬ（ｐ）に含まれていれば、ステップＳ１０６において、その時点でｐが仮マッチングしている志願者の数が定員Ｑ（ｐ）より少なければ、ペア（ａ，ｐ）を仮マッチングに加えてステップＳ１０１に戻る。一方、ステップＳ１０６において、その時点でｐが仮マッチングしている志願者の数が定員Ｑ（ｐ）より少なくなければ、ステップＳ１０７において、ｐと仮マッチングしている志願者の中で、ｐの優先度リストＲＯＬ（ｐ）で順位が最も大きいものをａ１とする。ａ１とプロポーズしている志願者ａとの間で、ＲＯＬ（ｐ）での順位を比較する。ａの順位の方が大きければ、ａ．ｉをａ．ｉ＋１に設定し直して、ステップＳ１０３に戻る。これは、ａの順位の方が大きければ企業ｐはａを拒絶することに相当する。拒絶された志願者ａは、ｐの次に自分の優先度リストＲＯＬ（ａ）での順位が小さい企業にプロポーズをやり直すことになる。このステップＳ１０７以降では企業ｐと仮マッチングしている志願者数が定員Ｑ（ｐ）と等しい。ステップＳ１０８において、ａ１の順位の方がａの順位より大きいので、ペア（ａ，ｐ）を仮マッチングに加え、ペア（ａ１，ｐ）を仮マッチングから除外し、ａをａ１に設定し直す。ステップＳ１０９において、ａ．ｉをａ．ｉ＋１に設定し直してステップＳ１０３に戻る。つまり、仮マッチングから除外された志願者（元のａ１）は、ｐの次に自分の優先度リストでの順位が小さい企業に対してプロポーズをやり直すことになる。図２１の処理が終了するのは、ステップＳ１０１において、すべての志願者が、いずれかの企業と仮マッチングされるか、または、自分の優先度リストに記載された企業すべてから拒絶されたときである。図２１の処理が終了した段階で最終的に得られた仮マッチングをマッチング結果とする。なお、Ｇａｌｅ−Ｓｈａｐｌｅｙアルゴリズムにより得られるマッチングは安定であることが非特許文献１に記載されている。
以上のように、従来のマッチングシステムにおいては、志願者と企業のように１対１になる組み合わせを、安定したマッチング結果が得られると定評の高いＧａｌｅ−Ｓｈａｐｌｅｙアルゴリズムにより求めている。
【００１９】
このようなアルゴリズムを応用したマッチングシステムの例は、特許文献１に記載されている。特許文献１のシステムは、一つの企業グループと、それに含まれる複数の企業とのそれぞれに対して定員が規定されており、各企業が独立したマッチング枠を持っている。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２０１０−１６５２２４号公報
【非特許文献】
【００２１】
【非特許文献１】「Ｔｈｅ  Ｓｔａｂｌｅ  Ｍａｒｒｉａｇｅ  Ｐｒｏｂｌｅｍ」、Ｄ．Ｇｕｓｆｉｅｌｄ  及び  Ｒ．Ｗ．Ｉｒｖｉｎｇ著、Ｔｈｅ  ＭＩＴ  Ｐｒｅｓｓ、１９８９年、ｐ．９
【発明の概要】
【発明が解決しようとする課題】
【００２２】
ところで、ある施設が単一のマッチング枠でなく複数の独立したマッチング枠を持っている場合、その施設内で各マッチング枠への希望者数が偏る場合がある。この場合、従来のマッチングアルゴリズムでは、施設全体の定員を考慮すると、各マッチング枠間で施設全体としてバランスのとれたマッチングができないという問題があった。
【００２３】
たとえば、ある施設が複数の研修プログラムを持っており、それぞれの研修プログラムが独立して参加者を募集する場合において、特定の研修プログラムに参加希望者が集中すると、その研修プログラムでは運用上望ましい適正定員を超えて物理的に受け入れ可能な定員上限（満員）に達する一方、他の研修プログラムでは参加者が定員を割り込み、施設全体としてバランスのとれたマッチングができない。
【００２４】
この発明は、かかる問題点を解決するためになされたものであり、複数のＡ要素（研修プログラム）のそれぞれと、複数のＢ要素（参加者）のそれぞれとの間でマッチングを行うマッチングシステムにおいて、人数調整の基準となる定員を超過しているＡ要素（研修プログラム）については一定の条件でＢ要素（参加者）のマッチングを取り消すことにより、集合Ａ（施設）全体としてバランスのとれたマッチングを適切に実現するマッチングシステムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
この発明に係るマッチングシステムは、集合Ａに含まれる複数のＡ要素のそれぞれと、集合Ｂに含まれる複数のＢ要素のそれぞれとの間でマッチングを行うマッチングシステムであって、Ａ要素の少なくとも１つは、複数のＢ要素とマッチ可能であり、Ｂ要素はそれぞれ、多くとも１つのみのＡ要素とマッチされるマッチングシステムにおいて、マッチングシステムは、集合Ａについて定義され、Ｂ要素の全部または一部を一意に順位付ける第一の優先度リストと、Ｂ要素のそれぞれについて定義され、Ａ要素の全部または一部を一意に順位付ける第二の優先度リストと、集合Ａとマッチ可能なＢ要素の最大数を表す集合Ａ定員数と、Ａ要素のそれぞれについて、そのＡ要素とマッチ可能なＢ要素の最大数を表すＡ要素定員上限数と、Ａ要素のそれぞれについて、Ａ要素定員上限数以下の所定の数を表すＡ要素定員数とを記憶し、マッチングシステムは、第一の優先度リストに含まれるＢ要素のそれぞれについて、第二の優先度リストに従ってＡ要素のそれぞれとの組合せについて順次仮マッチング処理を行うとともに、仮マッチング処理の結果として得られる仮マッチ集合に基づいてマッチングを行うものであり、仮マッチング処理において、以下の条件：‐集合Ａに関して仮マッチ集合に含まれている組合せの数が、集合Ａ定員数より小さい、‐仮マッチング処理中のＡ要素に関して仮マッチ集合に含まれている組合せの数が、そのＡ要素のＡ要素定員上限数より小さい、の双方が満たされる場合には、仮マッチング処理中の組合せを仮マッチ集合に加え、条件のいずれかが満たされない場合には、仮マッチング処理中の組合せを仮マッチ集合に加えるとともに、仮マッチ集合に含まれる組合せのいずれかを仮マッチ集合から除外する仮マッチ除外処理を行い、仮マッチ除外処理は、Ａ要素定員数を超える数の組合せが仮マッチ集合に含まれているＡ要素に関する組合せのいずれかを対象として行われる。
【００２６】
仮マッチ除外処理において、仮マッチ除外処理の対象となる組合せは、第一の優先度リストに基づいて決定されてもよい。
マッチングシステムは、仮マッチ除外処理において、仮マッチング処理中のＡ要素に関して仮マッチ集合に含まれる組合せの数が、仮マッチング処理中のＡ要素のＡ要素定員上限数以下である場合には、すべてのＡ要素のうちＡ要素定員数を超える数の組合せが仮マッチ集合に含まれているＡ要素を仮マッチ除外処理の候補とし、仮マッチング処理中のＡ要素に関して仮マッチ集合に含まれる組合せの数が、仮マッチング処理中のＡ要素のＡ要素定員上限数を超える場合には、仮マッチング処理中のＡ要素のみを仮マッチ除外処理の候補とし、マッチングシステムは、仮マッチ除外処理の候補となるＡ要素に関する組合せのうち、第一の優先度リストにおいて最も順位が低いＢ要素に関するものを、仮マッチ除外処理の対象と決定してもよい。
また、この発明に係るコンピュータプログラムは、コンピュータを、上述のマッチングシステムとして機能させる。
【発明の効果】
【００２７】
この発明によれば、マッチングシステムは、各Ａ要素について、マッチ数調整の基準となる定員数を記憶する。そして、Ａ要素の定員超過を許容する仮マッチングを行いつつ、Ａ要素の定員上限超過または集合Ａの定員超過が発生した場合には、定員数を超過してＡ要素に仮マッチされたＢ要素のいずれかについて仮マッチを取り消す。したがって、集合Ａ全体で見ると、各Ａ要素の定員数を基準としてバランスのとれたマッチングを実現することができる。
【図面の簡単な説明】
【００２８】
【図１】この発明の実施の形態１に係るマッチングシステムの全体の構成を示した構成図である。
【図２】この発明の実施の形態１に係るマッチングシステムを構成している各構成要素の内部構成を示した構成図である。
【図３】この発明の実施の形態１に係るマッチングシステムの研修プログラムマスタファイルの一例を示した説明図である。
【図４】この発明の実施の形態１に係るマッチングシステムの病院条件ファイルの一例を示した説明図である。
【図５】この発明の実施の形態１に係るマッチングシステムの病院研修プログラム情報ファイルの一例を示した説明図である。
【図６】この発明の実施の形態１に係るマッチングシステムの参加者ＲＯＬファイルの一例を示した説明図である。
【図７】この発明の実施の形態１に係るマッチングシステムの病院ＲＯＬファイルの一例を示した説明図である。
【図８】この発明の実施の形態１に係るマッチングシステムのマッチング結果格納ファイルの一例を示した説明図である。
【図９】この発明の実施の形態１に係るマッチングシステムの処理の流れを示した流れ図である。
【図１０】この発明の実施の形態１に係るマッチングシステムの処理の流れを示した流れ図である。
【図１１】この発明の実施の形態１に係るマッチングシステムの処理の流れを示した流れ図である。
【図１２】この発明の実施の形態１に係るマッチングシステムの処理の流れを示した流れ図である。
【図１３】この発明の実施の形態２におけるＲＯＬファイルの関連付けを示した図である。
【図１４】この発明の実施の形態２に係るマッチングシステムの病院研修プログラム情報ファイルの一例を示した説明図である。
【図１５】この発明の実施の形態２に係るマッチングシステムの病院ＲＯＬファイルの一例を示した説明図である。
【図１６】この発明の実施の形態３におけるＲＯＬファイルの関連付けを示した図である。
【図１７】この発明の実施の形態３に係るマッチングシステムの病院研修プログラム情報ファイルの一例を示した説明図である。
【図１８】この発明の実施の形態３に係るマッチングシステムの病院ＲＯＬファイルの一例を示した説明図である。
【図１９】従来のマッチング方法におけるマッチングの一例を示した説明図である。
【図２０】従来のマッチング方法における優先度リストの一例を示した説明図である。
【図２１】従来のマッチング方法の処理の流れを示したフローチャートである。
【図２２】従来のマッチング方法を示した説明図である。
【発明を実施するための形態】
【００２９】
実施の形態１．
この発明の実施の形態１に係るマッチングシステムは、施設の例として病院を想定し、施設が準備する複数の研修プログラムと、複数の参加者との間で組合せを決定するためのシステムである。例を挙げて説明すれば、例えば、医学部の卒業生で研修を希望する研修希望者（以下、参加者とする。）は、医療研修施設（すなわち、大学病院、総合病院など）で、研修を経験する必要がある。
【００３０】
また病院は、それぞれ異なる診察科（総合内科、循環器内科、心臓外科、小児科、女性診療科等）を有している。本実施の形態では、特定の病院の特定の診療科（Ｘ病院の心臓外科、Ｙ病院の総合外科、等）を、「研修プログラム」と呼ぶこととし、参加者と研修プログラムとがマッチングされるものとする。
【００３１】
研修プログラムのそれぞれをＡ要素とし、参加者のそれぞれをＢ要素とすると、病院は複数のＡ要素を含む集合（集合Ａとする）ということができ、また、本実施形態のマッチングシステムは、集合Ａに含まれる複数のＡ要素のそれぞれと、集合Ｂに含まれる複数のＢ要素のそれぞれとの間でマッチングを行うものであるということができる。
ここで、１つの研修プログラムは複数の参加者とマッチ可能であるものとする。すなわち、研修プログラムはそれぞれがマッチング枠として１人以上の参加者とマッチ可能であり、研修プログラムのうち少なくとも１つは、複数の参加者とマッチ可能である。逆に、１人の参加者が複数の研修プログラムとマッチすることはないものとする。すなわち、参加者はそれぞれ、１つの研修プログラムとのみマッチされるか、あるいはいずれの研修プログラムともマッチされない。
【００３２】
病院経営者は、各研修プログラムについて、「定員」および「定員上限」をあらかじめ決定しておく。定員とは、研修プログラム間の人数バランス調整の基準となる人数であり、たとえば運用上望ましい適正人数を指定することができる。また、定員上限とは、その研修プログラムとマッチ可能な参加者の最大数であり、たとえば物理的に受け入れ可能な満員人数を指定することができる。なお定員は定員上限と等しいかそれより小さい数である。
また、病院経営者は、病院の定員をあらかじめ決定しておく。この「病院の定員」とは、病院とマッチ可能な参加者（すなわち、その病院の全研修プログラムとマッチ可能な全参加者）の最大数である。病院の定員は、各研修プログラムの定員の合計以上であり、かつ、各研修プログラムの定員上限の合計以下である。
【００３３】
図１は、この発明の実施の形態１に係るマッチングシステムの全体の構成を示した図である。図１に示すように、実施の形態１に係るマッチングシステムは、参加者と病院との組合せを決定するマッチング処理を行うためのマッチングサーバ１００と、マッチングサーバ１００の管理およびメンテナンス等を行うマッチング管理者端末４００と、参加者が操作して病院の希望順位などを入力するための参加者端末２００と、病院に勤務している病院管理者が操作して研修プログラムに対する参加者の希望順位などを入力するための病院管理者端末３００とから構成されている。なお、マッチングサーバ１００、参加者端末２００、病院管理者端末３００、マッチング管理者端末４００は、インターネット等の通信網５００により接続されている。
【００３４】
図２は、図１に示した各構成要素の内部構成を示した図である。マッチングサーバ１００、参加者端末２００、病院管理者端末３００、およびマッチング管理者端末４００はいずれも周知の構成を有するコンピュータによって構成される。
図２に示すように、マッチングサーバ１００には、研修プログラムマスタファイル１、病院条件ファイル２、病院研修プログラム情報ファイル３、参加者ＲＯＬファイル４、病院ＲＯＬファイル５、およびマッチング結果格納ファイル６が記憶されている。これらは、共通の１つの記憶装置内に記憶されていてもよく、あるいは、複数の記憶装置内に記憶されていてもよい。さらに、マッチングサーバ１００には、通信網５００を介して外部との通信を行うための通信手段７と、マッチングに関する処理を実行するためのマッチング手段８とが設けられている。なお通信手段７およびマッチング手段８は、たとえばマッチングサーバ１００の演算手段（ＣＰＵ等）が、マッチングサーバ１００の記憶手段に記憶されたコンピュータプログラムを実行することによって実現することができる。
【００３５】
参加者端末２００内には、入力手段２０と、表示手段２１と、処理手段２２と、通信手段２３とが設けられている。通信手段２３は、マッチングサーバ１００の通信手段７とデータのやりとりを行い、参加者ＲＯＬファイル情報（ＲＯＬ入力情報）を送信し、入力受付完了通知を受信する。なお入力手段２０、表示手段２１、処理手段２２および通信手段２３は、たとえば参加者端末２００の演算手段（ＣＰＵ等）が、記憶手段に記憶されたコンピュータプログラムを実行することによって実現することができる。
病院管理者端末３００の内部構成は、参加者端末２００と同様である（図示は省略する）。
【００３６】
マッチング管理者端末４００内には、入力手段３０と、表示手段３１と、処理手段３２と、通信手段３３とが設けられている。通信手段３３は、マッチングサーバ１００の通信手段７とデータのやりとりを行い、入力データを送信し、マッチング結果通知を受信する。なお入力手段３０、表示手段３１、処理手段３２および通信手段３３は、たとえばマッチング管理者端末４００の演算手段（ＣＰＵ等）が、記憶手段に記憶されたコンピュータプログラムを実行することによって実現することができる。
【００３７】
図３は、研修プログラムマスタファイル１の一例を示した図である。研修プログラムマスタファイル１には、各研修プログラムについて、各研修プログラムの情報が格納されている。すなわち、研修プログラムマスタファイル１には、各研修プログラムを特定するための「研修プログラム番号」、その研修プログラムの定員数（人数バランス調整の基準となる人数）および定員上限数（参加者の最大受け入れ可能人数）が格納されている。また図３には図示していないが、研修プログラムに関する他の情報が格納されてもよい。
研修プログラムマスタファイル１の内容については、たとえばマッチング管理者端末４００において、入力手段３０が入力を受け付け、処理手段３２がこれを通信手段３３に受け渡し、通信手段３３からマッチングサーバ１００の通信手段７に送信され、マッチングサーバ１００の処理手段（図示せず）が研修プログラムマスタファイル１に記憶する。
【００３８】
図４は、病院条件ファイル２の一例を示した図である。病院条件ファイル２には、病院の定員数が定義される。この例では、病院コードＡ００１の病院の定員数は３５人である。なお、研修プログラムと異なり、病院ついては「定員数」のみが定義されていればよく、「定員上限数」を定義する必要はない。
病院条件ファイル２の内容については、たとえばマッチング管理者端末４００において、入力手段３０が入力を受け付け、処理手段３２がこれを通信手段３３に受け渡し、通信手段３３からマッチングサーバ１００の通信手段７に送信され、マッチングサーバ１００の処理手段（図示せず）が病院条件ファイル２に記憶する。
【００３９】
図５は、病院研修プログラム情報ファイル３の一例を示した図である。病院研修プログラム情報ファイル３は、病院と、その病院が提供する複数の研修プログラムとを関連付けるものであり、病院を特定するためのＩＤである「病院コード」に、その病院の名称を表す「病院名」、その病院の住所（所在地）を表す「病院住所」、および、その病院が提供する研修プログラムを特定する「研修プログラム番号」を関連付ける。なお、１つの病院が複数の研修プログラムを提供するので、１つの病院コードに対して複数の研修プログラム番号が関連付けられている。
【００４０】
図６は、参加者ＲＯＬファイル４の一例を示した図である。参加者ＲＯＬファイル４は、参加者のそれぞれが参加を希望する研修プログラムを、希望優先度の高いものから順に一意に順位付ける優先度リスト（第二の優先度リスト）である。参加者ＲＯＬファイル４に含まれる優先度リストは、参加者のそれぞれについて定義される。参加者ＲＯＬファイル４は、参加者を識別する「ユーザＩＤ」に対して、その参加者が参加を希望する研修プログラムの「研修プログラム番号」と、その希望順位である「順位」とを関連付ける。
【００４１】
参加者は、マッチングの結果によってどの研修プログラムでも参加を希望するという場合には、参加者ＲＯＬファイル４にすべての研修プログラムを登録する。そうでない場合には、参加者ＲＯＬファイル４に研修プログラムの一部を登録する。図６においては、各参加者について第１希望から順に第ｎ希望までの研修プログラムが順に格納されている。なお一人の参加者について同一の希望順位が重複して定義されることはないものとする。
【００４２】
各参加者は、例えば、インターネットのホームページ等から各病院の情報を得て、希望順位を決定する。希望順位を含むＲＯＬ入力情報は、たとえば参加者端末２００において、入力手段２０が入力を受け付け、処理手段２２がこれを通信手段２３に受け渡し、通信手段２３からマッチングサーバ１００の通信手段７に送信され、マッチングサーバ１００の処理手段（図示せず）が参加者ＲＯＬファイル４に記憶する。
【００４３】
図７は、病院ＲＯＬファイル５の一例を示した図である。病院ＲＯＬファイル５は、病院について１つ定義されるものであり、その病院が受け入れを希望する参加者を、希望優先度の高い人から順に一意に順位付ける優先度リスト（第一の優先度リスト）である。病院ＲＯＬファイル５は、病院を識別する「病院コード」に対して、その病院が受け入れを希望する参加者の「ユーザＩＤ」と、その希望順位である「順位」とを関連付ける。
【００４４】
病院は、マッチングの結果によってどの参加者でも受け入れるという場合には、病院ＲＯＬファイル５にすべての参加者を登録する。そうでない場合には、病院ＲＯＬファイル５に参加者の一部を登録する。図７においては、病院コードＡ００１について第１希望から順に第ｎ希望までのユーザＩＤが順に格納されている。なお１つの病院について同一の希望順位が重複して定義されることはないものとする。
【００４５】
図８は、マッチング結果格納ファイル６の一例を示した図である。マッチング結果格納ファイル６には、マッチング処理の結果得られたマッチング結果が格納されている。すなわち、図８に示すように、参加者を識別する「ユーザＩＤ」と、その参加者が割り当てられた研修プログラムの「研修プログラム番号」とが、それぞれ、対応付けて格納されている。これにより、どの参加者が、どの研修プログラムに参加するかを確認することができる。
【００４６】
次に、本実施の形態１に係るマッチングシステムの動作について説明する。図９は、マッチング管理者端末４００からのデータ入力処理について示した図であり、マッチング管理者が、研修プログラムマスタファイル１、病院条件ファイル２、および病院研修プログラム情報ファイル３の登録、追加、更新または削除の処理を行うときの処理の流れを示している。図９に示すように、まず、マッチング管理者端末４００の処理手段３２は、マッチング管理者の操作により入力手段３０が受け付けた入力データを通信手段３３に受け渡す（ステップＳ１）。次に、マッチング管理者端末４００の通信手段３３が、マッチングサーバ１００の通信手段７に当該入力データを送信する（ステップＳ２）。次に、マッチングサーバ１００の通信手段７が、受信したデータ内容により、研修プログラムマスタファイル１、病院条件ファイル２、または病院研修プログラム情報ファイル３にデータの追加、更新または削除を行う（ステップＳ３）。
【００４７】
図１０は、参加者端末２００からのデータ入力処理を示した図であり、参加者が希望順位を示す優先度リスト（ＲＯＬ入力情報）の入力を行うときの処理の流れを示している。図１０に示すように、まず、参加者端末２００の処理手段２２は、参加者の操作により入力手段２０が受け付けた入力データを通信手段２３に受け渡す（ステップＳ１１）。次に、参加者端末２００の通信手段２３がマッチングサーバ１００の通信手段７に当該入力データを送信する（ステップＳ１２）。次に、マッチングサーバ１００の通信手段７が、受信したデータ内容により、参加者ＲＯＬファイル４の追加、更新または削除を行う（ステップＳ１３）。
また、病院管理者端末３００からの病院ＲＯＬファイル５へのデータ入力を受付けるときも、図１０に示したフローチャートと同様の流れになる。
【００４８】
図１１は、本実施の形態におけるマッチング処理の流れを示すフローチャートである。
マッチング処理において、マッチング手段８は、参加者と研修プログラムとの組合せについて仮マッチング処理を行う。仮マッチング処理において、その参加者と研修プログラムとの組合せを所定の基準に従って仮マッチ集合に追加し、また別の基準に従って仮マッチ集合から除外し、これを繰り返して仮マッチ集合を決定する。すべての参加者について仮マッチング処理が終了した時点で結果として得られる仮マッチ集合が、最終的なマッチング結果を表すものとなる。
【００４９】
図１１に示すように、まずマッチング手段８は仮マッチ集合を空集合とする（ステップＳ２１）。次に、マッチング手段８は未処理の参加者が存在するか否かを判定する（ステップＳ２２）。未処理の参加者が存在しなければ、その時点の仮マッチ集合を最終的なマッチング結果としてマッチング結果格納ファイル６に格納し（ステップＳ２３）、処理を終了する。
【００５０】
未処理の参加者が存在する場合、マッチング手段８は、変数ａに、未処理の参加者いずれか一人のユーザＩＤを代入する（ステップＳ２４）。この変数ａは、処理中の参加者を表す。その後、マッチング手段８は、変数ａ．ｉに１を代入する（ステップＳ２５）。この変数ａ．ｉは、その参加者の参加者ＲＯＬにおける順位を表し、すなわちその順位に指定された研修プログラムに対応する。ステップＳ２５は、参加者ＲＯＬの第１希望の研修プログラムが、最初に処理の対象となることを示す。
以下、処理中の参加者（変数ａで表される）の参加者ＲＯＬを、「ＲＯＬ（ａ）」と表記する。
【００５１】
マッチング手段８は、ＲＯＬ（ａ）のサイズ（要素数、希望を登録した件数）が変数ａ．ｉ未満であるか否かを判定する（ステップＳ２６）。すなわち、仮マッチング処理で扱うべき第ａ．ｉ希望の研修プログラムが、ＲＯＬ（ａ）に指定されているか否かを判定する。
【００５２】
ＲＯＬ（ａ）のサイズが変数ａ．ｉ未満であれば、マッチング手段８はその参加者についての処理を終了し（ステップＳ２７）、ステップＳ２２に処理を戻す。これは、その参加者についてはいずれの研修プログラムとも仮マッチが成立しなかったということを意味する。
一方、ＲＯＬ（ａ）のサイズが変数ａ．ｉ以上であれば、マッチング手段８は変数ｐにＲＯＬ（ａ）のａ．ｉ番目の研修プログラムの研修プログラム番号を代入し（ステップＳ２８）、さらに変数ｍにその研修プログラムを提供する病院の病院コードを代入する（ステップＳ２９）。変数ｐは処理中の研修プログラムを表し、変数ｍは処理中の病院を表す。以下、処理中の病院の病院ＲＯＬを、「ＲＯＬ（ｍ）」と表記する。
また、組合せ（ａ，ｐ）は、処理中の参加者と処理中の研修プログラムとの組合せを表す。
【００５３】
マッチング手段８は、ａがＲＯＬ（ｍ）に含まれるか否かを判定する（ステップＳ３０）。これは、処理中の参加者がある研修プログラムを希望し、その研修プログラムを提供する病院の病院ＲＯＬに、その参加者が含まれるか否かを判定することに相当する。
【００５４】
ａがＲＯＬ（ｍ）に含まれない場合、マッチング手段８はａ．ｉを１だけ増加させ（ステップＳ３１）、処理をステップＳ２６に戻す。これは、処理中の組合せ（ａ，ｐ）について仮マッチが成立しなかったということを意味する。
一方、ａがＲＯＬ（ｍ）に含まれる場合、マッチング手段８は、処理中の組合せ（ａ，ｐ）について、以下のステップＳ３２〜Ｓ４１の仮マッチング処理を開始する。
【００５５】
仮マッチング処理において、マッチング手段８は、処理中の病院の定員および処理中の研修プログラムの定員上限数についての判定を行う（ステップＳ３２）。
病院の定員についての判定では、処理中の病院に関してその時点で仮マッチ集合に含まれる組合せの数が、その病院の定員よりも小さいか否かを判定する。これは、その病院が新たな参加者を受け入れる余裕があるか否かを判定することに相当する。
研修プログラムの定員上限数についての判定では、処理中の研修プログラムに関してその時点で仮マッチ集合に含まれる組合せの数が、その研修プログラムの定員上限数よりも小さいか否かを判定する。これは、その研修プログラムが新たな参加者を受け入れる余裕があるか否かを判定することに相当する。
【００５６】
ステップＳ３２の判定において、病院の定員および研修プログラムの定員上限数ともに余裕がある場合、マッチング手段８は処理中の組合せ（ａ，ｐ）を仮マッチ集合に追加し（ステップＳ３３）、処理中の参加者についての処理を終了し（ステップＳ３４）、処理をステップＳ２２に戻す。
また、ステップＳ３２の判定において、研修プログラムの定員上限数に余裕がない場合、病院の定員に余裕があるか否かに関わらず、マッチング手段８は処理中の組合せ（ａ，ｐ）を仮マッチ集合に追加し（ステップＳ３５）、仮マッチ除外処理を行う（ステップＳ３６）。
【００５７】
仮マッチ除外処理とは、仮マッチ集合に含まれている組合せのいずれかを仮マッチ集合から除外するという処理である。ステップＳ３５で組合せ（ａ，ｐ）が仮マッチ集合に追加されているため、仮マッチング処理中の研修プログラムに関して仮マッチ集合に含まれる組合せの数は、定員上限数を超えることになる（なお当然ながら、定員上限数≧定員であるので、組合せの数は定員を超えている）。
【００５８】
したがって、ステップＳ３６の仮マッチ除外処理では、全研修プログラムのうち仮マッチング処理中のもののみを仮マッチ除外処理の候補とし、この研修プログラムに関する組合せのうちから、実際に仮マッチ除外処理の対象となる組合せを選択する。この選択はＲＯＬ（ｍ）に基づいてなされる。すなわち、仮マッチング処理中の研修プログラムに関する組合せのうち、ＲＯＬ（ｍ）において最も順位が低い参加者との組合せが選択され、選択された組合せが仮マッチ集合から除外される。
なお、当然ながら、ＲＯＬ（ｍ）における参加者ａの順位が低い場合には、ステップＳ３５において仮マッチ集合に追加された組合せ（ａ，ｐ）が、その直後にステップＳ３６において仮マッチ集合から除外されるということもあり得る。
【００５９】
また、ステップＳ３２の判定において、研修プログラムの定員上限数には余裕があり、かつ病院の定員には余裕がない場合、マッチング手段８は処理中の組合せ（ａ，ｐ）を仮マッチ集合に追加し（ステップＳ３７）、仮マッチ除外処理を行う（ステップＳ３８）。この場合、処理中の研修プログラムの定員上限数には余裕があるので、仮マッチ除外処理は必ずしも処理中の研修プログラムを候補とする必要がない。
【００６０】
したがって、ステップＳ３８の仮マッチ除外処理では、各研修プログラムのうち、定員（定員上限数でなく、バランス調整の基準となる定員）を超えて仮マッチがなされている研修プログラムすべてを、仮マッチ除外処理の対象とする。なお、「定員を超えて仮マッチがなされている」とは、「定員を超える数の組合せが仮マッチ集合に含まれている」という意味である。
【００６１】
そして、仮マッチ除外処理の候補となった研修プログラムすべてに関する組合せのうちから、実際に仮マッチ除外処理の対象となる組合せを選択する。この選択はステップＳ３６と同様にＲＯＬ（ｍ）に基づいてなされる。すなわち、候補となる組合せのうち、ＲＯＬ（ｍ）において最も順位が低い参加者との組合せが選択され、選択された組合せが仮マッチ集合から除外される。
ここでも、ＲＯＬ（ｍ）における参加者ａの順位が低い場合には、ステップＳ３７において仮マッチ集合に追加された組合せ（ａ，ｐ）が、その直後にステップＳ３８において仮マッチ集合から除外されるということもあり得る。
【００６２】
ステップＳ３６またはステップＳ３８の後、マッチング手段８は、処理中の参加者については処理を終了し（ステップＳ３９）、仮マッチ除外処理の対象となった組合せに係る参加者のユーザＩＤを変数ａに代入する（ステップＳ４０）。すなわち、除外された参加者（すでに処理が終了していた参加者）が、新たに未処理の参加者となる。そして、この新たな未処理の参加者について、変数ａ．ｉを１だけ増加させ（ステップＳ４１）、処理をステップＳ２６に戻す。すなわち、ある組合せ（ａ１，ｐ１）が除外された場合、除外された参加者ａ１について、除外された研修プログラムｐ１の次の希望順位の研修プログラムから順に、再びマッチング処理が開始されることになる。
【００６３】
以上のように処理が進み、すべての参加者について処理が終了すると、ステップＳ２２からステップＳ２３へと分岐し、その時点の仮マッチ集合に基づいて最終的なマッチング結果が決定されマッチング結果格納ファイル６に格納される。
【００６４】
このように、実施の形態１に係るマッチングシステムは、病院の定員にも研修プログラムの定員上限数にも余裕がある場合には従来と同様に仮マッチを行う。一方で、病院の定員および研修プログラムの定員上限数のいずれかに余裕がない場合には、バランス調整の基準となる定員を超えて仮マッチされている研修プログラムのうちから、病院ＲＯＬにおいて最下位の参加者との仮マッチを除外する。したがって、定員を超過している研修プログラムからは参加者を減少させつつ、定員以下の研修プログラムは参加者を維持することができ、病院全体としてバランスのとれたマッチングを適切に実現することができる。
【００６５】
図１２は、マッチングサーバ１００の通信手段７によるマッチング結果の通知の処理について示した図である。図１２に示すように、まず、マッチングサーバ１００のマッチング手段８は、マッチング処理終了を通信手段７に通知する（ステップＳ５１）。次に、マッチングサーバ１００の通信手段７は、マッチング結果格納ファイル６を参照してマッチング結果を取得し、マッチング管理者端末４００の通信手段３３に通知する（ステップＳ５２）。次に、マッチング管理者端末４００の通信手段３３は、通知されたマッチング結果を処理手段３２に受け渡す（ステップＳ５３）。次に、マッチング管理者端末４００の処理手段３２は、受け渡されたマッチング結果を、インターネット等で公開する（ステップＳ５４）。
【００６６】
なおマッチング結果の公開については、図１２に示した方法によらず、ファイル形式や結果を印刷した紙にて、参加者及び研修プログラム管理者に通知する方法もある。また、該当のマッチング結果を参加者端末２００または、病院管理者端末３００に通知するように構成してもよい。例えば、参加者端末２００がユーザＩＤ  ００１でログインされていたとすると、ユーザＩＤ  ００１がマッチされた病院情報（例えば、病院コード  Ａ００１に関する情報）を参加者端末２００に送信するように構成してもよい。
【００６７】
以上のように動作するマッチングシステムについて、マッチング処理の流れの具体例を以下に説明する。
ある病院が３つの研修プログラムを提供しており、これに対して１２人の参加者が参加を希望しているとする。研修プログラム番号をＡ、ＢおよびＣで表し、参加者のユーザＩＤを００１〜０１２で表すとする。
【００６８】
病院の定員は１０人であり、各研修プログラムの定員および定員上限数は次のとおりとする。
研修プログラムＡ：定員３人、定員上限数６人
研修プログラムＢ：定員２人、定員上限数４人
研修プログラムＣ：定員４人、定員上限数８人
この例では、全研修プログラムの定員上限数の総和（１８人）＞病院の定員（１０人）＞全研修プログラムの定員の総和（９人）となっている。
【００６９】
病院ＲＯＬは順位の高いほうから（００９，０１０，００１，００２，００３，０１１，０１２，００５，００４，００７，００８，００６）であるとし、参加者ＲＯＬは次のとおりとする。下記ＲＯＬの記載は、順位が高いほうから並んでいるものとする。
参加者００１の参加者ＲＯＬ：Ｃ，Ａ，Ｂ
参加者００２の参加者ＲＯＬ：Ｃ，Ｂ
参加者００３の参加者ＲＯＬ：Ｃ
参加者００４の参加者ＲＯＬ：Ｂ，Ａ
参加者００５の参加者ＲＯＬ：Ｂ，Ｃ
参加者００６の参加者ＲＯＬ：Ｂ，Ｃ
参加者００７の参加者ＲＯＬ：Ｂ，Ａ
参加者００８の参加者ＲＯＬ：Ｂ，Ａ
参加者００９の参加者ＲＯＬ：Ａ，Ｂ
参加者０１０の参加者ＲＯＬ：Ａ，Ｂ，Ｃ
参加者０１１の参加者ＲＯＬ：Ａ，Ｃ，Ｂ
参加者０１２の参加者ＲＯＬ：Ｂ，Ａ
上記からわかるように、定員が２人と少ない研修プログラムＢに、６人の参加者の第１希望が集中している。一方、定員が４人と多い研修プログラムＣを第１希望に指定している参加者は３人だけである。このような状態で、従来のマッチングアルゴリズムを用いてマッチングを行うと、研修プログラムＢに定員上限数いっぱいまでマッチングがされる一方、研修プログラムＣは定員割れとなり、研修プログラム間で参加者数が偏るおそれがある。（厳密には、研修プログラムの定員に対する参加者数の比率が偏るおそれがある。）
【００７０】
この例において、図１１のフローチャートに従って動作を説明する。
参加者００１から処理が開始され、順次参加者００２、参加者００３、…と処理が進む。参加者００７までは病院の定員および研修プログラムの定員上限数ともに余裕があるので、ステップＳ３２の判定からステップＳ３３に分岐し、いずれの参加者も第１希望の研修プログラムとの仮マッチが追加される。
【００７１】
参加者００７の処理が終了した時点で、仮マッチ集合の内容は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：なし
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，００６，００７
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３
【００７２】
参加者００８の処理において、第１希望の研修プログラムはＢであるが、Ｂはすでに定員上限数まで仮マッチが成立しており余裕がない。したがって処理はステップＳ３２の判定からステップＳ３５に分岐し、研修プログラムＢに参加者００８の仮マッチを加えた上で、研修プログラムＢが仮マッチ除外処理の候補となる。参加者００４，００５，００６，００７，００８のうち、病院ＲＯＬにおいて最も順位が低いのは参加者００６であり、したがって参加者００６が仮マッチから除外される。
【００７３】
この時点で、仮マッチ集合の内容は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：なし
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，００７，００８
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３
【００７４】
除外された参加者００６について処理が再開される。第２希望の研修プログラムＣの定員上限数には余裕があるので、参加者００６は研修プログラムＣと仮マッチされる。
続いて参加者００９，０１０の処理が行われる。いずれも第１希望は研修プログラムＡであり、病院の定員および研修プログラムの定員上限数ともに余裕があるので、ステップＳ３２の判定からステップＳ３３に分岐し、仮マッチが追加される。
【００７５】
この時点で、仮マッチ集合の内容は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：００９，０１０
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，００７，００８
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３，００６
ここで、合計１０人の組合せが仮マッチ集合に含まれることになり、病院の定員に達する。
【００７６】
参加者０１１の処理において、第１希望の研修プログラムＡの定員上限数には余裕があるが、病院の定員に余裕がないので、処理はステップＳ３２からステップＳ３７に分岐する。研修プログラムＡに参加者０１１の仮マッチが加えられる。ここで、定員を超えて仮マッチがなされている研修プログラムは、研修プログラムＢのみであるので、研修プログラムＢのみが仮マッチ除外処理の候補となる。参加者００４，００５，００７，００８のうち、病院ＲＯＬにおいて最も順位が低いのは参加者００８であり、したがって参加者００８が仮マッチから除外される。
【００７７】
この時点で、仮マッチ集合の内容は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：００９，０１０，０１１
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，００７
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３，００６
【００７８】
除外された参加者００８について処理が再開される。第２希望の研修プログラムＡの定員上限数には余裕があるが、病院の定員に余裕がないので、処理はステップＳ３２からステップＳ３７に分岐する。研修プログラムＡに参加者００８の仮マッチが加えられる。ここで、定員を超えて仮マッチがなされている研修プログラムは、研修プログラムＡおよびＢであり、これらが仮マッチ除外処理の候補となる。候補に含まれる参加者００４，００５，００７，００８，００９，０１０，０１１のうち、病院ＲＯＬにおいて最も順位が低いのは参加者００８であり、したがって参加者００８が仮マッチから除外される。
【００７９】
ここで、参加者００８が除外されるという動作は、従来のマッチングシステムの動作とは異なる。この時点では病院の定員および研修プログラムの定員上限数いずれも余裕があるので、従来のようにバランス調整を考慮しないマッチングシステムでは、全研修プログラムのうち病院ＲＯＬにおいて最も順位が低い参加者００６が仮マッチから除外されることになる。結果として、研修プログラム間の人数バランス調整よりも病院ＲＯＬの順位が優先されてしまい、研修プログラムＢが適正人数（定員）を超えて上限いっぱいとなる一方、研修プログラムＣは適正人数（定員）に満たないことになり、偏りが発生する。
【００８０】
本実施形態のマッチングシステムの説明に戻る。除外された参加者００８について処理が再開されるが、参加者００８は第３希望を持たないので、処理はステップＳ２６からステップＳ２７に分岐し、仮マッチが成立しないまま参加者００８の処理は終了する。
【００８１】
参加者０１２の処理において、第１希望の研修プログラムＢの定員上限数には余裕があるが、病院の定員に余裕がないので、処理はステップＳ３２からステップＳ３７に分岐する。研修プログラムＢに参加者０１２の仮マッチが加えられる。ここで、定員を超えて仮マッチがなされている研修プログラムは、研修プログラムＢのみであるので、研修プログラムＢのみが仮マッチ除外処理の候補となる。参加者００４，００５，００７，０１２のうち、病院ＲＯＬにおいて最も順位が低いのは参加者００７であり、したがって参加者００７が仮マッチから除外される。
【００８２】
この時点で、仮マッチ集合の内容は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：００９，０１０，０１１
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，０１２
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３，００６
【００８３】
除外された参加者００７について処理が再開される。第２希望の研修プログラムＡの定員上限数には余裕があるが、病院の定員に余裕がないので、処理はステップＳ３２からステップＳ３７に分岐する。研修プログラムＡに参加者００７の仮マッチが加えられる。ここで、定員を超えて仮マッチがなされている研修プログラムは、研修プログラムＡおよびＢであり、これらが仮マッチ除外処理の候補となる。候補に含まれる参加者００４，００５，００７，００９，０１０，０１１，０１２のうち、病院ＲＯＬにおいて最も順位が低いのは参加者００７であり、したがって参加者００７が仮マッチから除外される。
【００８４】
除外された参加者００７について処理が再開されるが、参加者００７は第３希望を持たないので、処理はステップＳ２６からステップＳ２７に分岐し、仮マッチが成立しないまま参加者００７の処理は終了する。これによってすべての参加者の処理が終了するので、処理はステップＳ２２からステップＳ２３に分岐し、最終的なマッチング結果が決定する。
【００８５】
この時点の仮マッチ集合の内容（すなわち最終的なマッチング結果）は次のようになる。
研修プログラムＡ（定員３人、定員上限数６人）：００９，０１０，０１１
研修プログラムＢ（定員２人、定員上限数４人）：００４，００５，０１２
研修プログラムＣ（定員４人、定員上限数８人）：００１，００２，００３，００６
【００８６】
この例からわかるように、病院ＲＯＬでは参加者００６の順位が最も低いにもかかわらず、参加者００６は研修プログラムＣとマッチが成立している。一方、病院ＲＯＬにおいて参加者００６よりも順位が高いはずの参加者００７および００８は、いずれの研修プログラムともマッチできていない。この理由は、参加者００６が第２希望において比較的人気のない（すなわち定員を超過しない）研修プログラムＣを指定しており、参加者００７および００８はいずれも第２希望において比較的人気のある（すなわち定員を超過する）研修プログラムＡを指定しているからである。
【００８７】
このように、本発明の実施の形態１に係るマッチングシステムによれば、定員に余裕のある研修プログラムを希望する参加者を優先してマッチさせることにより、研修プログラム間で参加者数のバランスをとり、偏りを防ぐことができる。
【００８８】
上述の実施の形態１では病院は１つだけであるが、複数の病院をマッチングの対象とすることもできる。この場合は、病院条件ファイル２（図４）、病院研修プログラム情報ファイル３（図５）、および病院ＲＯＬファイル５（図７）に複数の病院コードを用いて複数の病院を定義しておけばよい。病院が複数ある場合でも、図１１のフローチャートでは、ステップＳ２９において処理対象の病院コードを特定することができるので、各病院の病院ＲＯＬを適切に用いて処理を進めることができる。
【００８９】
実施の形態２．
実施の形態２は、実施の形態１において、病院を複数とし、一部の病院について研修プログラムごとにＲＯＬを指定できる構成とするものである。
図１３に、実施の形態２における病院、研修プログラムおよびＲＯＬファイルの関係を示す。病院Ａについては実施の形態１と同様に、病院全体で共通となる病院ＲＯＬ（ＲＯＬ−Ａ）が指定されている。一方、病院Ｂについては、研修プログラムごとにＲＯＬが異なり、ＲＯＬ−ｂ１、ＲＯＬ−ｂ２およびＲＯＬ−ｂ３という３つのＲＯＬが指定されている。
【００９０】
図１４は、実施の形態２に係る病院研修プログラム情報ファイル３ａの構成の例を示す。実施の形態１（図５）と異なり、「一時的病院コード」および「一時的病院名」の列が設けられている。この「一時的病院コード」および「一時的病院名」は、実際には１つの病院であっても処理上は複数のコードを与え、複数の病院であるかのように扱うためのものである。このようにすると、研修プログラムごとに異なる一時的病院コードを用いて、事実上は研修プログラムごとにＲＯＬを定義しつつ、処理上は病院ごとに病院ＲＯＬが１つだけ定義されることになる。
【００９１】
また、図１５は、実施の形態２に係る病院ＲＯＬファイル５ａの構成の例を示す。実施の形態１（図７）と異なり、病院Ｂについては１つの病院であるにも関わらず複数のＲＯＬが定義されており、各研修プログラムにそれぞれ１つのＲＯＬが対応している。１つの病院について複数のＲＯＬが定義される場合、それぞれのＲＯＬは異なる一時的病院コードによって特定される。
【００９２】
実施の形態２に係るマッチングシステムのマッチング手段は、実施の形態１と同様に図１１のフローチャートに従って動作するが、ステップＳ２９では変数ｍに病院コードを代入するのではなく、処理中の研修プログラムに対応する一時的病院コードを代入する。この結果、ステップＳ３０、Ｓ３６およびＳ３８では各一時的病院コードに対応するＲＯＬを参照して処理が行われる。
【００９３】
実施の形態２では、マッチングシステムは病院設定手段（図示せず）を備え、この病院設定手段が、管理者の入力等に応じて、一時的病院コードおよび一時的病院名を生成し、病院研修プログラム情報ファイル３ａに格納する。あるいは、一時的病院コードおよび一時的病院名は、病院管理者端末３００またはマッチング管理者端末４００から入力されてもよい。
なお、病院設定手段は、マッチングシステムの演算手段が、記憶手段に記憶されたコンピュータプログラムを実行することにより実現することができる。
【００９４】
以上のように、実施の形態２に係るマッチングシステムによれば、病院Ａについては実施の形態１と同様に研修プログラム間で参加者数のバランスをとるマッチングを行いつつ、病院Ｂについては各研修プログラムのＲＯＬにより厳密に適合するマッチングを行うことができ、マッチング方針を柔軟に変更することができる。
【００９５】
実施の形態３．
実施の形態３は、実施の形態２において、１つの病院における研修プログラムの一部のみでＲＯＬを共有する構成とするものである。
図１６に、実施の形態３における病院、研修プログラムおよびＲＯＬファイルの関係を示す。病院Ａについては実施の形態１と同様に、病院全体で共通となる病院ＲＯＬ（ＲＯＬ−Ａ）が指定されている。一方、病院Ｂについては、研修プログラムｄに対しては独立したＲＯＬ（ＲＯＬ−ｂ１）が指定されているが、研修プログラムｅおよびｆに対しては共通のＲＯＬ（ＲＯＬ−ｂ２）が指定されている。
【００９６】
図１７は、実施の形態３に係る病院研修プログラム情報ファイル３ｂの構成の例を示す。実施の形態２（図１４）と異なり、研修プログラム番号Ｂ０００２およびＢ０００３について共通の一時的病院コードＢ００１ｂおよび一時的病院名「病院Ｂｂ」が指定されている。
【００９７】
図１８は、実施の形態３に係る病院ＲＯＬファイル５ｂの構成の例を示す。病院Ｂについては、研修プログラムｄに対応するＲＯＬファイル（一時的病院コードＢ００１ａ）と、研修プログラムｅおよびｆに対応するＲＯＬファイル（一時的病院コードＢ００１ｂ）との合計２つが定義されている。
【００９８】
実施の形態３に係るマッチングシステムのマッチング手段は、実施の形態２と同様に動作する。ただし、研修プログラムｅおよびｆは共通の一時的病院コードを持つので、処理上は１つの病院に属するものとして扱われることになる。
【００９９】
以上のように、実施の形態３に係るマッチングシステムによれば、１つの病院Ｂの中でも、研修プログラムｄについては独立したＲＯＬを用いて厳密に参加者を選考することができ、研修プログラムｅおよびｆについては実施の形態１と同様に参加者数のバランスをとることができる。
【０１００】
なお、実施の形態１〜３の説明においては、研修を希望する参加者と研修プログラムとのマッチング問題について説明したが、その場合に限らず、集合Ａ（病院に相当）に含まれる複数のＡ要素（研修プログラムに相当）と、集合Ｂ（参加者の集合に相当）に含まれる複数のＢ要素（参加者に相当）との各要素をマッチングするマッチング問題において、各Ａ要素に割り当てられるＢ要素の数のバランスを調整するという課題であればこれを解決できることはいうまでもない。
【０１０１】
また、実施の形態１〜３において、マッチングシステム（マッチングサーバ１００、参加者端末２００、病院管理者端末３００、マッチング管理者端末４００）は、コンピュータで実現できるものである。また図示していないが、それぞれの装置は、コンピュータプログラムを実行することによってその装置の機能を実現するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。
例えば、ＣＰＵは、バスを介して、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、通信ボード、表示装置、Ｋ／Ｂ（キーボード）、マウス、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤＤ（コンパクトディスクドライブ）、磁気ディスク装置、光ディスク装置、プリンタ装置、スキャナ装置等と接続されている。
ＲＡＭは、揮発性メモリの一例である。ＲＯＭ、ＦＤＤ、ＣＤＤ、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。
前述した実施の形態の各装置が扱うデータや情報は、記憶装置あるいは記憶部に保存され、装置の各部により、記録され読み出されるものである。
また、通信ボードは、例えば、ＬＡＮ、インターネット、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されている。磁気ディスク装置には、オペレーティングシステム（ＯＳ）、ウィンドウシステム、コンピュータプログラム群、ファイル群（データベース）が記憶されている。
コンピュータプログラム群は、ＣＰＵ、ＯＳ、ウィンドウシステムにより実行される。
上記各装置の各部は、一部或いはすべてコンピュータで動作可能なコンピュータプログラムにより構成しても構わない。或いは、ＲＯＭに記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
上記コンピュータプログラム群には、実施の形態の説明において「〜手段」として説明した処理をＣＰＵに実行させ、当該手段の機能を実現させるコンピュータプログラムが記憶される。これらのコンピュータプログラムは、例えば、Ｃ言語やＨＴＭＬやＳＧＭＬやＸＭＬなどのコンピュータ言語により作成される。
また、上記コンピュータプログラムは、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体に記憶され、ＣＰＵにより読み出され実行される。
【符号の説明】
【０１０２】
１  研修プログラムマスタファイル、２  病院条件ファイル、３，３ａ，３ｂ  病院研修プログラム情報ファイル、４  参加者ＲＯＬファイル（第二の優先度リスト）、５，５ａ，５ｂ  病院ＲＯＬファイル（第一の優先度リスト）、６  マッチング結果格納ファイル、７  通信手段、８  マッチング手段、１００  マッチングサーバ、２００  参加者端末、３００  病院管理者端末、４００  マッチング管理者端末、５００  通信網。
【図１】
2012118818.tif 000003
【図２】
2012118818.tif 000004
【図３】
2012118818.tif 000005
【図４】
2012118818.tif 000006
【図５】
2012118818.tif 000007
【図６】
2012118818.tif 000008
【図７】
2012118818.tif 000009
【図８】
2012118818.tif 000010
【図９】
2012118818.tif 000011
【図１０】
2012118818.tif 000012
【図１１】
2012118818.tif 000013
【図１２】
2012118818.tif 000014
【図１３】
2012118818.tif 000015
【図１４】
2012118818.tif 000016
【図１５】
2012118818.tif 000017
【図１６】
2012118818.tif 000018
【図１７】
2012118818.tif 000019
【図１８】
2012118818.tif 000020
【図１９】
2012118818.tif 000021
【図２０】
2012118818.tif 000022
【図２１】
2012118818.tif 000023
【図２２】
2012118818.tif 000024