制約の書き方
業務システムで
望みの解を得るために
2016.Feb.10 菅原システムズ
導入効果
• 120人 3シフト 人手で作成に2週間を要していた勤
務表が、
• ➡ 一解の求解時間 90秒に！
• ➡ 制約違反件数(ハード制約違反） ０に！
• ➡ 多数の勤務データを作成（20年、240ヵ月）
• ➡ Pythonで統計解析、人的リソースの過大・過小
の評価が可能に
• ➡人的リソースの最適化システムとして活用
• ➡人的リソースの削減が可能に！
目次
１．背景知識
２．用語集
３．スケジューリングは制約の積み重ね
４．コンピュータにルールを入力する前に
５．アルゴリズムを指示する必要はありません
６．ハード制約
７．ソフト制約
８．GUI設定
９．制約化の考え方
１０．外部制約
１１．Pythonによる検証・ポスト処理
１２．PythonライブラリによるExcelの操作
１３．業務スケジューリングシステムまとめ
背景知識
スケジューリング問題は、規模が大きくなると解きにくくなります。
実績から
看護師：25人4シフト 40MB/4CPU
看護師：25人10シフト 150MB/4CPU
業務システム：120人４シフト 300MB/4CPU
内部の学習が進むにつれ、メモリ消費が増大します。
⇒メモリ消費が大規模問題に対するボトルネックになります。
制約の書き方も重要です！⇒ エキスパートにご相談ください！
参考Keywords: 充足可能性問題,拙特許5807978号 拙特許
5807980号 人口知能学会
途中の解って意味あるでしょうか？
• 解が完成しない状態で出して、後はギブアップしてしまうソフ
トウェアがあります。
• しかし、スケジューリング問題は縦と横が複雑に絡んでいて
局所部分での別解は殆どないことが普通です。
• ⇒結局、全体見直しを余儀なくされます。
部分的にブランクにて可能な別解個数を調べる
用語集
ソルバ
答えを出す脳、に相当するソフトウェア
解
制約を満たす答え
アルゴリズム
問題を解く解き方
GUI
画面
SAT
解があること
UNSAT
解がないこと
Python
軽量スクリプト言語、フリーの処理系です。
行
横方向の列
列
縦方向の列
充足
制約を満たすこと
エラー
失敗。誤差（目標値からのずれ、ペナルティ）
スケジューリングは制約の積み重ね
• スケジューリングは、制約という
積み木の積み重ねです。最後ま
で倒れずに積み重ねができたと
きだけ、解があります。
• 積み重ねは、AND を意味します。
• 制約という積み木をどんどん積
み上げて行くと、一つ一つの制約
は難しくなくても、すべての制約
を満たさないといけないので次第
に難しくなっていきます。
• 途中で崩れてしまう（矛盾がある
と）と、解がありません。
コンピュータにルールを入力する前に
• 明文化しましょう。
• 自分ではなく、他人に
理解してもらう文章にし
ましょう。
• コンピュータは、曖昧さ
が苦手です。
国語が大事
アルゴリズムを指示する必要はありません
• ルール（制約）を指示し
ます。
• ルールは、コンピュータ
が理解する画面上
（GUI)で設定します。
• 業務システム用途等で、
GUIで設定しきれないと
きは、外部制約（テキス
トファイル）で記述しま
す。
• 制約を入力としてソル
バは、解を出力します。
ハード制約
• 必ず満たすべき制約です。
• ハード制約を一つでも満たさないと解がありません。
• ハード制約のみの場合、いわば、１か０のデジタル
世界です。解があればよし、無ければ＊なにも出力
されません。
• 原因がリソース不足の場合は、どこかで妥協する必
要があります。⇒ソフト制約
＊原因解析機構はあります。
ソフト制約
• 必ず満たす必要はないけれど
も、できれば満たしたい制約
です。
• ハード制約は１か０だったのに
対して、ソフト制約は、アナロ
グ的です。
• 個別にみると1か０ですが、全
体として総数で見た場合に、
できるだけ理想に近づける機
構（最適化）が働きます。
• ソルバは、望ましくない勤務を
エラーとして各エラーを加算し
総和数を最小化します。
ソフト制約
• ７つのレベルが可能です
レベル７ （最強）
レベル６
レベル５
レベル４
レベル３
レベル２
レベル１ （最低 、リザーブ 通常使わない）
ソフト制約
• 通常意識する必要はあ
りませんが、内部的に
は更に、レベルが分か
れています
予定制約
行制約
列制約
外部制約
ソフト制約化パターン
• ルール "できれば～"、"
～を基準とする"は、ソフト
制約になります。
• 全ての組み合わせパターン
に展開します。
• 絶対嫌が×、仕方ないが△、
OKを○で評価します。
• ｘをハード制約、△をエラー
としてカウント（ソフト制約）
するようにすると、コン
ピュータに人間の価値観を
正確に教えることが出来ま
す。 （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設定-行制約
ブランクはハード制約
スタッフ集合指定
ソフト制約
ただし１はリザーブ
最大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-８で保存することを忘れずに。
外部制約言語インデックス
•
•
•
•
文法
デバッグの仕方
クラスの活用法
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 2024 ExpyDoc
