(57)【要約】【課題】配分希望（履修希望）が集中した場合に抽選という調整手段を用いつつ、容量体（教室）の容量を考慮しつつ資源（学生）の上位の希望ができるだけかなうように工夫して全体の満足度を最大化する資源配分先決定処理プログラム（学生履修科目決定処理プログラム）を提供する。【解決手段】総合大学の教養原論の受講は、学生の希望を基に抽選で決定される。このとき、複数の教員が同一の曜日時限で開講されており、同数の教室が割り当てられている。まず、受講学生の第１希望を集計し、より多くの学生の希望が実現するように、教室を割り当てる。教室の容量を超えて希望者が居た場合は抽選となる。抽選漏れの学生については、第２希望を集計する。この際、第１希望の当選者が落選することのない範囲で、教室の容量を考慮しつつ第２希望までの学生数が最大となるように教員と教室の割り当てを行なうプログラムである。【選択図】図１
2007122532.tif 000002
【特許請求の範囲】
【請求項１】
資源ごとに配分先の希望を表わす希望データの入力を受け付け、個々の前記資源を前記希望データに基づいて前記配分先のいずれかに仮配分する仮配分処理ステップと、
前記配分先を前記仮配分後の資源数に基づいて前記配分先の仮順序付けをする配分先仮順序付け処理ステップと、
前記配分先の仮順序付けに従って前記配分先を容量体に対してその容量の大きい順に一対一に仮割り当てをして行く、配分先−容量体の仮割り当て処理ステップと、
各々の前記配分先ごとに、前記仮配分後の資源の数よりも少ない資源の受け入れ容量の容量体に対して前記仮割り当てがされている配分先に対して前記配分先の順序付けが上位となるよう両者間の順序付けを固定・分離する配分先順序付け分離処理ステップと、
各々の前記配分先について、前記仮配分後の資源の数が前記仮割り当てにかかる前記容量体の資源の受け入れ容量を超過している場合に当該超過数分の資源を選択して配分落選を決め、その他の資源には配分当選を確定する配分確定処理ステップを備え、
前記固定・分離にかかる順序付けを逆転しないことを条件として前記配分落選にかかる資源についての前記仮配分処理ステップから前記配分確定処理ステップを繰り返し、すべての前記資源について配分先となる前記配分先の確定と前記配分先の前記容量体への割り当ての確定とを行なうことを特徴とする資源配分先決定処理プログラム。
【請求項２】
前記繰り返しにおいて、すべての前記資源について配分先となる前記配分先が確定した時点をもって、前記容量体の順序付けと前記配分先の順序付けに従って前記配分先の前記容量体への割り当てを確定することを特徴とする請求項１に記載の資源配分先決定処理プログラム。
【請求項３】
前記配分先−容量体の仮割り当て処理ステップにおいて、各々の前記配分先ごとに、前記仮配分処理ステップにおける仮配分後の資源の数よりも多い容量を持つ容量体を割り当てできる容量体として確保してそれ以外を割り当てできない容量体として制限する条件、または、前記配分先−容量体の仮割り当て処理ステップにおいて割り当てられた容量体またはその容量以上の容量を持つ容量体を割り当てできる容量体として確保してそれ以外を割り当てできない容量体として制限する条件を設定しておき、当該条件に合致するように次回以降に繰り返される前記配分先−容量体の仮割り当て処理ステップを実行することを特徴とする請求項１又は２に記載の資源配分先決定処理プログラム。
【請求項４】
前記資源が人的資源としての複数の学生であり、前記配分先が前記学生が履修を希望する複数の履修科目であり、前記容量体が定員が決まっている複数の教室であり、すべての学生について配分先となる履修科目の確定と履修科目が開催される教室の割り当ての確定とを行なう学生履修科目決定処理プログラムとしたことを特徴とする請求項１乃至３のいずれか１項に記載の資源配分先決定処理プログラム。
【請求項５】
前記資源が物的資源としての貨物であり、前記配分先が前記貨物の配達を請け負う配送者であり、前記容量体が積載容量が決まっている配送手段であり、すべての前記貨物について配分先となる前記配送者の確定と前記配送手段の割り当ての確定とを行なう物流管理プログラムとしたことを特徴とする請求項１乃至３のいずれか１項に記載の資源配分先決定処理プログラム。
【請求項６】
前記資源が物的資源としての商品であり、前記配分先が前記商品の供給を受ける業者であり、前記容量体が収納容量が決まっている倉庫であり、すべての前記商品について配分先となる前記業者の確定と前記倉庫の割り当ての確定とを行なう商品管理プログラムとしたことを特徴とする請求項１乃至３のいずれか１項に記載の資源配分先決定処理プログラム。
【請求項７】
前記資源が人的資源としての避難民であり、前記配分先が前記避難民を受け入れる避難地区であり、前記容量体が収納容量が決まっている避難所であり、すべての前記避難民について配分先となる前記避難地区の確定と前記避難所の割り当ての確定とを行なう災害時の避難民誘導支援プログラムとした、請求項１乃至３のいずれか１項に記載の資源配分先決定処理プログラム。
【請求項８】
データを入力する入力部と、
請求項１乃至７のいずれか１項に記載の資源配分先決定処理プログラムを記憶した記憶部と、
前記資源配分先決定処理プログラムを読み込む手段と、前記入力部から入力されたデータを読み込む手段と、前記データをもとに前記資源配分先決定処理プログラムを実行処理する手段とを備えた制御部と、
前記制御部の実行処理により得られた結果を受けて出力する出力部とを備えた資源配分先決定システム。
【請求項９】
前記資源が人的資源としての複数の学生であり、前記配分先が前記学生が履修を希望する複数の履修科目であり、前記容量体が定員が決まっている複数の教室であり、すべての学生について配分先となる履修科目の確定と履修科目が開催される教室の割り当ての確定とを行なう学生履修科目決定システムとした請求項８に記載の資源配分先決定システム。
【請求項１０】
前記資源が物的資源としての貨物であり、前記配分先が前記貨物の配達を請け負う配送者であり、前記容量体が積載容量が決まっている配送手段であり、すべての前記貨物について配分先となる前記配送者の確定と前記配送手段の割り当ての確定とを行なう物流管理システムとした請求項８に記載の資源配分先決定システム。
【請求項１１】
前記資源が物的資源としての商品であり、前記配分先が前記商品の供給を受ける業者であり、前記容量体が収納容量が決まっている倉庫であり、すべての前記商品について配分先となる前記業者の確定と前記倉庫の割り当ての確定とを行なう商品管理システムとした請求項８に記載の資源配分先決定システム。
【請求項１２】
前記資源が人的資源としての避難民であり、前記配分先が前記避難民を受け入れる避難地区であり、前記容量体が収納容量が決まっている避難所であり、すべての前記避難民について配分先となる前記避難地区の確定と前記避難所の割り当ての確定とを行なう災害時の避難民誘導支援システムとした、請求項８に記載の資源配分先決定処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、資源について配分先となる配分先の確定と、配分先の容量体への割り当ての確定とを行なう資源配分先決定処理プログラムおよび資源配分先決定システムに関するものである。例えば、学生について配分先となる履修科目の確定と、履修科目が開催される教室の割り当ての確定とを行なう学生履修科目決定処理プログラムおよび学生履修科目決定システムに関する。
【背景技術】
【０００２】
人や商品などを何らかの属性にふるい分けて配分するというニーズは多数存在する。
例えば、多数の学生（人的資源）に履修を希望する科目（配分先）の申請をさせ、希望を考慮しつつ学生を履修科目ごとにふるい分けて配分するというニーズがある。
一般に、総合大学など学生数が多数にのぼる教育機関において、教養原論科目など学部、学科の垣根を越えて自由に履修が可能な履修科目に関しては、多数の種類の履修科目が設けられるとともに同じ履修科目が複数のクラスで開講されることも多い。例えば、履修科目の種類として、哲学、宗教学、英語、ドイツ語、フランス語など多岐にわたる科目が用意され、かつ、同じドイツ語の履修科目であっても、ドイツ語教員Ａが開講するクラス、ドイツ語教員Ｂが開講するクラス、ドイツ語教員Ｃが開講するクラスというように複数のクラスが開講されているのが通例である。学生はこれら教養原論科目の履修にあたっては、学部学科の垣根を越えて自由に履修科目を選び、その履修科目ごとに具体的に教員を選択して履修申請することができる場合が多い。例えば、「ドイツ語について水曜日第３限の○○先生のクラスを受講したい」という希望のもと、履修申請を行なう。
【０００３】
このように学生に履修科目の選択を学部学科の垣根を越えて自由に希望・選択させることは、学生にとり柔軟かつ自主的な履修計画が可能となり、学生の満足度も高いものとなることが期待できる。
ここで、履修科目の種類、開講曜日、開講時間、担当教員の違いにより、履修希望が集中する場合も多い。このように履修希望が集中してもすべての学生に対して希望どおりの履修を認めるのが理想的ではある。
【０００４】
しかし、実際には、履修科目のクラスが開講される教室の定員が限られており、履修科目のクラスには履修可能な学生数がおのずと制限される。つまり、資源の配分問題において資源を収納する容量体の容量による制限は無視できない条件となる。大学など教育機関が履修科目のクラスの開講に利用可能な教室は複数個あるが、それぞれには収容可能な定員数がある。同一曜日の同一時間帯に開講される複数の履修科目のクラスについて、限られた数の教室のうちから適当な定員数を持つ教室を選んで割り当てて行く必要がある。
【０００５】
このように、多数の学生に履修を希望する履修科目の申請をさせ、その希望を考慮しつつ学生を履修科目ごとにふるい分けて配分し、教室の割り当ても行なうことを目的とするシステムの開発が試みられている（例えば、特許文献１）。
【０００６】
【特許文献１】特開２０００−１１３０３４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
多数の学生から履修を希望する履修科目の申請を受け付け、学生の希望が最大限かなうように履修科目・クラスへの配分、教室の割り当てを適切に行なうことが好ましい。
しかし、上記従来の特許文献１に記載の技術には、実際の大学などでの履修申請の実態と履修希望が集中した場合の調整方法の実態に即した解決手段となっていないという問題がある。
【０００８】
まず、特許文献１記載の技術によれば、学生による履修申請が科目別の申請となっており、履修希望が集中した場合に、学生の履修希望をかなえるため自在にクラスを増やすという解決策を開示している。例えばその［００３１］段に、「たとえば、履修希望集計ファイル３２内のある科目の人数が２８８で、科目制約ファイル３３内の最大開講人数が４０の場合、２８８／４０＝７．２を計算し、０．２を繰り上げて、８が講座数とする」と開示されている。つまり、履修科目の申請が履修科目別であり、上記例では２８８人の学生の希望をすべてかなえるために必要なクラス数を８つと算出し、クラス数を柔軟に８つに増やすことをもって履修希望が集中した場合の履修調整手段としている。
【０００９】
しかし、実際の大学では履修希望が集中したからと言って動的にクラスを急に増やすということは事実上できない。つまり、ドイツ語の履修申請が集中したからと言ってドイツ語の教員を急に採用して開講されるクラス数を急に増加させることは現時的な解決策ではない。また、実際の大学などの履修申請の実態は、履修申請が教員単位（クラス単位）となっている。つまり、生徒は「Ａ教員のドイツ語」というふうに教員を直接希望している場合も多く、同じドイツ語であっても希望教員とは違う「Ｂ教員のドイツ語」が割り当たった場合、ドイツ語の履修が認められたからと言ってかならずしも学生の満足度が大きいとは限らない。つまり、上記特許文献１記載の技術ではかならずしも学生の満足度が大きい解決策を提供できるとは限らない。
【００１０】
次に、特許文献１に記載の技術は、学生の履修科目の希望が１つ（第１希望）しかなく、第１希望が外れた場合の第２希望以下の履修科目・クラスへ回るという調整方法が加味されていない。つまり、履修科目の申請において、第１希望が外れて第２希望以下に回るという事態を想定していない。しかし、実際の大学での履修希望が集中した場合の調整方法の実態は、履修科目の教員を急に増やして開講クラス数を増やすことはなく、抽選により履修申請を認める学生を絞ることにより調整が行なわれる。その結果、学生の中には第１希望の履修クラスが外れ、第２希望以下の履修クラスへ回されるという事態が起こり得る。
【００１１】
なお、実際の大学では学生の履修申請に対し、できるだけ上位の履修希望が適うように調整を試みるが、当該調整を最適化するアルゴリズムが確立しておらず、コンピュータを用いて自動的に調整することが難しく、実際には手作業で調整する場合も多い。
学生の第１希望の履修申請をできるだけかなえるためには、第１希望の履修申請の多いクラスから順に、定員の大きい教室を割り当てて行くという調整が想定される。
【００１２】
しかし、この単純な原則のみでは以下の問題が生じる。
第１希望が認められた学生数も最大化でき、第２希望で認められた学生も最大化できる方が学生全体の満足度が高いと言えるが、上記した単純に学生の第１希望の履修申請を集計した段階で履修申請が多いクラスから順に定員の大きい教室を割り当てる調整方法では、第１希望の履修申請が認められる学生数は最大化できても第１希望の履修申請が外れた学生の中で第２希望の履修申請がかなう学生数を最大化できるとは限らない。
そこで、第１希望と第２希望の履修申請の合計数が多いクラスから順に定員の大きい教室を割り当てて行くという調整が想定される。
【００１３】
しかし、この原則のみでも以下の問題が生じる。上記した第１希望と第２希望の履修申請の合計数が多いクラスから順に定員の大きい教室を割り当てる調整方法では、第１希望と第２希望の履修申請が認められる学生数は多くなるが、第１希望の履修申請が認められる学生数が最大化できるとは限らない。例えば、第１希望の履修申請の学生数が相対的に多くても第２希望の履修申請の学生数が少ない場合、第１希望と第２希望の履修申請の合計数での順序は相対的に下がり定員数の小さな教室が割り当る場合も起こりえる。この場合、当該教室の定員が第１希望の履修申請の数よりも小さい事態も想定され、この事態において行なわれる抽選では第１希望の履修申請の学生が落選してしまうこととなるからである。
【００１４】
上記問題点に鑑み、本発明は、履修希望が集中した場合に抽選という調整手段を用いつつ、学生の上位の履修希望ができるだけかなうように工夫して学生全体の満足度を最大化することを目的とする。具体的には、本発明では、学生全体の満足度は第１希望の履修申請がかなう学生数がもっとも多くなり、かつ、第１希望の履修申請が外れた学生の中で第２希望の履修申請がかなう学生数がもっとも多くなり、以下、上位の希望の履修申請が外れた場合に次点の希望の履修申請がかなう学生数が最大となるように調整して学生全体の満足度を最大化することを目的とする。
【００１５】
なお、本発明は、学生の履修申請時の調整に限らず、資源配分先決定システムとして、資源（人的資源、物的資源など）の配分先（履修クラスの別、配送先の別など）に配分し、配分先を資源の受け入れ容量が決まっている容量体（教室、車などの配送手段、倉庫など）に割り当てて資源を収納するというアプリケーションにおける調整に適用することを目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するため、本発明の資源配分先決定処理プログラムは、
資源ごとに配分先の希望を表わす希望データの入力を受け付け、個々の前記資源を前記希望データに基づいて前記配分先のいずれかに仮配分する仮配分処理ステップと、
前記配分先を前記仮配分後の資源数に基づいて前記配分先の仮順序付けをする配分先仮順序付け処理ステップと、
前記配分先の仮順序付けに従って前記配分先を容量体に対してその容量の大きい順に一対一に仮割り当てをして行く、配分先−容量体の仮割り当て処理ステップと、
各々の前記配分先ごとに、前記仮配分後の資源の数よりも少ない資源の受け入れ容量の容量体に対して前記仮割り当てがされている配分先に対して前記配分先の順序付けが上位となるよう両者間の順序付けを固定・分離する配分先順序付け分離処理ステップと、
各々の前記配分先について、前記仮配分後の資源の数が前記仮割り当てにかかる前記容量体の資源の受け入れ容量を超過している場合に当該超過数分の資源を選択して配分落選を決め、その他の資源には配分当選を確定する配分確定処理ステップを備え、
前記固定・分離にかかる順序付けを逆転しないことを条件として前記配分落選にかかる資源についての前記仮配分処理ステップから前記配分確定処理ステップを繰り返し、すべての前記資源について配分先となる前記配分先の確定と前記配分先の前記容量体への割り当ての確定とを行なう。
【００１７】
なお、上記の資源配分先決定処理プログラムにおいて、前記繰り返しにおいて、すべての前記資源について配分先となる前記配分先が確定した時点をもって、前記容量体の順序付けと前記配分先の順序付けに従って前記配分先の前記容量体への割り当てを確定する。
上記構成により、資源の配分先の第１希望がかなう資源の数を最大化しつつ、配分落選した資源について上位の希望がかなう資源の数も最大化することができ、資源配分に関する満足度を向上することができる。また、一度のフローではすべての資源の配分先の確定と配分先の容量体への割り当てが確定できない場合であっても、フローのループによってすべて確定することができる。
【００１８】
次に、前記配分先−容量体の仮割り当て処理ステップにおいて、各々の前記配分先ごとに、前記仮配分処理ステップにおける仮配分後の資源の数よりも多い容量を持つ容量体を割り当てできる容量体として確保してそれ以外を割り当てできない容量体として制限する条件、または、前記配分先−容量体の仮割り当て処理ステップにおいて割り当てられた容量体またはその容量以上の容量を持つ容量体を割り当てできる容量体として確保してそれ以外を割り当てできない容量体として制限する条件を設定しておき、当該条件に合致するように次回以降に繰り返される前記配分先−容量体の仮割り当て処理ステップを実行することが好ましい。
【００１９】
上記構成により、上記の資源配分先決定処理プログラムの繰り返し処理において、解がなくなる事態が避けられ、配分先の容量体への割り当てを最適化し、その中で資源の配分先の第１希望がかなう資源の数を最大化しつつ、配分落選した資源について上位の希望がかなう資源の数も最大化する解を得ることができる。
【００２０】
上記構成の資源配分先決定処理プログラムにおいて、前記資源が人的資源としての複数の学生であり、前記配分先が前記学生が履修を希望する複数の履修科目であり、前記容量体が定員が決まっている複数の教室であり、すべての学生について配分先となる履修科目の確定と履修科目が開催される教室の割り当ての確定とを行なうものとすれば、本発明の資源配分先決定処理プログラムを学生履修科目決定処理プログラムに適用することができる。
【００２１】
また、上記構成の資源配分先決定処理プログラムにおいて、前記資源が物的資源としての貨物であり、前記配分先が前記貨物の配達を請け負う配送者であり、前記容量体が積載容量が決まっている配送手段であり、すべての前記貨物について配分先となる前記配送者の確定と前記配送手段の割り当ての確定とを行なうものとすれば、本発明の資源配分先決定処理プログラムを物流管理プログラムに適用することができる。
【００２２】
また、上記構成の資源配分先決定処理プログラムにおいて、前記資源が物的資源としての商品であり、前記配分先が前記商品の供給を受ける業者であり、前記容量体が収納容量が決まっている倉庫であり、すべての前記商品について配分先となる前記業者の確定と前記倉庫の割り当ての確定とを行なうものとすれば、本発明の資源配分先決定処理プログラムを商品管理プログラムに適用することができる。
【００２３】
また、上記構成の資源配分先決定処理プログラムにおいて、前記資源が人的資源としての避難民であり、前記配分先が前記避難民を受け入れる避難地区であり、前記容量体が収納容量が決まっている避難所であり、すべての前記避難民について配分先となる前記避難地区の確定と前記避難所の割り当ての確定とを行なうものとすれば、本発明の資源配分先決定処理プログラムを災害時の避難民誘導支援プログラムに適用することができる。
【００２４】
上記目的を達成するため、本発明の資源配分先決定システムは、データを入力する入力部と、上記の資源配分先決定処理プログラムのいずれかを記憶した記憶部と、前記資源配分先決定処理プログラムを読み込む手段と、前記入力部から入力されたデータを読み込む手段と、前記データをもとに前記資源配分先決定処理プログラムを実行処理する手段とを備えた制御部と、前記制御部の実行処理により得られた結果を受けて出力する出力部とを備えたものである。
【００２５】
上記本発明の資源配分先決定システムは、前記資源が人的資源としての複数の学生であり、前記配分先が前記学生が履修を希望する複数の履修科目であり、前記容量体が定員が決まっている複数の教室であり、すべての学生について配分先となる履修科目の確定と履修科目が開催される教室の割り当ての確定とを行なうものとすれば、学生履修科目決定システムに適用することができる。
【００２６】
また、上記本発明の資源配分先決定システムは、前記資源が物的資源としての貨物であり、前記配分先が前記貨物の配達を請け負う配送者であり、前記容量体が積載容量が決まっている配送手段であり、すべての前記貨物について配分先となる前記配送者の確定と前記配送手段の割り当ての確定とを行なうものとすれば、物流管理システムに適用することができる。
【００２７】
また、上記本発明の資源配分先決定システムは、前記資源が物的資源としての商品であり、前記配分先が前記商品の供給を受ける業者であり、前記容量体が収納容量が決まっている倉庫であり、すべての前記商品について配分先となる前記業者の確定と前記倉庫の割り当ての確定とを行なうものとすれば、商品管理システムに適用することができる。
【００２８】
また、上記本発明の資源配分先決定システムは、前記資源が人的資源としての避難民であり、前記配分先が前記避難民を受け入れる避難地区であり、前記容量体が収納容量が決まっている避難所であり、すべての前記避難民について配分先となる前記避難地区の確定と前記避難所の割り当ての確定とを行なうものとすれば、災害時の避難民誘導支援システム適用することができる。
【発明の効果】
【００２９】
本発明に係る資源配分先決定処理プログラムおよび資源配分先決定システムによれば、配分先への配分希望が集中した場合に抽選という調整手段を用いつつ、上位の配分希望ができるだけかなうように工夫して資源全体の満足度を高くすることができる。具体的には、第１希望がかなう資源数がもっとも多くなり、かつ、第１希望が外れた資源の中で第２希望以下の希望がかなう資源数がもっとも多くなり、以下、上位の希望が外れた場合に次点の希望がかなう資源数が最大となるように調整し、資源全体の満足度を最大化することができる。
【００３０】
例えば、本発明に係る資源配分先決定システムを学生履修科目決定システムに適用した場合、本発明に係る学生履修科目決定システムによれば、履修希望が集中した場合に抽選という調整手段を用いつつ、学生の上位の履修希望ができるだけかなうように工夫して学生全体の満足度を高くすることができる。具体的には、学生全体の満足度は第１希望の履修申請がかなう学生数がもっとも多くなり、かつ、第１希望の履修申請が外れた学生の中で第２希望の履修申請がかなう学生数がもっとも多くなり、以下、上位の希望の履修申請が外れた場合に次点の希望の履修申請がかなう学生数が最大となるように調整し、学生全体の満足度を最大化することができる。
【発明を実施するための最良の形態】
【００３１】
以下、本発明の資源配分先決定処理プログラムおよび資源配分先決定システムの実施例について、図面を参照しながら詳細に説明していく。
最初に、実施例１として、本発明の資源配分先決定処理プログラムの基本フロー（配分先順序付けにおける「分離」の概念を導入したフロー）を示し、実施例２として、本発明の資源配分先決定処理プログラムの基本フロー（配分先順序付けにおける「分離」と「確保」の概念を導入したフロー）を示し、次に、実施例３として、資源配分先決定処理プログラムを学生履修科目決定処理プログラムに適用した例を示し、実施例４として、資源配分先決定処理プログラムを物流管理プログラムに適用した例を示し、実施例５として、資源配分先決定処理プログラムを商品管理プログラムに適用した例を示し、実施例６として、実施例１から実施例５のいずれかに示した資源配分先決定処理プログラムを組み込んだ資源配分先決定システムの例を示す。
【００３２】
以下、説明の便宜上、第１希望の数が最大であった配分先を「１番配分先」と呼び、第ｎ番目の配分先を第ｎ番配分先と呼ぶ。また、最大の容量体を「１番容量体」と呼び、第ｎ番目の容量体を第ｎ番容量体と呼ぶ。
【実施例１】
【００３３】
まず、本発明の資源配分先決定処理プログラムの基本フロー（配分先順序付けにおける「分離」の概念を導入したフロー）を説明する。
本発明の資源配分先決定処理プログラムの基本フローは、資源の配分先の第１希望がかなう資源の数を最大化しつつ、配分落選した資源について上位の希望がかなう資源の数も最大化し、資源配分に関する満足度を向上するために、以下の概念を導入している。
【００３４】
第１の概念が、配分先順序付けにおける「分離」処理の概念である。
この「分離」の概念の説明も含め、基本フローの流れを追いつつ説明する。
図１は、本発明の資源配分先決定処理プログラムの基本フローチャートである。
【００３５】
［１］（容量体）順序付け処理ステップ（ステップＳ１）
まず、資源の受け入れ容量が各々定められている複数の容量体を、その容量に基づいて順序付けをする。容量体の容量によって資源受け入れ数が異なるので、どの容量体にどの配分先を割り当てるかは重要な判断基準となる。そのため利用可能な容量体とその容量を把握する。
【００３６】
［２］（資源−配分先）仮配分処理ステップ（ステップＳ２）
次に、各々の資源ごとに配分先の希望を表わす希望データの入力を受け付け、個々の資源を希望データに基づいて配分先のいずれかに仮配分する。このステップＳ２の処理によって、第１回目の処理ループにおいては、個々の資源を第１希望の配分先に対してとりあえず仮配分することとなる。第ｎ回目の処理ループにおいては、後述する抽選に落選した資源に対して第ｎ希望の配分先に対してとりあえず仮配分することとなる。
【００３７】
［３］（配分先）仮順序付け処理ステップ（ステップＳ３）
次に、配分先を仮配分後の資源数に基づいて配分先の仮順序付けをする。このステップＳ３の処理によって、第１希望が多い順に配分先を仮順序付けし、第１希望がかなう資源数が多くなるように配分するには、どの配分先にどのぐらいの容量を持つ容量体を割り当てるかは重要な判断基準となるので、配分先を仮配分後の資源数に基づいて仮順序付けをするものである。第ｎ回目の処理ループにおいては、第ｎ希望が多い順に配分先を仮順序付けすることとなる。
【００３８】
［４］（配分先−容量体）仮割り当て処理ステップ（ステップＳ４）
次に、ステップＳ３の配分先の仮順序付けに従って、配分先を容量体に対してその容量の大きい順に一対一に仮割り当てをして行く。このステップＳ４の処理によって、容量の大きい順に並べられた容量体に対して、第１希望が多い配分先から順に割り当てて行くので、第１希望が１番大きい配分先には１番容量が大きい容量体が仮割り当てされ、第１希望が第ｍ番目に大きい配分先には第ｍ番目の容量の容量体が仮割り当てされるので、第１希望が満たされる資源の数が最大化されることとなる。
【００３９】
［５］（配分先）順序付け分離処理ステップ（ステップＳ５）
次に、各々の配分先ごとに、仮配分後の資源の数よりも少ない資源の受け入れ容量の容量体に対して仮割り当てがされている配分先に対して配分先の順序付けが上位となるよう両者間の順序付けを当該個所において固定・分離する。
【００４０】
この「分離処理」という概念について詳しく説明する。
図２（ａ）および図２（ｂ）は分離処理の概念を模式的に示す図である。
容量体は容量体ＡからＥの５つが容量を高さとして模式的に表わした四角の枠で示され、配分先ＡからＥの５つが仮配分された資源の数を高さとして模式的に表わした四角の斜めハッチングにより満たされた形で示されている。なお説明の便宜上、図２（ｂ）の容量体Ｃ、Ｄの容量は図２（ａ）の容量体Ｃ、Ｄの容量よりも小さいものとしている。
図２の状態は、既にステップＳ１からステップＳ４までの処理ステップが反映されている。容量体に関しては、容量の大きさの順に（この図では高さの順に）降順にソートされて並べられており、左側から順に容量体ＡからＥがその順に「第１番容量体」、「第２番容量体」、・・・「第５番容量体」と順序付けられている。配分先に関しては、既に資源が仮配分され、仮順序付けされ、配分先を容量体に対して一対一に仮割り当てされている。つまり、左側から順に資源数の大きさの順に（この図では斜めハッチングの高さの順に）降順にソートされて並べられており、配分先ＡからＥがその順に「第１番配分先」、「第２番配分先」、・・・「第５番配分先」と割り当てられている。
【００４１】
ここで、分離処理とは、各々の配分先ごとに仮配分されている資源の数を調べ、当該資源の数よりも少ない容量である容量体を特定し、それら容量体に対して仮割り当てがされている下位の配分先に対して配分先の順序付けがかならず上位となるよう順序ルールを確定し、両者間の順序付けを当該個所において固定・分離して行く処理である。つまり、第１回目の処理ループにおいて、配分先の仮順序付けでは、第１希望の数が第ｎ番目であった配分先が「第ｎ番配分先」であり、第（ｎ＋１）番目であった配分先が「第（ｎ＋１）番配分先」である並びとなり、容量体の仮割り当てでは、「第ｎ番配分先」が「第ｎ番容量体」に仮割り当てされ、「第（ｎ＋１）番配分先」が「第（ｎ＋１）番容量体」に仮割り当てされるが、「第ｎ番配分先」の希望資源の数が、「第（ｎ＋１）番容量体」の容量より大きい場合、配分先の仮順序付けにおいて「第ｎ番配分先」と「第（ｎ＋１）番配分先」の逆転が起こらないよう順序ルールを確定し、両者間の順序付けを当該個所において固定・分離する。
【００４２】
例えば、図２（ａ）の例で言えば、第１回目の処理ループにおいて、上記分離処理の条件に合致する部分は、第４番配分先である配分先Ｄと第５番配分先である配分先Ｅの間である。つまり、配分先Ａの仮配分資源数と容量体Ｂの容量、配分先Ｂの仮配分資源数と容量体Ｃの容量、配分先Ｃの仮配分資源数と容量体Ｄの容量、配分先Ｄの仮配分資源数と容量体Ｅの容量を比較すれば、前者の仮配分資源数が後者の容量体の容量よりも大きい個所は配分先Ｄと容量体Ｅの間しかない。ここで容量体Ｅが仮割り当てされている配分先Ｅに対して配分先Ｄの配分先順序付けが必ず上位となる順序ルールを確定し、配分先の仮順序付けの並びにおいて配分先Ｄと配分先Ｅの間を分離する。この分離処理により、以後の処理ループの配分先の順序付けにおいて、配分先Ｄは配分先Ｅよりも必ず上位の順序となりその順序が逆転することはないよう両者間の順序付けを当該個所において固定・分離する順序付けの条件が加えられる。
【００４３】
同様に、図２（ｂ）の例で言えば、第１回目の処理ループにおいて、上記分離処理の条件に合致する部分は、第２番配分先である配分先Ｂと第３番配分先である配分先Ｃの間、第３番配分先である配分先Ｃと第４番配分先である配分先Ｄの間、第４番配分先である配分先Ｄと第５番配分先である配分先Ｅの間である。ここで配分先Ｂに対して配分先Ｃの配分先順序付けが必ず上位となる順序ルールと、配分先Ｃに対して配分先Ｄの配分先順序付けが必ず上位となる順序ルールを確定し、配分先Ｄに対して配分先Ｅの配分先順序付けが必ず上位となる順序ルールを確定し、配分先ＢとＣ、配分先ＣとＤ、配分先ＤとＥの間においてそれぞれ順序付けを部分的に固定・分離する。この分離処理により、以後の処理ループの配分先の順序付けにおいて、配分先Ｂ、Ｃ、Ｄ、Ｅの順序が逆転することはないよう順序付けの条件が加えられる。
上記が「分離処理」という概念である。
【００４４】
［６］（資源−配分先）配分確定処理ステップ（ステップＳ６）
次に、各々の配分先について、仮配分後の資源の数がステップＳ４で仮割り当てされた容量体の資源の受け入れ容量を超過している場合に当該超過数分の資源を選択して配分落選を決め、その他の資源には配分当選を確定する。
つまり、この処理ステップでは、容量体に入りきらない資源数が仮配分されている状態があれば抽選を行なって当選と落選を決める。
【００４５】
上記の図２（ａ）の例では、第１番配分先である配分先Ａから第５番配分先である配分先Ｅのすべてについて仮割り当てされている容量体の容量の方が大きく、上記の抽選処理により配分の当落を決める必要はない。つまり、図２（ａ）の例では、配分先Ａから配分先Ｅのすべての配分先について、ステップＳ２で仮配分された資源の配分が確定することとなり、斜めハッチングで示された資源の配分がすべて確定する。
【００４６】
上記の図２（ｂ）の例では、第３番配分先である配分先Ｃについて、仮配分後の資源数（斜めハッチング）が仮割り当てされている容量体Ｃの容量を超えている。この配分先Ｃについては容量体Ｃの枠を越えているため、超過数分の資源を選択して配分落選を決め、その他の資源には配分当選を確定する必要がある。つまり、斜めハッチングで示された資源の数が容量体Ｃの枠内に収まるように抽選で当落を決める必要がある。同様に、第４番配分先である配分先Ｄについて、仮配分後の資源数（斜めハッチング）が仮割り当てされている容量体Ｄの容量を超えている。この配分先Ｄについても容量体Ｄの枠を越えているため、超過数分の資源を選択して配分落選を決め、その他の資源には配分当選を確定する必要がある。つまり、斜めハッチングで示された資源の数が容量体Ｄの枠内に収まるように配分当落を決める必要がある。
【００４７】
なお、配分当落の決定方法として多様な方法がある。資源の間に抽選についての優劣度合いを導入しない単純抽選方法、資源の間にあらかじめ抽選についての優劣度合いを導入しておく優先条件付き抽選方法、資源間で交渉を必要とする話し合い調整方法などが想定できる。ここでは一例として単純抽選方法を採用することとする。
【００４８】
［７］資源の配分先確定終了チェック
次に、すべての資源について配分先が確定したか否かチェックする（ステップＳ７）。
すべての資源について配分先が確定している場合（ステップＳ７：Ｙ）、すべての資源について配分先の確定と、配分先の容量体への割り当ての確定とを行なう（ステップＳ９）。つまり、すべての資源について、どの配分先に配分され、当該配分先がどの容量体に割り当てられたかが確定され、処理が終了する状態となる。なお、このケースは上記例で言えば、図２（ａ）のケースにあたり、資源配分の当落を決める抽選処理の必要がないケースに該当する。
【００４９】
ステップＳ７のチェックの結果、一部の資源について配分先が確定していない場合（ステップＳ７：Ｎ）、配分当落処理において、配分落選にかかる資源について（資源−配分先）仮配分処理ステップ（ステップＳ２）から（資源−配分先）配分確定処理ステップ（ステップＳ６）を繰り返すべく（資源−配分先）仮配分処理ステップ（ステップＳ２）に戻る（ステップＳ８、ステップＳ２に戻るループ）。
なお、このケースは上記例で言えば、図２（ｂ）のケースにあたり、資源配分の当落を決める抽選処理の結果、配分落選にかかる資源が存在するケースに該当する。
【００５０】
図３は、第１回目のステップＳ６の配分当落処理において配分落選した資源について、（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理が行なわれた例を模式的に示す図である。
図３（ａ）の状態は、図２（ｂ）の状態から配分当落処理が行なわれ、配分落選にかかる資源が決まった時点の状態を示している。配分先Ｃに仮配分後の資源のうち配分落選となった資源が縦ハッチングとして容量体Ｃの枠体から溢れた状態で示されている。同様に、配分先Ｄに仮配分されていた資源のうち配分落選となった資源が縦ハッチングとして容量体Ｄの枠体から溢れた状態で示されている。この縦ハッチングで示された資源について（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理が繰り返される。なお、他の斜めハッチングで示された資源については既に配分が確定しているので再処理に回されることはない。
【００５１】
［２再］（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理
図３（ｂ）の状態は、図３（ａ）において縦ハッチングで示された資源について（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理が行なわれた結果を示す図である。この例は、配分落選した資源のうち、配分先Ｂを第２希望としていたものが配分先Ａを第２希望としていたものよりも比較的に多かった例となっている。
なお、第１希望の配分落選にかかる資源のうち、配分先Ｃを第１希望としていた資源が配分先Ｄを第２希望に選択したり、配分先Ｄを第１希望としていた資源が配分先Ｃを第２希望に選択している場合も想定できるが、このような場合でも、そのまま仮配分する処理として良い。この例は配分先Ｃ、配分先Ｄを第２希望として選択した資源がない例を示している。
【００５２】
［３再］（配分先）仮順序付け処理ステップ（ステップＳ３）の再処理
次に、（配分先）仮順序付け処理ステップ（ステップＳ３）の再処理が行なわれる。ここで、前回の処理ループにおける（配分先）順序付け分離処理ステップ（ステップＳ５）において定めされた順序ルールを逆転しないことを条件となる。
図４（ａ）の状態は、図３（ｂ）の状態の第２回目の仮配分処理が反映された状態から、仮配分後の総資源数によりソートして配分先の仮順序付けを行なった状態を示す図である。この例では、仮配分後の総資源数において配分先Ｂの総資源数が配分先Ａの総資源数よりも多くなり逆転している。配分先Ａと配分先Ｂの間は順序ルールが定められていないため（つまり配分先Ａと配分先Ｂの順序付けの並びは分離されていないため）、配分先Ａと配分先Ｂの順序が入れ替わっている。
一方、この例では、仮配分後の総資源数において配分先Ｄの総資源数が配分先Ｅの総資源数よりも多くなり逆転しているが、配分先Ｄと配分先Ｅの間は順序ルールが定められているため（つまり配分先Ｄと配分先Ｅの順序付けの並びは分離されており、かならず配分先Ｄが配分先Ｅに対して上位となるよう順序ルールが定められているため）、配分先Ｄと配分先Ｅの順序は入れ替えることができない。
【００５３】
［４再］（配分先−容量体）仮割り当て処理ステップ（ステップＳ４）の再処理
次に（配分先−容量体）仮割り当て処理ステップ（ステップＳ４）の再処理が行なわれる。第１番配分先となった配分先Ｂに対して第１番容量体である容量体Ａが仮割り当てされ、第２番配分先となった配分先Ａに対して第２番容量体である容量体Ｂが仮割り当てされ、第３番配分先となった配分先Ｃに対して第３番容量体である容量体Ｃが仮割り当てされる。第４番配分先は依然配分先Ｄであるので配分先Ｄに対して第４番容量体である容量体Ｄが仮割り当てされ、第５番配分先は依然配分先Ｅであるので配分先Ｅに対して第５番容量体である容量体Ｅが仮割り当てされる。
【００５４】
［５再］（配分先）順序付け分離処理ステップ（ステップＳ５）の再処理
上記の例では、図４（ａ）に示した状態において配分先と容量体が仮割り当てされる。
次に（配分先）順序付け分離処理ステップ（ステップＳ５）の再処理が実行される。
図４（ａ）に示した例では、（配分先）順序付け分離による新たな順序ルールが定められる個所はない。
【００５５】
［６再］（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理
次に（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理が実行される。
ここでは、第２希望において仮配分後の資源の数が仮割り当てにかかる容量体の容量を超過していないものはその配分を確定し、仮配分後の資源の数が仮割り当てにかかる容量体の容量を超過している場合に第２希望で仮配分された資源から抽選により配分落選を決め、配分当選となった資源については配分を確定する。
図４（ｂ）に示したように、配分先Ｂに対して第２希望で仮配分された資源についてはすべて配分が確定され、配分先Ａに対して第２希望で仮配分された資源についてもすべて配分が確定され、両者とも当該部分が斜めハッチングに変わっている。一方、配分先Ｅについては仮配分後の資源の数が仮割り当てにかかる容量体Ｅの容量を超過しているので、配分当落処理が行なわれ、配分当選の資源のみが斜めハッチングに変わり、配分落選した資源については縦ハッチングのままとなっている。
【００５６】
以上で（資源−配分先）仮配分処理ステップ（ステップＳ２）から（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理ループが完了する。
再度、すべての資源について配分先が確定したか否かチェックし（ステップＳ７）、すべての資源について配分先が確定している場合（ステップＳ７：Ｙ）、すべての資源について配分先の確定と配分先の容量体への割り当ての確定とを行なう（ステップＳ９）。
【００５７】
図４（ｂ）の例では、配分先Ｅの一部の資源について配分先が確定していないので（ステップＳ７：Ｎ）、再度、（資源−配分先）仮配分処理ステップ（ステップＳ２）から（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理ループに回されることとなる。
【００５８】
図５は、図４（ｂ）の状態から、すべての資源について配分先が確定した場合を示しており（ステップＳ７：Ｙ）、すべての資源について配分先の確定と配分先の容量体への割り当ての確定が行なわれ（ステップＳ９）、処理が終了した状態となっている。
このように、繰り返し処理において、すべての資源について配分先となる配分先が確定した時点をもって、容量体の順序付けと配分先の順序付けに従って配分先の容量体への割り当てを確定する。
【００５９】
以上、資源の配分先の第１希望がかなう資源の数を最大化しつつ、配分落選した資源について上位の希望がかなう資源の数も最大化することができ、資源配分に関する満足度を向上することができる。
【実施例２】
【００６０】
実施例２として、本発明の資源配分先決定処理プログラムの基本フロー（配分先順序付けにおける「分離」と「確保」の概念を導入したフロー）を説明する。
実施例２の資源配分先決定処理プログラムの基本フローは、実施例１の基本フローの資源配分先決定処理プログラムの繰り返し処理のループにおいて解がなくなる事態を避ける工夫を追加したものである。
【００６１】
実施例２の資源配分先決定処理プログラムの基本フローは上記した繰り返し処理のループにおいて解がなくなる事態を回避するため配分先順序付けにおける「確保」の概念を導入する。
この「確保」の概念の説明も含め、基本フローの流れを追いつつ説明する。
図６は、実施例２にかかる資源配分先決定処理プログラムの基本フローチャートである。この基本フローチャートのうち（容量体）順序付け処理ステップ（ステップＳ１）、（資源−配分先）仮配分処理ステップ（ステップＳ２）、（配分先）仮順序付け処理ステップ（ステップＳ３）のステップは、図１に示した基本フローチャートのステップと同様であるので、ここでの説明は省略する。
【００６２】
［４］（配分先−容量体）仮割り当て処理ステップ（ステップＳ４’）
（配分先−容量体）仮割り当て処理ステップは、実施例１に示したステップＳ４と同様、ステップＳ３の配分先の仮順序付けに従って、配分先を容量体に対してその容量の大きい順に一対一に仮割り当てをして行く。この仮割り当て処理により、実施例１の処理と同様、第１希望が１番大きい配分先には１番容量が大きい容量体が仮割り当てされ、第１希望が第ｍ番目に大きい配分先には第ｍ番目の容量の容量体が仮割り当てされるので、第１希望が満たされる資源の数が最大化されるように、配分先が適切に容量体に仮割り当てられた状態となっている。
【００６３】
しかし、実施例２ではさらに、次回以降の処理ループにおいて配分先の順序付けが入れ替わったとしても、容量体の容量の関係から、当該配分先に対して割り当てを許す容量体（これを容量体の「確保」と呼ぶ）と、当該配分先に対して割り当てを許さない容量体（これを容量体の「制限」と呼ぶ）を決めて条件付けしておく処理を行なう。
この容量体の「確保」と「制限」の条件付けを行なっておくによって、第１回目の処理ループにおいて第１希望の資源数が多く仮配分されたものの、第２回目の処理ループにおいて第２希望の資源数が少なく仮配分後の総資源数の順位が大きく下位に変動した場合でも、第１回目の処理ループで確保されている容量の大きな容量体への割り当てが手当てされ、第１回目の処理ループで制限されている容量の小さな容量体への割り当てがされないように手当てされることとなる。
【００６４】
この容量体の「確保」と「制限」は、以下のデメリットを防止するものと捉えることができる。
第１希望と第２希望の資源数の総数での順序に沿って容量体を割り当てて行けば、第１希望または第２希望がかなう資源数が多くなるが、第１希望の資源数が相対的に多くても第２希望の資源数が少ない場合、（配分先）仮順序付け処理ステップにおける第１希望と第２希望の資源数の総数での順序は相対的に下がり、（配分先−容量体）仮割り当て処理ステップにおいて第１希望の資源数よりも小さな容量の容量体が割り当たる場合も想定される。この場合、上位に入れ替わった配分先の第２希望がかなう資源数が多くなる反面、下位に入れ替わった配分先ではすでに第１回目の処理ループにおいて第１希望で配分された資源の配分が確定しており抽選に回る資源がないためアルゴリズム上の解が存在しないというデメリットが生じることとなる。
また、すでに第１回目の処理ループの（資源−配分先）配分確定処理ステップにおいて配分が確定した資源について、再度抽選に回すという処理手順を導入する場合は、第１希望で配分されている資源数の一部が抽選において落選する資源数が生じてしまい、却って資源配分の満足度が低下するというデメリットが生じる。
そこで、容量体の「確保」と「制限」という概念を導入して、配分先ごとに（配分先−容量体）仮割り当て処理ステップにおいて仮割り当てできる容量体の範囲を定めておけば、上記デメリットを防止することができる。
【００６５】
容量体の「確保」と「制限」は各々の配分先ごとに以下の２つの基準により設定する。
第１の基準は、仮配分処理ステップにおける仮配分後の資源の数よりも多い容量を持つ容量体に対しては割り当てできる容量体として「確保」し、確保された容量体より小さい容量体に対しては割り当てできない容量体として「制限」を設定するものである。
第２の基準は、配分先−容量体の仮割り当て処理ステップにおいて割り当てられた容量体またはその容量以上の容量を持つ容量体に対しては割り当ててできる容量体として「確保」し、確保された容量体より小さい容量体に対しては割り当てできない容量体として「制限」を設定するものである。
【００６６】
図７に示した例では、すべての配分先について、上記の第１の基準により、同図の表のように容量体の確保と制限が設定される。
配分先Ａについては、配分先Ａに仮配分された資源数よりも容量が大きい容量体は容量体Ａと容量体Ｂであり、それらの容量体への仮割り当ての「確保」が設定され、仮配分された資源数よりも容量が小さい容量体Ｃ、容量体Ｄ、容量体Ｅへの仮割り当ての「制限」が設定される。同様に、配分先Ｂについては、配分先Ｂに仮配分された資源数よりも容量が大きい容量体Ａ、容量体Ｂ、容量体Ｃの「確保」が設定され、他の容量体Ｄ、容量体Ｅに対しては「制限」が設定される。同様に配分先Ｃ、配分先Ｄ，配分先Ｅについても、容量体の「確保」と「制限」が設定される。
【００６７】
なお、この「確保」と「制限」の条件を設定しておき、後述するように、次回以降に繰り返される処理ループ中の配分先−容量体の仮割り当て処理ステップ（ステップＳ４’）において当該条件に合致するように配分先−容量体の仮割り当てを実行する。
上記が配分先ごとの容量体の「確保」と「制限」の概念である。
【００６８】
［５］（配分先）順序付け分離処理ステップ（ステップＳ５）
この（配分先）順序付け分離処理ステップ（ステップＳ５）は実施例１のものと同様であり、図７の例では、配分先順序付けの並びにおいて、配分先Ｄと配分先Ｅの間が分離されることとなる。
【００６９】
［６］（資源−配分先）配分確定処理ステップ（ステップＳ６）
（資源−配分先）配分確定処理ステップ（ステップＳ６）は実施例１のものと同様である。図７の例では、配分先Ｅについて仮配分された資源数が、仮割り当てにかかる容量体Ｅの容量を超過しているので、配分先Ｅについては配分当落を決める抽選が行なわれ、当該超過数分の資源について配分落選を決め、その他の資源には配分当選が確定される。
図８（ａ）において、容量体Ｅに仮配分された資源のうち縦ハッチングが施された部分は、配分落選となったものを表わしている。
【００７０】
［７］資源の配分先確定終了チェック（ステップＳ７）
資源の配分先確定終了チェックについても実施例１と同様で良く、ここでは配分先Ｅについて配分落選となったものが残っているので、資源の配分先確定終了チェックの結果（ステップＳ７：Ｎ）、実施例１と同様、配分落選に係る資源を再処理ループに還流する（ステップＳ８）。
【００７１】
［２再］（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理
図８（ｂ）は、図８（ａ）において縦ハッチングで示された資源について（資源−配分先）仮配分処理ステップ（ステップＳ２）の再処理が行なわれた結果を示す図である。この例は、配分先Ｅの配分落選した資源のうち、配分先Ｃと配分先Ｄを第２希望としていたものが比較的多く、配分先Ａと配分先Ｂを第２希望としていたものは比較的に少ない例となっている。
【００７２】
［３再］（配分先）仮順序付け処理ステップ（ステップＳ３）の再処理
次に、図９（ａ）の状態は（配分先）仮順序付け処理ステップ（ステップＳ３）の再処理により、図８（ｂ）の状態の第２回目の仮配分処理が反映された状態から、仮配分後の総資源数によりソートして配分先の仮順序付けを行なった状態を示す図である。この例では、仮配分後の総資源数において配分先Ｃ、配分先Ｄの総資源数が、配分先Ａ、配分先Ｂの総資源数よりも多くなり逆転している。
【００７３】
［４再］（配分先−容量体）仮割り当て処理ステップ（ステップＳ４）の再処理
実施例２では、（配分先−容量体）仮割り当て再処理ステップにおいて、各配分先ごとに設定された容量体の「確保」と「制限」の条件に合致するように、配分先を容量体に仮割り当て処理して行く。
図９（ａ）に示した（配分先）仮順序付け処理の結果において、第３番配分先となった配分先Ａに対しては、実施例１に示した基本フローではそのまま第３番容量体である容量体Ｃが仮割り当てされる。しかし、図７に示したように、配分先Ａに対する仮割り当てされる容量体として容量体Ａと容量体Ｂが「確保」され、容量体Ｃ、容量体Ｄ、容量体Ｅは「制限」されている。確かに配分先Ａを容量体Ｃに割り当てると、第１希望として配分先Ａに配分が確定された資源についても容量体Ｃの枠内から溢れており割り当てはできないことが分かる。同様に、第４番配分先となった配分先Ｂに対しては、図７に示したように、容量体Ａ、容量体Ｂ、容量体Ｃが「確保」され、容量体Ｄ、容量体Ｅは「制限」されている。
【００７４】
図９（ｂ）は、容量体の「確保」と「制限」を考慮した（配分先−容量体）仮割り当て処理の結果を示す図である。
配分先Ａについては、図７に示した容量体の「確保」と「制限」により、第２番容量体である容量体Ｂまでに割り当てなければならないところ、配分先Ｃとの関係では（配分先）仮順序付けの再処理では下位になるため、容量体Ｂが仮割り当てされることとなる。同様に、配分先Ｂについては、図７に示した容量体の「確保」と「制限」により、第３番容量体である容量体Ｃまでに割り当てなければならないところ、配分先Ｃとの関係では（配分先）仮順序付けの再処理では下位になり、配分先Ａは図７に示した容量体の「確保」と「制限」により順序を入れ替えることが制限されるため、配分先Ｂには容量体Ｃが仮割り当てされることとなる。配分先Ｄについては図７に示した容量体の「確保」と「制限」により、容量体Ｄまでに割り当てなければならないところ、配分先Ｃとの関係では（配分先）仮順序付けの再処理では下位になり、配分先Ａと配分先Ｂは図７に示した容量体の「確保」と「制限」により、順序を入れ替えることが制限されるため、配分先Ｄには容量体Ｄが仮割り当てされることとなる。
【００７５】
［５再］（配分先）順序付け分離処理ステップ（ステップＳ５）の再処理
実施例１と同様である。
【００７６】
［６再］（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理
実施例１と同様である。ここでは、図１０（ａ）の状態となる。
以上で（資源−配分先）仮配分処理ステップ（ステップＳ２）から（資源−配分先）配分確定処理ステップ（ステップＳ６）の再処理ループが完了する。
【００７７】
［７再］資源の配分先確定終了チェック（ステップＳ７）の再処理
実施例１と同様である。
【００７８】
ここでは、図１０（ａ）に見るように、まだ縦ハッチングを施した配分落選にかかる資源が存在するので、配分落選した資源を再処理ループに還流する（ステップＳ８）
図１０（ｂ）は最終的に、すべての資源について配分先が確定した場合を示しており（ステップＳ７：Ｙ）、すべての資源について配分先の確定と配分先の容量体への割り当ての確定が行なわれ（ステップＳ９）、処理が終了した状態となっている。
このように、繰り返し処理において、すべての資源について配分先となる配分先が確定した時点をもって、容量体の順序付けと配分先の順序付けに従って配分先の容量体への割り当てを確定する。
以上、資源の配分先の第１希望がかなう資源の数を最大化しつつ、配分落選した資源について上位の希望がかなう資源の数も最大化することができ、資源配分に関する満足度を向上することができる。
【実施例３】
【００７９】
実施例３として本発明の資源配分先決定処理プログラムを学生履修科目決定処理プログラムに適用した例を示す。
実施例３の学生履修科目決定処理プログラムは、実施例１、実施例２に示した資源配分先決定処理プログラムにおいて、資源を人的資源としての複数の学生とし、配分先を学生が履修を希望する複数の教員とし、容量体を定員が決まっている複数の教室とし、すべての学生について配分先となる教員の確定と教員の履修科目が開催される教室の割り当ての確定とを行なう学生履修科目決定処理プログラムとしたものである。
図１１は、実施例２に示した資源配分先決定処理プログラムを適用した、学生履修科目決定処理プログラムの基本フローを示すフローチャートである。
基本フローの各処理ステップは、実施例１、実施例２に示した各処理ステップと基本的な流れは同様で良く、ここでの詳しい説明は省略する。
【００８０】
以下、上記の基本フローに沿い、設計した学生履修科目決定処理プログラムのアルゴリズムの一例を示す。一例であり他に多様な設計が可能であることは言うまでもない。
【００８１】
［１．入力データ］
Ａ 学生数を nin で表わす。
Ｂ 教官数（教室数と同じ）を L で表わす。
Ｃ 教室容量のデータ（教官数分）を cap[j] で表わす。
大きい教室の方から、第 j 番目の教室容量を cap[j], j=0 〜 L-1 とする。
Ｄ 学生希望データ kib[i,k] で表わす（完全希望かどうかの判定結果を含む）。
第 i 番目の学生の、第 k 希望が、元々の何番目の教官番号 1 〜 L のデータ。
1 〜 L は教官番号とする。
【００８２】
［２．初期設定］
step-1) 教室容量を多い順に並べ替える。
大きい教室の方から、第 j 番目の教室容量を cap[j], j=0 〜 L-1 とする。
step-2) 確保（変数名：kakuho）の初期化
各教官 j の確保教室 kakuho[j], j=0 〜 L-1 とする。
確保教室とは、その教官が確保すべき教室番号（大きい方から何番目か）である。
step-3) 分離（変数名：bunri）の初期化
すべての教官は、自分の後ろの教官と最初は分離されていない。
ただし、最終教官は後ろが無いので、分離されている。
bunri[j]=0, j=0 〜 L-2 ;  bunri[L-1]=1
step-4) 配属者数（変数名：haisaki）の初期化
学生の配属先教官番号 haisaki[i], i=0 〜 nin を、最初にすべて 0 とする。
【００８３】
［３．第１希望の処理］
step-5) 既配属者数（変数名：haisuu）の計算
今までの希望で、既に配属教官番号が決まっている学生数を集計する。
各教官番号 j 毎に、haisuu[j], j=1 〜 L を求める。未配属は haisuu[0] に。
（注意）ここは、教官番号が 1 〜 L と１つずれている。
（第１希望では、すべて 0 人である。）
step-6) 第１希望(k=0)の場合の希望人数（変数名：ninzuunow）の集計
各教官 j 毎の第１希望人数 ninzuunow[j], j=0 〜 L-1 を集計する。
step-7) 総希望人数（変数名：n）の計算
既配属者数 haisuu と、未配属者での第 k 希望人数 ninzuunow の合計を計算。
n[j], j=0 〜 L-1 を求める。（これは、１つずれていない。）
（第１希望では、既配属者数が 0 であるから、ninzuunow と同じである。）
step-8) 仮教官番号（変数名：karino）の計算（第１希望で多い順にソート）
ninzuu[m], m=0 〜 L-1 は、n[j] をソートしたものである。
karino[j], j=0 〜 L-1 は、多い方から j 番目の希望人数の、元の教官番号
step-9) 仮上限（変数名：ulorg）の設定
各教官毎に、仮教官番号を用いて、教室上限を設定する。
（第１希望では、これがそのまま上限 ul となる。）
step-10) 確保の計算
多い方から m 番目の教官希望者数 ninzuu[m] を、j=m+1 以上の教室容量 cap[j] 
と比較し、希望者が多ければ kakuho[karino[m]]=j としてストップ。これより小さ
い部屋とのチェックは行わない。
これを、m=0 〜 L-1 まで繰り返す。
step-11) 分離の計算
多い方から m 番目の教官希望者数 ninzuu[m] を、j=m+1 の教室容量 cap[j] と比
較し、希望者が多ければ bunri[m]=1
これを、m=0 〜 L-1 まで繰り返す。
step-12) 上限（変数名：ul）の設定
仮上限 ulorg から、既に配属された人数を引いて、第 k 希望での上限 ul を計算
する。
（第１希望では、これは仮上限 ulorg と同じである。）
step-13) 抽選の実行
第１希望での第 j 教官への希望者数 ninzuunow[j] が、上限 ul[j] を超えていな
かったら、希望者全員が当選して配属教官が確定する。上限を超えている場合は、
乱数を用いて抽選を行い、上限までの人数が当選し、落選した人のみが次の第２希
望 step-14) へ進む。
【００８４】
［４．第２希望以降の処理］
step-14) 既配属者数（変数名：haisuu）の計算
今までの希望で、既に配属教官番号が決まっている学生数を集計する。
各教官番号 j 毎に、haisuu[j], j=1 〜 L を求める。未配属は haisuu[0] に。
（注意）ここは、教官番号が 1 〜 L と１つずれている。
step-15) 第１希望(k=0)の場合の希望人数 ninzuunow の集計
各教官 j 毎の第１希望人数 ninzuunow[j], j=0 〜 L-1 を集計する。
step-16) 総希望人数 n の計算
既配属者数 haisuu と、未配属者での第 k 希望人数 ninzuunow の合計を計算。
n[j], j=0 〜 L-1 を求める。（これは、１つずれていない。）
step-17) 分離内教室入れ替えの開始
step-17-1) m=0 とする。
step-17-2) 分離内の擬似バブルソート
jj=0
分離を見て最初に bunri[jj]=1 となるまでの ninnzuu[j], karino[j] をデータ
とする。
これを、最大値のみをトップに移動（「擬似バブルソート」と呼ぶ）する。
これに伴って、karino も入れ替える。
step-17-3) 分離内トップの確保の計算
多い方から m 番目の教官希望者数 ninzuu[m] を、j=m+1 以上の教室容量 cap[j]
と比較し、希望者が多ければ kakuho[karino[m]]=j としてストップ。これより小
さい部屋とのチェックは行わない。
step-17-4) 分離内トップの分離の計算
多い方から m 番目の教官希望者数 ninzuu[m] を、j=m+1 の教室容量 cap[j] と
比較し、希望者が多ければ bunri[m]=1
step-17-5) 分離内２番手以降の分離の計算
擬似バブルソートによって新たに発生した「分離」を求める。
step-17-6) 次の m か又は次のステップへ
m=L-1 なら、step-12b) へ。そうでなければ m=m+1 として、step-8b-2) 以降を
繰り返す。
step-18) 上限（変数名：ul）の設定
仮上限 ulorg (k=0; 第１希望で設定)から、既に配属された人数を引いて、第 k 希
望での上限 ul を計算する。
step-19) 抽選の実行
第 k 希望での第 j 教官への希望者数 ninzuunow[j] が、上限 ul[j] を超えてい
なかったら、希望者全員が当選して配属教官が確定する。上限を超えている場合は、
乱数を用いて抽選を行い、上限までの人数が当選し、落選した人のみが次の第 k+1
希望の step-14) へ進む。ここで、k=L-1 であれば、抽選は終了(step-20) する。
step-20) 終了
【００８５】
以上、本発明の資源配分先決定処理プログラムを学生履修科目決定処理プログラムに適用した場合のアルゴリズムの一例を示した。上記のアルゴリズムを採用した場合であっても、実際のコーディングには多様な記述が有り得ることは言うまでもない。
【実施例４】
【００８６】
実施例４として、資源配分先決定処理プログラムを物流管理プログラムに適用した例を示す。
実施例４の物流管理プログラムは、実施例１、実施例２に示した資源配分先決定処理プログラムにおいて、資源を物的資源としての貨物とし、配分先を貨物の配達を請け負う配送者とし、容量体を積載容量が決まっているトラックなどの配送手段とし、すべての貨物について配分先となる配送者の確定と配送手段の割り当ての確定とを行なう物流管理システムとしたものである。
【００８７】
図１２は、実施例２に示した資源配分先決定処理プログラムを適用した、物流管理プログラムの基本フローを示すフローチャートである。
基本フローの各処理ステップは、実施例１、実施例２に示した各処理ステップと基本的な流れは同様で良く、ここでの詳しい説明は省略する。
【実施例５】
【００８８】
実施例５として、資源配分先決定処理プログラムを商品管理プログラムに適用した例を示す。
実施例５の商品管理プログラムは、実施例１、実施例２に示した資源配分先決定処理プログラムにおいて、資源を物的資源としての商品とし、配分先を商品の供給を受ける業者とし、容量体を収納容量が決まっている倉庫とし、すべての商品について配分先となる業者の確定と倉庫の割り当ての確定とを行なう物流管理システムとしたものである。
【００８９】
図１３は、実施例２に示した資源配分先決定処理プログラムを適用した、商品管理プログラムの基本フローを示すフローチャートである。
基本フローの各処理ステップは、実施例１、実施例２に示した各処理ステップと基本的な流れは同様で良く、ここでの詳しい説明は省略する。
【実施例６】
【００９０】
実施例６として、資源配分先決定処理プログラムを災害時の避難民誘導支援プログラムに適用した例を示す。
実施例５の災害時の避難民誘導支援プログラムは、実施例１、実施例２に示した資源配分先決定処理プログラムにおいて、資源を人的資源としての避難民とし、配分先を避難民を受け入れる避難地区とし、容量体を収納容量が決まっている避難所とし、すべての避難民について配分先となる避難地区の確定と避難所の割り当ての確定とを行なう災害時の避難民誘導支援プログラムとしたものである。
図１４は、実施例２に示した資源配分先決定処理プログラムを適用した、災害時の避難民誘導支援プログラムの基本フローを示すフローチャートである。
基本フローの各処理ステップは、実施例１、実施例２に示した各処理ステップと基本的な流れは同様で良く、ここでの詳しい説明は省略する。
【実施例７】
【００９１】
実施例６として、実施例１から実施例５のいずれかに示した資源配分先決定処理プログラムを組み込んだ資源配分先決定システムの例を示す。
図１５は実施例７にかかる本発明の資源配分先決定システムの構成例を示す図である。
資源配分先決定システムは、入力部１０、記憶部２０、制御部３０、出力部４０を備えている。ハードウェアの構成としては、いわゆるパーソナルコンピュータで良い。
入力部１０は、例えばキーボード、記録メディア読み取り装置、有線若しくは無線の通信ネットワークに接続された携帯端末などであり、外部からデータを入力できるものであれば良い。
【００９２】
入力されるデータは、資源を特定する情報（例えば、学生番号、学生名、貨物名、商品名、ＪＡＮコードなどの情報）に加え、資源の配分先の希望情報（第１希望データ、第ｎ希望データ）などが入力される。また、配分先に関する情報（例えば、教員番号、教員名、配送者名、業者名などの情報）、容量体に関する情報（例えば、教室、配送手段、倉庫に関する情報）などが入力される。
記憶部２０には、上記実施例１から５のいずれかに説明した資源配分先決定処理プログラム（例えば、学生履修科目決定処理プログラム、物流管理プログラム、商品管理プログラムなど）が記憶されている。
制御部３０は、記憶部２０に記憶されている資源配分先決定処理プログラムなどを読み込む手段と、入力部１０から入力されたデータを読み込む手段と、入力されたデータをもとに読み込んだ資源配分先決定処理プログラムを実行処理する手段とを備えている。
出力部４０は、例えば、モニタ、プリンタ、記録メディア書き込み装置など、制御部３０の実行処理により得られた結果を受けて出力する部分である。
【産業上の利用可能性】
【００９３】
上記本発明の資源配分先決定処理プログラムは、資源、配分先、容量体をさまざまに設定すれば、学生履修科目決定処理プログラムや物流管理プログラムや商品管理プログラム以外にも、柔軟に多様なプログラムに応用できる。
また、上記本発明の資源配分先決定システムは、資源、配分先、容量体をさまざまに設定すれば、学生履修科目決定システムや物流管理システムや商品管理システム以外にも、柔軟に多様なシステムとして応用・構築することができる。
【図面の簡単な説明】
【００９４】
【図１】本発明の資源配分先決定処理プログラムの基本フローチャート
【図２】分離処理の概念を模式的に示す図
【図３】（資源−配分先）仮配分処理ステップの再処理を模式的に示す図
【図４】第２回目の仮配分処理が反映された状態から仮配分後の総資源数によりソートして配分先の仮順序付けを行なった状態を示す図
【図５】再処理ループが繰り返され、最終的に確定された様子（処理が終了した状態）を模式的に示す図
【図６】実施例２にかかる資源配分先決定処理プログラムの基本フローチャート
【図７】容量体の「確保」と「制限」が設定された様子を模式的に示す図
【図８】配分落選となったものを示す図および配分落選の資源について（資源−配分先）仮配分処理ステップの再処理が行なわれた結果を示す図
【図９】配分先の仮順序付けの再処理を示す図および容量体の「確保」と「制限」を考慮した（配分先−容量体）仮割り当て処理の結果を示す図
【図１０】（資源−配分先）配分確定処理ステップの再処理を示す図および最終的にすべての資源について配分先が確定した状態を示す図
【図１１】実施例３にかかる学生履修科目決定処理プログラムの基本フローを示すフローチャート
【図１２】実施例４にかかる物流管理プログラムの基本フローを示すフローチャート
【図１３】実施例５にかかる商品管理プログラムの基本フローを示すフローチャート
【図１４】実施例６にかかる本発明の資源配分先決定システムの構成例を示す図
【図１５】実施例７にかかる資源配分先決定システムの構成例
【符号の説明】
【００９５】
１０  データ入力部
２０  記憶部
３０  制御部
４０  出力部
【図１】
2007122532.tif 000003
【図２】
2007122532.tif 000004
【図３】
2007122532.tif 000005
【図４】
2007122532.tif 000006
【図５】
2007122532.tif 000007
【図６】
2007122532.tif 000008
【図７】
2007122532.tif 000009
【図８】
2007122532.tif 000010
【図９】
2007122532.tif 000011
【図１０】
2007122532.tif 000012
【図１１】
2007122532.tif 000013
【図１２】
2007122532.tif 000014
【図１３】
2007122532.tif 000015
【図１４】
2007122532.tif 000016
【図１５】
2007122532.tif 000017