スケジューリングソルバScNurse 高速求解エンジンとしての利用法 2016.May.15 菅原システムズ.

Presentation on theme: "スケジューリングソルバScNurse 高速求解エンジンとしての利用法 2016.May.15 菅原システムズ."— Presentation transcript:

1 スケジューリングソルバScNurse 高速求解エンジンとしての利用法 2016.May.15 菅原システムズ

2 アプリから求解のための必要な情報を入力として受け取り解を出力します。
ScNurse（エスシーナース）とは？ スケジューリング専用の高速ソルバです。 アプリから求解のための必要な情報を入力として受け取り解を出力します。 貴アプリ ScNurse （スケジューリングソルバ） 入力 出力(解）

3 用語集 ソルバ 答えを出す脳、に相当するソフトウェア 制約 勤務のルール 解 制約を満たす答え ハード制約 必ず満たさないといけない制約。
ソフト制約 出来れば満たしたい制約 オプティマイズ 最適化。エラーの数を1個づつ減らして最小化すること。 リソース 人的資源。使用例）リソースがない➡人がいない 行 横方向の列 列 縦方向の列 充足 制約を満たすこと エラー 失敗。誤差（目標値からのずれ、ペナルティ） ボトルネック その制約を満たすことが難しいために解がない状態 トレードオフ 何かを達成するために別の何かを犠牲にしなければならない関係のこと。

4 用語集２ ハードエラー 解が存在しないこと（ソルバが矛盾を認識したときに出すエラー） solution1

5 ScNurseの特徴 関連特許 ScNurseは、下記取得済み特許に基づいて実装されています。 特許5807978号 特許5807980号
特許 号　 特許 号 高速求解 実務問題に強い。複雑なシフトほど高速性能を発揮します。物理CPU数に対して有効に作用します。200人または365日といった大規模用にもカスタマイズ対応が可能です。 複数の解提示 別解数をパラメータとして指定可能です UNSAT提示 解が存在しないことの証明が可能な場合、即座に報告しユーザを無駄に待たせません。 複数のアプリインターフェース 現状、次の3種をサポートしています。 １）Windows実装　ファイル渡しインターフェース( Windows7Desktop/Windows10 UWP　32Bit/64Bit) ２）Linux実装　TCP/IP　サーバインタフェース(64Bit) ３）Linux実装　WebSocket　サーバインタフェース(64Bit)

6 ScNurseの特徴続き 柔軟なソフト制約 優先度設定（Default 7レベル)が可能です。 最小予定変更の提示
制約を満足する最小の予定変更の提示が可能です。 厳密解・近似解 規模や問題の複雑度によりますが、Default動作モードは、厳密解出力になります。時間タイムアウトの場合は、近似解による出力になります。 エラーの原因表示 エラー原因要因を列挙できます。 言語処理による制約記述 言語処理により、複雑で大規模な記述も少ない行数で記述することも可能です。 検証コード出力 Windowsファイル渡しインターフェースの場合は、Pythonによる検証コードを出力出来ます。

7 スケジューリングに関し他のソルバとの比較
ScNurse MIPソルバ メタヒューリスティクス 高速求解 専用ソルバ。論理的な関係に対して学習が働くので複雑な論理関係になるほど、他のソルバより有利に働く 汎用ソルバ シフト数が多いと遅くなる、もしくは求解困難になる事例が見られる。 ソフト制約規模が大きいとき有利 論理関係の学習機構の実装が難しい。 極めて大規模の場合有利 価格 安価 寡占化により高価 多様 複数の解提示 ◎ △ UNSAT提示 × 最小予定変更 厳密解・近似解 ｘ エラーの原因表示

8 UNSAT証明 数独解が2つないことを証明します。 １解しかありません。 解２がありません。
解がないことが分からないと、いつまでも探し続けるしかありません。厳密解を出せないソルバ、例えばメタヒューリスティクスによる方法では、基本的に解がないことが分かりません。 ユーザに「もう解はありません。」とは言うことはできません。 １解しかありません。 解２がありません。

9 自明なエラーは即検出原因指摘が出来る これも厳密解を出せないソルバでは難しいと思われます。ScNurseでは、単純な論理矛盾は、コンパイル時に検出でき、即原因指摘が可能です。

10 複数解（別解）を出せます 解の個数を１０に指定した場合 １解しかありません。 解２がありません。

11 予定変更の最小解も出せます これ以上良い解がない証明ができた➡最小解を発見した。

12 予定変更の別解も出せます 予定変更位置の別解も求められます

13 Windows7 インタフェース 求解条件・制約 貴アプリ ScNurse 求解中止 求解状況報告 解
デスクトップアプリを想定したインターフェースです。 貴アプリは、求解条件・制約をファイルに書き込みます。 ScNurseを子プロセスとして起動します。 ScNurseは、ファイルを構文解析し求解します。 貴アプリは、求解途中で求解中止にしたいときは、パイプでMsgを送ります。 ScNurseは、求解状況をWindowsMsgで逐次報告します。 解が出来たらファイルに書き込みScNurseは終了します。 貴アプリ 求解条件・制約 ScNurse ファイル 求解中止 求解状況報告 解 ファイル

14 Windows10 UWP インタフェース 求解条件・制約 貴アプリ (XAML/C#/ ScNurse javascript) 求解中止
デスクトップアプリを想定したインターフェースです。 貴アプリは、求解条件・制約をファイルに書き込みます。 ScNurseをLaunchUriAsync（ファイル指定付き）で起動します。 ScNurseは、ファイルを構文解析し求解します。 貴アプリは、求解途中で求解中止にしたいときは、AppServiceConnectionをCloseします。 ScNurseは、求解状況をAppServiceConnectionで逐次報告します。 解が出来たらファイルに書き込みScNurseは終了します。 貴アプリ (XAML/C#/ javascript) 求解条件・制約 ScNurse ファイル 求解中止 求解状況報告 解 ファイル

15 TCP/IP インタフェース（Linuxサーバ）
フォーマットは前ページWindowsと同じです。 ScNurseは、送られたてきた入力情報を構文解析し求解します。 貴アプリは、求解途中で求解中止にしたいときは、TCP/IPプロトコルでMsgを送ります。 ScNurseは、求解状況をTCP/IPプロトコルで逐次報告します。 解が出来たらTCP/IPプロトコルで送ります。 貴アプリ 求解条件・制約 ScNurse Linuxサーバ TCP/IP TCP/IP求解中止 求解状況報告TCP/IP 解 TCP/IP

16 WebSocket インタフェース（Linuxサーバ）
Javascriptを想定したインターフェースです。 貴アプリは、求解条件・制約をJSONフォーマットにし、WebSocketプロトコルで送ります ScNurseは、送られたてきた入力情報を構文解析し求解します。 貴アプリは、求解途中で求解中止にしたいときは、WebSocketプロトコルでMsgを送ります。 ScNurseは、求解状況をWebSocketプロトコルで逐次報告します。 解が出来たらJSONフォーマットにしWebSocketプロトコルで送ります。 貴アプリ 求解条件・制約 ScNurse Linuxサーバ WebSocket WebSocket求解中止 求解状況報告WebSocket 解 WebSocket

17 インタフェースフォーマット概要 ソルバへの入力フォーマットは、求解条件と制約式から成ります。 名称 内容 求解条件
行数(人数）、列数(日数）の指定 シフトの種類の指定、求解数、タイムアウト値の指定 制約式 制約の本体部

18 求解条件 求解条件 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;//ソフトタイムアウト秒 …

19 制約式（例） 制約式は、コメントと制約関数から成ります。コメントは、エラー時の表示に使用します。 コメント（オプション）
//予定入力 ６ 菅原 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]); … 人、日、シフトの3次元で指定します。 制約関数。$Inv(),$And(),$Or()等、10種類位あります。

20 ライセンスの種類 名称 提供物 価格 備考 Unlimited
全ソースコード（Windows/LinuxServer/スケジュールナース、匠シフタ　：C++,C#,Javascript） 2000万円 分割払可。特許ライセンス費込。使用数量に関係なく自由に使うことが出来ますが、独占使用権ではありません。 技術指導・サポート 120万円 1年間のみ WindowsDesktop バイナリコード インタフェースSpec. 5万円Start １Windows組み込みあたり　 ミニマムロイヤリティ LinuxServer＊ インタフェースSpec＊＊. T.B.D. 1サーバあたり 240万円 ＊デモURLは　携帯ブラウザで 36x36数独を携帯ブラウザで数秒で解くことができます。 ＊＊制約ファイル仕様書に関しては、サポートまで依頼してください。

21 高速求解で広がる世界 高速求解＋クラウド・VPS使用で素早く、安価にスケジューリングサーバ構築が可能 技術指導によりノウハウを提供します。
ご清聴ありがとうございました