Document

スケジューリング・シンポジウム 2008
スタッフスケジューリングにおける修正
しやすい解を知る為の実験とその考察
○ 総合研究大学院大学久保琢磨
国立情報学研究所(NII) 宇野毅明
2008/09/19～2008/09/20
スタッフスケジューリングとは
スケジューリング・シンポジウム 2008
ホテルや看護士などの勤務シフトを作成する問題（NP困難）
必ず守らなければならない絶対制約（ある日の日勤が5人以上必要など）
なるべく尊重してあげたい考慮制約（スタッフの希望の考慮，公平さなど）
全ての制約を守らすことは大抵無理
目的関数
min 考慮制約ペナルティ
2008/09/19～2008/09/20
条件
絶対制約
スタッフスケジューリングとは
スケジューリング・シンポジウム 2008
運用面
運用
①input
絶対制約遵守
考慮ペナルティ最小
②ソルバ
勤務シフト作成者
修正は必ず生じる
⑤適用
③output
勤務シフト
④
修正作業
・スタッフの希望守りたい
・休みの回数均等の公平性
・相性・・・
2008/09/19～2008/09/20
・多大な時間を要する
背景と目的
スケジューリング・シンポジウム 2008
誰でも手軽に勤務シフトを作成可能で運用が楽になる仕組み
・日本の様々な場面で現れる問題
企業
カスタマイズ
（顧客側）
企業
企業
（開発側）
（顧客側）
・シンプルかつ汎用性が高い
手法で問題を簡単に解く
シンプルなモデル
企業
（顧客側）
企業
（顧客側）
修正作業
企業
企業
（顧客側）一括したモデル
（顧客側）
2008/09/19～2008/09/20
背景と目的
スケジューリング・シンポジウム 2008
最終目標
・Web検索のように，ユーザの簡単な工夫のみで最適化を自由に利用できる仕組み
③修正
修正しやすい解
①
②
Web
2008/09/19～2008/09/20
シンプルなモデル
を簡単に解く
背景と目的
スケジューリング・シンポジウム 2008
修正しやすい勤務シフトとは何か？
考慮制約違反におけるペナルティの総和の最小化
計算機の視点で最適でも，運用のしやすさの向上につながるとは限らない
目的
計算機で求めた解について，被験者がその解について修正作業を実施
・実験結果を分析し，修正作業の難易度について考察
・分析結果を考慮したモデル，手法開発への指針作成
2008/09/19～2008/09/20
実験対象
スケジューリング・シンポジウム 2008
実験で扱う某ホテルの問題（一般的な勤務形態）
スタッフ9人(ベテラン社員2人,普通社員4人,半新人社員1人，アルバイト2人)
期間は30日
◆Hは休み，Oは夜勤明けを意味．
3交代制
9:30
◆j日がNならば，j+1日はO
◆j日のシフトがNならばj日17:30に出勤し，
j+1日の10:00まで勤務
2交代制
17:30
18:00
日勤
(A)
日勤
(A)
準夜勤1(C1)
◆j日のシフトがC2ならばj-1日23:30に
出勤し， j日の10:00まで勤務
◆社員はC1以外割当て可能
10:00
◆アルバイトはH,C1のみ割当て可能
(翌日)
2008/09/19～2008/09/20
夜勤
(N)
23:30
準夜勤2(C2)
実験対象
スケジューリング・シンポジウム 2008
扱う問題の制約
・全員が7日に一回は休みを取る
・・・(H1)
・全員が月に6回以上休みを取る
・・・(H2)
・終了から次勤務まで8時間以上必要
・・・(H3)
・日勤は必ず2人の社員出勤
・・・(H4)
・日勤は1人以上のベテラン社員が必要
・・・(H5)
・夜勤は必ず社員が2人必要
・・・(H6)A
・j日にC1にアルバイトが1人いるならば，
・・・(H6)B
j日のNに社員が1人，j+1日のC2に社員が１人必要
・新人社員とアルバイトが同時出勤不可
・・・(H7)
・各スタッフは各日に1つのシフトを割当
・・・(H8)
・スタッフの希望をなるべく遵守したい
・グループごとに各シフトの回数を均等に
・社員のC2の回数をなるべく少なくしたい
・C2の連続，Hの後のC2は極力さけたい
2008/09/19～2008/09/20
・・・(S1)
・・・(S2)
・・・(S3)
・・・(S4)
絶対制約
考慮制約
実験データ
スケジューリング・シンポジウム 2008
スタッフの希望の申請（入力データ）
staff
シフト希望日
ベテラン社員0
10:H
ベテラン社員1
6:N以外、10:HorC2orO、11:H、18:H
普通社員2
0:H、1:N、2:O 、7:H、8:N、9:O
普通社員3
24:H、25:H、26:C2以外
普通社員4
24:N、25:O、26:C2以外
半新人社員5
希望なし
普通社員6
17:AorO、18:H
アルバイト7
H:1、H:8、 H:15、H:22、 H:29
アルバイト8
H:7、H:14、 H:21、H:28
2008/09/19～2008/09/20
実験作業方針
スケジューリング・シンポジウム 2008
修正作業を実施するにあたっての方針
・制約違反作業を容易にする為，実験用開発ツールを用いて作業
・被験者が、公平であると判断した段階で作業を終了してよい
・25分たっても終わらなければ打ち切ってもよい
・「休みが月に6回以上の制約」は最悪の場合、月5回以上でよい
新しく制約を追加
①連休を除いて、休みと休みの間隔は2日以上
②社員2と社員3，また社員4と社員5が同じ日に
夜勤（N）となる日が月に1回以上
2008/09/19～2008/09/20
・・・（休みの間隔の制約）
・・・（相性の制約）
実験問題
スケジューリング・シンポジウム 2008
問題について
絶対制約
を重要視
B-1
考慮制約
を重要視
絶対制約と考慮
制約を同程度
○
B-2
休みの間隔の制約
相性の制約
○
○
○
B-3.1
○
○
B-3.2
○
B-3.3
○
○
○
C-3.3
○
○
○
○
制約間の重要度
追加の新制約
2008/09/19～2008/09/20
同条件
実験問題
スケジューリング・シンポジウム 2008
B-1
2008/09/19～2008/09/20
実験問題
スケジューリング・シンポジウム 2008
被験者1のB-1修正後
修正時間：約23分
シフト回数均等
2008/09/19～2008/09/20
実験結果と考察
スケジューリング・シンポジウム 2008
実験結果（所要時間と修正難易度）
2008/09/19～2008/09/20
実験結果と考察
スケジューリング・シンポジウム 2008
実験結果（制約違反度）
2008/09/19～2008/09/20
実験結果と考察
スケジューリング・シンポジウム 2008
実験結果（公平性の考え方）
2008/09/19～2008/09/20
実験結果と考察
スケジューリング・シンポジウム 2008
考察
・絶対、考慮制約を少しずつ違反していた解が修正しやすい
→人間が新制約を追加する際にもあまり労力がかからない
・修正段階で制約違反が伝播する頻度が少ないとき、被験者は修正しやすいと感じる
・一部を修正した際、7日に一回以上休みがある制約がよく、違反されやすい
・休みの間隔制約を修正段階で考慮することは難しい
・相性の制約は修正段階でも考慮しやすい
・希望日の守り具合、休みの回数は公平性を考える際、特に重要なファクター
2008/09/19～2008/09/20
ディスカッション
スケジューリング・シンポジウム 2008
修正時に制約違反の伝播を抑える解を生成する為に
修正時に制約違反を起こしやすい制約
・全員が７日に１回は休みを取る制約（H1）
・終了から次勤務まで８時間以上必要である制約（H3）
・休みの間隔の制約
Staff1
Staff2
Staff3
休 A A A 休 A A A
N O C2 休 A N O 休
A A A A A 休 A 休
休み→出勤 ×
出勤→休み ○
2008/09/19～2008/09/20
Staff1
Staff2
Staff3
休 A A A A A A A
N O C2 休 A N O 休
A A A A 休休 A 休
各日の必要出勤人数が過剰である
状態から休みを少しずつふやすこと
が有効
ディスカッション
スケジューリング・シンポジウム 2008
公平性を維持する修正を行ないやすくする為に
公平性の定義は企業，勤務シフト作成者によって異なる
・スタッフの希望のどの部分を違反させるかは作成者が判断すべき
・あいまいさを含むバランス維持は計算機より作成者の方が得意
希望してないシフト→希望シフト ×
希望シフト→希望してないシフト ○
Staff1
Staff2
Staff3
希望はN,O
休 A A A A A A A
N O C2 休 A N O 休
A A A A 休休 A 休
希望通り
スタッフの希望を全て守った解を計算機で生成．スタッフの希望シフトを破らな
ければならない場合，バランスを考慮しながら，作成者が判断
2008/09/19～2008/09/20
ディスカッション
スケジューリング・シンポジウム 2008
修正しやすい解を得る為に
①スタッフの希望を全て満たし，各日の出勤必要人数が過剰である解の生成
②最低限必要な休みが守られていない解が生じるので，作成者は各日の出勤
数を必要人数に調整する際に，各スタッフの休みの日を増やしていく
③どうしても増やせなくなる場合は，作成者はスタッフの希望をバランスを考え
つつ，破っていく
2008/09/19～2008/09/20
まとめ
スケジューリング・シンポジウム 2008
結論と今後の課題
結論
・勤務シフト作成時の運用しやすさという新しい評価基準の導入
・ホテルの問題について，最適化手法を用いて解いたスケジュールに対し，
被験者が修正作業を行い、その結果の分析を実施
今後の課題
・修正しやすい解についての調査の継続
・調査結果を考慮したモデル，解法の研究
2008/09/19～2008/09/20

Download Report