成 膜 大 学 理 工 学 研 究 報 告 J,Fac.Sci、Tech.,Sei/keiUniv. Vol.48No.2(2011)pp.111-114 (特 別 研 究 費 に 係 る 論 文)
ナ ー ス ス ケ ジ ュ ー リ ン グ に お け る 探 索 空 間 の ネ ッ トワ ー ク 表 現
秋 田 博 樹*1,池 上 敦 子*2A Network Representation of the Search Space for Nurse Scheduling
Hiroki AKITA * 1, Atsuko IKEGAMI * 2
ABSTRACT : Nurse scheduling is a difficult combinatorial problem. Moreover, it is difficult to evaluate solutions because many of the constraints are subconsciously considered and not specified. Therefore, techniques that can easily grasp the size of the solutions space and the possibility of modifying a schedule are needed. In this work, we consider a subproblem of nurse scheduling to determine the optimal schedule for a nurse. We then represent all the feasible schedules of a subproblem as a network structure. In this structure, each node and each path represent a 7-day schedule and a feasible schedule, respectively. We develop a scheduling algorithm by using the networks created for each nurse and present two types of reduced networks that can help the scheduler create and modify a schedule
Keywords : nurse scheduling, search space, network, dynamic programming
(Received August 31, 2011) 1.は じ め に ナ ー ス ス ケ ジ ュー リン グ(病 棟 ナ ー ス 勤 務 表 作 成)は, 実 行 可 能解 を 見 つ け る こ と も難 しい 組 合 せ 問 題 と して 知 られ て きた1)。 さ らに,ど の 拘 束 条 件 を重 視 す べ きか, 何 を 持 っ て 最 適 な 勤 務 表 とす るか の 定 義 も難 しい 。一 方, 近 年 の 最 適 化 ソル バ ー の 高性 能 化 か ら,評 価 尺 度(目 的 関 数)を 明 確 に 与 えれ ば,厳 密 最 適解 を 得 る こ と も可 能 とな り2),今 後 の 研 究 の 興 味 は,暫 定 利 用 した 目的 関 数 が 与 え る最 適解 を ど う評 価 す るか や,与 え られ た 解 の 修 IE可 能 性 を ど う把握 す るか に 向 か うと考 え られ る。 本研 究 で は,勤 務 表 作 成 ア ル ゴ リズ ム の 構 築 だ けで な く,ナ ー ス 毎 の ス ケ ジ ュー ル 修 正 の 可 能性 を 把 握 す る仕 組 み構 築 の た め に,1ナ ー一一ス の 最 適 ス ケ ジ ュー一一ル を求 め る問題(ナ ー一一ス ス ケ ジ ュー一一リン グ にお け る部 分 問題3)) を扱 う。 動 的 計 画 法 の 考 え方 に 基 づ き,ナ ー ス 毎 の 部 分 問 題 の 全 実 行 可 能解 を ネ ッ トワー ク構 造 で 表 す こ とに よ り,部 分 問 題 の 最 適 解 を高 速 に 得 る こ と に加 え,部 分 問 題 の 実 行 可 能解 集 合 の 大 き さや 特 徴(偏 り等)を 把 握 で き る仕 組 み を 実 現 す る。 ま た,ネ ッ ト ワ ー ク の サ イ ズ が 大 き く な っ た 場 合 の 可 視 化 に つ い て も議 論 す る 。 本 稿 で は,探 索 空 間 が 膨 大 と な る3交 替 制 ナ ー一一ス ス ケ ジ ュ ー リ ン グ の 部 分 問 題 ネ ッ ト ワ ー ク の 構 築 を 示 す 。 2.ネ ッ トワ ー ク 表 現 の た め の 定 式 化 *1:理 工 学 研 究 科 理 工 学 専 攻 修 ± 学 生 *2:理 工 学 専 攻 教 授(atsuko@stseikei ,acjp) 部 分 問 題 の 実 行 可 能 解(1ナ ー一一ス の1ヶ 月 分 の 実 行 可 能 ス ケ ジ ュ ー ル)は,各 勤 務(日 勤,準 夜 勤,深 夜 勤, 休 み)の 回 数 の 上 下 限 を 守 り,休 み 希 望 や セ ミ ナ 等 の 予 定 を 確 定 し な が ら,各 勤 務 の 連 続 回 数 や 間 隔 と い っ た 勤 務 の 並 び に つ い て の 条 件 を満 た す も の と な る。 そ の 数 は 100万 程 度 と考 え ら れ,陽 的 な 列 挙 や 保 持 は 現 実 的 で は な い 。 本 稿 で は,列 挙 可 能 な 程 度 の 長 さ の 実 行 可 能 部 分 ス ケ ジ ュ ー ル(以 降,パ タ ー ン)を 利 用 し た 定 式 化 を 提 案 し, こ れ に 基 づ くネ ッ ト ワ ー ク を 構 築 す る 。 パ タ ー ン の 長 さ は,隣 接 す る 週 の パ タ ー ン 同 ± が 連 結 可 能 か 否 か で,拘 束 条 件 の 多 く を 考 慮 で き る よ うに7日 と し た 。 勤 務 集 合 を 凪 週 数 をq,h週 の 日の 集 合 をNh,ナ ー一一
スiのh週 の パ タ ー一一ン集 合 を 」Pihとし,パ タ ー一一ンPEPihを
iihpik(1日 が 勤 務kな ら1,そ うで な け れ ば0)で 表 す 。
ま た,ナ ー ス ∫ の 乃 週 の パ タ ー ンρ と 翌 週 の パ タ ー ング の 間 の 連 結 可 能 性 を θihpp・(可能 な ら1,不 可 能 な ら0) で 表 し,1ヶ 月 の 各 勤 務 回 数 の 下 限 をCik,上 限 をdikと す る 。意 思 決 定 変 数 は,ナ ー ス'の 乃 週 の パ タ ー ンρ を 採 用 す る か 否 か を1とoで 表 すAihpを 利 用 す る 。 与 え られ た 試 行 解 で ナ ー ス'以 外 の ス ケ ジ ュ ー ル を 固 定 し た 場 合 の ナ ー一一スiの 各 パ タ ー一一ン の コ ス ト(全 体 勤 務 表 作 成 に お け る,ス キ ル レ ベ ル を も 考 慮 し た 人 数 過 不 足 の 度 合 い)を プ伽 と し,部 分 問 題 の 定 式 化 を 示 す 。 部 分 問 題(ナ ー ス の の 定 式 化
