(57)【要約】      （修正有）【課題】複雑な評価規則を満足しつつ、局所解に陥ることなく、比較的短時間で看護師勤務表を作成することが可能なソフトウエアを提供する。【解決手段】各看護師に関する熟練度合・勤務系列・各曜日の割付勤務・必要人数を含む評価規則の入力を促す画面を表示するステップ１０、評価規則をできるだけ満足するようにコンピュータによって自動計算し、所定の終了条件を満たした後に、暫定解を画面に表示するステップ１２、前記暫定解に対して、ユーザの手入力による修正を促すステップ１４、評価規則の更新を行うステップ１８を含むソフトウエアで構成され、ユーザは、出力された勤務表候補について判断を行うステップ１６で、最終的なものであると認める場合に作業を終了する。【選択図】        図３
2004151790.tif 000002
【特許請求の範囲】
【請求項１】
複数の看護師の勤務工程を２週間以上の長期間に渡って備えた勤務表を作成するために、▲１▼各看護師に関する熟練度合・勤務系列・各曜日の割付勤務・必要人数を含む評価規則の入力を促す画面を表示するステップ、▲２▼前記評価規則をできるだけ満足するようにコンピュータによって自動計算するステップ、▲３▼自動計算によって所定の終了条件を満たした後に、暫定解を画面に表示するステップ、▲４▼前記暫定解に対して、ユーザの手入力による修正を促すステップ、▲５▼前記評価規則の更新を行うステップを含むソフトウエアであって、
前記▲２▼ステップには、（ａ）ランダムに発生させた親勤務表の二個を交叉させる交叉ステップ、（ｂ）前記交叉させた点を含む所定の近傍箇所を突然変異または／およびヒューリスティクスによって子勤務表を再生成するステップ、（ｃ）前記子勤務表に較べて劣パレートな親勤務表を子勤務表と置き換えるステップを含むことを特徴とするソフトウエア。
【請求項２】
前記▲２▼ステップには、更に（ｄ）所定の回数だけ前記（ａ）〜（ｃ）ステップを繰り返した後に評価値の改善が認められない場合に、全体への突然変異を行うステップを含むことを特徴とする請求項１に記載のソフトウエア。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、看護師勤務表作成ソフトウエア等に関するものである。
【０００２】
【従来の技術】
複数の看護師の勤務スケジュール（看護師勤務表）を作成する問題（看護師勤務表作成問題（Ｎｕｒｓｅ  Ｓｃｈｅｄｕｌｉｎｇ  Ｐｒｏｂｌｅｍ：  ＮＳＰ）は、複数の評価規則（制約条件）を含んだ複雑な組合せ最適化問題である。一般に看護師勤務表は、月毎に各病棟の婦長によって作成される。この勤務表作成には、多くの時間と労力を必要とすることから、多忙な婦長にとって大きな負担となっている。この問題を解決するため、従来には遺伝的アルゴリズム（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ：  ＧＡ）を用いた勤務表作成システム（山村、小林、山岸、阿瀬「遺伝的アルゴリズムによるナーススケジューリング」北野宏明  著  遺伝的アルゴリズムｐｐ．８９−１２５，１９９３）等が開発  されてきた。
【０００３】
しかしながら、この従来システムは、婦長の人的負担を軽減することを目的として、全自動型アルゴリズムを採用していた。このため、かえって局所解に陥りやすく、婦長が満足する解を得るためには、何度も始めからやり直さなければならないという問題点があった（竹本「コンピュータを導入した看護師勤務表作成の現状と課題」看護管理Ｖｏｌ．３  Ｎｏ．１  ｐｐ３８−４２  １９９３）。
【０００４】
そこで、本発明者らは、上記の問題点に対して検討を加えた結果、解探索の過程にユーザが関与しながら、ユーザとソフトウエアとが協調して勤務表作成を行う対話型看護師勤務表作成支援ソフトウエア及び、このソフトウエアを含むシステムを提案した（井上、古橋、前田、高羽「インタラクティブＥＡを用いたナーススケジューリング支援システムのためのＥＡエンジンに関する一考察」第１６回ファジィシステムシンポジウム（秋田），９月６日〜８日，２０００、講演集ｐｐ６１９−６２２）。このソフトウエアは、全自動型アルゴリズムではなく、解探索の過程で勤務表案がユーザ（例えば、婦長）に呈示され、これに対してユーザがこの勤務表案のデータに対して、修正及び／または一部固定等を行いながら、ユーザの求める勤務表案の作成を進める。このため、評価規則を充分に満足しないままでも、ユーザとソフトウエアとの協調により勤務表作成を進めることができる。勤務表案の修正時には評価規則の修正を行うことができる。このソフトウエアに用いたバクテリア進化的計算（Ｂａｃｔｅｒｉａｌ  Ｅｖｏｌｕｔｉｏｎａｒｙ  Ａｌｇｏｒｉｔｈｍ：ＢＥＡ）は、短い日数（例えば、３日間〜５日間）からなる勤務形態の改善には効果的である。しかしながら、各看護師の勤務負荷を一月にわたって平等に割付けることには工夫の余地が残されていた。
【０００５】
【非特許文献１】山村、小林、山岸、阿瀬「遺伝的アルゴリズムによるナーススケジューリング」北野宏明著  遺伝的アルゴリズム  ｐｐ．８９−１２５，  １９９３
【非特許文献２】竹本「コンピュータを導入した看護師勤務表作成の現状と課題」看護管理Ｖｏｌ．３  Ｎｏ．１  ｐｐ３８−４２  １９９３
【非特許文献３】井上、古橋、前田、高羽「インタラクティブＥＡを用いたナーススケジューリング支援システムのためのＥＡエンジンに関する一考察」第１６回ファジィシステムシンポジウム（秋田），９月６日〜８日，２０００、講演集ｐｐ６１９−６２２
【０００６】
【発明が解決しようとする課題】
本発明は、上記した事情に鑑みてなされたものであり、その目的は、複雑な評価規則を満足しつつ、局所解に陥ることなく、比較的短時間で看護師勤務表を作成することが可能なソフトウエアを提供することにある。
【０００７】
【課題を解決するための手段】
本発明者らは、バクテリア進化的計算のみでは、長期間（例えば、二週間以上、約１ヶ月程度）に渡る看護師勤務表を平等に割り付けることが困難であるという問題点を解決するために鋭意検討を行った。その結果、▲１▼適当に発生させた親勤務表（「親個体」と表記することがある。）群に対して交叉演算を行い、▲２▼その交叉演算によって生成された子勤務表（「子個体」ということがある。）の交叉点近傍に対して、突然変異または／およびヒューリスティクスを適用することにより、所期の目的を達成することができることを見出し、基本的には本発明を完成するに至った。また、更に局所的な解に陥ることを防ぐために、勤務表全体に突然変異を発生させることにより、公平さを良好とすることができた。
【０００８】
すなわち、本発明者らの検討によれば、交叉演算を勤務表全体に対する突然変異と組み合わせることにより、各看護師の一月の勤務負荷の均等化に対して効果が期待された。それでもなお、交叉演算によって、交叉点の前後の勤務形態が大きく崩れてしまうという問題点が残されてしまう。そこで、本発明者らは、更に交叉点の修復に看護師勤務表作成問題の性質を利用したヒューリスティックスを導入することで、交叉演算の適用を可能とし、局所解に陥らないで勤務表全体に対する探索を必要とする評価項目「勤務負荷の公平さ」に対しても効率的な探索手法を提供することができるに至った。
【０００９】
上記の課題を解決するために第１の発明は、複数の看護師の勤務工程を２週間以上の長期間に渡って備えた勤務表を作成するために、▲１▼各看護師に関する熟練度合・勤務系列・各曜日の割付勤務・必要人数を含む評価規則の入力を促す画面を表示するステップ、▲２▼前記評価規則をできるだけ満足するようにコンピュータによって自動計算するステップ、▲３▼自動計算によって所定の終了条件を満たした後に、暫定解を画面に表示するステップ、▲４▼前記暫定解に対して、ユーザの手入力による修正を促すステップ、▲５▼前記評価規則の更新を行うステップを含むソフトウエアであって、前記▲２▼ステップには、（ａ）ランダムに発生させた親勤務表の二個を交叉させる交叉ステップ、（ｂ）前記交叉させた点を含む所定の近傍箇所を突然変異または／およびヒューリスティクスによって子勤務表を再生成するステップ、（ｃ）前記子勤務表に較べて劣パレートな親勤務表を子勤務表と置き換えるステップを含むことを特徴とする。
また、前記▲２▼ステップには、更に（ｄ）所定の回数だけ前記（ａ）〜（ｃ）ステップを繰り返した後に評価値の改善が認められない場合に、全体への突然変異を行うステップを含むことが好ましい。
【００１０】
＜看護師勤務表作成問題＞
看護師勤勤務表作成問題（ＮＳＰ）は、勤務制約、看護の質、各看護師からの要求等の制約の下で、「日勤」（ＡＭ８：００〜ＰＭ４：００）、「準夜勤」（ＰＭ４：００〜ＡＭ０：００）、「深夜勤」（ＡＭ０：００〜ＡＭ８：００）の３つの勤務形態を各看護師に割り付ける組合せ最適化問題である。図１には、具体的な勤務表の例を示す。この勤務表には、１０人（ＳｔａｆｆＡ〜Ｊ）の看護師について、１４日分の勤務日程が表されている。表中の記号「日」は「日勤」、「準」は「準夜勤」、「深」は「深夜勤」を表している。また、勤務表中の空欄は休みを表している。一番左の列は各看護師の熟練の度合いを表し、熟練度の高いＡから経験の浅いＣまでにランク付けされている。下段の３つの行は、各日の各勤務形態を割付けられた看護師数を表す。右側の４つの列は各看護師への各勤務の割付け日数を表している。
【００１１】
勤務表の評価規則には、▲１▼勤務系列、▲２▼各曜日の割付け勤務、▲３▼必要人数、および▲４▼割付け日数に関するもの等がある。▲１▼勤務系列は、一人の看護師に注目したときに、その勤務日が、「日勤」〜「深夜勤」や、「日勤」〜「休み」〜「準夜勤」のように複数日にわたる勤務形態についての系列を意味している。この勤務系列は、看護師の健康面で無理のないものとする必要がある。▲２▼各曜日の割付け勤務に関する規則は、例えば、「看護師Ａは土曜日に準夜勤を割付けない」等、看護師の特殊性を反映した制約である。▲３▼必要人数は、例えば深夜勤２人の内の１人は必ず熟練の看護師を割付ける等、看護の質を維持するための制約である。▲４▼割付け日数は、看護師間で均等に割付けることが基本であるが、各看護師の事情や先月分の割付け日数も考慮し、広い視点で公平感を与える割付けを行う必要がある。さらに、現場では、看護師間の相性、アクシデントによる急な日程変更等の細かな制約が加わることがあるので、評価規則について柔軟な対応が要求される。
【００１２】
＜看護師勤務表作成支援ソフトウエア＞
本発明者らが、  解決しようとした問題点は、主として次の３つであった。▲１▼看護師勤務表作成問題の評価規則は病院毎に異なり、ユーザ（例えば、婦長）は勤務表の自動作成に必要な全ての評価規則を定義しなければならない。従来のように手作業で勤務表を作成していた場合には、評価規則は整理されていないことが多かったことから、評価規則の設定漏れが起きやすかった（問題点１．評価規則設定の困難性）。▲２▼勤務表の自動計算アルゴリズムでは、局所解に陥りやすいため、ユーザは満足のいく解を得るためには何度も初めからスケジューリングをやり直さなくてはならなかった（問題点２．解探索の困難性）。▲３▼解探索に長時間が掛かるため、多忙なユーザ（特に婦長）にとって長い計算待ち時間は心理的負担となり得た（問題点３．計算時間の長さ）。
これらの問題に対処するために、図２に示す対話型勤務表作成支援システムを提案する。このシステムによる勤務表作成は、例えば図３に示すように、次の手順で行うことができる。
【００１３】
まず、ユーザは、評価規則をできる限り洗い出し、システムに入力する（ステップ１０．評価規則入力）。次に、定義された評価規則の下で自動スケジューリングを行う。ただし、解候補の呈示を待っているユーザに対して、長時間の演算によって心理的な負担を与える前に探索を打ち切り、暫定的な解を呈示する（ステップ１２．突然変異（「バクテリア進化的計算（ＢＥＡ）」と称することがある。）を用いた勤務表候補の生成）。すなわち、本発明のアルゴリズムを実行するにあたり、自動計算実行時の終了判定は、多くの場合に繰り返し計算回数で与えることが好ましい（或いは、自動計算実行中の時間で判定することもできる。多くの場合に、ユーザが自動計算中のコンピュータの結果表示を待てる時間は、せいぜい１分間〜２分間程度のものである。そのため、使用するコンピュータのスペックにより、自動演算の繰り返し回数または、自動演算時間によって、終了条件を設定しておくことが実際的である。それは、勤務演算表の大きさを考えてみれば分かる。例えば、１０人の看護師について、３０日間の勤務表を作成するには、各々のセルに割り付ける場合の数は日勤・準夜勤・夜勤・休日の四種類であるから、全部で４１０ｘ３０通りの勤務表群ができうる。これらの広大な勤務表群の中から評価規則を満たすものを作成することになる。
【００１４】
自動計算方法としては、後述するように、（１）親個体間の交叉演算、（２−１）交叉点の近傍におけるヒューリスティクス、（２−２）交叉点の近傍における突然変異、及び（３）個体全体への突然変異を適当に組み合わせて用いることができる。
また、暫定的な解を呈示する場合には、評価規則を満たさない問題箇所については、評価規則を満足する他の箇所とは異なる背景色を用いることによって、ユーザが分かり易いようにすることが好ましい。このとき、評価規則に二つ以上の段階がある場合には、それぞれ異なる背景色を用いることが好ましい（例えば、後述のように、絶対禁止の評価規則を満たさない箇所には「赤色」、妥協禁止の評価規則を満たさない箇所には「黄色」、評価規則を満足する箇所には「青色」の背景色をそれぞれ用いることができる。）。解の質と演算時間とはトレードオフの関係にあるため、演算時間を短くするためには、効率的な探索アルゴリズムを採用する必要がある。看護師勤務表作成問題の探索には、局所部分の探索（例えば、３日間〜５日間）に有効なバクテリアＥＡを採用することができる。
【００１５】
次に、ユーザはシステムが呈示した解候補に対し、手入力による直接修正を加える（ステップ１４．勤務表候補の修正と部分的固定）。このステップ１４では、ユーザは、勤務表データの一部を変更・置換等の作業を行うことができる。このとき、解候補は唯一ではなく、複数のものを並列的に呈示することができる。また、特定の解候補について、部分的に満足のいく箇所があれば、その箇所を固定して、再計算箇所の絞り込みを行うことができる。
【００１６】
ここでユーザは、出力された勤務表候補について判断を行い（ステップ１６）、最終的なものであると認める場合には作業を終了する。また、上記ステップ１０において気付かなかった評価規則にユーザが気付いた場合には、その評価規則の更新を行い（ステップ１８．評価規則の更新）、更新された評価規則の下で、ステップ１４において修正された勤務表を初期個体として、ステップ１２から再度実行する（未固定個所の再計算）。このとき、ステップ１４において、ユーザが固定を指定した部分については、突然変異の対象外とする。
以下、ユーザが満足できる勤務表を獲得できるまで、上記のステップ１２〜ステップ１８を繰り返す。最後に完成した勤務表は、次回の勤務表作成時にステップ１０で利用される。
【００１７】
＜交叉とヒューリステックスとの併用＞
問題点３の課題は、システムとユーザとが円滑に協調作業を行う上で最も重要な課題である。すなわち、上記ステップ１２においては、ユーザの手作業による負担を軽減するために、良質の解候補を迅速に導出することが望まれる。ここで解の質と演算時間とは、トレードオフの関係にあるため、効率的な探索アルゴリズムが必要である。本発明者らは、看護師勤務表作成問題の探索に、局所探索に有効なバクテリアＥＡ（ＢＥＡ）を適用した。ＢＥＡはバクテリアの進化過程を参考にしたアルゴリズムであり、染色体の局所部分の改善に有効である。看護師勤務表作成問題では、勤務系列に関する評価規則は、連続する２日〜４日程度のものが多いことから、隔たった日の間の依存関係は低い。このため、染色体の局所部分毎に集中的に解の改善を図るＢＥＡのバクテリア演算が効果的であった。しかしながら、勤務表においては各看護師の１ヶ月間の勤務負荷を平等とする「割付け日数の公平さ」が要求される。そこで、本発明者らは、良質の解を迅速に導出するために、通常の交叉と看護師勤務表作成問題の性質を利用したヒューリスティクスとを組み合わせることを試みた。
【００１８】
本発明者らは、  良質な解候補を迅速に提示するため、進化的計算における交叉に着目した。この方法では、交叉を効率的に行うため、交叉演算とヒューリスティクスとを組合せることで、勤務系列の劣化を抑えると共に、パレート最適解探索により染色体群の多様性を保証した。次に、その手法の詳細について説明する。
【００１９】
＜パレート最適解探索＞
次に、パレート最適解探索について説明する。パレート最適解探索を行う理由は、（１）ユーザに呈示する勤務表候補に多様性を持たせること、（２）染色体群に多様性を持たせることで交叉の際に似通った個体同士が組になることを抑えることの２点がある。本手法では、トレードオフの関係にある割付け日数とそれ以外の評価項目の２つの評価軸を用いたパレート最適解探索を行うこととした。ただし、評価規則の中には必ず満たさなければならない「絶対制約」と、勤務日数との兼ね合いで妥協することのある「妥協制約」とが存在する。そこで、絶対制約は双方の軸に加えることとし、評価関数を以下の式（１）〜式（５）のように定義した。
【００２０】
Ｈ１  ＝  Ａ  ＋  Ｂ  （１）
Ｈ２  ＝  Ａ  ＋  Ｃ  （２）
Ａ  ＝  １  −  １  ／  （  １  ＋  ａ  ）  （３）
Ｂ  ＝  １  −  １  ／  （  １  ＋  ｂ  ）  （４）
Ｃ  ＝  １  −  １  ／  （  １  ＋  ｃ  ）  （５）
【００２１】
ここで、ａは絶対制約違反数、ｂは妥協制約違反数  、ｃは平均勤務日数からの差の絶対値の総和である。制約違反数とは、絶対制約または妥協制約を満足しない個数を意味しており、勤務表内の割付けが何らかの評価規則に違反した場合に＋１だけ加算される。Ｈ１，Ｈ２のいずれにおいても優れた個体が存在しない場合には、その個体をパレート最適個体とする。但し、サブ染色体群の個体がパレート最適であり、かつ染色体群に劣パレート最適な個体が存在しない場合は、次式（６）の評価関数に従って保存個体を選択することとした。
Ｈ  ＝  Ａ  ＋  Ｂ  ＋  Ｃ  （６）
【００２２】
＜ＧＡとヒューリスティクスとの複合手法＞
上記の看護師勤務表作成問題における各評価項目は、進化的計算による最適化を行う上で互いに影響を及ぼし合うために、解探索を困難にしている。割付け日数以外の評価項目は、互いに隔たった日の間の依存関係が低い。そのため、染色体全体に対して均等に突然変異を行うのではなく、ＢＥＡのように一部分に突然変異を集中し、局所部分の探索を行う手法が効果的である。ＢＥＡによる局所部分の探索は、勤務表作成者が勤務表のある期間（例えば、３日間〜５日間の数日間）に限定して、看護師同士で勤務割付けを入れ替えて試行錯誤する作業に相当する。一方、割付け日数に関しては、各看護師の一月の勤務負荷が均等となるように考慮する必要があるため、ＢＥＡのように狭い期間に集中的に突然変異を加える手法では、良好な解を得る効果が低い。この問題を解決するには、染色体全体に対する突然変異と交叉との両方の効果が期待される。しかし、交叉を行うと、その交叉点の前後で勤務系列が途切れるために、評価値を著しく悪化させてしまう。そこで、交叉演算による勤務系列の劣化を補修しながら解探索を行う手法として、本発明者らは次の手法を提案する。
【００２３】
交叉演算を行い、その交叉点の周辺（例えば、３日間〜５日間）の修復に、手動作成時のヒューリスティクスを用いる。また、この手法は局所解に陥る危険があることから、更に突然変異を加えることとした。次に、図４及び図５を参照しつつ、その方法のアルゴリズムの一例を説明する。
【００２４】
まず、Ｎ個の初期個体群を生成する（ステップ２０）。ここで、全体への突然変異が必要か否かを判断する（ステップ２１）。なお、下記実施例において、方法論を検討する場合には、本方法と全体への突然変異を含む方法（ステップ２１のＹｅｓ方向）と切り離して実施することがある。ステップ２１でＹＥＳの場合には、「Ａ」に進んで、全体への突然変異アルゴリズムを実施する（後に詳述する。）。一方、ＮＯの場合（或いは、全体への突然変異アルゴリズムを切り離して実施する場合）には、染色体群から２個の親個体をランダムに選択し、一点交叉によって新たな子個体を１つ生成する（ステップ２２）。また、ステップ２１において、全体への突然変異アルゴリズムを実施した後に、再び「Ｂ」からヒューリスティクスのアルゴリズムに戻ってくる場合がある（後述）。このように、ヒューリスティクスと全体への突然変異とは、相互に組み合わせて用いることができる。
次に、予め設定されたＬＢＭ日の局所部分（親個体の交叉箇所を中心として再生成する長さ）について、子個体の再作成箇所をヒューリスティクスによって再作成する（ステップ２４：ヒューリスティクスの詳細については後述する。）。次に、子個体の再作成範囲内の各日に対して確率ＰＢＭ／ＬＢＭで突然変異を施す（ステップ２６）。ここで、子個体の評価値を計算し、染色体群の評価値と比較し、子個体がパレート最適な個体であれば、染色体群の劣パレートな個体の中から１個体をランダムに選択し置き換える（ステップ２８）。こうして再計算された染色体群が終了条件を満たすか否かを判断し（ステップ３０）、ＹＥＳの場合には操作を終了し、ＮＯの場合には、ステップ２１からステップ２８を繰り返す。
【００２５】
＜手動作成をモデル化したヒューリスティクス＞
次に、ヒューリスティクスの手順について説明する。本手法では、勤務表の未割付け箇所を逐次的に決定する作業をモデル化した。手作業で逐次的に割付けを行っていく場合には、必要人員数や勤務系列などの制約により、選択可能な勤務形態が少ない箇所から割付けを決定する。また、手作業による勤務表作成では、通常は、日付の早い方から優先的に割付けを行う。このため、日付毎に各看護師の割付け優先度を求めることとした。まず、解析に用いたパラメータについて説明する。
【００２６】
パラメータＬ（ｓ）は、看護師ｓの看護技能ランクを意味する。パラメータＷ（ｄ，ｓ）は、作成過程の勤務表における日付ｄの看護師ｓへの割付け内容を示し、Ｓ（ｄ，ｓ）の割付けは、勤務形態ｎ∈｛“日勤”，“準夜勤”，など｝および未割付け：φの状態をとる。パラメータＲ（ｄ，ｎ，ｌ）は、日付ｄの勤務形態ｎにおける看護技能ランクｌの必要人員数に対するランク別不足人員数を示す（ただし、ｌ＝＃（ｄｏｎ’ｔ  ｃａｒｅ）の場合は、総必要人員に対する不足人員数を示す）。パラメータＶ（ｄ，ｓ，ｎ）は、日付ｄにおける看護師ｓへ割付けを勤務形態ｎとした場合の勤務系列、各曜日の割付け勤務および必要人員の評価規則に対する割付け判定を示す。パラメータＭ（ｄ，ｎ）は、日付ｄにおける勤務形態ｎの必要人員制約を満たすことができる看護師の数を示す。パラメータＵ（ｄ，ｓ，ｎ）は、日付ｄにおける看護師ｓへ割付けを勤務形態ｎとする割付け作業に対する優先度を示す。
ここで、割付け  判定Ｖ（ｄ，ｓ，ｎ）について説明する。Ｖ（ｄ，ｓ，ｎ）は、勤務系列、各曜日の割付け勤務、及び必要人員の各評価規則に従い、次の判定を行うこととした。
【００２７】
割付け判定のうち、Ｖ（ｄ，ｓ，ｎ）  ＝  ０  は、絶対禁止を意味し、勤務系列の絶対制約違反、各曜日の割付け勤務の絶対制約違反、および総人員数もしくはランク別人員数が必要人員に対し定員超過を起こした場合がある。また、Ｖ（ｄ，ｓ，ｎ）＝  １  は、妥協禁止を意味し、Ｖ（ｄ，ｓ，ｎ）  ＝  “絶対禁止”の条件を満たさず、勤務系列の妥協制約違反もしくは各曜日の割付け勤務の妥協制約違反の何れかを起こした場合がある。また、Ｖ（ｄ，ｓ，ｎ）＝  ２  は、配置可能を意味し、勤務系列、各曜日の割付け勤務、および必要人員の評価規則の何れの評価規則に対しても制約違反を起こすことがない場合である。
【００２８】
次に、優先度Ｕ（ｄ，ｓ，ｎ）の決定法について説明する。Ｕ（ｄ，ｓ，ｎ）  ＝  ０  は、割付け不可を意味し、条件｛Ｗ（ｄ，ｓ）ｚ≠φ｝を満たす場合である。また、Ｕ（ｄ，ｓ，ｎ）＝  １  は、優先度最低を意味し、条件｛Ｗ（ｄ，ｓ）  ＝φ  ａｎｄ  Ｖ（ｄ，ｓ，ｎ）  ＝  ０｝を満たす場合である。また、Ｕ（ｄ，ｓ，ｎ）  ＝  ２  は、優先度低を意味し、条件｛Ｗ（ｄ，ｓ）＝φ  ａｎｄ  Ｖ（ｄ，ｓ，ｎ）  ＝  １｝を満たす場合である。また、Ｕ（ｄ，ｓ，ｎ）  ＝  ３  は、優先度中を意味し、条件｛Ｗ（ｄ，ｓ）  ＝φ  ａｎｄ  Ｖ（ｄ，ｓ，ｎ）  ＝  ２  ａｎｄ  Ｒ（ｄ，ｎ，＃）  ＝  ０  ａｎｄ  Ｒ（ｄ，ｎ，Ｌ（ｓ））  ＝  ０｝を満たす場合である。また、Ｕ（ｄ，ｓ，ｎ）  ＝  ４  は、優先度高を意味し、条件｛Ｗ（ｄ，ｓ）＝φ  ａｎｄ  Ｖ（ｄ，ｓ，ｎ）  ＝  ２  ａｎｄ  （Ｎ（ｄ，ｎ）  ＞  ０  ｏｒ  Ｒ（ｄ，ｎ，Ｌ（ｓ））  ＞  ０）｝を満たす場合である。また、Ｕ（ｄ，ｓ，ｎ）＝  ５  は、優先度最高を意味し、条件｛Ｗ（ｄ，ｓ）  ＝φ  ａｎｄＶ（ｄ，ｓ，ｎ）  ＝  ２  ａｎｄ  （Ｎ（ｄ，ｎ）  ＞  ０  ｏｒ  Ｒ（ｄ，ｎ，Ｌ（ｓ））＞  ０）ａｎｄ  （Ｍ（ｎ）≦Ｒ（ｄ，ｎ，＃）  ｏｒ  Ｍ（ｎ）≦Ｒ（ｄ，ｎ，Ｌ（ｓ）））｝を満たす場合である。
ヒューリスティクスは、前述のパラメータを用いて割付けを行う。そのアルゴリズムの一例について、図６を参照しつつ説明する。このアルゴリズムは、例えば既述のステップ２４中において、用いることができる。
【００２９】
まず、再作成箇所を未割付けとして空白にする（ステップ４０）。次に、未割付けが存在する最も早い日付を選択して、割付け日Ｄとする（ステップ４２）。次に、日付ＤにおけるＲ（Ｄ，ｓ，＃）およびＲ（Ｄ，ｓ，ｌ）を計算する（ステップ４４）。次いで、日付Ｄにおける全ての看護師ｓおよび勤務形態ｎに対して、優先度Ｕ（Ｄ，ｓ，ｎ）を計算する（ステップ４６）。次に、日付Ｄにおける優先度Ｕ（Ｄ，ｓ，ｎ）の最大値Ｕｍａｘを計算する（ステップ４８）。更に、日付Ｄにおいて、優先度が条件｛Ｕ（Ｄ，ｓ，ｎ）＝  Ｕｍａｘ｝を満たす看護師ｓの人数の最少の値を計算し、最小値をとる勤務形態を割付け勤務Ｎとする（ステップ５０）。このとき、最小値をとる勤務形態が複数存在する場合は、これらの中からランダムに１つを選択し、割付け勤務Ｎとする。
【００３０】
次に、日付Ｄにおいて、優先度が条件｛Ｕ（Ｄ，ｓ，Ｎ）  ＝  Ｕｍａｘ｝を満たす看護師ｓの中からランダムに１つ選択し、割付け看護師Ｓとする（ステップ５２）。次いで、勤務表の割付けＷ（Ｄ，Ｓ）に対して割付け勤務Ｎを割付ける（ステップ５４）。ここで、未割付けが存在するか否かを判断し（ステップ５６）、存在しない場合には作業を終了し、存在する場合にはステップ４２〜ステップ５４を繰り返す。
【００３１】
＜交叉点近傍の修復にバクテリア突然変異を用いた手法＞
交叉による勤務系列の破壊の修復は、交叉点近傍に突然変異を集中するバクテリア突然変異を適用する手法が考えられる。そのアルゴリズムの一例について、図７及び図８を参照しつつ説明する。
【００３２】
まず、染色体群を初期化した後に（ステップ５９）、全体への突然変異が必要であるか否かが判断される（ステップ６０）。ここでＹｅｓの場合には、後述の染色体全体への突然変異アルゴリズムを行う（なお、下記実施例において、方法論を検討する場合には、本方法と全体への突然変異を含む方法（ステップ６０のＹｅｓ方向）と切り離して実施することがある。）。
ステップ６０でＮｏの場合には、染色体群から２個の親個体をランダムに選択し、一点交叉によって新たな子個体を１つ生成する（ステップ６２）。次いで、親個体の交叉箇所を中心に長さがＬＢＭ日の局所部分を局所改善範囲に選定し、子個体をＮＣ個に増殖し、サブ染色体群を生成する（ステップ６４）。次に、サブ染色体群から１個体をランダムに選択し、その複製を１個生成し、選択した個体の局所改善範囲内の各日に対して確率ＰＢＭ／ＬＢＭで突然変異を施す（ステップ６６）。
【００３３】
次に、突然変異個体を評価する。つまり、この個体とサブ染色体プールからランダムに選択した個体とを比較し、評価値の良い個体を残し、劣悪な個体を削除する（ステップ６８）。ここで、ステップ６６〜ステップ６８をＮＳＴ回繰り返す（ステップ７０）。次に、サブ染色体群の個体の評価値を染色体群の個体の評価値を比較し、パレート最適な個体を染色体群の劣パレートな個体の中からランダムに選択したものと置き換える（ステップ７２）。終了条件を満たすまで、ステップ６２〜ステップ７２を繰り返す（ステップ７４）。
【００３４】
＜染色体全体への突然変異＞
勤務日数の公平さに対する探索は、染色体全体への一様な突然変異によって探索効率が向上する可能性がある。特に、染色体群の多様性が無くなると、交叉演算の効果が消失するため、解探索が停滞する可能性がある。そこで、上述のアルゴリズムにおける親個体の淘汰演算（ステップ２８及び、ステップ７２）を所定の回数（ＮＸＴ回）だけ行う間にパレート最適な子個体が新たな親個体として染色体群に加えられず、評価値の改善が見られない場合には、交叉の代わりに染色体全体への突然変異による探索を行う。そのためのアルゴリズムの一例を図９を参照しつつ説明する。このアルゴリズムは、ステップ２１又はステップ６０において、全体への突然変異が必要である（すなわち、所定回数（ＮＸＴ）の淘汰演算によっても評価値の改善が見られない場合）と判断された場合に実施することができる。
【００３５】
まず、更に全体への突然変異が必要か否かを判断し（ステップ７８）、Ｙｅｓの場合には、以下のステップ８０〜ステップ９０のアルゴリズムを実行する。一方、ステップ７８において、全体への突然変異が必要でないと判断された場合には、「Ｂ」に進み、ステップ２２（＜ＧＡとヒューリスティクスとの複合手法＞）又は、ステップ６２（＜交叉点近傍の修復にバクテリア突然変異を用いた手法＞）に進むことができる。つまり、本法は、▲１▼ＧＡとヒューリスティクスとの複合手法、又は▲２▼交叉点近傍の修復にバクテリア突然変異を用いた手法を組み合わせて実施することができる。
ステップ７８でＹｅｓの場合には、染色体群から親個体をランダムに選択し（ステップ８０）、その親個体を複製してＮＣ個に増殖し、サブ染色体群を生成する（ステップ８２）。次いで、サブ染色体群から１個体をランダムに選択し、その複製を１個生成し、選択した個体の染色体全体に確率ＰＢＭ／（１ｍｏｎｔｈ）で一様な突然変異を施す（ステップ８４）。次いで、突然変異個体を評価する。つまり、この個体とサブ染色体プールからランダムに選択した個体とを比較して、評価値の良い個体を残し、劣悪な個体を削除する（ステップ８６）。次に、ステップ８４〜ステップ８６をＮＬＴ回繰り返す（ステップ８８）。そして、サブ染色体群の個体の評価値を染色体群の個体の評価値と比較し、パレート最適な個体があれば染色体群の劣パレートな個体と置き換える（ステップ９０）。終了条件を満たした場合にはアルゴリズムを終了し（ステップ９２のＹｅｓ）、終了条件を満足しない場合にはステップ７８に戻る（ステップ９２のＮｏ）。
【００３６】
【発明の実施の形態】
次に、本発明の一実施形態について、図面を参照しつつ詳細に説明するが、本発明の技術的範囲は、下記の実施形態によって限定されるものではなく、その要旨を変更することなく、様々に改変して実施することができる。また、本発明の技術的範囲は、均等の範囲にまで及ぶものである。
次に、上記の各種アルゴリズムを単独で、或いは複数を組み合わせて用いることにより、実際に看護師勤務表の作成を行った。
【００３７】
＜問題設定＞
看護師勤務表作成には、看護師数２０人の病棟の例を用いた。その際に用いた評価規則を以下に示す。
（１）  勤務系列  に関する規則
勤務系列に関する規則についての絶対制約と妥協制約とは。それぞれ次の通りである。
まず、絶対制約としては、▲１▼  「準夜勤」  の次に「深夜勤」  を割り付けない、▲２▼深夜勤は４日以上連続して割り付けない、▲３▼深夜勤と深夜勤を挟んで深夜勤以外の割り付けをしない、及び▲４▼６日以上の連続勤務は禁止とする、の四点である。
また、妥協制約としては、▲１▼「休み」の次に「深夜勤」を割り付けない、▲２▼「準夜勤」、「日勤」、「深夜勤」をこの順に割り付けない、▲３▼日勤のリーダは３日間または４日間連続して割り付ける、及び▲４▼深夜勤を３日連続して割り付けない、の四点である。
【００３８】
（２）各曜日の割付け規則
各曜日の割付け規則についての絶対制約と妥協制約とは、それぞれ次の通りである。
絶対制約としては、▲１▼Ｓｔａｆｆ  Ｊ  は日勤と日勤リーダのみ、▲２▼Ｓｔａｆｆ  Ｓ  は土日休み、及び▲３▼Ｓｔａｆｆ  Ｔ  は土日休み、の三点である。
また、妥協制約としては、▲１▼Ｓｔａｆｆ  Ａ  は日勤以外割り付けない、及び▲２▼ＳｔａｆｆＡ  は土日休み、の二点である。
【００３９】
（３）必要人数に関する規則
必要人数に関する規則の絶対制約は、次の通りである。
絶対制約としては、▲１▼「準夜勤」に２人以上ランクＣの看護師を割り付けない、▲２▼「深夜勤」に２人以上ランクＣの看護師を割り付けない、▲３▼「準夜勤」に１人以上ランクＡの看護師を割り付ける、▲４▼「深夜勤」に１人以上ランクＡの看護師を割り付ける、及び▲５▼「日勤のリーダ」はランクＡもしくはＢを割り付ける、の五点である。
【００４０】
（４）割付け日数に関する規則
上記の規則の他に、▲１▼Ｓｔａｆｆ  Ａ  とＳｔａｆｆ  Ｊ  以外は出来るだけ公平に割り付ける、という割付け日数に関する規則を設けた。
次に、各実験で用いたパラメータを示す。局所探索／再作成の幅はＬＢＭ  ＝  ４と、染色体群内の個体数はＮ  ＝  ８と、突然変異パラメータはＰＢＭ＝  ０．０５と、サブ染色体群内の個体数ＮＣ  ＝  ２と、局所改善回数ＮＳＴ  ＝  １００と、探索変更確認周期ＮＸＴ＝  ５０と、大域突然変異回数ＮＬＴ  ＝  １００と、それぞれの数値を設定した。
【００４１】
ただし、ＬＢＭ  は解探索が停滞した場合に変化することとし、親個体の淘汰演算において染色体群内に新たなパレート最適個体が加えられない状態が１０回続く毎に、ＬＢＭ  を１増加させることとし、染色体群に新たなパレート最適個体が追加された場合は元の値に戻すこととした。
【００４２】
＜実施例１  ＧＡとヒューリスティクスの複合手法＞
上記したＧＡとヒューリスティクスとの複合手法の効果を調べた。また、ステップ２６の突然変異の効果についても併せて調べた。▲１▼交叉後にヒューリスティクスのみを用いた場合（ステップ２６を飛ばして実行した場合）、▲２▼交叉後にヒューリスティクスとステップ２６の突然変異を用いた場合、及び▲３▼交叉を行わずステップ２４のＬＢＭ日の局所部分をランダムに設定してヒューリスティクスとステップ２６の突然変異を行った場合、のそれぞれについて、得られる看護師勤務管理表を比較した。各方法の比較には、親個体の淘汰演算回数が５，０００回までの演算を５０回施行し、染色体群において式（６）による最良個体の評価値の平均を求め、初期個体からの平均評価値の改善値の推移を調べた。ただし、ステップ２１の判断を行わず、図９に示す染色体全体への一様な突然変異は行わなかった。
【００４３】
図１０及び図１１には、各実施例に用いたソフトウエアの表示画面を示した。本ソフトウエアには、三種類のメニュータブ１５が設けられており、それぞれ勤務表作成を実行させるメニュー画面（図１０）、勤務表設定用メニュー画面（図１１）、及び抽出ルール設定画面とされている。
【００４４】
このうち勤務作成実行用メニュー画面（図１０）の左欄１０には、２０名の看護師（Ｓｔａｆｆ＿Ａ〜Ｓｔａｆｆ＿Ｔ）が示されており、そこから右には、約一ヶ月分（例示する画面上には、３７日分）の勤務行程マトリックスデータ１１が示されている。また、このデータ１１の下欄１２には、各日についての日勤スタッフ数・準夜勤スタッフ数・深夜勤スタッフ数・リーダ数が示されている。更に、データ１１の右欄１３には、各看護師についての一ヶ月当たりの休日数・日勤数・準夜勤数・深夜勤数・リーダ担当数が示されている。
【００４５】
また、勤務表設定用メニュー画面（図１１）は、大きく５個の枠１６〜２０に分けられている。このうち最も左の枠１６は、各スタッフに関する設定（例えば、技能・リーダ適応・勤務割付の公平さ・最大連動数）がなされる。また、中央上枠１７では、特定のスタッフについての個別的な禁止勤務制約（例えば、▲１▼特定の曜日には勤務できない（或いは、日勤のみ可能）・リーダを４日間に渡って割付可能・深夜勤４日間連続は不可等の内容と、▲２▼その制約の優先度との組合せデータとなっている。）が設定できる。右上枠１８には、日勤・準夜勤・深夜勤・リーダについて、所定の技能（左枠１６において、各スタッフについて設定されたもの）を備えた者の上限数と下限数とが設定される。また、下枠１９，２０では、各曜日の日勤・準夜勤・深夜勤・リーダ・休みについて、最低割付数と最大割付数とが設定される。このようにして、勤務表設定用メニュー画面において設定された評価規則に基づいて、勤務作成実行用メニュー画面で所定の計算及びマニュアル処理がなされる。
【００４６】
図１２には、式（６）の総合評価値の改善値の推移を、図１３には、勤務日数の公平さのみの評価値の改善値の推移を、また図１４には、勤務日数の公平さを除いた評価値の改善値の推移を示した。この結果より、交叉が公平さの評価値の改善に効果があり、突然変異が公平さを除いた評価値の改善に効果があることが分かった。
【００４７】
＜実施例  ２  ヒューリスティクスの効果＞
交叉後の勤務系列の破壊の修復に、ステップ２０〜ステップ３０のヒューリスティクスを用いた場合と、ステップ６０〜ステップ７４のバクテリア突然変異を用いた場合とについて比較した。なお、ステップ２０〜ステップ３０のアルゴリズムでは、純粋にヒューリスティクスのみの効果を確認するために、ステップ２６の突然変異は用いなかった。また、ステップ２１の判断を行わず、図９に示す染色体全体への一様な突然変異は行わなかった。
【００４８】
各場合について、親個体の淘汰演算回数が５，０００回までの演算を５０回施行し、染色体群において式（６）による最良個体の評価値の平均を求め、初期個体からの平均評価値の改善値の推移を調べた。ただし、染色体全体への一様な突然変異（ステップ７８〜ステップ９０）は行わなかった。尚、実験パラメータである局所改善回数ＮＳＴは、親個体の淘汰演算回数を５，０００回行うために必要な演算時間が、それぞれの場合においてほぼ等しくなるようにするため、ＮＳＴ＝  １００とした。初期個体から評価値の改善値の推移を図１５に示した。
この結果、バクテリア突然変異に較べると、ヒューリスティクスの方が探索効率が良いことが示された。
【００４９】
＜実施例  ３  全体への突然変異の効果＞
次に、染色体全体への突然変異の効果を調べた。交叉後に、ステップ２０〜ステップ３０のヒューリスティクスと突然変異とを併用する場合のアルゴリズムについて、ステップ７８〜ステップ９２の染色体全体への一様な突然変異の有無の効果を調べた。染色体の評価演算回数が５，０００回までの演算を５０回施行し、染色体群において式（６）による最良個体の評価値の平均を求め、初期個体からの平均評価値の改善値の推移を調べた。但し、全体への突然変異を行う場合は、ヒューリスティクスを用いた交叉を行う場合に較べて、評価演算時間が約２０倍高速となることを考慮して、全体への突然変異が行われている時は、評価演算回数２０回を改めて評価演算回数１回とした。
【００５０】
図１６には、式（６）の総合評価値の改善値の推移を、図１７には、勤務日数の公平さのみの評価値の改善値の推移を、図１８には、勤務日数の公平さを除いた評価値の改善値の推移をそれぞれ示した。
この結果、染色体全体への一様な突然変異を加えることで、勤務日数の公平さに対する探索効率が向上することが判明した。但し、染色体全体への突然変異のみを加える手法では、探索効率が著しく悪くなってしまった。
【００５１】
＜考  察＞
本発明者らの検討によれば、交叉点近傍の勤務系列の修復にヒューリスティクスを組合せることで、勤務日数の公平さに対する効率的な探索が実現できることが示された。また、ヒューリスティクスと突然変異とを併用することにより、更に良好な結果を得ることができた。これは、手動作成にヒントを得たヒューリスティクスのみを用いるアルゴリズムでは、局所解に陥りやすいが、突然変異を併用することにより、そのような局所解を回避できたためと考えられた。
ヒューリスティクスのみを用いた場合に局所解に陥りやすい原因としては、ヒューリスティクスに関するアルゴリズムが不完全であるため、解の探索方向を誤ったためであると考えられた。しかし、本発明者らの検討結果によれば、事前知識を用いた探索であるヒューリスティクスに、確率的探索である突然変異を併用することで、ヒューリスティクスの不完全さを補うことができたことを示している。
【００５２】
以上の改善に、更に全体への一様な突然変異を加えることによって、勤務日数の公平さに対する探索の更なる効率化が示された。これは、全体への一様な突然変異が公平さのような大域的探索には効果があることを示唆している。
また、交叉点近傍の修復について、ヒューリスティクスを用いないで、バクテリア突然変異のみを行った場合では、探索性能はあまり良好ではないことが示された。
このように本実施形態によれば、複雑な評価規則を満足しつつ、かつ局所解に陥ることなく、比較的短時間で勤務時間の公平な看護師勤務表の作成を行うことが可能となる。
【００５３】
【発明の効果】
本発明者らの発明によれば、複雑な評価規則を更新しながら満足させつつ、局所解に陥ることなく、かつ比較的短時間で看護師勤務表を作成することができる。
【図面の簡単な説明】
【図１】具体的な看護師勤務表の一例を示す図である。図中の左欄（熟練度）中の、「Ａ」は熟練を、「Ｂ」は非熟練を、「Ｃ」は新人を示す。また、「日」は日勤（ＡＭ  ８：００〜ＰＭ４：００）を、「準」は、準夜勤（ＰＭ４：００〜ＡＭ０：００）を、「深」は深夜勤（ＡＭ０：００〜ＡＭ８：００）を示す。
【図２】対話型看護師勤務表作成支援システムの概要を示す図である。
【図３】実施形態に記述した看護師勤務表作成支援システムによる勤務表の作成手順を示す図である。
【図４】ＢＥＡとヒューリスティクスとの複合手法による看護師勤務表作成支援ソフトウエアのアルゴリズムを示す図である。
【図５】ＢＥＡとヒューリスティクスとの複合手法による看護師勤務表作成支援ソフトウエアのフローチャートである。
【図６】手動作成をモデル化したヒューリスティクスのフローチャートである。
【図７】
交叉点近傍の修復にバクテリア突然変異を用いた手法のアルゴリズムを示す図である。
【図８】交叉点近傍の修復にバクテリア突然変異を用いた手法のフローチャートである。
【図９】全体への突然変異を加えるためのフローチャートである。
【図１０】各実施例を実行したときに用いたソフトウエアの実行用メニュー画面１である。
【図１１】各実施例を実行したときに用いたソフトウエアの実行用メニュー画面２である。
【図１２】実施例１において、
総合評価値の改善値の推移を示すグラフ図である。なお、図中■は、交叉とヒューリスティクスと突然変異とを併用したアルゴリズム、▲は、交叉とヒューリスティクスとを併用したアルゴリズム、×は、ヒューリスティクスと突然変異とを併用したアルゴリズム、を用いてそれぞれ計算したときの結果を示す。
【図１３】実施例１において、公平さ評価値の改善値の推移を示すグラフ図である。なお、図中の記号の意味は、図１２と同様である。
【図１４】実施例１において、公平さを除いた評価値の改善値の推移を示すグラフ図である。なお、図中の記号の意味は、図１２と同様である。
【図１５】実施例２において、評価値改善値の推移を示すグラフ図である。なお、図中◆は、交叉とヒューリスティクスとを併用したアルゴリズム、■は、交叉とバクテリア突然変異とを併用したアルゴリズム、を用いて、それぞれ計算したときの結果を示す。
【図１６】実施例３において、
総合評価値の改善値の推移を示すグラフ図である。なお、図中◆は、交叉とヒューリスティクスと突然変異と全体変移とを併用したアルゴリズム、■は、交叉とヒューリスティクスと突然変異とを併用したアルゴリズム、を用いてそれぞれ計算したときの結果を示す。
【図１７】実施例３において、公平さ評価値の改善値の推移を示すグラフ図である。なお、図中の記号の意味は、図１６と同様である。
【図１８】実施例３において、公平さを除いた評価値の改善値の推移を示すグラフ図である。なお、図中の記号の意味は、図１６と同様である。
【図１】
2004151790.tif 000003
【図２】
2004151790.tif 000004
【図３】
2004151790.tif 000005
【図４】
2004151790.tif 000006
【図５】
2004151790.tif 000007
【図６】
2004151790.tif 000008
【図７】
2004151790.tif 000009
【図８】
2004151790.tif 000010
【図９】
2004151790.tif 000011
【図１０】
2004151790.tif 000012
【図１１】
2004151790.tif 000013
【図１２】
2004151790.tif 000014
【図１３】
2004151790.tif 000015
【図１４】
2004151790.tif 000016
【図１５】
2004151790.tif 000017
【図１６】
2004151790.tif 000018
【図１７】
2004151790.tif 000019
【図１８】
2004151790.tif 000020