制約の書き方 業務システムで 望みの解を得るために 2016.Feb.10 菅原システムズ 導入効果 • 120人 3シフト 人手で作成に2週間を要していた勤 務表が、 • ➡ 一解の求解時間 90秒に! • ➡ 制約違反件数(ハード制約違反) 0に! • ➡ 多数の勤務データを作成(20年、240ヵ月) • ➡ Pythonで統計解析、人的リソースの過大・過小 の評価が可能に • ➡人的リソースの最適化システムとして活用 • ➡人的リソースの削減が可能に! 目次 1.背景知識 2.用語集 3.スケジューリングは制約の積み重ね 4.コンピュータにルールを入力する前に 5.アルゴリズムを指示する必要はありません 6.ハード制約 7.ソフト制約 8.GUI設定 9.制約化の考え方 10.外部制約 11.Pythonによる検証・ポスト処理 12.PythonライブラリによるExcelの操作 13.業務スケジューリングシステムまとめ 背景知識 スケジューリング問題は、規模が大きくなると解きにくくなります。 実績から 看護師:25人4シフト 40MB/4CPU 看護師:25人10シフト 150MB/4CPU 業務システム:120人4シフト 300MB/4CPU 内部の学習が進むにつれ、メモリ消費が増大します。 ⇒メモリ消費が大規模問題に対するボトルネックになります。 制約の書き方も重要です!⇒ エキスパートにご相談ください! 参考Keywords: 充足可能性問題,拙特許5807978号 拙特許 5807980号 人口知能学会 途中の解って意味あるでしょうか? • 解が完成しない状態で出して、後はギブアップしてしまうソフ トウェアがあります。 • しかし、スケジューリング問題は縦と横が複雑に絡んでいて 局所部分での別解は殆どないことが普通です。 • ⇒結局、全体見直しを余儀なくされます。 部分的にブランクにて可能な別解個数を調べる 用語集 ソルバ 答えを出す脳、に相当するソフトウェア 解 制約を満たす答え アルゴリズム 問題を解く解き方 GUI 画面 SAT 解があること UNSAT 解がないこと Python 軽量スクリプト言語、フリーの処理系です。 行 横方向の列 列 縦方向の列 充足 制約を満たすこと エラー 失敗。誤差(目標値からのずれ、ペナルティ) スケジューリングは制約の積み重ね • スケジューリングは、制約という 積み木の積み重ねです。最後ま で倒れずに積み重ねができたと きだけ、解があります。 • 積み重ねは、AND を意味します。 • 制約という積み木をどんどん積 み上げて行くと、一つ一つの制約 は難しくなくても、すべての制約 を満たさないといけないので次第 に難しくなっていきます。 • 途中で崩れてしまう(矛盾がある と)と、解がありません。 コンピュータにルールを入力する前に • 明文化しましょう。 • 自分ではなく、他人に 理解してもらう文章にし ましょう。 • コンピュータは、曖昧さ が苦手です。 国語が大事 アルゴリズムを指示する必要はありません • ルール(制約)を指示し ます。 • ルールは、コンピュータ が理解する画面上 (GUI)で設定します。 • 業務システム用途等で、 GUIで設定しきれないと きは、外部制約(テキス トファイル)で記述しま す。 • 制約を入力としてソル バは、解を出力します。 ハード制約 • 必ず満たすべき制約です。 • ハード制約を一つでも満たさないと解がありません。 • ハード制約のみの場合、いわば、1か0のデジタル 世界です。解があればよし、無ければ*なにも出力 されません。 • 原因がリソース不足の場合は、どこかで妥協する必 要があります。⇒ソフト制約 *原因解析機構はあります。 ソフト制約 • 必ず満たす必要はないけれど も、できれば満たしたい制約 です。 • ハード制約は1か0だったのに 対して、ソフト制約は、アナロ グ的です。 • 個別にみると1か0ですが、全 体として総数で見た場合に、 できるだけ理想に近づける機 構(最適化)が働きます。 • ソルバは、望ましくない勤務を エラーとして各エラーを加算し 総和数を最小化します。 ソフト制約 • 7つのレベルが可能です レベル7 (最強) レベル6 レベル5 レベル4 レベル3 レベル2 レベル1 (最低 、リザーブ 通常使わない) ソフト制約 • 通常意識する必要はあ りませんが、内部的に は更に、レベルが分か れています 予定制約 行制約 列制約 外部制約 ソフト制約化パターン • ルール "できれば~"、" ~を基準とする"は、ソフト 制約になります。 • 全ての組み合わせパターン に展開します。 • 絶対嫌が×、仕方ないが△、 OKを○で評価します。 • xをハード制約、△をエラー としてカウント(ソフト制約) するようにすると、コン ピュータに人間の価値観を 正確に教えることが出来ま す。 (OKは教えなくてよ い) ○ A B C A B A A B C × B B A C × A C △ B C △ B B × C C × ○ ソフト制約要因調査 • 各ソフト制約は適用チェックボックスで適用すること ができます。 チェックした制約だけ適用される Fine Tuning • 下位のエラーが(想定より)多すぎる場合 • ⇒上位でのエラー数を寛容にしてその余力で、下位エラー数を 少なくする戦略が有効 何を優先するということは、何かを切り捨てること • ハード制約だけで済めば理想ですが、物事は例外 がつきものであり、特にリソースの限界に近いシス テムでは、ソフト制約は必須です。 • 優先度の高い制約は優先的に確保されますが、反 対に低い制約は、満足行かない結果になるかもし れません。 • 何を優先するということは、何かを切り捨てることで す。高速求解により、この辺のトレードオフを複数パ ターン試してみることをお勧めします。 • 最も望みの結果に近い、優先レベル設定、エラー数 設定、求解時間をユーザ様自身で発見してください。 GUI設定-行制約と列制約 スタッフ毎の制約:行制約 Day毎制約:列制約 GUI設定-行制約 ブランクはハード制約 スタッフ集合指定 ソフト制約 ただし1はリザーブ 最大4個まで可。5は禁止 GUI設定-列制約 スタッフ集合指定 Day集合指定 1以上1以下=>Onlyone GUI設定-スタッフ毎の設定 • 各スタッ フ毎の 属性を 設定 • 月々の 変更は この ページ で吸収 すること が望ま しい 制約化の考え方 • 恒久的な仕様 ⇒制約化 • スタッフの諸事情 ⇒他の 人も共通に使えるならス タッフプロパティで吸収する ように制約化 • 予定入力も各スタッフ各日 毎にソフト制約(1-7)に出来 ます その個人だけ・その月だけ • ⇒制約化するよりも予定入力で入れてしまった方が速い。何が何で も制約化,という考えに囚われない。制約化を考える時間の方が長いと本末転倒。 解を入力に戻す • 解を全部入力に戻して、マニュアルで気に入らない箇所を修 正していくこともできます。(制約化もご検討ください。) 解画面 予定入力編集画面 戻した解をブランクにして再編集/再求解も可能 GUIと外部制約の役割分担 • • • • • • • • スケジュール開始日、スケジュール終了日 シフト定義 予定入力 Day集合定義 シフト集合定義 スタッフ集合定義 行制約 各スタッフ毎の勤務パターン 列制約 各日毎の勤務制約 • 上記で記述不能な箇所がある場合のみ、外部制約で記述し ます。(複雑なルールを持つ業務システムの場合であり、通 常は必要ありません。) 外部制約 • テキストファイルで記述 します。 • ソルバは、GUIと外部制 約を入力として解と Pythonソースを出力し ます。 • このPythonソースを利 用してExcelを操作する ことも容易です。 外部制約の例 • //数独列制約 GUIで定義したものがそのまま使えます • for (day in 全日){ • for (シフト in 全シフト){ • vector V; • 日本語変数名 for (人 in 全スタッフ){ • V.push_back(X[人][day][シフト]); • } • $Onlyone(V); ベクタVに後ろから入れます • } • } 制約関数 外部制約の例 続き • //数独行制約 • for (人 in 全スタッフ){ • for (シフト in 全シフト){ • vector V; • for (day in 全日){ • V.push_back(X[人][day][シフト]); • } • $Onlyone(V); • } • } 外部制約の例 続き • • • • • • • • • • • • • • //ブロック制約 for (人 in スタッフブロックトップ){ for (シフト in 全シフト){ for (day in ブロックトップ日集合){ vector V; for (i=0 to 2){ for (j=0 to 2){ V.push_back(X[人+i][day+j][シフト ]); } } $Onlyone(V); } } 僅か34行で数独記述完了!後は、求解ボタンを押すだけ } 外部制約のポイント • GUIで定義した集合定義を利用 • for/if文 で制約目的の対象群を絞り込みvectorに 集めます。 • 集めたvectorを制約関数で制約します。 • UTF-8で保存することを忘れずに。 外部制約言語インデックス • • • • 文法 デバッグの仕方 クラスの活用法 vector活用法 • 制約関数まとめ • できれば避けたい記述 • 「AならばB」はどう記 述? • 制約の検証 $And動作説明 $And動作説明 続き $Or動作説明 $Or動作説明続き $SeqLEの説明 $SeqErrorの説明 $SeqExprの説明 $EnableGateの説明 Pythonによる検証・ポスト処理 • 解が出たとしても目視でチェックするのは辛いし漏 れの心配もあります。 • そこで、有効な手段はPythonによる検証です。 • スケジュールナースが吐いたPythonソースをイン ポートしてスクリプトを書くと簡単に短い行数で検証 を書けます。 $ python3 Ana3交代X2.py 2 ... 3 Pass. 4 Pass. 5 週連続休日夜勤不可 6 週連続休日夜勤不可 をチェック中です。 をチェック終了しました。 PythonライブラリによるExcelの操作 • スケジュールナースが 吐くPythonソースを利 用してExcel操作が可 能です。 ・Exceベースでも検証や 集計が楽です。 最終検証 • 開発した制約プロジェクトファイルが最終的に問題 ないということを検証するにはどうしたらよいでしょう か? • 前月からの流れがあるので厳しい月の単月だけ検 証すればよいといものではありません。 • 今月から20年後の2036年まで、シフト勤務表を自動 で作成する機能もあります。(20*12=240勤務表、オ プション) • 多数のデータが揃うと、統計解析が可能になります。 • リソースの最適化、最適化によって負荷の公平化の みならず、人的リソースの削減も可能になります。 業務スケジューリングシステムのまとめ • 複雑なルールを有するシステムでは、外部制約は不可欠で す。 • 一方、予定入力や、結果確認には、GUIが便利です。 • ハード・ソフト制約で、最適化を図りつつ、個々のスタッフの 事情にも配慮したPython検証付き、GUI+言語による最適化 システムを紹介しました。 • 今までのノウハウは無駄になりません。何が重要で何を取捨 選択するべきかを知っているのはコンピュータではなくそれ を指示する人間だからです。今までのノウハウを生かしつつ、 道具を使えるところは使って業務の改善に生かして頂けれ ば幸いです。 • ご清聴ありがとうございました。
© Copyright 2025 ExpyDoc