ナーススケジューリング問題に対するペナルティ法の実験的評価（野中）

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

病院の病棟ナースの勤務表を作成する最適化問題のことをナーススケジューリング問題といいます。人の命に関わる現場で、看護の質を守りながら、ナースの健康状態をも考慮する勤務表作成は、責任が重く、時間を費やす困難な問題として有名です。

• 入力：計画期間、ナースの人数、制約条件
• 出力：全ナースの全期間に関する勤務表

上の表は、勤務表の例です。勤務表作成時には、様々な制約が与えられます。大きく２種類の制約に分けられます。

• 横の制約：ナースの健康状態を考慮する制約
  例）「連勤は5日まで」「夜勤後の日勤は禁止」など
• 縦の制約：看護業務の質を保つための制約
  例）「土曜日は日勤が5人、夜勤が4人必要」など

横の制約は必ず満たす必要があり、縦の制約は満たせなかった場合に違反点数が発生します。縦の制約による違反点数の合計を目的関数とし、最小化します。

提案手法

1人の看護師について、最適なスケジュールを新たに決定していく操作を全ナースに対して繰り返すことで、解を改善していきます。

探索の際、縦の制約の充足具合を点数で保持し、この点数をもとに最適な1人のスケジュールを決定していきます。

計算機実験と評価

計画期間、ナースの人数、シフトタイプの数など様々な入力のベンチマークに対して、計算機実験を行いました。

比較対象として数理最適化ソルバーのSCIPというものを用いました。

その結果、評価値に関してはSCIPより悪い結果になりました。入力のスケールが大きくなるほど、SCIPとの差が大きくなったので、問題を分割して解く手法やSCIPを利用した手法の考案などを今後の取り組みとして考えています。