2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 スタッフスケジューリングにおける 修正 しやすい解を知る為の実験とその考 察 ○ 総合研究大学院大学 久保琢磨 国立情報学研究所 (NII) 宇野毅明.

Presentation on theme: "2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 スタッフスケジューリングにおける 修正 しやすい解を知る為の実験とその考 察 ○ 総合研究大学院大学 久保琢磨 国立情報学研究所 (NII) 宇野毅明."— Presentation transcript:

1 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 スタッフスケジューリングにおける 修正 しやすい解を知る為の実験とその考 察 ○ 総合研究大学院大学 久保琢磨 国立情報学研究所 (NII) 宇野毅明

2 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 スタッフスケジューリングとは 様々な条件を考慮しながら，最適な勤務シフトを計算機にて求 める ホテルや看護士の勤務シフトの作成は難しい NP 困難

3 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 必ず守らなければならない絶対制約（ある日の日勤が 5 人以上必要な ど） なるべく尊重してあげたい考慮制約（スタッフの希望の考慮，公平さな ど） スタッフスケジューリングとは ホテルや看護士などの勤務シフトを作成する問題（ NP 困 難） 全ての制約を守らすことは大抵無理 目的関数 条件 絶対制約

4 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 スタッフスケジューリングとは 運用面 ① input 修正作業 ④ ③ output 勤務シフト作成者 運用 勤務シフト ⑤適用 ・スタッフの希望守りたい ・休みの回数均等の公平性 ・相性・・・ ・多大な時間を要す る ②ソルバ 絶対制約遵守 考慮ペナルティ最小 修正は必ず生じる

5 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 背景と目的 誰でも手軽に勤務シフトを作成可能で運用が楽になる仕組み ・日本の様々な場面で現れる問題 企業 （顧客 側） 企業 （開発 側） 企業 （顧客 側） 企業 （顧客 側） カスタマイズ 一括したモデル 企業 （顧客 側） シンプルなモデ ル 企業 （顧客 側） 企業 （顧客 側） 修正作業 ・シンプルかつ汎用性が高 い 手法で問題を簡単に解く

6 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 背景と目的 最終目標 ・ Web 検索のように，ユーザの簡単な工夫のみで最適化を自由に利用できる仕 組み ③修正 Web ① ② シンプルなモデ ルを簡単に解く 修正しやすい 解

7 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 背景と目的 修正しやすい勤務シフトとは何か？ 考慮制約違反におけるペナルティの総和の最小化 計算機で求めた解について，被験者がその解について修正作業を実施 計算機の視点で最適でも，運用のしやすさの向上につながるとは限らない 目的 ・実験結果を分析し，修正作業の難易度について考察 ・分析結果を考慮したモデル，手法開発への指針作成

8 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験概要 作業概要 ②ソルバ ① input ③ output 勤務シフト作成者 ⑤適用 被験者 修正 ④ ・各問題について, 修正作業とアンケー ト 分析 ？ 勤務シフト SA( 焼きなまし 法 )

9 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験対象 実験で扱う某ホテルの問題（一般的な勤務形態） スタッフ 9 人 ( ベテラン社員 2 人, 普通社員 4 人, 半新人社員 1 人，アルバイ ト 2 人 ) 期間は 30 日 9:30 17:30 18:00 23:30 10:00 ( 翌日 ) 日勤 (A) 夜勤 (N) 準夜勤 1(C1) 準夜勤 2(C2) 日勤 (A) 3 交代制 2 交代制 ◆ H は休み， O は夜勤明けを意味． ◆ j 日が N ならば， j+1 日は O ◆ j 日のシフトが N ならば j 日 17:30 に出勤 し， j+1 日の 10:00 まで勤務 ◆ j 日のシフトが C2 ならば j-1 日 23:30 に 出勤し， j 日の 10:00 まで勤務 ◆社員は C1 以外割当て可能 ◆アルバイトは H,C1 のみ割当て可能

10 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 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) ・スタッフの希望をなるべく遵守したい・・・ (S1) ・グループごとに各シフトの回数を均等に・・・ (S2) ・社員の C2 の回数をなるべく少なくしたい・・・ (S3) ・ C2 の連続， H の後の C2 は極力さけたい・・・ (S4) 絶対制約 考慮制約

11 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験データ スタッフの希望の申請（入力データ） staff シフト希望日 ベテラン社員 0 10:H ベテラン社員 16:N 以外、 10:HorC2orO 、 11:H 、 18:H 普通社員 20:H 、 1:N 、 2:O 、 7:H 、 8:N 、 9:O 普通社員 324:H 、 25:H 、 26:C2 以外 普通社員 424:N 、 25:O 、 26:C2 以外 半新人社員 5 希望なし 普通社員 617:AorO 、 18:H アルバイト 7H:1 、 H:8 、 H:15 、 H:22 、 H:29 アルバイト 8H:7 、 H:14 、 H:21 、 H:28

12 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験作業手順 実験手順 B-1,B-2,B-3-1,B3-2,B3-3,C3-3(6 題 ) （事前に練習問題で慣れてもらう） 手作業での制約違 反チェックは大変 Excel 上で、制約 チェック容易に可 能

13 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験作業方針 修正作業を実施するにあたっての方針 ・被験者が、公平であると判断した段階で作業を終了してよい ・ 25 分たっても終わらなければ打ち切ってもよい ・「休みが月に 6 回以上の制約」は最悪の場合、月 5 回以上でよい ①連休を除いて、休みと休みの間隔は 2 日以上・・・（休みの間隔の制約） ②社員 2 と社員 3 ，また社員 4 と社員 5 が同じ日に 夜勤（ N ）となる日が月に 1 回以上・・・（相性の制約） 新しく制約を追加 ・制約違反作業を容易にする為，実験用開発ツールを用いて作業

14 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 問題について 絶対制約 を重要視 考慮制約 を重要視 絶対制約と考 慮制約を同程 度 休みの間隔の制約相性の制約 B-1○○ B-2○○ B-3.1○○ B-3.2○○ B-3.3○○○ C-3.3○○○ 制約間の重要度 追加の新制約 同条件

15 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 B-1

16 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 B-2

17 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 B3-1,B3-2,B3-3

18 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 C3-3

19 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験問題 被験者 1 の B-1 修正後 シフト回数均 等 修正時間：約 23 分

20 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験アンケート アンケートの一部 質問項目 修正に要した時 間 ○○ 分 終了判断理由公平と判 断 これ以上よく ならないと判 断 いきづまりその他 修正状況ずっとい きづまり スムーズ → いきづまり いきづまり → スムーズ ずっと スムーズ 公平性の考え方シフト回 数 休み回数希望日の守り 具合均等 その他 （） 制約違反の伝播ほぼなし ○○ の制約ばか り違反 どの制約もよ く違反 その他 （）

21 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験結果と考察 実験結果（所要時間と修正難易度）

22 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験結果と考察 実験結果（制約違反度）

23 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験結果と考察 実験結果（公平性の考え方）

24 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 実験結果と考察 考察 ・絶対、考慮制約を少しずつ違反していた解が修正しやすい → 人間が新制約を追加する際にもあまり労力がかからない ・修正段階で制約違反が伝播する頻度が少ないとき、被験者は修正しやすいと感 じる ・一部を修正した際、 7 日に一回以上休みがある制約がよく、違反されやすい ・休みの間隔制約を修正段階で考慮することは難しい ・相性の制約は修正段階でも考慮しやすい ・希望日の守り具合、休みの回数は公平性を考える際、特に重要なファクター

25 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 ディスカッション 修正時に制約違反の伝播を抑える解を生成する為に 修正時に制約違反を起こしやすい制約 ・全員が７日に１回は休みを取る制約（ H1 ） ・終了から次勤務まで８時間以上必要である制約（ H3 ） ・休みの間隔の制約 休み → 出勤 × 出勤 → 休み ○ 各日の必要出勤人数が過剰である 状態から休みを少しずつふやすこ とが有効

26 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 ディスカッション 公平性を維持する修正を行ないやすくする為に 公平性の定義は企業，勤務シフト作成者によって異なる ・スタッフの希望のどの部分を違反させるかは作成者が判断すべき ・あいまいさを含むバランス維持は計算機より作成者の方が得意 希望してないシフト → 希望シフト × 希望シフト → 希望してないシフト ○ スタッフの希望を全て守った解を計算機で生成．スタッフの希望シフト を破らなければならない場合，バランスを考慮しながら，作成者が判断 希望は N,O 希望通り

27 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 ディスカッション 修正しやすい解を得る為に ①スタッフの希望を全て満たし，各日の出勤必要人数が過剰である解の生成 ②最低限必要な休みが守られていない解が生じるので，作成者は各日の出勤 数を必要人数に調整する際に，各スタッフの休みの日を増やしていく ③どうしても増やせなくなる場合は，作成者はスタッフの希望をバランスを考 え つつ，破っていく

28 2008/09/19 ～ 2008/09/20 スケジューリング・シンポジウム 2008 まとめ 結論と今後の課題 結論 ・勤務シフト作成時の運用しやすさという新しい評価基準の導入 ・ホテルの問題について，最適化手法を用いて解いたスケジュールに 対し， 被験者が修正作業を行い、その結果の分析を実施 今後の課題 ・修正しやすい解についての調査の継続 ・調査結果を考慮したモデル，解法の研究