実用的なシフトスケジューリングシステムの試作
M2008MM014 伊東尚美
指導教員：鈴木敦夫

1

はじめにてを行う．また，VBA プログラムを用いて，割当てを自動生成するシステムを作成する．

シフトスケジューリング問題は，大学や病院，一般企業などで日常的に業務で扱われている問題である．しか 2.2 問題解決の手順
し現在シフトスケジューリングは，多くの場合そのシフ
まず割当ての最適化を行う前に，入試で使用する試験トを必要とする業務の責任者によって手作業で作成され 室数と作業担当者数を合わせる作業を行う．これは，入試ている．その責任者は時間と労力を費やしており，これ 課が作成するデータを用いる．試験室数より担当者数のは，責任者にとって大きな負担となっている．この負担 方が多い場合，一人が 2 教室受け持たなければならない．
を軽減するためには，シフトスケジューリングを自動化 このとき，確認する答案枚数ができるだけ偏らないようするシステムを作成する必要がある考えた．そしてこの にするため，あらかじめ答案枚数の少ない 2 つの試験室シフト作成の業務が自動化し，短時間でシフトを作成す を 1 教室とする．この作業を行う際，日にち・学科・方式ることができれば，それぞれの責任者は本来の業務に時 を跨がないように試験室数の変更を行わなければならな間を使うことができ，より良いサービスを提供すること い．各学科・方式の中で前後の試験室の答案枚数を足し，ができるようになる．
その和が最小となる 2 教室を 1 教室として考える．また
シフトスケジューリングを自動化するシステムは多く 試験室数より作業担当者数の方が多い場合は，ダミー教市販されている．しかしそれらは使い勝手が悪く，シフ 室を作る．このダミー教室には，6 日間の合計枚数を平均ト作成にあまり使用されていない．
化するため，1 人が 1 日に担当する答案枚数の平均（総答
そこで本研究では，使いやすく実用性の高いシステム 案枚数÷作業担当者数÷ 6 日間）枚数を代入する．試験を作成することが重要であると考えた．これを実現する 室数を変更するこの作業は，VBA プログラムを用いる．
ため，現場の担当者にインタビューを行い，現場の人の意
次に，試験室数を変更したデータを用いて，試験室に見を取り入れた．これらの知見を反映させて，オペレー 作業担当者を割当てる．シフトを作成するための条件は，ションズ・リサーチを用いた業務の改善手法を考案する． 始めてこの業務を担当する新人職員と今まで経験したこ
具体的には，南山大学における一般入試の作業本部担当 とのある職員がペアとなり，新人職員同士のペアを作ら者の自動割当，病棟看護師勤務シフトの 2 つを取り上げ ないようにすること．入試期間中の 6 日間に担当する答る．そして，これらの問題を 0-1 整数計画法の問題とし 案枚数は新人職員，経験職員のそれぞれについてあらかて定式化し，PC 上に実装されている数理計画ソフトウェ じめ与えられた範囲以内におさめることあである．この
アを用いた解法を考案する．また，Eccel における VBA 問題は，制約条件を満たす実行可能解を求める．
プログラムを活用し，実用可能なシステム作成を目指す．
2.3 担当者割当問題のモデル

2

南山大学における一般入試の作業本部担当者の自動割当

2.1

問題概要

南山大学では，2003 年以降オペレーションズ・リサーチを用いて大学の業務改善を行っている [2]．このオペレーションズ・リサーチの手法を用いた業務改善はプロジェ
クト N と呼ばれている．このプロジェクト N の一つとして本研究も行う．
シフト作成の自動化の要請は多く，入学試験に関しては，短時間に多くの業務を行わなければならない．
そこで本研究では，入学試験に関する業務の効率を上げるため以下の問題のシフト作成を行う．
南山大学の一般入試では，試験室から回収された答案の枚数が受験者数と一致するかどうかを確認する業務がある．この業務の担当者はペアを組み，互いに自分が確認した答案を交換して再度確認する．この答案枚数を確認する作業を作業本部と呼んでいる．学科・方式別に分けられた答案用紙を誰がどの試験室を担当するかを割当てる．この問題を 0-1 整数計画法として定式化し，LINDO
社の数理計画ソフト What’s Best!9.0.5.0 を用いて，割当定式化に用いた記号は以下のとおりである．

2.3.1

記号の定義

定数
I:職員の集合I1 :新人職員の集合
I2 : I \ I1
J:作業を行う日数の集合
Kj :j ∈ J 日に使用する教室の数
mi :6 日間に経験職員 i ∈ I2 が担当する最低答案枚数
Mi :6 日間に経験職員 i ∈ I2 が担当する最高答案枚数
ni :6 日間に新人職員 i ∈ I1 が担当する最低答案枚数
Ni :6 日間に新人職員 i ∈ I1 が担当する最高答案枚数
ajk :j ∈ J 日に教室 k の答案枚数
k = 1, … , Kj
変数
1 職員 i ∈ I が j ∈ J 日に教室 k を担当する
k = 1, … , Kj
xijk =0
職員i∈
Iがj∈
J日に教室kを
担当しない
k = 1, … , Kj

2.3.2定式化

上記の記号を用いて，以下の制約式を満たす xijk を求める．
subject to3

病棟看護師勤務シフト

医療施設では人の命に関わる業務を行うため，絶え間なく質の高い医療サービスを提供しなければならない．そのためには，適切な看護師の配置を考える必要がある．しl K −1 m
かし，勤務の組み合わせや各看護師についての条件が多j2
いため，毎日の各勤務に必要とされる看護師の人数を満∑
xij,2l+1 = 0i ∈ I1 j ∈ J(1) たし，各看護師の勤務負荷に関する制約を満たす勤務表
l=0の作成は困難である．
Kj
勤務表作成の自動化システムは存在し，システムを購∑∑mi ≤ajk xijk ≤ Mii ∈ I2(2) 入する病院が多くなっているが，実際には表計算を行う
j∈J k=1
ソフトウェアとしての利用がほとんどであり，勤務表作
Kj
成にあまり使用されていない．
∑∑ni ≤
ajk xijk ≤ Nii ∈ I1(3)このようなナース・スケジューリングの難しさは国内外j∈J k=1で広く知られており，研究も多くされている．池上氏の論Kj
文にも勤務表作成は解くことが困難な組み合わせ問題で∑xijk = 1i∈Ij∈J(4) あり，なんらかのスケジューリング機能を持ったシステム
k=1が望まれていることも書かれている [1]．ここでは，青野∑
xijk = 1j∈J
k = 1, … , Kj
(5) の 3 交替制の勤務シフトの自動化システムを作成する研究を引き継ぎ，2 交替制のシフトの作成を行う [3]．青野i∈Ixijk ∈ {0, 1}i∈Ij∈J
k = 1, … , Kj (6) の研究では条件が多く問題が複雑なため一部の勤務のみを割当てた．勤務表の一部としては良い結果を得ることができたが，すべての勤務に対しすべての条件を満たす定式化の説明解を得ることはできなかった．これは勤務表の一部が割(1) 新人職員 i は偶数番目の試験室 k のみ割当てる．
当てられていたため，勤務の並びの条件を満たすことが(2) 経験職員 i が 6 日間で担当する答案枚数の範囲．
できなかったと思われる．この研究を基に本研究を行う．
(3) 新人職員 i が 6 日間で担当する答案枚数の範囲．
近年，看護師の勤務は 3 交替制から 2 交替制に移行し(4) 職員 i が j 日に担当する試験室 k を 1 つ割当てる． つつある．本研究では 2 交替制勤務を行っている部署の(5)j 日の試験室 k に職員 i を 1 人割当てる．
シフト作成条件から，実データを用いて実用的な勤務表(6)0-1 変数で表す．
作成を目指す．この問題を 0-1 整数計画法として定式化し，LINDO 社の数理計画ソフト What’s Best!9.0.3.3 を2.4 実行結果と計算時間用いて，勤務シフトを作成する．
この問題は 2008 年に自動化システムを作成した．実際に 2009 年度の入学試験で使用し，改善点が 2 つあげら 3.1 病棟看護師勤務表れた．
勤務表は，縦軸に看護師氏名や番号，横軸に日付や曜
一つ目は，新人職員の 6 日間の合計答案枚数が経験職 日が記入される．看護師氏名と日付の交差点には「その員より多い場合があったため，新人職員と経験職員が担 看護師のその日の勤務の記号」が記入されることによっ当する答案枚数の範囲を分ける制約条件にした．て勤務スケジュールが決定していく．勤務表を作成する
二つ目は，この割当て作業をすべて自動化することで 際，もっとも重要とされるのは，毎日の「看護の質」をある．2009 年度では，割当てを行う担当者が手作業で行 一定レベル以上に保たなければならないことである．こうところがあったため，すべての作業に約 1 時間かかっ れは池上氏 [1] に従って以下の二つのことが挙げられる．ていた．試験室数を変更する作業をすべて VBA プログ
1. 縦の条件：毎日の各勤務のメンバー構成で質を守る．
ラムで作成できるようにした．
2. 横の条件：各看護師についての勤務スケジュール．
そして，この改善したものを 2010 年度の入学試験で使用した．このときの問題は，7350 変数，505 制約式の問 勤務表作成は，看護師数に余裕のない状況で，この「縦題として定式化され，What’s Best!9.0.5.0 を用いて 4 秒 の条件」と「横の条件」を同時に満たさなければならな
いところが難しい．
で解を求めることができた．
この問題では，業務担当者数 35 名，そのうち 15 名が 3.2 ナース・スケジューリング問題
新人職員であった．試験室数は 6 日間でのべ 276 室であっ3.2.1 勤務割当ての原則た．経験職員の最大答案枚数を 500，最低答案枚数を 440，勤務表作成において，守るべき条件を以下に示す．
新人職員の最大答案枚数を 480，最低答案枚数を 410 に設定した．今年の割当て作業にかかった時間は，5 分程度
1. 勤務希望を満たす．
であった．すべてを自動化したことによりかなりの時間
2. 毎日の各勤務に必要な人数を確保する．
を短縮することができた．

3. スキルレベルを考慮して各勤務のメンバーを構成す
る．

r=2
r=3

:スキルレベル 1 から師長を除く:全体からスキルレベル 5 と師長を除く

4. 各看護師について各勤務の回数を決められた範囲内におさめる．

r=4:全体から師長を除く

5. 禁止される勤務パターン（勤務の並び）を入れない．
2〜3 は，各シフトの業務に支障を起こさないための縦の条件である．
4〜5 は，各看護師の勤務の負荷を考慮する横の条件である．
目的関数

3.3

ナース・スケジューリング問題の目的関数は，病院を経営する側から考えるとコスト最小化が考えられる．しかし，勤務表作成においては，コスト最小化を考える必要はない．なぜなら，コストは看護師勤務表作成以前の看護師配置人数に関わっているからである．病院が雇用する看護師数は，厚生労働省が定めた診療報酬に大きく依存する．それには，医療の質や安全を確保する費用，医療従事者の人件費も含まれており，看護師の配置人数も決められている．よって目的関数はコスト最小化ではな
く，勤務表を作成する上で一番優先される勤務の希望を満たす満足度最大化とする．

etsr：t ∈ T1 日の勤務 s ∈ S に対するグループ r からの下限必要人数
ftsr：t ∈ T1 日の勤務 s ∈ S に対するグループ r からの上限必要人数
arn ：グループ r に属する看護師 n ∈ N の夜勤勤務
可能回数
g ：日曜日に勤務 s ∈ S を割当てることのできる回数h：土曜日に勤務 s ∈ S を割当てることのできる回数
l：定められた週休 s = 1 の下限回数
m：定められた週休 s = 1 の上限回数
p：夜勤勤務を 2 日間連続して勤務する人数
Qnts：看護師 n ∈ N が t ∈ T1 日に勤務 s ∈ S をした
ときの満足度
1 看護師 n ∈ N が t ∈ T1 日に
勤務 s ∈ S を希望する
Hnts =0
看護師 n ∈ N が t ∈ T1 日に
勤務 s ∈ S を希望しない変数

1

ナース・スケジューリング問題のモデル

3.4
3.4.1

記号の定義

定数
T ：一ヶ月間の日にちの集合
T1 ：スケジュール対象となる日の集合
T1 ={1, 2, … , w}(w = 28)
T2 ：土曜日の集合
T2 ⊂ T1
T3 ：日曜日の集合
T3 ⊂ T1
T4 ：土・日曜日・祝日の集合
T4 ⊂ T1
T5 ：土・日曜日・祝日を除いた集合
T5 ⊂ T1
N ：スケジュール対象となる看護師の集合
N = {1, 2, … , n}
N ′ ：師長と夜勤勤務を行わない看護師の集合
N′ ⊂ NN ′′ ：師長と夜勤勤務を行わない看護師を除いた集合
N ′′ ⊂ N
S ：勤務の種類の集合
S={1, 2, … , s}(s = 7)

s=1
s=2:週休:日勤 1

s=3
s=4
s=5:日勤 2:夜勤:午前半日

s=6
s=7:研修:休日（祝日・リフレッシュ休暇・年休）

M ：連続パターンを禁止する日数の集合
M ={k1 , … km }(m = 3)
k1 =1,k2 =2,k3 =6
Gr ：グループ r に属する看護師
r=1,… ,4
r=1

:スキルレベル 5

xnts =

3.4.2


0



看護師 n ∈ N が t ∈ T1 日に勤務 s ∈ S をする
看護師 n ∈ N が t ∈ T1 日に勤務 s ∈ S をしない定式化

以下の条件を満たし，満足度が最大となるような xntsを求める．
maxmize∑ ∑∑Qnts xnts
(7)n∈N t∈T1 s∈Ssubject to∑n ∈ N,

xnts = 1,s∈S

etsr ≤∑t ∈ T1(8)xnts ≤ ftsrn∈Grt ∈ T4 ,r = 1, 2, s = 2, 3∑
etsr ≤xnts ≤ ftsr

(9)n∈Grt ∈ T5 , r = 4, s = 2, 3∑
et4r ≤xnt4 ≤ ft4r , t ∈ T1 , r = 1, 2

(10)
(11)

n∈Gr

∑

xnt4 ≤ arn ,r = 1, 3,t ∈ T1

(12)

s∈S

(13)

n∈Gr

xnts = Hnts ,n ∈ N,

6∑∑t∈T3 s=2xnts ≤ g,t ∈ T1 ,n∈N

(14)

6
∑∑

3.5xnts ≤ h,n∈N(15)xnt1 ≤ m,n∈N(16)

xnt4 /|N ′ | ≤ 72(17)t∈T2 s=2l≤∑t∈T115150 ≤ 7.5(t∈T n∈N ′

∑

+15
∑

∑

xnt2 +t∈T17.5(∑ ∑∑t∈T1

t∈T1

xnt6 +t∈T1+4∑

∑

∑

xnt3

t∈T1n ∈ N ′′xnt4 ≤ 158,

∑xnt7 )+7.75

t∈T1

t∈T1

xnt2 +∑xnt6 +xnt7 ) + 7.75t∈T1(18)∑xnt3

t∈T1n ∈ N′xnt5 = 158,(19)t∈T1xnts ∈ {0, 1},
6 ∑7∑n ∈ N,xn,t+β−7,s ≤ k3 ,t ∈ T1 ,n ∈ N,s∈S(20)t ∈ {1, … , w − k3 }s=2 β=1(21)t ∈ {1, … , w − k1 }(22)xn,t−1,4 + xnt3 ≤ k1 , n ∈ N ′ , t ∈ {1, … , w − k1 }(23)∑′xn,t−2,4 ∗ xnt4 ≤ k1 n ∈ N , t ∈ {1, … , w − k1 }xn,t−1,4 + xnt2 ≤ k1 ,n ∈ N ′,t∈T1

∑ ∑xn,t−2,4 ∗ xnt4 ≤ p(24)(25)

n∈N ′ t∈T1xn,t−4,4 + xn,t−2,4 + xnt4 ≤ k2n ∈ N ′,t ∈ {1, … , w − k2 }(26)

定式化の説明(7) 勤務希望満足度の合計最大化．
(8) 看護師 n の t 日に勤務 s を 1 つ割当てる．
(9),(10)t 日の日勤勤務（s=2,3）におけるグループ rからの人数を上下限の幅におさめる．
(11)t 日の夜勤勤務（s=4）におけるグループ r からの人数を上下限の幅におさめる．
(12) 各看護師 n に決められた回数以上夜勤勤務を割当てない．
(13) 看護師 n の t 日に勤務を s に固定するまたは s を禁止する．
(14) 日曜日に決められた回数以上勤務を割当てない．
(15) 土曜日に決められた回数以上勤務を割当てない．
(16) 週休を勤務する回数を上下限の幅におさめる．
(17)1ヶ月間で夜勤勤務時間を平均 72 時間以内におさめる．
(18),(19) 勤務時間を 150〜158 時間にする．
(20)0-1 変数で表す．
(21)7 連続勤務を禁止する．
(22),(23) 夜勤勤務の次の日は日勤勤務を禁止する．
(24) 夜勤勤務の 2 日間連続勤務を 1 回までにする．
(25) 夜勤勤務の 2 日連続勤務をする人の人数制限．
(26) 夜勤勤務の 3 日間連続勤務を禁止する．

実行結果と計算時間

インタビューで聞いた条件をすべて満たす解を得ることができなかった．そこで休みの回数の条件を緩くして，解を得ることができた．この問題は，平成 22 年 2 月 7 日（日）〜3 月 6 日（土）の実際の希望を使用したものである．
これは 26 名がスケジュール対象者となり，この中の一人が育児のため夜勤勤務を行わないようにした．14963 変数，7116 制約式の問題として定式化され，What’s best!9.0.3.3を用いて 19 分 10 秒で解くことができた．このとき使用した PC の PCU は Intel(R)M 1.60GHz，メモリ 504MB，
OS は Microsoft Windows XP Professional である．この問題は，非線形の制約条件が存在するため，What’s Best!
が線形化して解を求めている．上記に示した値のうち 607
変数，2428 制約式が線形化するために加えられた．

4

おわりに

本研究では，シフトスケジューリング問題である南山大学における一般入試の作業本部担当者割当問題とナース・スケジュール問題を取り上げた．これらの問題を 0-1
整数計画法の問題として定式化し，PC に実装されている数理計画ソフトウェアを用いた解法を考案した．
本学における一般入試の作業本部担当者割当問題では，作業担当者を試験室に自動的に割当てるシステムを作成した．その結果，短時間ですべての条件を満たす解を求めることができた．オペレーションズ・リサーチの手法を用いることによって，これまで数日をかけ労力を費やしていた業務に対し，実際に適用できる改善手法を考案することができた．
ナース・スケジューリング問題は，ある医科大学病院で聞いたすべての条件を満たす解を求めることができなかった．一日に勤務できる上限人数を入れ縦の条件を満たすことができても，横の条件を満たすことができなかった．これは条件が厳しすぎるためだと考えられる．そのため，ある医科大学病院の担当者に，再度条件の確認をする必要がある．条件のどこかを緩くすることができれば，短時間で勤務表を作成することが実現できる．やはり，ナース・スケジューリング問題は条件が厳しく解を求めることが難しい．今後の課題は，条件を確認し条件を満たす勤務表を作成すること，現時点では一部しか自動化されていないためすべての自動化システムを作成することである．

参考文献[1] 池上敦子：我が国におけるナース・スケジューリン
グ ―モデル化とアプローチ― , 成蹊大学大学院博士学位論文，2001．
[2] 鈴木敦夫，山本佳奈，伊東尚美：シフトスケジュー
リング ―南山大学での事例紹介― , スケジューリ
ング・シンポジウム講演論文集，25-30,2009.
[3] 青野愛：病棟看護師勤務シフトの自動作成に関する実際的研究，2008 年度南山大学大学院数理情報研究科数理情報専攻修士論文，2008．