自動スケジューリングのモデル
アルゴリズムとシステム開発

株式会社 NTTデータ数理システム
nuopt-info@msi.co.jp

Copyright © 2011 NTT DATA Corporation

Copyright © 2014 NTT DATA Mathematical Systems Inc.

株式会社 ＮＴＴデータ数理システム
所在地「数理システム」から社名変更

東京都新宿区信濃町

設立
昭和57年4月1日 （2012年2月15日にＮＴＴデータグループに）

主な業務
パッケージソフトウェア開発・販売
ソフトウェア受託開発
データ分析、数理計画の各種コンサルティング

パッケージソフトウェア（※以外は全て自社開発）
最適化パッケージ NUOPT
データ解析ソフト S-PLUS ※データマイニングツール Visual Mining Studio
テキストマイニングツール Text Mining Studio
シミュレーションツール S-cube
ベイジアンネット構築支援システム BayoNet
半導体ＴＣＡＤシミュレーション PW2など
2Copyright © 2014 NTT DATA Mathematical Systems Inc.

スケジューリング分野導入実績
株式会社カネカ 食用油脂配送 配車計画システム
参考 URL http://www.msi.co.jp/nuopt/interview/interview5.html
大阪ガス株式会社 当直シフト編成ツール
参考 URL http://www.msi.co.jp/nuopt/interview/interview4.html
社団法人日本将棋連盟 関東奨励会における対戦表自動作成システム
参考 URL http://www.msi.co.jp/nuopt/interview/interview1.html
東日本旅客鉄道株式会社 大規模勤務システムの自動勤務作成機能
参考 URL http://www.msi.co.jp/nuopt/solution/shift/case_jr.html
財団法人鉄道総合技術研究所 鉄道線路保守計画の最適化システム
参考 URL http://www.msi.co.jp/userconf/09/Pdf/09miwa.pdf
・大学病院 ナーススケジューリング
・ケアセンター 介護士シフトスケジューリング
・銀行窓口業務スタッフスケジューリング
・美容院における美容師スタッフスケジューリング
・メディカルセンター 健診スタッフスケジューリング ・エネルギー事業所 発電設備運転計画
・コールセンター 受電予測を考慮したインバウンドオペレータースケジューリング
・コールセンター 架電計画を考慮したアウトバウンドオペレータースケジューリング
・フィットネスクラブ スタッフ ・ビル清掃／ビル警備／テナントスタッフ（ 2011 年度 2012 年度 実績）

3
Copyright © 2014 NTT DATA Mathematical Systems Inc.

個人の制約（１）1日の最短・最長勤務時間
連続休日数上限
連続勤務日数上限
シフト並びの考慮（ex. ×遅番→早番）
月の労働時間/日数上下限
各 (人,日) の勤務可能時間帯
指定シフト（ex.Aさん6/2研修）

週の労働時間/日数上下限
早番/遅番 回数上下限
土日祝の出勤回数

定式化は明確で容易→数理計画適用のメリット
4
Copyright © 2014 NTT DATA Mathematical Systems Inc.

個人の制約（２）余剰人員削減
人数不足偏り防止
スキルレベル平準化
スケジューリングの質を決定する要件

5
Copyright © 2014 NTT DATA Mathematical Systems Inc.

個人の制約（２）
要件が多義的・定式化が明確ではない

すべてを満たすことはできない⇒折り合いが必須 6
Copyright © 2014 NTT DATA Mathematical Systems Inc.

我々の戦略（定式化）
ハード充足不可時のしわよせ先• 制約をハード・セミハード・ソフトに分類

ウエイトの「インフレ」の回避
シフト破壊の回避• オーソドックスな定式化∑xs∈Shiftm,d ,s

ウエイト調整の余地= 1, m ∈ Man, d ∈ Day
xm ,d , s ∈ {0,1} ：変数とする定式化

個人が取れるシフトパターン（平均15）7
Copyright © 2014 NTT DATA Mathematical Systems Inc.

我々の戦略（ツール）
複雑な割り当て問題に関する実績•WCSP（NUOPT組込み）– 「局所探索」と「タブーサーチ」に基づく近似解法– 京都大学「問題解決エンジン」開発グループ
K. Nonobe and T. Ibaraki,``An improved tabu search method for the weighted constraint satisfaction problem,''
INFOR 39, pp.131-151, 2001.
K. Nonobe and T. Ibaraki, An improved tabu search method for theweighted constraint satisfaction problem,INFOR 39, pp.131-151, 2001.

•SIMPLE–汎用モデリング言語
Copyright © 2014 NTT DATA Mathematical Systems Inc.

一般の制約記述に対応
WCSPに近傍の情報を提供
Excelと連携

8

なぜヒューリスティクス解法か
検索エンジンによる調査の実際の例•とりあえず始めてみる•出てきた結果からキーワードを調整する–釣れるキーワード・釣れないキーワード•著者情報からキーになる人を知る•枯れた分野・盛んな分野を知る•人物から業績を検索

検索の方法を調整⇒なんとなくできてしまう

9
Copyright © 2014 NTT DATA Mathematical Systems Inc.

なぜヒューリスティクス解法か
検索エンジンの特性•検索結果が複数現れる•結果が良さげな順にソートされている•素早く結果が得られる

人間系とフィードバックループを構成
10
Copyright © 2014 NTT DATA Mathematical Systems Inc.

ヒューリスティクス解法によるモデル定式化のプロセス• まずは明らかな制約を入れよう⇒なるほどこんなものか（速度と解の質を体感）• 平準化入れてみよう⇒ちょっと応答鈍くなるなあ• スキルの制約入れてみた⇒それほど効いてないぞ（結果を前のと比較）• 不足平準化の制約入れてみた⇒あれれ，結果の様相が変わった，重み調整だ

人間系とフィードバックループを構成
顧客を交えた11Copyright © 2014 NTT DATA Mathematical Systems Inc.

ヒューリスティクス解法のメリット•良解を複数出す•応答が速い⇒ フィードバックループの構成モデルが流動的な場合には複数の良解は一個の最適解に勝る

12
Copyright © 2014 NTT DATA Mathematical Systems Inc.

重み（=双対変数）の調整の具体例
問題Ｐ：
最小化 2x + y + z
制約 x + y + z ≥ 5

緩和

問題 L(λ )x − y − 2z ≥ 3
最小化 2 x + y + z − λ1 ( x + y + z − 5)5 ≥ x, y , z ≥ 0− λ2 ( x − y − 2 z − 3)
制約 5 ≥ x, y, z ≥ 0θ (λ（) ≡ L(λ )の目的関数の最小値:下界値）を最大化してみよう
Copyright © 2014 NTT DATA Mathematical Systems Inc.

13

直観だけを頼りに．．

•満たしてない⇒重みを増やす
満たしている⇒重みを減らす

14
Copyright © 2014 NTT DATA Mathematical Systems Inc.

理論的な背景•θ (λ ) は凸関数′) ⋅ g ( x)}θ (tλ + (1 − t )λ ′) = min{f(x)−(tλ+(1−t)λx′ ⋅ g ( x))}= min{t(f(x)−λ⋅g(x))+(1−t)(f(x)−λx′ ⋅ g ( x))≥ t ⋅ min( f ( x) − λ ⋅ g ( x)) + (1 − t ) ⋅ min(f(x)−λxx= t ⋅ θ (λ ) + (1 − t ) ⋅ θ (λ ′)−g(x) 方向に進めば θ (λ)•

は少なくとも減らないθ (λ ) の更新に関する示唆θ (λ ) ≤ f ( x ) − g ( x ) ⋅ λ , x ∈ Ω⇒意外と直観と合致 15
Copyright © 2014 NTT DATA Mathematical Systems Inc.

正解は

実は

λ1 = 1.5, λ2 = 0.5
θ ≤ 0 x + 0 y + 0.5 z + 9•

θ (λ1 , λ2 ) 全体の形（凸だが不連続）

振る舞いは読みにくい
Copyright © 2014 NTT DATA Mathematical Systems Inc.

16

Open Question（Ｉ）

良い解・多彩な解を出すための制約重みの調整方法？
「１０段階のきめ細かな設定が可能です！
「ユーザーさまが重みを調整して多様な解を出力できるようにしました！」17
Copyright © 2014 NTT DATA Mathematical Systems Inc.

スケジューリング問題の数学的な性質• 制約が多い⇒矛盾が起きやすい• 対称性が激しい⇒良解が多数

ヒューリスティクス
解法向き！

18
Copyright © 2014 NTT DATA Mathematical Systems Inc.

タブサーチ（近似解法）

ゲーム・パズルの方法

変更を繰り返して少しでも手持ちの解を改善する
制約は改善目標⇒解を切り捨てない近傍最良の改善解出力初期点改善解19

Copyright © 2014 NTT DATA Mathematical Systems Inc.

分枝限定法（厳密解法）
最適解になり得ない種制約を満たし得ない種は調べずに捨てて絞り込む

最適解⇒出力:緩和解（最適解の種）:暫定解（制約を満たす最適解の候補）:制約を満たし得ない緩和解:最適解になり得ない緩和解
20

Copyright © 2014 NTT DATA Mathematical Systems Inc.

分枝限定法（厳密解法）
実行不可能⇒最初からやりなおし解は出力されない:緩和解（最適解の種）:暫定解（制約を満たす最適解の候補）:制約を満たし得ない緩和解:最適解になり得ない緩和解
21
Copyright © 2014 NTT DATA Mathematical Systems Inc.

分枝限定法（厳密解法）に適した問題構造良さ• 制約と目的関数の区別が明確• 最適性の尺度が明確• 最適解の存在が論理的に絞り込める
Copyright © 2014 NTT DATA Mathematical Systems Inc.

22

スケジューリング作成コンペの結果
INRC2010(International Nurse Rostering Competition)（人数：10, 日数：28, シフト数：4～5, 計算時間：10秒）

分枝限定法ベース（人数：30～31, 日数：28, シフト数：5～6, 計算時間：10分）（人数：49～50, 日数：28, シフト数：6, 計算時間：10時間）

列生成法

WCSP
23
ほぼすべてヒューリスティック解法

23
Copyright © 2014 NTT DATA Mathematical Systems Inc.

実は「平準化」だった．．
現場担当者：「ＡさんとＢさんとも，シフトＸとシフトＹに関する適合度は同じですね」
数理：「はい」現場担当者：「ならばＡさんばかりシフトＸやっているのは修正してください」

数理：「．．．」「平準化」はかなり強い要請だが隠れていることが多い
24
Copyright © 2014 NTT DATA Mathematical Systems Inc.

「平準化」≒シフトの質
メタヒューリスティクスが教えてくれた小技• 誤り

平準化尺度：∑ 理想値-実績値jj∈人×差がつかない25
Copyright © 2014 NTT DATA Mathematical Systems Inc.

「平準化」≒シフトの質メタヒューリスティクスが教えてくれた小技•正解

typeII

尺度
typeI

実績値
理想値
26
Copyright © 2014 NTT DATA Mathematical Systems Inc.

「平準化」≒シフトの質
メタヒューリスティクスが教えてくれた小技• サンプル部署での確認

社員数 : 29人
シフト数 : 18勤務
泊まり勤務数合計 : 186
平準化なし

type I

type II

泊まり数上限９９８

泊まり数下限

３２

３

１．６

１．４５

１．２

泊まり数標準偏差27
Copyright © 2014 NTT DATA Mathematical Systems Inc.

プロジェクトマネジメントの話題
フィードバック可能な環境づくり• モデリング言語＋Ｅｘｃｅｌの利用– 手軽な定式変更・変化の直観的な把握• 開発プロセスの工夫
ウオーターフォール•実担当の方に評価してもらう現場の経験者>>システム担当

28
Copyright © 2014 NTT DATA Mathematical Systems Inc.

典型的な役割分担

現場担当者

NTTデータ
数理システム

眼前の業務標準化・給与システ
ムとの連携

現場担当者
眼前の業務効率化

システム担当

現場担当者
眼前の業務

経営者
Copyright © 2014 NTT DATA Mathematical Systems Inc.

29

システム担当⇔現場担当の距離感（１）

数理：「結果を見ていただきましたか」
システム担当：「はい．」
数理：「何か違和感でも」システム担当：「私，現場を知らないのでわかりませんが，明確な制約違反はないので大丈夫でしょう．あとで現場担当にメイルでもしておきます」
数理：「．．．」

30
Copyright © 2014 NTT DATA Mathematical Systems Inc.

システム担当⇔現場担当の距離感（２）

数理：「人同士の相性のデータ揃いましたか」
システム担当：「現場の人にExcelを渡しておいたのですが．．」数理：「何か問題でも？」システム担当：「こんなに入力が面倒なら要らないって．．」
数理：「．．．」
データ入力を少なく抑えることが実は肝要
31
Copyright © 2014 NTT DATA Mathematical Systems Inc.

じつは珍しいタイプのシステムなのかも．．

現場担当：「シフトに穴が空くんですが」
数理：「このシフトに誰も入れないことになってますよ」
現場担当：「え！可能性をすべて書かなくてはならないんですか？」
数理：「．．．」
実はシフト担当可能性マトリクスの記述
は（現場にとって）かなりの難物
Copyright © 2014 NTT DATA Mathematical Systems Inc.

32

ウオーターフォールはやめましょう！
STEP１
問題整理

STEP２
プロトタイピング

STEP３
検証

STEP４
システム化

ＳＴＥＰ１：問題整理

ＳＴＥＰ２：プロトタイピング

最も重要なところとも言えるが，事前に全てのルールを洗い出すのは困難．検証からフィードバックを繰り返し行うのが使えるシステムを作成するポイントとなる．

解けなければ意味がない．大規模問題の場合には変数の数を減らすことや，特別なスキームを用意する等の工夫もときには必要．

ＳＴＥＰ３：検証

ＳＴＥＰ４：システム化

手作業で現在作成している方や，作成された答えに基づき行動する担当者の意見をフィードバックすることが大切．必ずしもモデルの開発者とは限らない．

現在使用しているシステムや，Excel 等の GUIからコールする仕組みを作成する．NUOPT はexe や DLL の形にできるので，平行しての開発も可能．

33
Copyright © 2014 NTT DATA Mathematical Systems Inc.

（実録）ある看護現場の要望
Aさんが夜勤リーダーのときには，チーム１はC,D,Eのいずれか，チーム２はF,G,Hのいずれかが担当するようにしてください．ただ，CさんとFさんは移ってきたばかりで慣れてないので，夜勤をするとしたらKさんとペアになるようにしてください．日勤については特に制約はないのですが，１年目の人だけになるのはやめてほしいのです．
あと夜勤担当は前日も担当した人が申し送りのために一人は２日連続勤務にするようにしてください．８月は夏休みなので各人３日連続で休ませてあげて．．．

要望の網羅的実装≠顧客の満足34
Copyright © 2014 NTT DATA Mathematical Systems Inc.

「できない」に対する対処の意思疎通システム担当：「17日のシフトに空きができますね」
数理：「無理なんです」
システム担当：「ではバグ票起こしておきます．．」
数理：「いえ，そういう話じゃなくて．．」
現場担当：「ああ，なるほど，これはそもそも無理だね」

35
Copyright © 2014 NTT DATA Mathematical Systems Inc.

泥沼プロジェクト
わりとよくあるシステム作成側：「度重なる仕様変更，顧客の一貫しない態度，予想外に重たくなるシステム」
ユーザ側：「導入効果がわからない，使えない答えばかり出る，データ入力多すぎ，実行不可能って何さ？」

全力で避けましょう
36
Copyright © 2014 NTT DATA Mathematical Systems Inc.

スケジュールをなぜ人に頼ってしまうのか
数理計画があるのに• 熟練者には簡単には勝てない• 現場の実務者の協力が得にくい• 制約が多彩すぎる• 守備範囲の設定が意外と面倒（勤怠管理システムとの連携）（何でもできるわけではない）• 現場が消極的（データ入力が嫌）• 良さの定義がまちまち
37Copyright © 2014 NTT DATA Mathematical Systems Inc.

得られた効果•省力化•平等性•部分→全体スケジューリングの流れを促進
主な勝因：•緊密なフィードバック•プロジェクトの到達点の共有•高精度な需要予測
38
Copyright © 2014 NTT DATA Mathematical Systems Inc.

Open Question（ＩＩ）

スケジューリング自動計算の出口？
⇒そのまま運用⇒要員シミュレーションとして⇒試行錯誤のベース⇒単なる feasibility study「だまってすわればぴたりと当たる」「大幅なコスト削減」
39
Copyright © 2014 NTT DATA Mathematical Systems Inc.

将来の課題•一日の出面を新人のみとしないような配慮•担当者の「思い」を入力する余地•インタフェースの簡略化•とっつきの「難しさ」の改善

40
Copyright © 2014 NTT DATA Mathematical Systems Inc.

アルゴリズムの課題•結果の必然性や理由•重要な制約の峻別•重要な変数選択の峻別•より直観的なインタフェース–サーチエンジン型（キーワード入力，選択）–算盤型（振る，押さえる，動かす）

41
Copyright © 2014 NTT DATA Mathematical Systems Inc.

まとめ•解法選択–ヒューリスティクスの意義•問題の特色•プロジェクトマネジメントによる環境設定–ゴールの設定

42
Copyright © 2014 NTT DATA Mathematical Systems Inc.

本日はありがとうございました
多数の受託解析、システム構築事例がございます
お気軽にご相談ください

お問い合わせTEL : 03 - 3358 - 6681
FAX : 03 - 3358 – 1727
【URL】 http://www.msi.co.jp【E-mail】 sales@msi.co.jp
各種カスタマイズ・コンサルティングもお受けしております43
Copyright © 2014 NTT DATA Mathematical Systems Inc.