スケジューリングソルバScNurse

スケジューリングソルバ
ScNurse
高速求解エンジンとしての利用法
2016.May.15 菅原システムズ
ScNurse（エスシーナース）とは？
• スケジューリング専用の高速ソルバです。
• アプリから求解のための必要な情報を入力として受
け取り解を出力します。
入力
貴アプリ
出力(解）
ScNurse
（スケジュー
リングソル
バ）
用語集
ソルバ
答えを出す脳、に相当するソフトウェア
制約
勤務のルール
解
制約を満たす答え
ハード制約
必ず満たさないといけない制約。
ソフト制約
出来れば満たしたい制約
オプティマイズ
最適化。エラーの数を1個づつ減らして最小化すること。
リソース
人的資源。使用例）リソースがない➡人がいない
行
横方向の列
列
縦方向の列
充足
制約を満たすこと
エラー
失敗。誤差（目標値からのずれ、ペナルティ）
ボトルネック
その制約を満たすことが難しいために解がない状態
トレードオフ
何かを達成するために別の何かを犠牲にしなければならない
関係のこと。
用語集２
ハードエラー
解が存在しないこと（ソルバが矛盾を認識したときに出すエ
ラー）
solution1
1番目の答え、solution2は、2番目の答え
ScNurseの特徴
関連特許
ScNurseは、下記取得済み特許に基づいて実装されています。
特許5807978号
特許5807980号
高速求解
実務問題に強い。複雑なシフトほど高速性能を発揮します。物理
CPU数に対して有効に作用します。200人または365日といった大
規模用にもカスタマイズ対応が可能です。
複数の解提示
別解数をパラメータとして指定可能です
UNSAT提示
解が存在しないことの証明が可能な場合、即座に報告しユーザ
を無駄に待たせません。
現状、次の3種をサポートしています。
１）Windows実装ファイル渡しインターフェース(
複数のアプリイン
Windows7Desktop/Windows10 UWP 32Bit/64Bit)
ターフェース
２）Linux実装 TCP/IP サーバインタフェース(64Bit)
３）Linux実装 WebSocket サーバインタフェース(64Bit)
ScNurseの特徴続き
柔軟なソフト制約
優先度設定（Default 7レベル)が可能です。
最小予定変更の提示
制約を満足する最小の予定変更の提示が可能です。
厳密解・近似解
規模や問題の複雑度によりますが、Default動作モード
は、厳密解出力になります。時間タイムアウトの場合は、
近似解による出力になります。
エラーの原因表示
エラー原因要因を列挙できます。
言語処理による制約記述
言語処理により、複雑で大規模な記述も少ない行数で
記述することも可能です。
検証コード出力
Windowsファイル渡しインターフェースの場合は、Python
による検証コードを出力出来ます。
スケジューリングに関し他のソルバとの比較
ScNurse
メタヒューリスティクス
MIPソルバ
汎用ソルバ
高速求解
価格
専用ソルバ。論理的な関係に
対して学習が働くので複雑な
論理関係になるほど、他のソ
ルバより有利に働く
シフト数が多いと遅くなる、論理関係の学習機構の
実装が難しい。
もしくは求解困難になる
事例が見られる。
極めて大規模の場合有
ソフト制約規模が大きい利
とき有利
安価
寡占化により高価
多様
複数の解提示
◎
△
△
UNSAT提示
◎
◎
×
最小予定変更
◎
△
△
厳密解・近似解
◎
◎
ｘ
◎
×
×
エラーの原因表示
UNSAT証明
数独解が2つないことを証明します。
解がないことが分からないと、
いつまでも探し続けるしかあり
ません。厳密解を出せないソル
バ、例えばメタヒューリスティ
クスによる方法では、基本的に
解がないことが分かりません。
ユーザに「もう解はありませ
ん。」とは言うことはできませ
ん。
１解しかありません。
解２があり
ません。
自明なエラーは即検出原因指摘が出来る
これも厳密解を出せないソルバでは難しいと思われます。
ScNurseでは、単純な論理矛盾は、コンパイル時に検出
でき、即原因指摘が可能です。
複数解（別解）を出せます
解の個数を１０に指定した
場合
１解しかありません。
解２があり
ません。
予定変更の最小解も出せます
これ以上良い解がない証明ができた
➡最小解を発見した。
予定変更の別解も出せます
予定変更位置の別解も求められ
ます
Windows7 インタフェース
デスクトップアプリを想定したインターフェースです。
貴アプリは、求解条件・制約をファイルに書き込みます。
ScNurseを子プロセスとして起動します。
ScNurseは、ファイルを構文解析し求解します。
貴アプリは、求解途中で求解中止にしたいときは、パイプでMsgを送ります。
ScNurseは、求解状況をWindowsMsgで逐次報告します。
解が出来たらファイルに書き込みScNurseは終了します。
ファイル
求解条件・制約
求解中止
貴アプリ
求解状況報告
解
ファイル
ScNurse
Windows10 UWP インタフェース
デスクトップアプリを想定したインターフェースです。
貴アプリは、求解条件・制約をファイルに書き込みます。
ScNurseをLaunchUriAsync（ファイル指定付き）で起動します。
ScNurseは、ファイルを構文解析し求解します。
貴アプリは、求解途中で求解中止にしたいときは、AppServiceConnectionをCloseします。
ScNurseは、求解状況をAppServiceConnectionで逐次報告します。
解が出来たらファイルに書き込みScNurseは終了します。
ファイル
求解条件・制約
求解中止
貴アプリ
(XAML/C#/
javascript)
求解状況報告
解
ファイル
ScNurse
TCP/IP インタフェース（Linuxサーバ）
貴アプリは、求解条件・制約をTCP/IPプロトコルで送ります。
フォーマットは前ページWindowsと同じです。
ScNurseは、送られたてきた入力情報を構文解析し求解します。
貴アプリは、求解途中で求解中止にしたいときは、TCP/IPプロトコルでMsgを送ります。
ScNurseは、求解状況をTCP/IPプロトコルで逐次報告します。
解が出来たらTCP/IPプロトコルで送ります。
TCP/IP
求解条件・制約
TCP/IP求解中止
貴アプリ
求解状況報告TCP/IP
解
TCP/IP
ScNurse
Linuxサーバ
WebSocket インタフェース（Linuxサーバ）
Javascriptを想定したインターフェースです。
貴アプリは、求解条件・制約をJSONフォーマットにし、WebSocketプロトコルで送ります
ScNurseは、送られたてきた入力情報を構文解析し求解します。
貴アプリは、求解途中で求解中止にしたいときは、WebSocketプロトコルでMsgを送ります。
ScNurseは、求解状況をWebSocketプロトコルで逐次報告します。
解が出来たらJSONフォーマットにしWebSocketプロトコルで送ります。
WebSocket
求解条件・制約
WebSocket求解中止
貴アプリ
求解状況報告WebSocket
解
WebSocket
ScNurse
Linuxサーバ
インタフェースフォーマット概要
ソルバへの入力フォーマットは、求解条件と制約式から成ります。
名称
内容
求解条件
行数(人数）、列数(日数）の指定
シフトの種類の指定、求解数、タイムアウト
値の指定
制約式
制約の本体部
求解条件
求解条件
persons=9;//行数
Days=9;//列数
{ _A,_B,_C,_D,_E,_F,_G,_H,_I};//シフトの種類
parameter int NofCpus=8;//使用CPU数
parameter int N_of_solutions=2;//解数
parameter int not_repeat_planned_errors=0;
parameter int HardTimeout=120;//タイムアウト秒
parameter int ErrorAnalysis=0;//エラー解析
parameter int SoftTimeout=26;//ソフトタイムアウト秒
…
制約式（例）
制約式は、コメントと制約関数から成ります。コメントは、エラー時の表示
に使用します。
コメント（オプション）
//予定入力６菅原 2014年5月2日
$DayEntry(1,X[0][1][_F],X[0][1][_A],X[0][1][_B],X[0][1][_C],X[0][1][_D],X[0][1][_
E],X[0][1][_G],X[0][1][_H],X[0][1][_I]);
//予定入力１菅原 2014年5月3日
$DayEntry(1,X[0][2][_A],X[0][2][_B],X[0][2][_C],X[0][2][_D],X[0][2][_E],X[0][2][_
F],X[0][2][_G],X[0][2][_H],X[0][2][_I]);
…
制約関数。
$Inv(),$And(),$
Or()等、10種類
位あります。
人、日、シフトの
3次元で指定しま
す。
ライセンスの種類
名称
Unlimited
WindowsD
esktop
提供物
価格
備考
全ソースコード
（Windows/LinuxServer/ス 2000万円
ケジュールナース、匠シ
フタ：C++,C#,Javascript）
分割払可。特許ライセ
ンス費込。使用数量に
関係なく自由に使うこ
とが出来ますが、独占
使用権ではありません。
技術指導・サポート
120万円
1年間のみ
バイナリコード
インタフェースSpec.
5万円Start
１Windows組み込みあ
たり
120万円
ミニマムロイヤリティ
T.B.D.
1サーバあたり
240万円
ミニマムロイヤリティ
LinuxServer バイナリコード
＊
インタフェースSpec＊＊.
＊デモURLは携帯ブラウザでhttp://www.nurse-scheduling-software.com/W/piyo04142016.php
36x36数独を携帯ブラウザで数秒で解くことができます。
＊＊制約ファイル仕様書に関しては、サポートまで依頼してください。
高速求解で広がる世界
• 高速求解＋クラウド・VPS
使用で素早く、安価にスケ
ジューリングサーバ構築が
可能
• 技術指導によりノウハウを
提供します。
ご清聴ありがとうございました

Download Report