The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

1D1-03

制約充足問題によるチームを考慮した
ナーススケジューリングシステムの実装
An Implementation of a Nurse Scheduling System with a Team Structure Using CSP
山口翁央∗1

大囿忠親∗1伊藤孝行∗1新谷虎松∗1

Toshihiro Yamaguchi

Tadachika Ozono

Tkayuki ItoToramatsu Shintani∗1

名古屋工業大学

大学院工学研究科

情報工学専攻Dept. of Computer Science and Engineering Graduate Scool of Engineering, Nagoya Institute of Technology

We propose a novel constraint satisfaction problem (CSP) for constructing a nurse scheduling system introduced
fixed team nursing. There is a problem that isn t to be able to do responsible nursing in an existing nursing
form. The fixed team nursing is one of the new nursing forms for solving the problem. Then, we think about
the construction of the nurse scheduling system that can consider the fixed team nursing. The system can beconstructed by adding the constraint of the fixed team nursing to an existing system. However, it is difficult toobtain the result of considering fixed team nursing in the method, because the constraint of the fixed team nursing
is buried in other constraint. Then, we propose a novel CSP that the fixed team nursing can be considered. It isshown for the computational speed to improve by introducing the new CSP more than an existing system, and to
be able to consider fixed team nursing .

1.

はじめににおける実験および評価について示し，最後に本研究についてまとめる．

近年，看護の世界では患者によりよい看護を行なうため新たな看護形式を取り入れよう，という動きが活発になっている．
従来の看護形式では，患者の家族とお互いに信頼関係ができず，後々まで悔恨を残すことになってしまったケースも報告されている [6]．問題の原因は患者に対して受持ち看護師を決めても，1ヶ月に実際に受持ち患者を担当することは 4〜5 日しかないことである．そのため，受持ち看護師となっても看護に責任を持つことができない．この問題を解決し，よりよい看護を実現するための看護方式の 1 つとして固定チームナーシン
グがある．実際に固定チームナーシングを導入した結果，自分自身の看護に対する責任を持つことができ，仕事のやりがいが向上したなどの成果が文献 [6] より報告されている．そこで，
本研究では従来の看護形式だけでなく，固定チームナーシングを考慮可能なナーススケジューリングシステムを構築する．
固定チームナーシングを考慮するための手法としては，固定チームに関する制約を既存にあるナーススケジューリングシステム ([2], [7]) に加えることで簡単に実現することができる．
しかし，固定チームナーシングの制約が既に設定されている他の制約の中に埋もれ，固定チームナーシングを考慮した解を得ることが難しい．また，制約の増加によりさらなる過制約となってしまうことで，実用的時間で実用に堪えうる解を得ることが困難になる．そこで，本論文では固定チームナーシングを考慮でき，実用可能な時間内で解を得られるナーススケジューリングシステムを構築するため，新たに提案した制約充足問題の枠組みを用いて実装を行なう．
本論文の構成は以下の通りである．2 章では，ナーススケジューリングにおける問題を明示し，本システムが勤務計画表作成のための条件を定義する．3 章では，本研究が提案する新たな制約充足問題について説明し，4 章では，実装したナーススケジューリングシステムについて述べる．5 章では，本研究2.

ナーススケジューリング

看護師勤務計画表作成問題は，それぞれの看護師を各日付に関してそれぞれに適切な勤務シフトを割り当てる問題であり，最適化問題の 1 つである．看護の勤務形式には，1 日を 3つの勤務に分ける 3 交替制と 2 つの勤務に分ける 2 交替制がある．本論文では 3 交替制として実装した．3 交替制は勤務シ
フトを日勤, 準夜勤, および深夜勤に分ける．勤務計画表の例を図 1 に示す．勤務計画表は行に看護師を示す ID，列には日付が対応している．各セルではそれぞれ，日勤を”●”，準夜勤を”▲”，深夜勤を”■”を深夜勤，休日を空白として表現する．
看護師勤務計画表作成における問題は，勤務計画表作成において考慮するべき条件が厳しいことが挙げられる．本論文では，文献 [5] に従い，勤務計画表作成において考慮する条件として 5 つの条件を用いる．(1). 毎日の各勤務において必要な人数を確保する．(2). 技術レベルなどを考慮し勤務メンバーを構成する．(3). 看護師の各勤務回数は決められた範囲に抑える．(4). 他の業務や休みの希望を達成する．(5). 禁止される勤務パターンを入れない．以上の 5 つの条件をすべて満たすことは困難であり，すべての条件を満たす解が存在しない過制約な問題となる．そこで，条件ごとに異なる重要度を設定し，重要度が最も高い値を可能な限り求めることが本研究の目標となる．

2.1

固定チームナーシング

固定チームナーシグは文献 [6] により５つの定義がある．

(定義 1) リーダーとメンバーを一定期間 (1 年以上) 固定し，役割と業務を明確にしてチーム活動をする
固定する期間を 1 年以上とするのは，チームの成熟，リーダーの育成のために時間が必要だからである．

(定義 2) 各チームは年間目標をもつ

連絡先: 山口翁央，名古屋工業大学 大学院工学研究科 情報工学専攻 新谷研究室，〒 466-8555 愛知県名古屋市昭和区御器所町，電話番号 052-735-7968，Fax 052-735-5477，
okina@ics.nitech.ac.jp

チーム活動には必ずチーム目標がある．目標をもって活動することで，方向性が明確になりチームが一体感をもって協力することができる．

1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

看護領域

看護チーム

...

看護師個人

図 2: 看護組織図

制約 c による A の評価値は以下のように与えられる．

½
ϕ(A, c) =図 1: 看護師勤務計画表の例⊥ϕ(c)if c is satisfied by Aotherwise(1)

そして，A の全体の評価値は以下のように定義する．

(定義 3) 各チームは患者グループを継続して受持つ

ϕ(A) =患者すべてではなく，患者をグループ分けすることによって，半分あるいは 3 分の 1 を把握し，個別性のある看護を提供する．

(2)

VCSP の V P の解は，V P の全変数 Xn への値割当ての中で違反している制約の重みの総和が最小となる値割当てである．

3.2

階層的 VCSP

本研究では固定チームナーシングを考慮する．看護組織における階層構造を問題に表現するため，本研究では階層的CSP(Hierarchical CSP : HCSP)[3] の枠組みを導入する．また，ナーススケジューリングは過制約な問題であり，各看護師の要望なども満たす必要がある．そこで，本研究では，制約に重みを付加し，違反する制約の重みの合計を最小化されるように解を求める HCSP，つまり固定チームナーシングを解く枠組みとして階層的重み付き CSP(Hierarchical Valued CSP: HVCSP) を定義する．
階層は制約 C の有限の分割により HPi = (Xn , Dn , Ci , S, ϕ)として定義される．Xn , Dn , S, ϕ は VCSP と同じく，変数の集合，値域，評価構造および評価関数を表す．制約 Ci は階層 Hiにおける制約を表す．階層の順序関係は制約 Ci の ≺i によって順序関係が決定する．すなわち，H0 ≺0 H1 ≺1 H2 ≺2 H3 ...
が成り立つ．順序関係は制約の重要度によって決まる．制約の重要度が高いほど上部の階層へいく．制約の重要度が高いものを上層部にもっていくことで，重要度の高い制約を低い制約に比べて，より考慮することが可能になる．HVCSP の解は最も上の階層において，全変数 X への値の割当ての中で違反している制約の重みの総和が最小となる値の割当である．

個々の患者には継続する受持ち看護師が存在する．各看護師には受持ちの患者がおり，その人を中心になって看護診断をしてナーシングプランを立案する．しかし，受持ち看護師が不在の時がある．そのときに，責任をもち継続した看護を支援しいくのがその看護師が所属する固定チームである．

(定義 5) 年間チーム活動と日々のチーム活動があり，応援機能をもつ固定チームナーシングであっても，他のチームに応援勤務をしなければならないことが時々起こる．他のチームに応援に行った時でも，患者チャートの記録や日常業務等の必要情報が提示されていれば，問題なく業務を行なうことができる．

CSP

CSP とは，与えられた制約を全て満たすように変数の値を割当てる問題である．CSP は (Xn , Dn , Cm ) で定義される．Xnは有限な変数の集合である．Dn は離散値を要素とする変域の有限集合であり，変数 Xi は変域 Di の要素の 1 つを割当てられる．Cm は CSP の制約の集合である．Cm をすべて満たした Xn への値割当が CSP の解である．制約の表現方法によって様々な問題を解くことができる．

3.1

ϕ(A, c).

c∈C(定義 4) 個々の患者には継続する受持ち看護師が存在し，固定チームが支援する

3.

X

重み付き CSP

重 み 付 き CSP(Valued CSP : VCSP)[4] は V P =(Xn , Dn , Cm , S, ϕ) と表される．(Xn , Dn , Cm ) は通常の CSPと同じく変数，値域および制約の集合である．S = (E, Σ, ≺)は評価構造であり，ϕ = C → E は評価関数である．E は問題で使用する評価値の集合であり，最小値と最大値をそれぞれ⊥ と > する．また E の全要素は ≺ によって順序関係が定義される各制約による評価値は ϕ によって得られる．Σ は評価値の総計である．ここで，A を全変数への割り当てとすると，

4.

ナーススケジューリングシステム

4.1

HVCSP に基づく定式化

本節は，2 章で述べたナーススケジューリング問題を HVCSPとして定式化する．本研究が対象としている看護の組織は図2 に示す構造となっている．本システムでは看護組織の構造を利用することにより HVCSP へ適用する．すなわち，看護部全体を最上位の階層とし，次に看護チーム，そして看護師個人を最下層とする．変数の集合 Xi = {x1 , x2 , ..., xn } の各要素は，各日付における各看護師の勤務内容を表すとする．つまり，各変数は図 1 に示した勤務表の各セルに対応する．Di は変数の値域集合を表し，本システムにおいては全変数で値域は共通のものとし，di = 0, 1, 2, 3 ∈ Di とする値域のそれぞれの2

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

図 4: チーム編集画面
図 3: チーム編集画面

4.3
値は，”0”が休日，”1”が日勤，”2”が準夜勤，”3”が深夜勤である．また評価構造 S = (E, Σ, ≺) に関して，E は整数の集合であり，⊥ = 0, > = 9 である．また，≺ は通常の全順序関係とする．以上より，全変数への完全な値の割当を A とすると，φ(A) は違反制約の重みの和となる．つまり，本システム
は φ(A) が最小となる全変数への値割当を探索することが目標となる．
制約 Cm の形式を limit(min, max, List, w) として定義する．ここで，min および max は，全変数に割当てられた値の集合 Ai と List を比較した場合に，一致する要素数の下限と上限を表す．List は制約が要求する任意の変数の集合である．w は制約の重みであり，0 9 の整数値を取る．制約は Ai と List の間で一致する要素数 n が，min ≤ n ≤ max である場合にのみ充足される．具体的には，ある看護師がスケジューリングの対象期間中に，休日を 5 回以上，かつ 8 回以下を希望する場合の制約は以下のように記述できる．limit(5, 7, x0 = 0, x1 = 0, ...,, 6)
この制約は 0 の値を割当てられた変数の数が 5 以上 8 以下である場合に充足されることを意味する．また，この制約が違反された場合は 6 のコストが加算される．本形式による制約の表現は，本研究におけるナーススケジューリングを取り扱う制
約のすべてを表現可能にする．

4.2

解探索手法

制約充足問題における解を探索する手法として文献 [1] による確率的山登り法 (Stochastic Hill-Climbing : SHC) によって解を探索する．全探索を行なうとナーススケジューリングの計算量は以下のように表すことができる．
計算量 = 勤務の種類数(看護師数∗スケジューリング期間)

ナーススケジューリングシステムのインタフェース

看護師勤務計画表を見やすくするため，本システムには”管理”, ”全景”, ”今週”, ”本日”の種類別によるインターフェースがある．”管理”は図 1 であり，各日付の勤務数，各看護師の勤務数を用意に確認でき，勤務計画表を管理することに適している．”全景”は，勤務計画表の概観を知るために，作成した勤務計画表を一覧で見ることができる．”今週”は，今週の勤務計画表を見るためのものである．今週の勤務計画における変更点や誰がどの日に勤務するのか分かりやすく表示する．”本日”は，本日の勤務計画表を表示する．本日の勤務でどの看護師がなんの勤務をしているのかすぐに確認することができる．
本システムではチームを作成する際に，はじめにチーム数を決める．チーム数は文献 [6] に従い，チームの人数が平等で，かつチームの人数が 10 人程度にして決定する．チームを編集するために本システムは図 4 に示すインターフェースが用意されている．チーム編集では 1 人の看護師がチームに重複しないように XOR 制御されている．また，チームを選択していない看護師がいれば，その看護師を知らせてくれる誤動作防止機能もある．
本システムには勤務表の管理を支援するための機能がある．
看護師の希望した勤務が満たされていれば，対応するセルの背景色を赤色に変更して表示する．また，事前に変更できないとわかっている勤務は，セルの背景色を緑色に変えるて勤務計画表に表現する．勤務表が決定した後に，看護師から変更の要求があって，再スケジューリングを行なう必要が生じることがある．看護師の要望を充足したために，他の勤務に影響がでたセルを黄色の背景色に変更して勤務計画表に表示する．加えて，勤務シフトの各値ごとにセルの色を変化させて表示可能であり，勤務計画表を確認や管理をするときに有効な機能である．

(3)

勤務の種類数は 3 交替制の場合 4 となる．看護師数を 15，スケ
ジューリング期間を 30 日間とする場合の計算量は約 1.0∗10271である．この計算量では解を得るために非常に膨大な計算時間を必要とする．そこで，実用に堪えうる時間内において解を探索するため SHC を用いる．SHC は状態を確率的に遷移することで，局所最適解を回避するアルゴリズムである．SHC のアルゴリズムを図 3 に示す．SHC は，P = 1/(1 + exp(∆/T )) によって計算される確率を用いて状態の遷移を行なう．∆ は制約違反数の変化量である．T が無限大の極限であれば，P = 0.5となりランダム探索になる．T が 0 の極限では，状態遷移に確率的な要素がなくなる．この SHC で重要となる T の値は問題によって依存する．

5.

実験・評価

5.1

実験概要

本提案手法を検証するため，我々の研究室で以前開発した文
献 [7] のナーススケジューリングシステムにおける制約充足問
題 DyVCSP との比較実験を行なう．実験は以下に示す条件で行なった．スケジューリング期間を 1ヶ月，看護師の人数を 15人とする．チーム数は A チームと B チームの 2 つのチームに分けた．本システムの勤務計画表は技術レベルが等しい看護師を扱うものとする．各日においては日勤，準夜勤および深夜勤に必要な人数を設定する．以下の条件を表す制約のもとで勤務計画表を作成した．

3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

HVCSP
DyVCSP

5.2

表 1: 実験結果
平均計算速度 (s) 平均制約違反度 (%)
1120.521320.49

結果と考察

本実験に使用した計算機は OS : Windows2000, AMD
Athlon(tm) XP 1700+, メインメモリ 512MB である．表 1
から，本手法による計算速度は DyVCSP に比べ早くなる結果が得られた．しかし，制約違反度では，本手法より DyVCSPによる手法の方が優れていた．図 5, 6 はスケジューリング結果の一部を示す．図 5, 6 から，HVCSP ではチームにおける制約をほとんど満たしているが，DyVCSP は満たしていない箇所が見受けられる．つまり，チームを考慮する上で本手法を取り入れることによって，解探索の効率が向上し，チームの制約を十分に満たした解が得られると考えられる．

図 5: HVCSP によるスケジューリング結果

6.

まとめと今後の課題

本論文では，階層構造を取り入れた HVCSP の枠組みを用いてナースケジューリングシステムを構築した．HVCSP によって以前のシステムに比べ計算効率を向上し，またチーム条件を十分に考慮できることが分かった．しかし，制約の違反部分が以前に比べ増加してしまった．今後は，HVCSP による制約違反部分をどうすれば減少させることができるか検討していく必要がある．

参考文献[1] Ackley, D. H. : ”A Connectionist machine for Genetic
Hillclimbing, Kluwer Academic Publishers, 1987.
[2] S. Abdennadher and H. Schlenker, ”Nurse Schedulingusing Constraint Logic Programming”, Eleventh Annual Conference on Innovative Applications of Artificial Intelligence, IAAI-99, 1999.

図 6: DyVCSP によるスケジューリング結果

必ず満たすべき条件 (重要度が高い)
1 日の各勤務に必要な人数をみたすこと．日勤は 4〜6 人，
準夜勤は 2〜4 人，深夜勤は 2〜3 人である．勤務の禁止パターンを，”深夜勤後の日勤”，”深夜勤後の準夜勤”，”
準夜勤後の日勤”，および”3 連続深夜勤”とした．チームの制約は各チームから日勤を２名以上，準夜勤を１名以上，深夜勤を１名以上必要とする．

[3] Hofe, H. M. : ”ConPlan/SIEDAplan: Personnel Assignment as a Problem of Hierarchical Constaint Satisfaction”, in Proc. of the 3rd International
Conference on Practical Applications of COnstraintTechnologies(PACT-97), pp.257-272, 1997.
[4] T. Schiex, H. Fargier, and G. Verfaillie, ”Valued constraint satisfaction problems: Hard and easy problems”, in Proc. of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), 631-637,1995.

満たすことが望ましい条件 (重要度が低い)
看護師の各勤務回数および休日の日数に関する条件である．日勤を７日以上，準夜勤を 5 日以上，深夜勤を 4 日以内とした．また，ないこと望ましい勤務パターンを”4連続夜勤”，”5 連続日勤”，”前後が休日となる勤務”として条件を設定した．

[5] 池上 敦子, 丹羽 明, 大倉 元宏, ”我が国におけるナース・スケジューリング問題”, オペレーションズ・リサーチ,
Vol.41, No.8, pp. 436-442, 1996.

比較実験を行なうため，解を得るまでの計算速度と得られた解の制約違反の程度 (制約違反度) を測定した．制約違反度
は，(制約違反数)/(制約総数)，で与えられ，すべての制約のうちどれだけ違反した制約があるかを示す．測定結果は表 1 に示す．

[6] 西本 勝子, 杉野元子, ”固定チームナーシング 責任と継続性のある看護のために”, 出版：医学書院, 1999.
[7] 山口翁央, 伊藤孝行, 新谷虎松, ”安定した再スケジューリングが可能な看護師勤務スケジュール管理支援システムの実装”, 第 18 回人工知能学会全国大会論文集, 2004.

4