TOP > 国内特許検索 > プログラム及びスケジューリング装置 > 明細書

明細書 :プログラム及びスケジューリング装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4467286号 (P4467286)
公開番号 特開2005-149148 (P2005-149148A)
登録日 平成22年3月5日(2010.3.5)
発行日 平成22年5月26日(2010.5.26)
公開日 平成17年6月9日(2005.6.9)
発明の名称または考案の名称 プログラム及びスケジューリング装置
国際特許分類 G06N   3/00        (2006.01)
G05D   1/02        (2006.01)
G05B  19/418       (2006.01)
FI G06N 3/00 550C
G05D 1/02 L
G05B 19/418 Z
請求項の数または発明の数 4
全頁数 28
出願番号 特願2003-385876 (P2003-385876)
出願日 平成15年11月14日(2003.11.14)
新規性喪失の例外の表示 特許法第30条第1項適用 特許法第30条第1項適用、第47回システム制御情報学会研究発表講演会講演論文集(平成15年5月14日)第415-416頁に発表
審査請求日 平成18年9月8日(2006.9.8)
特許権者または実用新案権者 【識別番号】593006630
【氏名又は名称】学校法人立命館
発明者または考案者 【氏名】亀井 且有
【氏名】糸賀 健
【氏名】谷口 典之
個別代理人の代理人 【識別番号】110000280、【氏名又は名称】特許業務法人サンクレスト国際特許事務所
審査官 【審査官】北川 純次
参考文献・文献 特開平09-282299(JP,A)
糸賀健,星野孝総,亀井且有,ナーススケジューリング問題解法のための共存型GAの探索効率の改善,ファジィシステムシンポジウム講演論文集,日本,2003年 9月 5日,Vol.19th,pp.485-488
調査した分野 G06N 3/00
G05B 19/418
G05D 1/02
JSTPlus(JDreamII)
JST7580(JDreamII)
特許請求の範囲 【請求項1】
所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置としてコンピュータを機能させるプログラムであって、
前記所定期間の各日において、前記各個体間に課せられた制約条件としての必要要員数を満足する初期世代の個体群を生成する初期個体群生成手段と、
前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、である現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、
前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、
前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、
前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、
前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、
前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、
を備え、
更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、
前記スケジューリング装置として前記コンピュータを機能させるプログラム。
【請求項2】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目が含まれる請求項1記載のプログラム。
【請求項3】
所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置であって、
前記所定期間の各日において、前記各個体間に課せられた制約条件を満足する初期世代の個体群を生成する初期個体群生成手段と、
前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、からなる現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、
前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、
前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、
前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、
前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、
前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、
を備え、
更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、
スケジューリング装置。
【請求項4】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目が含まれる請求項3記載のスケジューリング装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、プログラム及びスケジューリング装置に関し、特に探索効率を向上するための対策に係るものである。

【背景技術】
【0002】
従来より、所定の集団に属する各要員のスケジュールを最適化するスケジューリング問題が一般的に知られている。この種のスケジューリング問題として、例えば、特許文献1に開示されているように遺伝的アルゴリズム(Genetic Algorithm、以下単にGAと呼ぶ。)に代表される進化的計算手法を用いた解法が提案されている。
【0003】
遺伝的アルゴリズムとは、生物の進化を模倣した最適化手法の一種であり、その具体的な処理を説明すると、まず、ランダムに生成した個体の集合としての初期個体集団を生成し、この各個体を所定の評価尺度に従って評価する。そして、そのうちの2つの個体を選択し、この2個体の一部を互いに交換する交叉処理を行う。この交叉処理によって生成された新たな個体の一部を変更して新たな個体を生成する突然変異処理を行う。そして、この突然変異処理において生成された新たな個体の解としての優秀さを所定の評価尺度に従って評価し、個体集団中の最も低い個体の評価値と比較し、新たな個体の評価値の方が優れている場合には、個体集団中の最も劣った個体と入れ替える操作を行う。これらの処理を繰り返すことにより、与えられた問題の準最適解が得られるというものである。
【0004】
前記特許文献1に開示されたスケジューリング方法では、初期個体集団の中からより評価値の高い個体をランダムに選択し、この2個体に対して交叉を実行するようにしている。そして、交叉によって生成された個体に連続して何度も突然変異を施すことによって解の改善を図るようにしている。
【0005】
特許文献2には、複数の交叉法を用意するとともに、この中からより良い解を生成する交叉法を選択する処理を行うことが開示されている。そして、遺伝操作を施した個体群が前世代の個体群と同じ場合には、突然変異の操作を行う割合を高くして、局所解から脱出するようにすることが示されている。
【0006】
非特許文献1には、多重制約性と多目的性に対して提案される共存型GAが開示されている。この共存型GAは、複数の個体からなる集団全体に対して制約条件を課し、評価項目を適用して集団全体を改善することを目的とするものであり、この共存型GAにおいては、各個体は他の個体と多重の制約条件によって拘束されており、個体は解候補の一部を担い個体集団としての解候補を表すこととしている。
【0007】
共存型GAを例えばナーススケジューリング問題(Nurse Scheduling Problem、以下単にNSPという。)に適用した場合について説明する。勤務スケジュール表は看護師個人の例えば1ヶ月のスケジュールを集合して全体のスケジュールが構成される。この個人の1ヶ月のスケジュールが一個体となり、全体の1ヶ月のスケジュールが一集団となる。このナーススケジューリング問題では、看護師数をnとし、また日数をmとするとn×m行列を決定する問題となる。そして、準最適解を導出すべく以下に示す処理を順次実行する。
H1:看護師の属する集団に課せられたある制約条件を満たした初期個体集団をランダムに生成する。たとえば、1日の各勤務における必要人員数等がこの制約条件に該当する。
H2:各個体の評価を与えられた個体の評価尺度にしたがって計算し、その結果を評価値とする。
H3:個体の評価値に応じて選ばれやすくなるようにバイアスをかけてランダムに2個体を選択する。この選ばれた2個体を親ペアと呼ぶ。
H4:親ペアの一部を互いに交換して新たな個体を生成する。生成された2個体を子ペアと呼び、親ペアの一部を互いに交換する操作を交叉と呼ぶ。このとき、前記制約条件を満たした初期個体集団を生成することにより、交叉処理を行っても常にこの制約条件が満たされるようになっている。
H5:生成された子ペアを親ペアと置き換えて新たな集団を生成する。この新たに生成された集団を次世代解候補と呼ぶ。
H6:生成された次世代解候補の評価を予め設定された集団の評価尺度にしたがって計算し、その結果を評価値とする。
H7:H4~H6を繰り返すことで複数の次世代解候補を生成する。
H8:複数の次世代候補の中から集団の評価により1つの次世代解を選択し、現世代解を次世代解に置き換える。
H9:前記処理H2~H8を1サイクルとして繰り返し処理を行う。これにより、全体のスケジュールが準最適解に達することとなる。

【特許文献1】特開2000-132604号公報
【特許文献2】特開平9-69050号公報
【非特許文献1】北野宏明、「遺伝的アルゴリズム(2)」、日本、産業図書、1995年、p.89-125
【発明の開示】
【発明が解決しようとする課題】
【0008】
前記特許文献1に示されたものでは、評価値に基づいて2個の個体をランダムに選択して交叉を行うために、制約を充足しない実行不可能な解(致死遺伝子)を発生させる可能性がある。このため、この致死遺伝子の発生を抑制するために交叉箇所が限定されてしまうという問題を生じ、制約を充足するのが困難となる。さらに致死遺伝子の発生を抑制するための突然変異操作を行うことが余儀なくされるという問題がある。
【0009】
また、前記特許文献2に記載されたものでは、複数の交叉法を用意するとともに、この中からより良い解を生成する交叉法を選択する処理を行うことにより評価指標に依存することなく良い結果を取得できるようにしている。しかしながら、このものにおいても致死遺伝子が発生する可能性があるために、致死遺伝子の生成を抑制するためには前記同様の問題が発生する。
【0010】
一方、前記非特許文献1に記載されたものでは、1つのスケジュール全体を1つの集団に、1人の看護師に対応する勤務スケジュールを1つの個体に対応させてコード化するとともに、制約条件を満たす初期集団を生成することにより、交叉を繰り返しても致死遺伝子が生じる危険がないという利点がある。しかしながら、このものでは、図9に示すように、親ペアを選択するのは1つのみであるために、多様な子が生成されにくいものとなっている。このため、解空間に対して探索空間が狭くなり、初期収束や探索効率が低下するという問題がある。
【0011】
そこで、本発明は、かかる点に鑑みてなされたものであり、その目的とするところは、致死遺伝子の生成を抑止しつつ、探索効率を向上することにある。
【課題を解決するための手段】
【0012】
前記の目的を達成するため、本発明は、所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置としてコンピュータを機能させるプログラムであって、前記所定期間の各日において、前記各個体間に課せられた制約条件としての必要要員数を満足する初期世代の個体群を生成する初期個体群生成手段と、前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、である現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、を備え、更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、前記スケジューリング装置として前記コンピュータを機能させるプログラムである。

【0013】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目を含むことができる。

【0014】
また、本発明は、所定の集団に属する各要員の所定期間における日毎のスケジュールを構成するデータを個体とし、遺伝的アルゴリズムを用いて演算することにより全要員についての個体の集合である個体群の最良解を、全要員の所定期間におけるスケジュールとして作成するスケジューリング装置であって、 前記所定期間の各日において、前記各個体間に課せられた制約条件を満足する初期世代の個体群を生成する初期個体群生成手段と、前記初期世代の個体群又は前記初期世代の個体群を元にして生成された所定の世代の個体群、からなる現行世代の個体群から2つの個体を親ペアとして選択し、その際に、親ペアの一方をランダム選択するとともに、親ペアの他方を現行世代の個体群を構成する各個体の評価値に基づく評価の悪い個体ほど選択され易い確率で選択する処理を行う親ペア選択手段と、前記親ペア選択手段によって選択された親ペアを構成する各個体についてそれぞれ同一の日を交差箇所として設定し、設定された交差箇所について、親ペアを構成する各個体を互いに交叉させて子ペアを生成する交叉手段と、前記交叉手段によって交叉された結果生まれた子ペアを親ペアと置き換えることで、制約条件を満足する現行世代の個体群から、制約条件が満足された状態が維持された次世代候補の個体群を生成し、その次世代候補の個体群をメモリに格納する次世代候補生成手段と、前記親ペアの選択、交叉及び次世代候補の生成を複数回実行させて、複数の次世代候補の個体群を生成させる複数次世代候補生成処理の制御手段と、前記制御手段によって次世代候補の生成が複数回行われた結果得られてメモリに格納されている複数の次世代候補の個体群それぞれの評価値に基づいて、複数の次世代候補に対するパレート最適選択を行い、パレート最適解となった次世代候補の中からランダムに1つの次世代候補の個体群を選択して、選択された次世代候補の個体群を次世代の個体群とする次世代選択処理を行う次世代選択手段と、前記次世代選択手段によって選択された次世代の個体群を現行世代の個体群に置換して、複数次世代候補生成処理及び次世代選択処理を所定回数繰り返させる繰り返し手段と、を備え、更に、次世代候補の中から最良解となる個体群を選択する手段を備え、この手段による最良解の選択は、次世代候補の個体群の評価値が、最適解に対して距離最小のものを選択することにより行われる、スケジューリング装置である。
【0015】
次世代候補の個体群の評価値には、一日に関する評価項目から得られる評価値が含まれ、前記一日に関する評価項目には、特定の要員の組み合わせ禁止に関する評価項目を含むことができる。

【発明の効果】
【0016】
以上説明したように、本発明によれば、各個体間に課せられた最低限満たさなければならない制約条件の下で初期世代の個体群を生成し、この初期世代の個体群を元にして親ペアの交叉を行うために、致死遺伝子が生成されるのを抑止することができる。そして、このとき親ペアの選択を複数回実行することから、複数の親ペアが選択されることとなり、この複数の親ペアに対して各親ペアを構成する各個体の一部同士を互いに交叉して複数の子ペアを生成している。この結果、複数の親ペアから多様な子ペアが生成されることが可能となり、解の探索空間の拡大を図ることができて探索効率を向上できるとともに局所解に陥る確率を低減することができる。
【0017】
また、本発明によれば、親ペアを構成する各個体の交叉箇所が少ない場合であっても、交叉処理を行うに当たり複数の親ペアを選択するために、各親ペアを選択する毎に交叉箇所を逐次選択することが可能となる。この結果、各親ペア毎の交叉箇所の選択についての組み合わせを増大させることができるので、解の探索空間の拡大により最適解に近い最良解を取得しやすくできる。
【発明を実施するための最良の形態】
【0018】
以下、本発明の実施形態を図面に基づいて詳細に説明する。
【0019】
図1は、本発明の実施形態に係るスケジューリング方法を実施するためのスケジューリング装置の構成を示すブロック図である。本スケジュール装置は、病院の所定の科に属するスケジューリング対象となる全看護師のスケジュールを調整するための装置であり、各看護師の1ヶ月のスケジュールを構成する個体としての各データを共存型遺伝的アルゴリズム(以下、共存型GAという。)を用いて演算し、この科全体の看護師のスケジューリングを行うためのコンピュータを備えている。このコンピュータは、入力部、CPU、ROM、RAM、外部記憶装置、表示装置、印字装置等から構成されている。そして、このコンピュータは、ハードディスク等の外部記憶装置に予め記憶されているスケジューリングプログラムをCPU等で実行することにより、スケジューリング装置として機能する。
【0020】
入力部は、マウス、キーボード等から構成され、後述する各評価項目に必要なデータをユーザーが入力するために使用される。
【0021】
コンピュータは、データ受付部1と、初期個体集団生成部2と、個体評価値計算部3と、親ペア選択部4と、交叉処理部5と、次世代解候補生成部6と、次世代解候補評価値計算部7と、次世代解選択部8と、最良解更新部9と、出力部10と、メモリ部11と、制御部12とを備えている。
【0022】
データ受付部1は、入力部によって入力されたデータを受け付け、このデータを初期個体集団生成部2等へ出力する。ここで出力されるデータには、スケジューリング問題に関するパラメータと共存型GAに関するパラメータとがある。
【0023】
スケジューリング問題に関するパラメータとしては、スケジューリング対象となる看護師、スケジューリング対象となる日にち、土日祝の日にち、勤務形態(日勤、準夜勤、深夜勤)ごとに必要な必要勤務者数、各勤務形態ごとに必要な最低看護レベル、勤務パターンの評価値、研修、会議、希望休暇等の変更不可能な固定箇所等が挙げられる。
【0024】
また、共存型GAに関するパラメータとしては、全体処理の繰り返し回数即ち世代数、次世代解候補を生成する数、評価計算に用いられる重み係数等が挙げられる。本実施形態では、例えば全体処理の繰り返し回数(世代数)を5000回とし、また次世代解候補を生成する数(交叉数)として10000としている。
【0025】
本実施形態では、各個体は、スケジューリング対象期間となる所定期間(本実施形態では1ヶ月)におけるある看護師の勤務スケジュールを構成するデータからなる。そして、この個体の集合である、スケジューリング対象となる全ての看護師の勤務スケジュールが個体群となる。
【0026】
初期個体集団生成部2は、初期個体群生成手段を構成するものであり、スケジューリング対象となる全ての看護師の前記所定期間の勤務スケジュールを初期世代の個体群としてランダムに構成するように構成されている。この初期世代の個体群からなる初期集団は、各看護師の勤務スケジュール間に課せられた最低限満たすべき制約条件を満足するように構成される。例えば、1日の必要勤務者数、より具体的には日勤、順夜勤、深夜勤の各勤務形態において要求される要員数を満足するような初期集団が形成される。また、研修、会議、希望休暇等の変更不可能な固定箇所についてはそれを満足するような初期集団として形成される。
【0027】
個体評価値計算部3は、個体評価手段を構成するものであり、予め設定された所定の評価関数に基づいて演算された個体評価値に従って各個体の評価計算を実行するように構成されている。この個体評価値の詳細は後述する。
【0028】
親ペア選択部4は、親ペア選択手段を構成するものであり、現行世代の個体群の中から親ペアとしての2つの個体を選択してメモリ11に格納する処理を実行するように構成されている。この親ペアの選択は、親ペアの一方をランダム選択するとともに、この親ペアの他方を適応度の低いもの即ち個体評価値計算部3による評価の悪いものほど選択され易い確率で選択する方式で実行される。言い換えると、親ペアの一方は個体評価値計算部3による評価の影響を受けることなくランダムに選択される一方、親ペアの他方は前記評価の悪いものを積極的に選択するようになっている。
【0029】
交叉処理部5は、交叉手段を構成するものであり、選択された親ペアに対してこの親ペアを構成する各個体の一部を互いに交叉する交叉処理を実行し、子ペアを生成してメモリ11に格納するように構成されている。この交叉処理では、親ペアを構成する各個体についてそれぞれ同じ交叉箇所をランダムに設定し、その所定の交叉箇所内のデータを個体間でそれぞれ入れ替える処理を実行する。本実施形態では2点交叉を行うように構成されている。このとき、研修等の変更不可能な固定箇所については交叉しないようになっている。尚、これに代え、例えば1点交叉としてもよくあるいは3点以上の多点交叉としてもよい。
【0030】
共存型GAでは、各個体についてそれぞれ同一の交叉箇所を設定することにより、交叉実行後も各看護師の勤務スケジュール間に課せられた最低限満たすべき制約条件が常に満足されるようになっている。例えば、各日にちの必要勤務者数が満足されるように初期集団が設定されており、この初期集団を元にしてある2人の看護師の所定の日の勤務パターンを入れ替えたとしてもその日にちにおける必要勤務者数が満足されることとなる。
【0031】
次世代解候補生成部6は、次世代候補生成手段を構成するものであり、交叉処理部5によって生成された子ペアを親ペアと置き換えることにより、新たな集団としての次世代の個体群である次世代解候補の個体群を生成してメモリ11に格納する制御を実行するように構成されている。親ペアの選択は後述するように複数(多数)回実行されるようになっている。この結果、次世代解候補は、複数(多数)生成される。
【0032】
次世代解候補評価値計算部7は、予め設定された評価計算に基づいて次世代解候補についての評価値の計算を実行するように構成されている。この評価計算についての詳細は後述する。
【0033】
次世代解選択部8は、次世代解選択手段を構成するものであり、生成された複数(多数)の次世代解候補の中からパレート最適選択によって次世代解を1つ選択する制御を実行するように構成されている。この次世代解候補の選択は、後述するように繰り返し行われるようになっており、次世代解候補の選択が行われることで世代が順次交代していくこととなる。
【0034】
最良解更新部9は、選択された次世代解がそれ以前に得られた次世代解よりも高い評価値であるときにこの次世代解を最良解として更新してメモリ11に格納する制御を実行するように構成されている。
【0035】
出力部10は、最良解更新部9に格納された最良解を計算終了時に最終結果として表示装置等へ出力するように構成されている。
【0036】
メモリ部11は、処理中の結果等を一時的に記憶するように構成されている。
【0037】
制御部12は、前記各部1,‥,11による制御を順次実行させるように構成されている。また、この制御部12は、交叉及び次世代候補の生成を複数回実行する制御手段を構成している。例えば図2に示すように、ある所定の世代において親ペアは複数選択されることとなり、この各親ペアからそれぞれ1つずつ子ペアが生成される。
【0038】
この制御部12には、2つのカウンタが設けられている。一方は全体処理の繰り返し回数を計数するカウンタであり、もう一方は次世代解候補を生成する回数を計数するカウンタである。
【0039】
続いて評価項目及び評価計算の詳細について説明する。ここでは、実際に大阪市立枚方市民病院の脳外科の看護師の勤務スケジューリングを行ったときのものについて説明する。スケジューリング対象となる看護師23名であり、スケジューリング対象期間は30日(例えば11月)である。勤務スケジューリング上で分類されるこの科の勤務形態としては、日勤、準夜勤、深夜勤及び休日がある。
【0040】
まず、この科の勤務スケジュール作成担当者である師長に評価項目について聞き取り調査を行い、勤務スケジュールを作成するに当たっての評価すべき評価項目の整理を行った。評価項目は、個人に関する評価項目と1日に関する評価項目とに分類できる。尚、師長はスケジューリング対象には属していない。
【0041】
個人に関する評価項目として、
(1)勤務パターンの負荷度合いの軽減
(2)勤務日数の公平さ
(3)その他の個人に関する評価項目
が挙げられる。
【0042】
また、1日に関する評価項目として、
(4)必要勤務者数の確保
(5)看護の質の維持
(6)その他の1日に関する評価項目
が挙げられる。
【0043】
以下、これらの評価項目の定式化を行う。
【0044】
まず、スケジューリング対象となる看護師の集合をM={m1,m2,‥,mi,‥,m23}とし、またスケジューリング対象期間の日にちの集合をD={1,2,‥,j,‥,30}とする。また、日にちjにおける看護師miが勤務している時刻をTj(mi)とする。
【0045】
日にちjにおける日勤の看護師の集合をMjdayとし、また日にちjにおける準夜勤の看護師の集合をMjsemとし、また日にちjにおける深夜勤の看護師の集合をMjmidとし、また日にちjにおける休日の看護師の集合をMjhomとすると、これらMjday、Mjsem、Mjmid、Mjhomはそれぞれ以下の式(1)~式(4)の通り、
【数1】
JP0004467286B2_000002t.gif
と定義することができる。
【0046】
また、看護師miにおける日勤の日にちの集合をDidayとし、また看護師miにおける準夜勤の日にちの集合をDisemとし、また看護師miにおける深夜勤の日にちの集合をDimidとし、また看護師miにおける休日の日にちの集合をDihomとすると、これらDiday、Disem、Dimid、Dihomはそれぞれ以下の式(5)~式(8)の通り、
【数2】
JP0004467286B2_000003t.gif
と定義することができる。
【0047】
(1)勤務パターンの負荷度合いの軽減
隔たった日にち間においては勤務パターンの負荷度合いについての依存関係が低くなるために、勤務パターンの評価は、連続3日の勤務パターンで評価することが可能である。そこで、師長に依頼して勤務パターン及びその評価値dijを以下の表1に示すように4種類に分類してもらった。各勤務パターンにおける勤務例を表1の中に示している。スケジューリングにおいては勤務負荷の少ない最優先パターンをできるだけ増やすことを目的にする。一方、禁止パターンについては評価の重みを大きくすることで制約条件となるようにした。
【0048】
【表1】
JP0004467286B2_000004t.gif

【0049】
看護師miの1ヶ月間の勤務パターンに関する負荷度合いを表す評価関数F1iは、以下の式(9)の通り、
【数3】
JP0004467286B2_000005t.gif
と定義することができる。ここで、dijは看護師miの日にちjにおける勤務パターンに対応する評価値を表している。
【0050】
(2)勤務日数の公平さ
勤務日数に関する評価項目として、例えば「休日は土日祝の数と同じにする」、「夜勤は8回以下とする」及び「準夜勤・深夜勤の上限はそれぞれ4回とする」という項目が挙げられる。これら各項目に違反する場合には、各項目に違反する毎にペナルティを課す。よって、看護師miにおける休日に関する評価関数F2i及び夜勤に関する評価関数F3iは、以下の式(10)、(11)の通り、
【数4】
JP0004467286B2_000006t.gif
と定義することができる。ここで、Nhomは1ヶ月間の土日祝の日数、Nsemは準夜勤回数の上限値、Nmidは深夜勤回数の上限値を表している。つまり、式(10)から明らかなように、1ヶ月間の土日祝の日数に対して休日に過不足が発生したときには、その日数に応じたペナルティを課す。また、式(11)から明らかなように、準夜勤の回数が上限値を超えたときや深夜勤の回数が上限値を超えたときには、その超えた日数に応じたペナルティを課す。
【0051】
(3)その他の個人に関する評価項目
この評価項目として、例えば「6日間以上の連続勤務を禁止する」、「連続する6日間のうちで4回以上の夜勤を禁止する」及び「研修の翌日の深夜勤を禁止する」という項目が挙げられる。これらの項目に違反する場合には、各項目に違反する毎にペナルティを課す。言い換えると、これらの項目に対する違反する毎に1を加算していくようになっており、看護師miにおけるこの評価項目の評価関数F4iは、加算された点数の合計として表される。
【0052】
(4)必要勤務者数の確保
この病棟における1日の必要勤務者数は、日勤で10~11人であり、準夜勤で3人であり、深夜勤で3人である。この必要勤務者数は最低限満たさなければならない制約条件となっている。本実施例では、共存型GAによる演算を行うために、初期集団を形成するときにこの制約条件を満足するように各日にち毎の勤務者数を割り付けるために、交叉を繰り返してもこの制約条件が満たされるため、致死遺伝子を発生させる危険性はない。
【0053】
(5)看護の質の維持
業務に支障がないように日勤、準夜勤、深夜勤のそれぞれについて一定レベル以上の看護の質を維持する必要があり、また日によって看護の質に偏りが生じるのをなるべく抑制する必要がある。そこで、各看護師のレベルを1~10の10段階に分類して看護レベルL(mi)を数値化することとした。看護師miの看護レベルL(mi)を表2に示している。ベテラン看護師の看護レベルL(mi)は7~10と、また中堅看護師の看護レベルL(mi)は4~6と、また新人看護師の看護レベルL(mi)は1~3となっている。
【0054】
【表2】
JP0004467286B2_000007t.gif

【0055】
本評価項目においては、各勤務形態毎の看護レベルL(mi)の総和が予め設定された最低看護レベル以上となることを目的とした。日にちjにおける日勤の看護レベルに関する評価関数G1j、日にちjにおける準夜勤の看護レベルに関する評価関数G2j、日にちjにおける深夜勤の看護レベルに関する評価関数G3jは、それぞれ以下の式(12)~式(14)の通り、
【数5】
JP0004467286B2_000008t.gif
と定義することができる。ここで、Ljdayは日にちjにおける日勤の最低看護レベルを、またLjsemは日にちjにおける準夜勤の最低看護レベルを、またLjmidは日にちjにおける深夜勤の最低看護レベルをそれぞれ表しており、これらは予め設定された値である。師長と話し合った結果、日勤の最低看護レベルLjdayは、平日は54、土曜日は33、日祝日は28と設定し、また準夜勤及び深夜勤の最低看護レベルはそれぞれ16と設定した。つまり、本評価項目では、式(12)~式(14)から明らかなように、看護レベルL(mi)の総和が各勤務ごとに予め設定された最低看護レベルに満たないときには、その不足する点数に応じた評価値が算出されることとなる。
【0056】
(6)その他の1日に関する評価項目
本評価項目としては、「夜勤に相性の悪い看護師同士を組み合わせるのは禁止する」、「夜勤に新人同士を組み合わせるのは禁止する」及び「夜勤には少なくとも1人のベテランを割り振る」が挙げられる。これらの項目に違反する場合には、各項目に違反する毎にペナルティを課す。言い換えると、これらの項目に対する違反する毎に1を加算していくようになっており、日にちjにおける本評価項目に関する評価関数G4jは、加算された点数の合計として表される。
【0057】
以上、各個体の評価値(個体評価値)Fiは、個人に関する評価項目に対する前記評価関数F1i~F4iを用い、以下の式(15)の通り算出する。また、個体群全体としての評価は、互いに干渉し合う勤務パターンの負荷度合いに関する評価値H1と、それ以外の個人に関する評価項目から得られる評価値H2と、一日に関する評価項目から得られる評価値H3とをそれぞれ評価軸とする3軸パレート評価を行う。これにより、多様性を持った解探索が行えるようになっている。これら評価値H1,H2,H3は以下の式(16)~式(18)の通り算出する。
【0058】
【数6】
JP0004467286B2_000009t.gif

【0059】
そして、以下の式(19)及び式(20)に示す通り、
【数7】
JP0004467286B2_000010t.gif
前記評価値H1,H2,H3のユークリッド距離を計算して得られた最終評価値Hにより最良解か否かを判定した。すなわち、最終評価値Hがなるべく低くゼロに近い値であるときの解が最良解となる。この最終評価値Hは、最適解に対する得られた最良解の距離(distance)を表している。
【0060】
次に、本実施形態に係るスケジューリング装置によるスケジューリング処理について図3を参照しながら説明する。まず、ステップS1においてデータ受付部1は、各評価項目に必要なデータを受け付け、これらデータを初期集団生成部2等へ出力する。ここでは、スケジューリング対象となる看護師、スケジューリング対象となる日にち等のスケジューリング問題に関するパラメータと、全体処理の繰り返し回数(世代数)G、次世代解候補を生成する数(交叉数)N等の共存型GAに関するパラメータとが入力される。
【0061】
そして、ステップS2において、初期個体集団生成部2が、スケジュール対象となる各看護師毎に各日にち毎の勤務形態が割り付けられた各個体の集合としての初期集団をランダムに生成する。このとき、1日の必要勤務者数等の最低限満たすべき制約条件を満足するように初期集団をランダムに生成する。つまり、このステップS2は初期個体群生成ステップを構成している。尚、このとき全体処理の繰り返し回数Gを計数するカウンタのカウントhをリセットする。
【0062】
次に、ステップS3では個体評価値計算部3が、外部記憶装置に記憶された評価関数F1i,‥,F4iを用いて各個体に対して個体評価値Fiを演算してメモリ9に格納する。この各個体は、初回の評価では初期集団が現行世代を形成するため、この初期集団を形成する個体に対して行われ、繰り返し計算後においては交叉処理が行われた後の現行世代を形成する個体に対して行われる。また、このステップS3を実行する度に全体処理の繰り返し回数Gを計数するカウンタのカウントhに1を加算して更新し、次世代解候補を生成する回数を計数するカウンタのカウントqをリセットする。
【0063】
次に、ステップS4では、親ペア選択部4が、現行世代を形成する個体群の中から1つの親ペアとして2つの個体を選択し、メモリ11に格納する。つまり、このステップS4は親ペア選択ステップを構成している。この親ペアの選択は、親ペアの一方をランダム選択するとともに、この親ペアの他方を適応度の低い(評価の悪い)もの即ち個体評価値Fiの大きいものほど選択され易い確率で選択する方式で実行される。つまり、個体評価値Fiはペナルティを加算して得られるものであるので、この値が大きいものほど評価が悪いこととなる。そしてこのとき、次世代解候補を生成する回数を計数するカウンタのカウントqに1を加算して更新する。
【0064】
次に、ステップS5では、交叉処理部5が、選択された親ペアに対し、各個体の交叉箇所をランダムに設定して交叉処理を実行し、子ペアを生成してメモリ11に格納する。つまり、このステップS5は交叉ステップを構成している。このとき、親ペアを構成する各個体について同じ箇所を交叉箇所として設定している。
【0065】
次に、ステップS6では、次世代解候補生成部6が、メモリ11に格納された子ペアを、メモリ11に格納されている親ペアと置き換えてできる新たな集団としての次世代の個体群である次世代解候補の個体群を1つ生成し、メモリ11に格納する。つまり、ステップS6は次世代候補生成ステップを構成している。
【0066】
次に、ステップS7では、次世代解候補評価値計算部7が、前述した評価計算に基づいて次世代解候補についての評価値H1,H2,H3を計算する。
【0067】
次に、ステップS8では、次世代解候補を生成する回数を計数するカウンタのカウントqがデータ受付部1に入力された設定数Nを超えたか否かを判断する。そして、カウントqが回数N以下であるときには判定がNOとなってステップS4へ戻る。したがって、次世代解候補がN個生成されるまで、ステップS4~ステップS8が繰り返し実行される。このときメモリ11では、親ペアが選択されるたびにこの親ペアがメモリ11に格納されている親ペアに上書きされ、また子ペアが生成されるたびにこの子ペアがメモリ11に格納されている子ペアに上書きされている。したがって、次世代解候補の生成回数Nを10000と設定してもメモリ11に記憶されるデータ量が膨大になることはない。
【0068】
そして、カウントqが回数Nを超えるとステップS8における判定がYESとなってステップS9に移る。ステップS9では、次世代解選択部8が、多数の次世代解候補の中からパレート最適選択によってパレート最適解の中から1つ選択して次世代解とし、この次世代解を現行世代解と置換する。つまり、ステップS9は次世代解選択ステップを構成している。
【0069】
次に、ステップS10では、最良解更新部9が、選択された次世代解の最終評価値Hがそれ以前に得られた次世代解候補よりも良い値(ユークリッド距離が小さい値)であるときにこの次世代解候補を最良解として更新してメモリ9に格納する。
【0070】
次に、ステップS11では、全体処理の繰り返し回数Gを計数するカウンタのカウントhがデータ受付部1に入力された繰り返し回数Gを超えたか否かを判断する。そして、カウントhが繰り返し回数G以下であるときには判定がNOとなってステップS3へ戻る。したがって、世代交代が繰り返し回数Gに達するまでステップS3~ステップS11が繰り返し実行される。そして、カウントhが繰り返し回数Gを超えるとステップS11における判定がYESとなってステップS12に移る。
【0071】
ステップS12では、出力部10が、最良解更新部9に格納された最良解を最終結果として出力し、全処理が終了する。
【0072】
実際に得られた最良解の一例を図4に示す。この図は、看護師23人の30日間の勤務スケジュールを示している。この図から分かるように、各制約条件を維持しつつ、各看護レベルをも維持できている。また、表3に示すように勤務パターンの負荷度合いと看護の質の維持に関する評価が特に改善されていた。
【0073】
【表3】
JP0004467286B2_000011t.gif

【0074】
各世代に対する最良解の推移を図5に示している。図5では、本実施形態における演算結果を実線で示すとともに、師長が実際に作成された勤務スケジュール表から得られた最終評価値Hを比較例として破線で示している。師長はこの勤務スケジュール表を2,3日かけて作成している。本実施形態ではおよそ最良解が収束する2000世代辺りまで計算するのに約20分で得ることができ、親ペアを多数回に亘って繰り返し選択する演算を行うにもかかわらず実用可能な時間で処理を終えることができる。尚、図5は、c1=0.2、c2=0.2、c3=0.2、c4=0.4、d1=0.1、d2=0.1、d3=0.1、d4=0.7、G=5000、N=10000としたときの一例である。
【0075】
以上説明したように、本実施形態によれば、各個体間に課せられた最低限満たさなければならない制約条件の下で初期世代の個体群を生成し、この初期世代の個体群を元にして親ペアの交叉を行うために、致死遺伝子が生成されるのを抑制することができる。そして、このとき親ペアの選択を複数回実行することから、複数の親ペアが選択されることとなり、この複数の親ペアに対して各親ペアを構成する各個体の一部同士を互いに交叉して複数の子ペアを生成している。この結果、複数の親ペアから多様な子ペアが生成されることが可能となり、解の探索空間の拡大を図ることができて探索効率を向上できるとともに局所解に陥る確率を低減することができる。
【0076】
また、本実施形態では、親ペアを構成する各個体の交叉箇所が少ない場合であっても、交叉処理を行うに当たり複数の親ペアを選択するために、各親ペアを選択する毎に交叉箇所を逐次選択することが可能となる。この結果、各親ペア毎の交叉箇所の選択についての組み合わせを増大させることができるので、解の探索空間の拡大により最適解に近い最良解を取得しやすくできる。
【0077】
また、本実施形態では、各親ペアの一方をランダム選択するとともに、各親ペアの他方を個体評価値Fiの大きいものほど選択され易い確率で選択する処理を行うようにしているので、次世代候補をランダムに生成しつつ、適応度を高くすることができる。
【0078】
また、本実施形態では、次世代解候補を生成するたびに親ペア及び子ペアをメモリ11に格納されている親ペア及び子ペアに対して上書きしていくように処理しているので、メモリ11に格納されるデータ量が膨大になるのを防止することができる。
【0079】
尚、本発明は、前記実施形態について、以下のような構成としてもよい。
【0080】
前記実施形態では、ユークリッド距離に基づいたパレート最適選択によって次世代解候補の中からランダムに次世代解を選択する構成としているが、これに代えハミング距離に基づいて次世代解を選択する構成としてもよい。
【0081】
また、前記実施形態では、ステップS4~ステップS8を繰り返し実行する構成としたが、これに代え、メモリ9に余裕があるとき等には、親ペアの選択~次世代の生成までを並行して実行する構成としてもよい。
【0082】
また、前記実施形態では、本発明を看護師のスケジュールを調整するための装置に適用したものについて説明したが、本発明はこれに限られるものではなく、例えば工場等における従業員シフトスケジュール、ゼミにおける発表スケジュール、アルバイトやパートタイマーのシフトスケジュール等を調整するための装置に適用することもできる。
【0083】
また、前記実施形態では、看護師のスケジュールを調整するスケジューリング装置について説明したが、これに限られるものではなく、コンピュータを機能させて前記同様のステップを順次実行させるコンピュータプログラムとしてもよい。
【実施例】
【0084】
この実施例は、本発明を所定の研究室におけるゼミ発表スケジュール問題に適用したものである。このゼミ発表スケジュール問題は、毎週研究室等で行われるゼミの発表者を割り当てる問題である。本実施例では、研究室の要員数が13人、ゼミ回数が26回、一回あたりのゼミ発表者人数が3人であるとした場合の最適なゼミ発表スケジュールを得ることを目的としている。つまり、本実施例では、個体数13、個体長が26となる。そして、研究テーマは3つとし、それぞれの発表者数は5人、4人、4人とした。この事例では最適な発表回数は6回、最適な発表間隔は4.3週となる。
【0085】
個体の評価は、発表回数の均等化と発表間隔の均等化を目的とした評価を行う。適応度関数Fは、以下の式(21)に示すように、
【数8】
JP0004467286B2_000012t.gif
とした。ここで、Nを最適な発表間隔とした場合において、f1iは発表者iにおける発表回数を、またf2は最適な発表回数を、またf3iはN週間における発表者iによる発表が2回以上又は0回の回数を、またf4iは発表者iにおける発表間隔がN+1週間以上又はN-1週間以下の回数をそれぞれ表している。個体の適応度関数の重みは、α=2、β=2、γ=1とした。
【0086】
集団としての評価は、(1)全体の発表負荷の最小化、(2)全体の発表負荷の均等化、(3)発表テーマ重複度の最小化を評価項目として行った。この(1)及び(2)は、各発表者のスケジュールの評価値の平均及び標準偏差を評価値としている。また(3)は、ゼミ1回の発表者の中で同じテーマ重複度を算出し、この総和を評価値としている。テーマ重複度とは、テーマごとにM-1を算出し、その総和で決定される。尚、Mは重複人数を表している。
【0087】
また、本問題においては、テーマ重複度を取り入れない実験1と、テーマ重複度を取り入れた実験2との2つの実験を行った。
【0088】
本実施例における共存型GAに関するパラメータについて説明する。本実施例でも、親ペアの選択は、一方をランダム選択とする一方、他方を適応度の低いもの即ち評価の悪いものほど選択され易い確率で選択する方式としている。そして、比較例としての従来の共存型GAは2点交叉で行い、本実施例2は1点交叉とした。次世代解候補の生成数を300とし、世代数は、実験1では700世代、実験2では3000世代とした。
【0089】
そして、次世代解候補の中からの最良解の選択は最適解からのユークリッド距離の最小のものを選択することにより行った。今回の問題では、最適解の値は、平均が1.8、標準偏差が0.4、テーマ重複度が4となる。
【0090】
次に実験結果について説明する。
【0091】
図6は、実験1において各探索過程で得られた解候補の分布を示している。この図から、実施例では解候補の分布が平均値によらず一様であるとともに広い探索空間を保持して探索が進められるのに対し、比較例では解の分布が局所的であるとともに解候補の探索空間が実施例に比べて狭くなっていることが分かる。
【0092】
図7及び図8は、各世代で得られた次世代解に対する最適解までの距離の推移を示している。図7はテーマ重複度を取り入れない実験1における結果を示しており、この図から分かるように実施例は比較例に比べ最適解へ早く収束している。一方、図8は実験2における結果を示しており、この図から実施例は比較例に比べ最適解との距離が小さくなっていることが分かる。したがって、実施例の方が比較例に比べ最適解に近い解に収束しており、精度の良い解が得られていると言える。この実験2では、テーマ重複度を取り入れることで問題が複雑化しており、このために、比較例では最適解に近づけない局所解に陥ったと考察される。
【0093】
以上より、本実施例では、比較例に比べて解の探索空間の拡大を図ることができて探索効率を向上できるとともに局所解に陥る確率を低減することができる。
【図面の簡単な説明】
【0094】
【図1】本発明の実施形態に係るスケジューリング装置の全体構成を示すブロック図である。
【図2】本発明の実施形態に係るスケジューリング装置による共存型GAを概念的に示す図である。
【図3】本発明の実施形態に係るスケジューリング装置の制御動作を示すフロー図である。
【図4】本発明の実施形態に係るスケジューリング装置によって得られた勤務スケジュール表の一例を示す図である。
【図5】本発明の実施形態に係るスケジューリング装置によって得られた各世代に対する最適解との距離の推移を示す図である。
【図6】本発明の実施例における解候補の広がりを示す特性図であり、(a)は比較例での結果例を示し、(b)は実施例での結果例を示している。
【図7】本発明の実施例における実験1での探索結果を示す特性図である。
【図8】本発明の実施例における実験2での探索結果を示す特性図である。
【図9】従来の共存型GAを概念的に示す図である。
【符号の説明】
【0095】
2 初期個体集団生成部(初期個体群生成手段)
3 個体評価値計算部(個体評価手段)
4 親ペア選択部(親ペア選択手段)
5 交叉処理部(交叉手段)
6 次世代解候補生成部(次世代候補生成手段)
8 次世代解選択部(次世代解選択手段)
12 制御部(制御手段)
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8