3M-4

情報処理学会第66回全国大会

ナーススケジューリングシステムにおける動的重み付き CSP に基づく再スケジューリング機能の実装
磯村 厚誌

伊藤 孝行

大囿 忠親

新谷 虎松

名古屋工業大学 大学院 工学研究科
e-mail: {isomura,itota,ozono,tora}@ics.nitech.ac.jp

1

はじめに看護勤務の予定表作成時には，看護師は数週間先の要望まで提示する必要がある．先の予定になるほど予測できない要求が発生する可能性は高く，要求を満たすには再スケジューリングの必要がある．しかし，看護勤務表の満たすべき条件が複雑であるため，小さな予定変更が大幅な変化をもたらすことになり，再スケジューリングは非常に困難なタスクとなる．
そこで本稿では，動的重み付き CSP に基づき再スケジューリングを視野に入れたナーススケジューリングシステムを提案する．問題の変化を表現する枠組みである動的 CSP と，制約毎の重用度を扱う重み付きCSP の特長を活かし，安定して看護勤務予定を提供できる再スケジューリングを実現した． 本稿では，２章でナーススケジューリング問題について述べ，３章において動的重み付き制約充足問題にもとづく定式化を行う．４章ではナーススケジューリングにおける再スケジューリングを実現し，５章で実験により評価を行う．そして最後に本研究についてまとめる．

2

ナーススケジューリング問題

本システムの対象とする看護勤務表は３交代制と呼ばれるものであり，一日を日勤，準夜勤，及び深夜勤の３つの勤務シフトに分ける．図 1 に我々が実装したシステムが扱う勤務表の例を示す．

図 1: スケジューリングシステムによる看護勤務表
勤務表中では行に看護師を示す ID，列には日付が対応している．各セルにはそれぞれ，▲：日勤，■：準夜勤，▼：深夜勤の値が割り当てられ，空白のセルには休日が割り当てられている．
勤務表作成の際には毎日の各勤務の人数，各看護師に予定される勤務シフトの回数，禁止される勤務パターン及び個人の要望等の条件を考慮した割り当てを実現する．禁止される勤務パターンには， 深夜勤後の日勤 ， 深夜勤後の準夜勤 及び 準夜勤後の日勤 等があり，排除が望まれるパターンに， ４連続準夜勤 ，５連続日勤 ， １日のみ孤立した深夜勤 及び 前後が休日となる孤立した勤務 が挙げられる．
Implementation of Re-schedulable Nurse Scheduling System based on Dynamic Valued Constraint Satisfaction Problem
Atsushi Isomura, Takayuki Ito, Tadachika Ozono, Toramatsu Shintani
Graduate School of Engineering, Nagoya Institute of Technology, Gokiso-cho, Showa-ku, Nagoya 466-8555,

3

DyVCSP に基づく定式化

3.1

動的重み付き制約充足問題 (DyVCSP)

状況が変化する問題を考慮した枠組みとして本システ
ムでは動的 CSP[Dechter 88] の考えかたを導入した．また，要望や規則などを区別するために制約の重用度も考慮する．そこで重み付き制約を考慮した動的 CSP を動的重み付き制約充足問題 (Dynamic Valued Constraint
Satisfaction Problem : DyVCSP) とし，DyVCSP に基づきナーススケジューリング問題の解決を試みる．
DyVCSP は重み付き CSP(VCSP) の列で表される(式 1)．

P = {V P0 , V P1 , ..., V Pi , ...}

(1)

V Pi は時刻 i における VCSP であり, V Pi+1 は V Piに対して変化を加えた問題となる．VCSP は，V Pi =(Xi , Di , Ci , S, ϕ) の構造を持つ．(Xi , Di , Ci ) は通常のCSP と同じく，変数，値域及び制約の集合である．S及び ϕ は評価構造と評価関数であり，DyVCSP 全体を通して一定である．

3.2

ナーススケジューリング問題の定式化

ナーススケジューリング問題を DyVCSP に基づいて定式化するにあたって，時刻 i の VCSP における(Xi , Di , Ci ) を次のように定める：変数 xst ∈ Xi は看護師 s の t 日の予定とする．すなわち，勤務表のセルに対応する．値域は全変数共通で dst = □, ▲, ■, ▼ ∈ Diとする．制約の集合 C は勤務表を作成する際の条件を基に作成し，1 日に必要な人数，看護師の勤務回数，禁止パターン及び特定変数への要望を表現する．評価関数 ϕ は，重用度が制約の追加時に指定されるので，この値を参照しコストを求める．評価構造 S については，評価値は整数とし，オペレータを通常の加算とする．
DyVCSP における各 VCSP の変化は，変数，値域及び制約の変化による．しかし，本システムでは値域が□, ▲, ■, ▼の 4 値から変更されることはない．また，スケジューリングの期間を一定とし，変数にも変化は発生しない．ナーススケジューリングを DyVCSPとして定式化するにあたって，V Pi に発生し得る変化は主に制約の追加と削除による．

4DyVCSP に基づく再スケジューリング

4.1

安定した解の生成

通常の動的 CSP の目標は主に２つある．一つは，各CSP の計算すなわち i 番目の問題 Pi から i + 1 番目の問題 Pi+1 の解を得るまでの計算を効率化することである．そしてもう一つは，Pi から Pi+1 の解の変更を少なく解決することであり，後者の性質は解の安定性(stability) と呼ばれる．

2−75

既存の動的 CSP の解決手法には計算の効率化のみを目的とするものも存在し，動的 CSP の第一の目的は計算効率にある．しかし，本システムにおける再スケジューリングは短期間に頻発するものではない．また，変更の度に人間がスケジュールを確認する必要があるため，解の安定性を重視した解決を試みる．そこ
で本研究では，状況の変化に対しても常に安定したスケジュールを得るために，各変数に対して以前の解である割り当てと同じ値をもつという重み付き制約を付加する．すなわち，安定した解を得ること自体を重み付きの制約として追加する．

4.2

再スケジューリング機能の実現

本システム重み付き CSP の特長を活かし，解の安定性を得ること自体を重み付き制約として一時的に問題を変更する．具体的には，急な用件等で要望に変化が生じたとき，対応する変数に関する制約が追加され，問題 V Pi が問題 V Pi+1 に変化する．安定して解を得るために，本システムでは次の Step1 から Step4 の手順に従い問題 V Pi+1 の解を求める．

Step 1: 新たに追加された制約 cnew を V Pi に追加し，V Pi+1 とする．
Step 2: 全ての変数に関して，前回の結果と同一であるという制約 Ctmp を，V Pi+1 に追加し，V Pi+1とする．変数 xij の前回の割り当てを vij とすると {xij = vij } を指定する制約が追加される：Step 3: 問題 V Pi+1を stochastic hill climbinig により解決する．Step2 の制約 Ctmp により，問題
V Pi+1を解くとで安定した解を得ることができる．

Step 4: 安定性を得るために追加された制約 Ctmp のうち，満たされた制約全てを CSP から削除する．
から V Pi+1
後の状況の変化に備え，問題を V Pi+1へと戻す．
一般的な動的 CSP の解決手法と大きく異なる点は，解の安定性を得るために CSP の解決アルゴリズムを工夫するのではなく，問題そのものにさらに変更を加えたことにある．Step1 で制約 cnew を追加することによって変化した問題 V Pi+1 に，Step2 でさらに制約Ctmp を加え，解くことで安定性も満たすことが保証される問題 V Pi+1へと一時的に再度変換している．本システムで処理する VCSP の列は式 (2) のようになる：
P = {V P0 , V P1 , V P1 , ..., V Pi , V Pi+1, V Pi+1 , ...}

5

評価・実験

5.1

実験の概要

(2)

本システムの有用性を示すため，以下の条件の下で実験を行なった．スケジューリングの対象期間を一週間，人数を 10 人とする．1 日の各勤務に必要な人数 (日勤：3〜6 人，準夜勤：2〜4 人，深夜勤：1〜3 人)，看護師の各勤務回数 (日勤及び準夜勤 1 日以上，深夜勤 2 日以内，休日 1〜2 日) 及び禁止パターンに関する制約を与える．加えて特定変数に対する要望を表す制約をランダムに 5 つ追加した問題を，時刻 i の時点での問題
Pi と考える．Pi の解をあらかじめ求めておき，Pi+1への変化を対象に実験を行う．

図 2: スケジューリング結果の比較

Pi に対し，ある特定の看護師に緊急の変更要請がある場合を仮定し再スケジューリングを行なう．変更を要求する制約は，変数はランダム，勤務シフトは現在の値以外の値を指定する．変更を要求する制約を 1〜5個追加し問題を Pi+1 とした場合について，Pi の解から変化する変数の割合を計測する．
の解決には Pi の解の情報は用本手法における Pi+1いず，休日と夜勤を優先的に配置し初期値を得る． 初期値利用法を用いて Pi+1 を解いた場合の stochastic
hill climbing との比較を行った．また，それぞれの手法による効果を確かめるために，解の安定性を意識せずにスケジューリングした場合との比較も実施した．

5.2

実験結果

本実験の結果を図 2 に示す．グラフの横軸は追加される制約数である．縦軸は制約追加前の解から変更された変数の割合であり，それぞれの条件下での 10 試行の平均である．変更の割合は，要望のある変数を除いた変数のうち，Pi の解から変更された割合である．図2 より，本手法により再編集される勤務表の変化が小さく済むことがわかる．初期値利用法を用いた場合では，追加制約が少なく問題の変化が小さい場合には効果が見られるが，問題が大きく変更されるケースでは安定性を意識しない場合と比べてもわずに１割程度の差しか見られない．本手法では問題が複雑になった場
合でも予定の変更は 2 割程度に抑えられている．

6

おわりにDyVCSP に基づナーススケジューリングシステムを実装し，看護勤務表における再スケジューリングの可能性を示した．再スケジューリング後の勤務表は，5 つまでの複数の制約を加えた場合にも変更前の割り当てを 8 割以上維持することが出来た．

参考文献[Dechter 88] Dechter, R., and Dechter, A., “BeliefMaintenance in Dynamic Constraint Networks”.
In Proc. of AAAI-88 , pp.37–42, 1988
[Verfaillie 94] G. Verfaillie, and T. Schiex: Solution Reuse in Dynamic Constraint Satisfaction
Problems. Proceedings of the Twelfth National
Conference on Artificial Intelligence, pp.307-312,
1994

2−76